浙江大學寧波理工學院200_8_–200_9_學年_一_學期
《資料結構（乙）》課程期末考試試卷（b）答案
開課分院： 資訊分院 ，考試形式：閉卷
考試日期：__ 2008 ___年__12__月__28__日，考試所需時間： 120 分鐘
考生姓名學號考生所在分院： 專業班級
一、單項選擇題（本大題共10小題，每小題2分，共20分）
( b )（1）下列排序方法中，哪一種方法的比較次數與紀錄的初始排列狀態無關？
a．直接插入排序 b．直接選擇排序 c. 快速排序 d.起泡排序
( a )（2）已知迴圈佇列的儲存空間為陣列data[18]，且當前佇列的頭指標和尾指標的值分別為7和2，則該佇列的當前長度為？
a．13 b．5c．9 d．18
( c )（3）在單鏈表中，已知指標p所指結點不是尾結點，若在*p之後插入結點*s，則應執行下列哪乙個操作？
a．s-> next = p； p-> next = s； b．s-> next = p-> next；p = s；
c．s-> next = p-> next；p-> next = s； d．p-> next = s； s-> next = p；
( d )（4）一組記錄的關鍵碼為（46，79，56，38，40，84），則利用快速排序的方法，以第乙個記錄為基準得到的一次劃分結果為？
a. 38，40，46，56，79，84 b. 40，38，46，79，56，84
c. 40，38，46，84，56，79 d. 40，38，46，56，79，84
( b )（5） 任何一棵二叉樹的葉子結點在前序、中序和後序遍歷序列中的相對次序？
a.發生改變 b.不發生改變 c.不能確定 d.以上都不對
( c )（6）一棵含18個結點的二叉樹的高度至少為
a. 3b. 4c. 5 d. 6
( b )（7）在用於表示無權有向圖的相鄰矩陣中，對第j列的非0元素個數進行累加，可得到第j個頂點的？
a．出度 b．入度 c．權值 d．連線邊個數
( c )（8）若進棧序列為1，2，3，4，下面哪乙個序列不可能是這個棧的輸出序列？
a. 1，3，2，4 b. 2，3，4，1 c. 4，3，1，2 d. 3，4，2，1
( a )（9）按照二叉樹的定義，具有3個結點的不同形狀的二叉樹有幾種？
a. 5 b. 4 c. 3 d. 6
( d )（10）對乙個滿二叉樹，m個樹葉，n個結點，深度為h，則?
a. n=h+m b. h+m=2n c. m=h-1 d. n=2h-1
二、填空題（本大題共10小空，每小空2分，共20分）
1. 在雙鏈表中，每個結點有兩個指標域，乙個指向前驅結點，另乙個指向後繼結點。
2. 佇列是線性結構，只能在隊尾插入元素和隊首刪除元素。
3. 某二叉樹的前序遍歷為abdgcefh，中序遍歷為dgbaechf，則後序遍歷的為gdbehfca。
4. 一棵二叉樹的第i（i≥1）層最多有2i-1個結點。
5. 在單鏈表中，指標p指向元素為x的結點，實現「刪除x的後繼」的語句是p->next=p->next->next。
6. 一棵二叉樹中雙分支結點數為15，單分支結點數為30個，則葉子結點數為16個。
7. 在乙個具有n個頂點的無向圖中，要連通全部頂點至少需要n-1條邊。
三、問答題（本大題共4小題，每小題6分，共24分）
1. 設字元a,b,c,d,e,f的使用權值分別是7, 9, 12, 22, 23, 27，畫出huffman樹，並寫出a,b,c,d,e,f的huffman編碼。
huffman編碼為
a: 1110 b: 1111 c: 110d: 00 e: 01 f: 10
2. 已知有向圖的鄰接矩陣如圖所示，要求完成如下任務：
（1）請畫出此有向圖；（2）給出該有向圖的鄰接表。
有向圖為鄰接表為：
3．二叉樹如圖所示，要求完成如下任務：
（1）畫出該二叉樹的中序線索二叉樹；（2）畫出該二叉樹對應的森林。。
中序線索二叉樹為該二叉樹對應的森林為：
4．已知帶權有向圖如下所示，用dijkstra演算法求從頂點v1到其他各頂點的全部最短路徑，請給出演算法的處理過程。
四、程式閱讀題（本大題共2小題，每小題6分，共12分）
1. 完成順序表的刪除。
#include<>
struct sqlist
;void remove(struct sqlist *p,int i)
printf("此線性表為：");
for (i=0;isize;i++)
printf("%d->",p->list[i]);
}void main()
printf("輸入位置:");
scanf("%d",&i);
remove(&l,i) ;
}2. 完成對帶頭結點的單鏈表l進行簡單選擇排序，使得l中的元素按值從小到大排列。
void selectsort(linkedlist l)
}五、程式編寫題（本大題共2小題，每小題12分，共24分）
1.優化的氣泡排序的子函式實現。
void bubblesort(int a[20], int n)
}2.線性單鏈表的生成實現，在已給的程式基礎上編寫生成子函式，結點資料從鍵盤輸入。
#include<>
typedef struct lnode* linklist;
linklist creatlist()
while(q->data
return (head);
}void main(void)
本科生期末試卷資料結構答案
本科生期末試卷十四答案 一 選擇題 1 c 2 c 3 b 4 b 5 c 6 b 7 a c d 8 a c 9 b 10 d 二 填空題 1 a 記憶體 b 外存 c 記憶體 2 a 高速性 b 先行 c 陣列 3 a 瞬間啟動 b 儲存器 c 固態盤 4 a 指令週期 b 布林代數 c 閘電路...
第二學期資料結構期末試卷A卷
合肥學院20 13 至20 14 學年第 2 學期 資料結構與演算法設計課程考試 a 卷 系級專業學號姓名 一 選擇題 2分 15 30分 1 棧和佇列的共同特點是 a 只允許在端點處插入和刪除元素 b 都是先進後出 c 都是先進先出 d 沒有共同點 2 以下資料結構中哪乙個是非線性結構？a 佇列 ...
資料結構試卷 A
密封線密封線 考生姓名准考證號原所在單位 嘉應學院考試卷 a 電腦科學與技術專業資料結構試題 題號得分評卷人 二 判斷題 本大題共10小題，每小題1.5分，共15分，正確的在答題框內打上 t 錯誤的在答題框內打上 f 題號答案12 3456 78910 得分一二三 四五六七 總分複核人 一 單選題 ...