1、數(shù)據(jù)結(jié)構(gòu)試卷第1套三、單項選擇題：(每小題1分，共5分)1 .對于只在表的首、尾進(jìn)行插入操作的線性表，宜采用的存儲結(jié)構(gòu)為：A)順序表B)用頭指針表示的單循環(huán)鏈表C)用尾指針表示的單循環(huán)鏈表D)單鏈表2.假設(shè)以第一個元素為分界元素，對字符序列(Q, H, C, Y, P, A, M, S, R, D, F, X)進(jìn)行快 速排序，則第一次劃分的結(jié)果是：A) (A, C, D, F, H, M, P, Q, R, S, X, Y) B) (A, F, H, C, D, P, M, Q, R, S, Y, X) C) (F, H, C, D, P, A, M, Q, R, S, Y, X) D) (P

2、, A, M, F, H, C, D, Q, S, Y, R, X) 3.下面是三個關(guān)于有向圖運算的敘述：(1)求有向圖結(jié)點的拓?fù)湫蛄校浣Y(jié)果必定是唯一的(2)求兩個指向結(jié)點間的最短路徑，其結(jié)果必定是唯一的(3)求AOE網(wǎng)的關(guān)鍵路 徑，其結(jié)果必定是唯一的其中哪個(些)是正確的？A)只有(1) B) (1)和(2) C)都正確 D)都不正確4.若進(jìn) 棧序列為a, b, c,則通過入出棧操作可能得到的a, b, c的不同排列個數(shù)為：A) 4B) 5C) 6D) 7 5.以下關(guān)于廣義表的敘述中，正確的是：A)廣義表是由。個或多個單元素或子表構(gòu)成的有限序列B)廣義表至少有一個元素 是子表0廣義表不能遞

3、歸定義D)廣義表不能為空表四、填空題：(每小題2分，共20分)1. 一棵含有101個結(jié)點的完全二叉樹存儲在數(shù)組AL. 101中，對lWkWlOl,若 Ak是非葉結(jié)點，則k的最小值是：，k的最大值是：o 2.設(shè)s=' YOU ARE JUDGING IT RIGHT OR WRONG, ,順序執(zhí)行下列操作：SubString (subl, s, 1, 8) ; SubString (sub2, s, 20, 5) ; StrCat (subl, sub2);則最后 subl的值為：o3 .若一個算法中的語句頻度之和為T(n) = 3720n+4nlogn,則算法的時間復(fù)雜度為 o (a)

4、, b), c) ,(d)4 .廣義表(由，9,。)，1)的表頭是，表尾是o5.已知有向圖的鄰接矩陣，要計算i號結(jié)點的入度，計算方法是：將 累加。6 .要在一個單鏈表中p所指結(jié)點之后插入一個子鏈表，子鏈表第一個結(jié)點的地址為s, 子鏈表最后一個結(jié)點的地址為t,則應(yīng)執(zhí)行操作： 和O7 .用帶頭結(jié)點的循環(huán)鏈表表示的隊列，若只設(shè)尾指針rear,則隊空的條件 是。8 .已知二維數(shù)組A10 20采用行序為主方式存儲，每個元素占2個存儲單元，并且 A00的存儲地址是1024,則A618的地址是9.在表示二叉樹的二義鏈表中，共有個空鏈域。10. n個頂點的連通無向圖至少有條邊，至多有條邊。五、構(gòu)造題：(每小題

5、6分，共30分)1 .已知二義樹的中序序列為DBGEAFC,后序序列為DGEBFCA,給出對應(yīng)的二叉樹。2 .已知一個圖的頂點為A、B、C、D,其鄰接矩陣的上三角元素全為0 (包括主對角 線元素)，其他元素均為1。請畫出該圖，并給出其鄰接表。3 .給定權(quán)值8, 12, 4, 5, 26, 16. 9,構(gòu)造一棵帶權(quán)路徑長度最短的二叉樹，并 計算其帶權(quán)路徑長度。4 .圖2表示一個地區(qū)的通訊網(wǎng)，邊表示城市間的通訊線路，邊上的權(quán)值表示架設(shè)線 路花費的代價，請找出能連通每個城市、口總代價最省的n-l條線路。圖25.對關(guān)鍵字序列(72, 87, 61, 23, 94, 16,05, 58)進(jìn)行堆排序，使之

6、按關(guān)鍵字遞減次序排列。請寫出排序過程中得到的初始堆 和一趟排序后的序列狀態(tài)。三、單項選擇題：(每小題1分，共5分)2.在長度為n的順序表的第i ( 1W i Wn+1 )個位置上插入一個元素，元素的移動 次數(shù)為：A) n-i+1B) n-iC) iD) i-l 3.下面關(guān)于圖的存儲的敘述中正確的是A)鄰接矩陣占用的存儲空間只與圖中結(jié)點個數(shù)有關(guān)，而與邊數(shù)無關(guān)；B.用鄰接表 法存儲圖，占用的存儲空間大小與圖中邊數(shù)和結(jié)點個數(shù)都有關(guān)C)鄰接表占用的存儲空間 只與圖中結(jié)點個數(shù)有關(guān)，而與邊數(shù)無關(guān)：D)鄰接表占用的存儲空間只號圖中邊數(shù)有關(guān)，而與結(jié)點個數(shù)無關(guān)。4.在待排序記 錄已基本有序的前提下，下述排序方法

7、中效率最高的是：A)直接插入排序B)簡單選擇排序C)快速排序D)歸并排序四、填空題:(每小題2分，共20分)1 .向一個有n個元素的有序表中插入一個新元素并保持原來順序不變，平均要移動 n/2個元素。2 .設(shè)廣義表L=(),(),則head(L)是 ；tail(L)是 ：L的長度是 ：深度是_head(L) = () tail(L) = (0)L的長度為2L的深度為2數(shù)據(jù)結(jié)構(gòu)試卷A參考答案與評分標(biāo)準(zhǔn)(2001級)一、簡答題：(每小題3分， 共15分)1.前驅(qū)與后繼之間通常為一對多或多對多的關(guān)系。2.順序表優(yōu)點：隨機查找，存 儲密度大順序表缺點：插入、刪除不便，靜態(tài)分配，表長固定單鏈表優(yōu)點：插入

8、、刪除方便, 動態(tài)分配，表長靈活單鏈表缺點：查找不便，存儲密度小3.關(guān)鍵字相同的兩個記錄，排序前后其先后順序不變。4. typedef struct node ElemType data; struct node * next; *LinkStack;5.當(dāng)二又排序樹接近平衡二叉樹或完全二叉樹時查找性能較好，當(dāng)二義排序樹為單 邊單枝二又樹時查找性能最差。三、單項選擇題：(每小題1分，共5分)1. C) 2. C) 3. D) 4. B) 5. A)四、填空題：(每小題2分，共20分)1.12. ' YOU ARE RIGHT*5. i列元素>next=rear3. O(nlogn

9、)4.(a),b),c) >(d)6. t->next=p->next » p->next=s 7. rear-13009.n+110. n-1五、構(gòu)造題：(每小題6分，共30分)1.3.或:WPL=8 X 3+4 X 4+5 X4+16X 2+9 X3+12X 3+26 X 2=207注:哈夫曼樹的左右子樹可以互換。4.解1：解 2：注:邊上的權(quán)值可以省略。5.初始堆：05, 23, 16, 58, 94, 72, 61, 87一趟排序后的序列狀態(tài)：87, 23, 16, 58, 94, 72, 61, 05篩成堆后為：16, 23, 61, 58, 94,

10、 72, 87, 05注:如果采用大根堆，應(yīng)適當(dāng)減分。六、算法設(shè)計題：(共25分)1.15分void min(LinkList L) if (L->next=NULL) return; q=L; r=L->next; m=r->data; while (l >next!=NULL) if(r->next->datar->next->data; q=r; r=r->next; p=q->next; if(m%2=l) q">next=p->next; free(p); 2.10 分void layer(CSTree root) InitQueue(&Q); EnterQueue(&