1、數據結構試卷（一）參考答案一、選擇題（每題2 分，共 20 分）12345678910二、填空題（每空1 分，共 26 分）1. 正確性易讀性強壯性高效率2. O(n)3. 9 3 34. -1 34X*+2Y*3/-5. 2n 1 16. e 2e7. 有向無回路8. n(1)/2 n(1)9. （12，40）（）（ 74）（23,55 ，63）10. 增加 111. O(2n) O( 2n)12. 歸并三、計算題（每題6 分，共 24 分）1. 線性表為：（78，50，40，60，34， 90）011101010111011101012. 鄰接矩陣：01110鄰接表如圖 11 所示：圖 1

2、13. 用克魯斯卡爾算法得到的最小生成樹為：(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)204. 見圖 12442222244545458832圖 123 584四、讀算法（每題7 分，共 14 分）1. （ 1）查詢鏈表的尾結點（ 2）將第一個結點鏈接到鏈表的尾部，作為新的尾結點（ 3）返回的線性表為（ a23, 1）2. 遞歸地后序遍歷鏈式存儲的二叉樹。五、法填空（每空2 分，共 8 分）>>六、編寫算法（ 8 分）(* x)0; *為計數器() (>); >,出循環時 i 中的值即為x 結點個數i;數據結構試卷（二）參考答案一

3、、選擇題12345678二、填空題1. 構造一個好的函數，確定解決沖突的方法2. ，3. 有序4. O(n2) ，O(2n)5. N0-1 ，2N016. 27. (31 ，38，54，56，75， 80， 55，63)8. (1 ，3，4， 5，2) ，(1 ， 3，2，4， 5)三、應用題1. (22 ，40，45，48，80， 78) ， (40 ，45，48，80，22，78)2. > >> >> >3. 291*1+2*2+3*4+4*2)=25/94. 樹的鏈式存儲結構略，二叉樹略5. (1 ，3) ，(1 ，2) ，(3 ， 5) ， (5 ，

4、6) ， (6 ， 4)6. 略四、算法設計題1. 設有一組初始記錄關鍵字序列（ K1， K2，），要求設計一個算法能夠在 O(n) 的時間復雜度內將線性表劃分成兩部分，其中左半部分的每個關鍵字均小于， 右半部分的每個關鍵字均大于等于。( r, s, t), , s;(i<j)(i<j rj>x) 1; (i<j) rij1; (i<j ri<x) 1; (i<j) rji1;ri;2. 設有兩個集合 A 和集合 B，要求設計生成集合 B 的算法，其中集合 A、 B 和 C用鏈式存儲結構表示。 ; *;(*)*p,*q,*t;(00>) (0&g

5、t;) (>>) ;(0) ( *)(); >>> ;數據結構試卷（三）參考答案一、選擇題12345678910第 3 小題分析：首先用指針變量 q 指向結點 A的后繼結點 B，然后將結點 B 的值復制到結點 A 中，最后刪除結點 B。第 9 小題分析： 9 快速排序、歸并排序和插入排序必須等到整個排序結束后才能夠求出最小的 10 個數，而堆排序只需要在初始堆的基礎上再進行 10 次篩選即可，每次篩選的時間復雜度為 O(2n) 。二、填空題1. 順序存儲結構、鏈式存儲結構2. 9， 5013. 54. 出度，入度5. 06.7. 中序8. 79. O(1)10.

6、2， 2111. (5 ，16，71，23，72，94，73)12. (1 ，4， 3，2)13. 1， j14. (t) ，>第 8 小題分析：二分查找的過程可以用一棵二叉樹來描述，該二叉樹稱為二叉判定樹。 在有序表上進行二分查找時的查找長度不超過二叉判定樹的高度 12n。三、計算題1AEBFGCNULLDHFKJ2、H(36)=367=1;H (22)=(1+1)7=2; .沖突H(15)=157=1;. 沖突H2(22)=(2+1)7=3;H(15)=(1+1)7=2;H(40)=407=5;H(63)=637=0;H(22)=22 7=1; . 沖突（1）01234 5 6633

7、6152240（2） 12 11 31.653、(8,9,4,3,6,1),10,(12,18,18)(1,6,4,3),8,(9),10,12,(18,18)1,(3,4,6),8,9,10,12,18,(18)1,3,(4,6),8,9,10,12,18,181,3, 4,6,8,9,10,12,18,18四、算法設計題1. 設計在單鏈表中刪除值相同的多余結點的算法。; ; *; ( *)*p,*q,*s;(0>)(>0; )(>>) >> (q)>>2. 設計一個求結點 x 在二叉樹中的雙親結點算法。 ; *,*; ;*q20; 000;(

8、 *, x)(0 0)(>) 1; ;(1)% 20; qr; (>); (>); ( * x)i;();(1; i< ) (qi->> qi->>) ;(0) (" xn"); (i<) ("">); (" ");數據結構試卷（四）參考答案一、選擇題1C2D3 D4B5 C6A7B8 A9C10A二、填空題1. O(n2) ，O(2n)2. p>>> >>>3. 34. 215. 26. 50，517. 1， ()8. 1，9. (19

9、，18，16，20，30， 22)10. (16 ，18，19， 20， 32，22)11. Aij=112. 等于13.14. i=0， k三、計算題1LS 1 -> 1->1111-> 10e0 a1-> 1-> 10 b0 c0 d2(1) ;；(2) ;林轉換為相應的二叉樹；ABGCHDIEJFK3H(4)(5)=0(3)(6)(9)=2(8)=3(2)(7)=60451269 33 845627789四、算法設計題1. 設單鏈表中有僅三類字符的數據元素 ( 大寫字母、數字和其它字符 ) ，要求利用原單鏈表中結點空間設計出三個單鏈表的算法，使每個單鏈表只包

10、含同類字符。; ; *; (*)*p; 000;(0)> >0;(>>='A' ><='Z') > ;(>>='0' ><='9') > ; > ;2. 設計在鏈式存儲結構上交換二叉樹中所有結點左右子樹的算法。 ; *,*; ; ( *)*p;(0) ;(>); (>);> >> >3. 在鏈式存儲結構上建立一棵二叉排序樹。n 10 ; *,*; ( * )(0)( *)(); >>>0;(>&

11、gt;) (>); (>);( *)i;(1<) (100);數據結構試卷（五）參考答案一、選擇題1 A2 B3A4A5D6 B7 B8B9C10 C二、填空題1. 1+122. 可以隨機訪問到任一個頂點的簡單鏈表3. i(1)/214. ，5. ，6. 8， 647. 出度，入度8. <2i < 219. ，r1j10.()/2 ，r>k三、應用題1.2. (1,5),(5,2),(5,3),(3,4)103. (1*1+2*2+3*4)/7=17/74. 1=7/6 ，2=4/3四、算法設計題1. 設計判斷兩個二叉樹是否相同的算法。 ; *,*; ;(

12、*1 *2)(10 20) (1);(10 20 1->2->) (0);(1->2->)*(1->2->);2. 設計兩個有序單鏈表的合并排序算法。(*)*0;(0 0)(><>)(0) ; > ;>(0) ; > ;>(0) > >數據結構試卷（六）參考答案一、選擇題1D2 A3A4A5D6D7 B8A9C10 B11 C 12A 13 B 14D 15 B二、判斷題1錯 2對 3對 4對 5錯6錯 7對 8錯 9對 10對三、填空題1. O(n)2. >> >3. (1 ，3，2，

13、 4，5)4. 15. 1296.7. >0>08. O(n2)9. O(2n) ， O(n)10. 開放定址法，鏈地址法四、算法設計題1. 設計在順序有序表中實現二分查找的算法。; ;( r , k)01;(<)()/2;(r) (1); (r>k) 1; 1;(0);2. 設計判斷二叉樹是否為二叉排序樹的算法。327681; ; *,*; ( *)(0) (>); (>>)0; >(>);3. 在鏈式存儲結構上設計直接插入排序算法( *)*s,*p,*q;t;(0 >0) ;(>0>)(>>) (>&

14、gt;>) ;(>); >> >> > >>>>數據結構試卷（七）參考答案一、選擇題1B2 B3C4B5B6A7 C8C9B10 D二、判斷題1對2對3對4對5對6對7對8錯9錯10錯三、填空題1. >， >2. n(1) ， n(1)/23. 24. 開放定址法，鏈地址法5. 146. 21，217. (12 ，24，35，27， 18， 26)8. (12 ，18，24，27， 35， 26)9. 510.i<j ri<， ri四、算法設計題1. 設計在鏈式結構上實現簡單選擇排序算法。( *)*p,*

15、q,*s;(0 >0) ;(; 0>)> ;(> 0>) (>>)> ;()> >> >2. 設計在順序存儲結構上實現求子串算法。( s , , , t )(s);(<1 >) ("");(1>) (""); (10; i<1) tji; tj= '0'3. 設計求結點在二叉排序樹中層次的算法。0; ; *,*; ( * x)(0); (>) ;(>>x) (>); (>);數據結構試卷（八）參考答案一、選擇題1C

16、 2C3C 4B5B6C 7B8C 9A10 A二、判斷題1對 2錯 3對 4錯 5錯6對 7對 8對 9對 10對三、填空題1. (49 ，13，27，50， 76， 38， 65，97)2. ( *)()， (>)3. >4. >， >5.6. 1， 167. 08. (13 ，27，38，50， 76， 49， 65，97)9. 110. 50四、算法設計題1. 設計一個在鏈式存儲結構上統計二叉樹中結點個數的算法。( * )(0); (>); (>);2. 設計一個算法將無向圖的鄰接矩陣轉為對應鄰接表的算法。 m; mm; 1 ; 1 *; 2 *;(

17、 g1 g2 ); *p;(0<1) g2i0;(0<1) (0<1)(g1ij1)( *)()>>i; gi;( *)()>>j; gj;數據結構試卷（九）參考答案一、選擇題1A2A3A4C5D6D 7C8B9C10 A11 C 12C 13 D 14A 15 A二、填空題1. >， >2. 503. 14. 6， 85. 快速，堆6. 19/77.8. 69. (24 ，65，33，80， 70， 56， 48)10. 8三、判斷題1錯 2對 3對 4對 5錯6錯 7對 8對 9錯 10對四、算法設計題1設計計算二叉樹中所有結點值之和的

18、算法。( * )(0) > (>); (>);2設計將所有奇數移到所有偶數之前的算法。( r, s, t)s;(i<j)(i<j rj%20) 1;(i<j) rij1;(i<j ri%21) 1;(i<j) rji1;ri;3設計判斷單鏈表中元素是否是遞增的算法。( *)(0>0) (1)(> 0; >)(>>>) (0);(1);數據結構試卷（十）參考答案一、選擇題1A2D3B4B5B6D7A8D9D 10C 11 B 12 D二、填空題1. 4， 102. O(2n) ，O(n2)3. n4. 1， 25. n(1)+16. >7. 線性結構，樹型結構，圖型結構8. O(n2) ， O()9. 8/310. (38 ， 13，27， 10， 65， 76，97)11. (10 ， 13，27， 76， 65， 97，38)12. 12