編號：0025 座位號：
17-18學年第1學期期末考試
數據結構 試題

一、選擇題：（每題4分，共20分）

1．假定一個順序隊列的隊首和隊尾指針分別為front和rear，存放該隊列的數組長度為N，則判斷隊空的條件為________。
A．（front+1）% N == rear
B．（rear+1）% N == front
C． front == 0
D． front == rear

2．對于一棵具有n個結點的樹，該樹中所有結點的度數之和為_______。
A．n　　 B．n+1　
C．n-1 D．2n

3．由權值分別為３,９,６,２,５的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為＿＿。
Ａ．24 　　　 　Ｂ．55 　　　
Ｃ．72 　　　 Ｄ．53

4．根據下列二叉樹遍歷的結果為A,B,C,D,E,F,G，則此遍歷為＿＿。
　　A　　　　　　　　　A．前序
　　　　B　　　　E　　 　　　　B．中序
　　C　　　D　　　　F　　　　　C．后序
　　　　　　　　 G　 　　　　　D．層次

5．每次通過相鄰元素之間的比較和交換使較小的元素逐漸從底部移向頂部，此種排序方法叫做＿＿＿排序。
A．直接插入　　　 Ｂ．直接選擇　　　
Ｃ．氣泡　　　 Ｄ．堆排序

二、填空題：（每空2分，共20分）

1．在循環雙向鏈表中表頭結點的左指針域指向________結點，表尾結點的右指針域指向________結點。

2．在一個稀疏矩陣中，每個非零元素所對應的三元組包括該元素的_______、_______和________三項。

3．在線性表的散列存儲中，處理沖突有_______和_______兩種方法。

4．對于一個具有n個頂點和e條邊的有向圖和無向圖，若采用邊集數組表示，則存于數組中的邊數分別為_______和________。

5．假定一組記錄的排序碼為（４６,７９,５６,３８,４０,８４），對其進行歸并排序的過程中，第二趟歸并結果為__________________________。

三、問答題：（共40分）

已知一個圖的頂點集V和邊集G分別為：
V={0，1，2，3，4，5，6，7}
E={(0,1)8, (0,2)5, (0,3)2, (1,5)6, (2,3)25, (2,4)13, (3,5)9, (3,6)10, (4,6)4, (5,7)20}
求該圖的最小生成樹的權。（20分）

最小生成樹的權為：____________________

2．已知一組元素的排序碼為（36，25，48，12，65，20），寫出用直接選擇排序法每次選擇和交換后的排列結果。（20分）

四、閱讀算法，寫出執行后的結果
（共20分）

Stack S;
InitStack(S);
Push(S,3);
Push(S,4);
Push(S,5);
int x=Pop(S)+2*Pop(S);
Push(S,x);
int i,a[4]={5,8,12,15};
for (i=0;i<4;i++) Push(S,a[i]);
while(!StackEmpty(S)) cout<<Pop(S)<<’’;

結果為：_________________________________。

總結

以上是生活随笔為你收集整理的【渝粤教育】国家开放大学2018年春季 0025-21T数据结构 参考试题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。