《數據結構》期末復習題 答案

1、1. 以下與數據的存儲結構無關的術語是（ c ）C、哈希表 2. 一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是（ B ） B、1083. 假設帶頭結點的單向循環(huán)鏈表的頭指針為head,則該鏈表為空的判定條件是（ C ）C、head>next= =head 4. 若進棧序列為1，2，3，4，5，6，且進棧和出?？梢源┎暹M行，則不可能出現的出棧序列是（ D ）D、2，3，5，1，6，45. 下列關鍵字序列中，構成小根堆的是（ A ）A、12，21，49，33，81，56，69，41 6. 下列數據結構中，不屬于二叉樹的是（ A ）A、B樹 7. 用順序存儲的

2、方法來存儲一棵二叉樹，存放在一維數組A1.N中，若結點Ai有右孩子，則其右孩子是（ C ）。 C、A2i+1 8. 設樹T的高度為4，其中度為1、2、3、4的結點個數分別為4、2、1、1，則T中葉子數為（ D ） D、 89. 有數據53，30，37，12，45，24，96，從空二叉樹開始逐個插入數據來形成二叉排序樹，若希望高度最小，則應選擇下面哪個序列輸入（ B ）B、37，24，12，30，53，45，9610. 對下面有向圖給出了四種可能的拓撲序列，其中錯誤的是（ C ）C、5，1，6，3，4，2 11. m階B-樹中所有非終端（除根之外）結點中的關鍵字個數必須大于或等于( B ) B、

3、m/2-112. 散列文件也稱為( C ) B 、索引文件13. 數據結構是（ D ）D、相互之間存在一種或多種特定關系的數據元素的集合14. 從邏輯關系來看，數據元素的直接前驅為0個或1個的數據結構只能是（ C ）C、線性結構和樹型結構 15. 設p為指向雙向循環(huán)鏈表中某個結點的指針，p所指向的結點的兩個鏈域分別用pllink和prlink表示，則同樣表示p指針所指向結點的表達式是（ D ） D、pllinkrlink16. 若棧采用順序存儲方式存儲，現兩棧共享空間V1.m，topi代表第i個棧( i =1,2)棧頂，棧1的底在v1，棧2的底在Vm，則棧滿的條件是（ B ）B、 top1+1

4、=top2 17. 若一棵二叉樹有11個葉子結點，則該二叉樹中度為2的結點個數是（ A ）A、1018. 樹的先根序列等同于與該樹對應的二叉樹的（ A ）A、先序序列19. 下面關于哈希(Hash，雜湊)查找的說法正確的是( C )C、不存在特別好與壞的哈希函數，要視情況而定20. 下列序列中，（ D ）是執(zhí)行第一趟快速排序后所得的序列。 D、 68，11，69，23，18 93，7321. 下列關鍵字序列中，構成小根堆的是( D )D、 (15，28，46，37，84，58，62，41)22. ISAM文件和VASM文件屬于( C ) C、索引順序文件 23. 下面程序段的時間復雜度為（ C

5、 ）for (i=0; i<m; i+)for (j=0; j<n; j+)Aij=i*j;C、O(m*n) 24. 已知指針p和q分別指向某單鏈表中第一個結點和最后一個結點。假設指針s指向另一個單鏈表中某個結點，則在s所指結點之后插入上述鏈表應執(zhí)行的語句為（ A ）A、q->next=s->next；s->next=p； 25. 為便于判別有向圖中是否存在回路，可借助于（ D ）D、拓撲排序算法26. 若以S和X分別表示進棧和退棧操作，則對初始狀態(tài)為空的棧可以進行的棧操作系列是（ D ）D、SSSXXSXX27. 設有一順序棧S，元素s1,s2,s3,s4,s5

6、,s6依次進棧，如果6個元素出棧的順序是s2,s3,s4,s6,s5,s1,則棧的容量至少應該是( B )B、3 28. 假設以數組Am存放循環(huán)隊列的元素。已知隊列的長度為length，指針rear指向隊尾元素的下一個存儲位置，則隊頭元素所在的存儲位 置為（ B ）。B、(rear-length+m)%m 29. 在一個鏈隊列中，front和rear分別為頭指針和尾指針，則插入一個結點s的操作為（ D ）。D、rear->next=s;rear=s;30. 對于哈希函數H(key)=key%13,被稱為同義詞的關鍵字是（ D ）D、25和5131. 采用二叉鏈表存儲的n個結點的二叉樹，共

7、有空指針（ A ）個。A、n+132. 連通網的最小生成樹是其所有生成樹中（ D ）D、邊的權值之和最小的生成樹33. 對記錄序列(314，298，508，123，486，145)依次按個位和十位進行兩趟基數排序之后所得結果為（ B ） B、508，314，123，145，486，29834. 任何一個無向連通圖的最小生成樹( C )。C、一棵或多棵 35. 無向圖的鄰接矩陣是一個( C ) C、對稱矩陣 36. 設無向圖G-=(V,E)和G=(V,E),如G為G的生成樹，則下列說法中不正確的是( B )。B、G為G 連通分量37. 以v1為起始結點對下圖進行深度優(yōu)先遍歷，正確的遍歷序列是（

8、D ）D、 v1，v2，v5，v6，v7，v3，v438. 下面幾個符號串編碼集合中，不是前綴編碼的是（ B ）B、0,1,00,1139. 希爾排序的增量序列必須是（B ）。B、遞減的 40. 采用起泡排序法對n個關鍵字進行升序排序，若要使排序過程中比較關鍵字的次數最多，則初始時的序列應滿足條件（ D ） D、關鍵字從大到小排列41. 在下列內部排序中( A )是不穩(wěn)定的。A、希爾排序42. 分別以下列序列構造二叉排序樹，與用其它三個序列所構造的結果不同的是( C )。A、（100，80， 90， 60， 120，110，130） 43. 在查找過程中，沖突指的是（ C ）。C、不同鍵值對應

9、相同的存儲地址44. 對有14個元素的有序表A1.14作二分查找，查找元素A4時的被比較元素依次為（ D ）。D、A7，A3，A5，A445. 以v1為起始結點對下圖進行廣度度優(yōu)先遍歷，正確的遍歷序列是（ A ）A、 v1，v2，v3，v4，v5，v6，v7二、填空題(本大題共10小題，每小題2分，若有兩個空格，每個空格1分，共20分)1. 數據的物理結構包括 數據元素 的存儲和 數據之間關系 的存儲。2. 若一個算法中的語句頻度之和為T(n)=1921n+4nlogn,則算法的時間復雜度為 nlogn 。 3. 下面程序段的時間復雜度是 。 i=1； while (i<=n) i=i*

10、3；4. 循環(huán)隊列用數組A0.m-1存放其元素值，已知其頭尾指針分別是front和rear ，則當前隊列的元素個數是 （ rear-front+m ）% m 5. 主要是使插入和刪除等操作統(tǒng)一 6. （n-1）/2 。7. 在單鏈表中設置頭結點的作用是 深度優(yōu)先 。8. 線性表L=（a1,a2,an）用數組表示，假定刪除表中任一元素的概率相同，則刪除一個元素平均需要移動元素的個數是 相同值關鍵字 。9. 已知一無向圖G=（V，E），其中V=a,b,c,d,e E=(a,b),(a,d),(a,c),(d,c),(b,e)現用某一種圖遍歷方法從頂點a開始遍歷圖，得到的序列為abecd，則采用的是

11、 前移 遍歷方法。10. 如果排序過程不改變 時間復雜度 之間的相對次序，則稱該排序方法是穩(wěn)定的。11. 從順序表中刪除一個元素時，表中所有在被刪元素之后的元素均需 出度 一個位置。 12. 當問題的規(guī)模n趨向無窮大時，算法執(zhí)行時間T(n)的數量級被稱為算法的 10 。13. 若以鄰接矩陣表示有向圖，則鄰接矩陣上第i行中非零元素的個數即為頂點vi的 sxssxxssxssxxx 。14. 一棵含999個結點的完全二叉樹的深度為 12 。15. 假設S和X分別表示進棧和出棧操作，由輸入序列“ABC”得到輸出序列“BCA”的操作序列為SSXSXX，則由“a*b+c/d”得到“ab*cd/+”的操作

12、序列為 4 。16. .如圖所示的有向無環(huán)圖可以排出 L->next->next=L 17. 邊 種不同的拓撲序列。18. 從空樹起，依次插入關鍵字1l，27，35，48，52，66和73構造所得的二叉排序樹，在等概率查找的假設下，查找成功時的平均查找長度為 384 。19. 帶頭結點的雙循環(huán)鏈表L中只有一個元素結點的條件是 隊列 。 20. 求最小生成樹的克魯斯卡爾(Kruskal)算法耗用的時間與圖中 邊稠密 、邊稀疏 的數目正相關。21. 已知一棵完全二叉樹中共有768結點，則該樹中共有 5 個葉子結點。22. 實現圖的廣度優(yōu)先搜索，除了一個標志數組標志已訪問的圖的結點外，還

13、需要 8、64 存放被訪問的結點以實現遍歷。23. Prim（普里姆）算法適用于求 2h-1 的網的最小生成樹；kruskal（克魯斯卡爾）算法適用于求 2h-1 的網的最小生成樹。24. 對長度為20的有序表進行二分查找的判定樹的高度為 n-1 。25. 設一棵完全二叉樹有128個結點，則該完全二叉樹的深度為 n ，有_ 個葉子結點。26. 高度為h的完全二叉樹中最少有 棧 個結點，最多有 個結點。27. 設連通圖G中有n個頂點e條邊，則對應的最小生成樹上有 3 條邊。28. 構造n個結點的強連通圖，至少有 O(n2) 條弧。29. 表達式求值是 （42,13,94,55,05,46,17）

14、 應用的一個典型例子。30. 設棧S和隊列Q的初始狀態(tài)為空，元素e1,e2,e3,e4,e5,e6依次通過棧S，一個元素出棧后即進入隊列Q，若6個元素出隊的序列是e2,e4,e3,e6,e5,e1，則棧的容量至少應該是 。31. 快速排序算法在最差的情況下其時間復雜度是 。32. 對序列55，46，13，05，94，17，42進行基數排序，第一趟排序后的結果是 。三、應用題（本大題共5小題，每小題6分，共30分）1. 已知二叉樹的先序遍歷序列ABCDEFGH，中序遍歷序列為CBEDFAGH，畫出二叉樹。答案：二叉樹形態(tài) 2. 如圖請給出鄰接表、鄰接矩陣及逆鄰接表。V1V3V2V4參考答案如下：

15、（1）鄰接表：(注意邊表中鄰接點域的值是頂點的序號，這里頂點的序號是頂點的下標值-1)   vertex firstedge  next  （2）逆鄰接表：（3）3. 由字符集s，t，a，e，I及其在電文中出現的頻度構建的哈夫曼樹如圖所示。已知某段電文的哈夫曼編碼為111000010100，請根據該哈夫曼樹進行譯碼，寫出原來的電文。答案：原來的電文為：eatst4. 請畫出下圖所示的樹所對應的二叉樹，并寫出對應二叉樹的先序遍歷和中序遍歷。12345678答案：12345678先序遍歷為：12345687 中序遍歷為：348675215. 設散列表為HT1

16、3, 散列函數為 H (key) = key %13。用閉散列法解決沖突, 對下列關鍵碼序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。采用線性探查法尋找下一個空位, 畫出相應的散列表, 并計算等概率下搜索成功的平均搜索長度。答案：使用散列函數 H(key) = key mod 13，有H(12) = 12, H(23) = 10,H(45) = 6,H(57) = 5,H(20) = 7,H(03) = 3,H(78) = 0,H(31) = 5,H(15) = 2,H(36) = 10.利用線性探查法造表： 0 1 2 3 4 5 6 7 8 9

17、10 11 12 78 15 03 57 45 20 31 23 36 12 (1) (1) (1) (1) (1) (1) (4) (1) (2) (1)搜索成功的平均搜索長度為ASLsucc = (1 + 1 + 1 + 1 + 1 + 1 + 4 + 1 + 2 + 1) = 6. 已知帶權圖G如圖所示，畫出圖G的一棵最小生成樹。答：7. 假設用于通信的電文由字符集a,b,c,d,e,f,g,h中的字母構成，這8個字母在電文中出現的概率分別為0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10，請為這8個字母設計哈夫曼編碼。哈夫曼編碼為：a:1001 b:01

18、c:10111 d:1010 e:11 f:10110 g:00 h:1000注意：答案不唯一8. 試用權集合12,4,5,6,1,2構造哈夫曼樹，并計算哈夫曼樹的帶權路徑長度。WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=699. 畫出與如圖所示森林對應的二叉樹。答：10. 已知一個散列表如下圖所示：3520334859 0 1 2 3 4 5 6 7 8 9 10 11 12 其散列函數為h(key)=key%13, 處理沖突的方法為雙重散列法，探查序列為： hi=(h(key)+*h1(key)%m =0,1,，m-1其中： h1(key)=key%11+1回答

19、下列問題：（1）對表中關鍵字35，20，33和48進行查找時，所需進行的比較次數各為多少？（2）該散列表在等概率查找時查找成功的平均查找長度為多少？答：（）對關鍵字35、20、33和48進行查找的比較次數為、；（）平均查找長度11. 請畫出與下列二叉樹對應的森林。答：12. 對于給定結點的關鍵字集合K=5，7，3，1，9，6，4，8，2，10，（1）試構造一棵二叉排序樹；（2）求等概率情況下的平均查找長度ASL。答：74312596108（2）ASL=(1*1+2*2+3*4+4*3)/10=2.913. 給出下圖對應的鄰接矩陣，并給出A，B，C三個頂點的出度與入度 答案: 鄰接矩陣為： A

20、B C D E F其中頂點A的入度為2，出度為1；其中頂點B的入度為2，出度為2；其中頂點C的入度為1，出度為3；14. 已知圖5.32如下所示，求從頂點a到其余各頂點的最短路徑。（給出求解過程）543223356abdfce答：終點最短路徑求解過程b6 (a,b)5 (a,c,b)c3 (a,c)d¥6 (a,c,d)6 (a,c,d)e¥7 (a,c,e)7 (a,c,e)7 (a,c,e)f¥¥¥9 (a,c,d,f)9 (a,c,d,f)vjcbdefSa,ca,c,ba,c,da,c,ea,c,d,f15. 閱讀下列算法，并回答問題：

21、（1）假設串由合法的英文字母和空格組成，并以0作結束符。設串s=”Iamastudent”(表示空格符)，寫出f30（s）的返回值；（2）簡述算法f30的功能。int f30 (char*s)答案：(1) 4(2)算法功能：統(tǒng)計單詞的個數。16. 閱讀下列函數,并回答問題：（1）假設隊列q中的元素為(a,b,c,d,e),其中“a”為隊頭元素。寫出執(zhí)行函數調用Conv(&q)后的隊列q；（2）簡述算法Conv的功能。答案：（1） e，d，c，b，a（2） 將隊列里的值反轉17. 閱讀下列函數,并回答問題：已知整形數組L1.8中的元素依次為（19，18，15，17，16，13，12，10

22、），閱讀下列函數，并寫出執(zhí)行函數調用sort(L, 8)時，對L進行的頭兩趟（pass分別為0和1）處理結果。答案：（1）第一趟（pass = 0）19 15 18 16 17 12 13 10（2）第二趟（pass = 1）19 15 16 18 12 17 10 13keynext18. 已知帶頭結點的單鏈表中的關鍵字為整數，為提高查找效率，需將它改建為采用拉鏈法處理沖突的散列表。設散列表的長度為m，散列函數為Hash(key)=key%m。鏈表的結點結構為： 。請在空缺處填入適當內容，使其成為一個完整算法。void f33 (LinkList L, LinkList H, int m)答

23、案：（1） NULL （2）p->next=Hj p=q19. 下列函數的功能是，對以帶頭結點的單鏈表作為存儲結構的兩個遞增有序表（表中不存在值相同的數據元素）進行如下操作：將所有在Lb表中存在而La表中不存在的結點插入到La中，其中La和Lb分別為兩個鏈表的頭指針。請在空缺處填入合適內容，使其成為一個完整的算法。答案：（1）pre->next=pb （2）pre->next=pa （3）pre->next=pb20. 閱讀算法f30，并回答問題：下列算法為有向圖拓撲排序,請在空缺處填入合適的內容，使其成為一個完整的算法。答案：(1）top=-1 （2）top=grap

24、hj.count （3）graphk.count=021. 閱讀算法f31，并回答問題：下列算法功能為在數組a的前n(n>=1)個元素中找出第k(1<=k<=n)小的值。這里假設數組a中各元素的值都不相同。請在空缺處填入合適的內容，使其成為一個完整的算法。答案：（1）(i=k) return; （2）i+1 （3）i-122. 閱讀算法f33，并回答問題：下列算法功能為奇偶交換排序，思路如下：第一趟對所有奇數的i,將ai和ai+1進行比較,第二趟對所有偶數的i,將ai和ai+1進行比較,每次比較時若ai>ai+1,將二者交換;以后重復上述二趟過程,直至整個數組有序。請在

25、空缺處填入合適的內容，使其成為一個完整的算法。答案： (1)ai=t (2)(i=2;i<=n;i+=2) (3)flag四、算法設計題（本大題共2小題，每小題10分，共20分）1. 已知單鏈表的結點類型為Lnode，包含next和data成員。編寫算法，實現帶頭結點單鏈表的逆置算法。參考答案： void invent(Lnode *head) Lnode *p,*q; if(!head->next) return ERROR; p=head->next; q=p->next; p->next =NULL; while(q) p=q; q=q->next;

26、p->next=head->next; head->next=p; 2. 編寫一個函數，要求借助一個棧把一個數組中的數據元素逆置。其中，棧類型為SeqStack，可以直接使用InitStack(SeqStack*)、Push(SeqStack*,ElemType)、Pop(SeqStack*,ElemType*)函數。參考答案：void Inverse(ElemType arr,int n)SeqStack *s;int i;InitStack(&s);for(i=0;i<n;i+) /數組元素依次入棧Push(s,arri);for(i=0;i<n;i+

27、) /棧中元素依次出棧，存入數組，是數組逆序Pop(s,&arri);3. 二叉樹采用鏈接存儲結構，結點類型為Btree，包括left、right和data三個成員，試設計一個算法計算一棵給定二叉樹的度為2的結點的個數。參考答案：int twochild(Btree *b) int num1,num2; if (b=NULL) return 0; else num1=twochild1(b->left); num2=twochild1(b->right);if ( b->left!=NULL&&b->right!=NULL) return (nu

28、m1+num2+1); else return (num1+num2); 4. 假設以帶雙親指針的二叉鏈表作為二叉樹的存儲結構，其結點結構的類型說明如下所示：typedef char DataType;typedef struct node DataType data; struct node *lchild, *rchild; /左右孩子指針 struct node *parent; /指向雙親的指針 BinTNode;typedef BinTNode *BinTree;若px為指向非空二叉樹中某個結點的指針，可借助該結構求得px所指結點在二叉樹的中序序列中的后繼。(1)就后繼的不同情況，簡

29、要敘述實現求后繼操作的方法；參考答案：（1）分兩種情況討論當*px的右子樹不為空時，則從*px的右孩子開始，沿其左孩子往下查找，直到找到一個沒有左孩子的節(jié)點為止，則該結點為*px在中序序列中的后繼；當*px的右孩子為空時，則沿*px的雙親指針鏈向上查找，直至找到其左子樹中包含*px的最年輕祖先，則該祖先結點為*px在中序序列中的后繼。(2)編寫算法求px所指結點的中序序列后繼，并在算法語句中加注注釋。（2）BinTree f34(BinTree px)BinTree q=px->rchild;if(q!=NULL)/沿左孩子往下查找px=q;while(px->lchild!=NU

30、LL)px=px->lchild;else/沿雙親指針鏈向上查找while(px!=NULL && px->rchild=q)q=px;px=px->parent;return px;/返回所找到的中序序列后繼結點的指針 /或者無后繼結點時返回空指針5. 已有鄰接表表示的有向圖，請編程判斷從第u頂點至第v頂點是否有簡單路徑，若有則印出該路徑上的頂點。參考答案： void AllSPdfs(AdjList g,vertype u,vertype v) /求有向圖g中頂點u到頂點v的所有簡單路徑，初始調用形式：AllSPdfs(g,u,v)int top=0,s; s+top=u; visitedu=1; while (top>0 | p) p=gstop.firstarc; /第一個鄰接點。 while (p!=null &&am