1、數據結構試題及答案一、選擇題（每小題 2 分，共 20 分），每個題的備選答案中，只有一個是正確 的，請將答案填寫在試題的括號中。1、對順序存儲的線性表，設其長度為 20 ，在任何位置上插入或刪除操作都是 等概率的。插入一個元素時平均要移動表中的（ A ）個元素。A 10B 9C 11D 122、若某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一 個元素，則采用（ D ）存儲方式最節省運算時間。A. 單鏈表B 僅有頭指針的單循環鏈表C.雙鏈表D .僅有尾指針的單循環鏈表3、當利用大小為 n 的數組順序存儲一個棧時，假定用 top=n 表示棧空，則向 這個棧插入一個元素時，首先應

2、執行（ B ）語句修改 top 指針。A. top+ B . top- C . top = 0 D . top4、設入棧順序為A, B, C, D, E,則出棧序列不可能是（C ）。A. EDCBA B. ABCDE C. ADEBC D . ABDEC5、已知關鍵字序列（ 46, 79, 56, 38, 40, 84 ）,采用快速排序（以位于最左位 置的關鍵字為基準）得到的第一次劃分結果為：（ A ）A. 40, 38, 46, 56, 79, 84 B. 38, 46, 79, 56, 40, 84 C. 38, 46, 56, 79, 40, 84 D. 40, 38, 46, 79,

3、56, 84 6、一個有 n 個頂點和 n 條邊的無向圖一定是（ C ）。A .不連通的 B .連通的 C .有環的 D .無環的7、 在一棵具有n個結點的二叉樹的第i層上，最多具有（B ）個結點。A . 2i B . 2i-1 C . 2i+1 D . 2n8、 對線性表采用折半查找法,該線性表必須（B ）。A.采用順序存儲結構B.采用順序存儲結構，且元素按值有序C.采用鏈式存儲結構D .采用鏈式存儲結構，且元素按值有序9、在一棵具有 n 個結點的完全二叉樹中,分支結點的最大編號為（ C ）。A. ?（n-1）/2? B . ?n/2? C . ?n/2? D . ?n/2? -110、 在

4、一個無向圖中,所有頂點的度數之和等于所有邊數的（ D ） 倍。A. 3 B . 1/2 C . 1 D . 2二、填空題（每小題 2 分,共 20 分）,請將正確的結果,填寫在試題的橫線上。1、帶頭結點的循環鏈表 L 為空的條件是。2、 序列A=12, 70, 33, 65, 24, 56 給出對應于序列A的大頂堆HA （以線性數 組表示）。3、每次使兩個相鄰的有序表合并成一個有序表,這種排序方法叫做 排序。4、 設循環隊列Q的隊頭和隊尾指針分別為front和rear，隊列的最大容量為 MaxSize,且規定判斷隊空的條件為 Q.front = = Q.rear ，則隊列的長度 為。5、已知數

5、組 A0.110.8 按行優先存儲,每個元素占有 5個存儲單元,且A00 的地址為 1000（十進制）,則 A67 的地址為 。6、已知廣義表 A=（a, （）, （b, （c） ,則其深度為。7、在一棵二叉樹中,假定度為 2 的結點個數為 5 個,度為 1 的結點個數為 6個,則葉子結點數為 _ 個。8、 設森林F中有3棵樹，第1、2、3棵樹的結點個數分別為n1、n2、n3 ,當 把森林F轉換成一棵二叉樹后，其根結點的右子樹中有 個結點。9、 將含有 64 個結點的完全二叉樹從根結點開始順序編號，根結點為第1 號， 其他結點自上向下，同一層自左向右連續編號。則第 30 號結點的雙親結點的編

6、號為 。10、有序表 （1,2,3,4,5,6,7,8,9） 用折半查找方法，查找元素 3 的比較次數為 。三、判斷題（每小題2分，共20分），下列說法正確的在前面括號內畫“乂”錯誤的畫“&”（） 1 、線性表的邏輯順序與存儲順序總是一致的。（） 2、在單鏈表中，要取得某個元素，只要知道該元素的指針即可，因此，單鏈表是隨機存取的存儲結構。（） 4、棧是僅限定在一端進行插入和刪除的線性表。（） 5、用鄰接矩陣存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小與圖中的頂點個數無關，只與圖的邊數有關。（） 6、對于 AOE 網絡，加速任一關鍵活動就能使整個工程提前完成。（） 7、對兩棵具有

7、相同關鍵字集合而形狀不同的二叉排序樹，按中序遍歷它們得到的序列的順序是一樣的。（） 8、有向網中從一個頂點到另一個頂點的最短路徑只有一條。（） 9、對于一棵具有 n 個結點，其深度為 h 的二叉樹，進行任一種次序遍歷的時間復雜度為 O（n）。（） 10 、快速排序和堆排序是不穩定的排序方法。四、應用題（共 40 分）1、（10分）假定一個待哈希存儲的線性表為 32,75,63,48,94,25,36,18 ，哈 希地址空間為010,若采用哈希函數H（k）=k MOD 11和線性探測再散列法 處理沖突，試給出對應的哈希表（給出求解過程），并求出在等概率情況下查 找成功時的平均查找長度。2、（10

8、 分）有 8 個帶權結點，其權值分別為 4， 26， 12， 8， 7， 13， 15， 15， 試以它們為葉結點生成一棵 Haffman 樹（給出過程），然后求出該樹的帶權路 徑長度 WPL。3、 （ 10分）已知一棵二叉樹，其先序序列為：ABDEGMNCFH中序序列為： DBMGNEACHF,請畫出這棵二叉樹（給出過程），并給出其后序序列。4、（ 10 分）已知關鍵字序列（ 37，23，42，55，61 ，36，28，33），請給出 采用快速排序法對序列作升序排序時每一趟的過程。答案一、選擇題（每小題 2 分，共 20 分）題號 1 2 3 4 5 6 7 8 9 10答案 A D B C

9、 A C B B C D二、填空題（每小題 2 分，共 20 分）1、L-next=L2 、 70，65，56，12，24，333、歸并 4、（Q.rearQ.front+MaxSize）%MaxSize5 、 13056、 37 、 6 8、 n2+n39 、 1510、3三、判斷題（每小題 2 分，共 20 分）題號 1 2 3 4 5 6 7 8 9 10答案 x x x V x x V x V V四、應用題(共 40 分)1、過程 4分，哈希表 4分，平均查找長度 2分，共 10 分 H(32)=32 Mod 11=10 H(75) =75 Mod 11=9 H(63) =63 Mod

10、 11=8 H(48) =48 Mod 11=4 H(94) =94 Mod 11=6 H(25) =25 Mod 11=3 H(36) =36 Mod 11=3 ，與 25 沖突，所以 H1= (3+1 )Mod 11=4 ，與 48 沖突， H2= (3+2 )Mod 11=5 ，所以 36 的哈希地址是 5， H(18) =18 Mod 11=7 0 1 2 3 4 5 6 7 8 9 1025 48 36 94 18 63 75 32 查找成功時， 36 將比較 3 次，其它都是比較 1 次，所以平均查找長度是： ASL=( 1+1+1+1+1+1+3+1 )/8=10/8=5/4=1

11、.252、WPL值正確3分；過程每步1分；共7分WPL=4*4+7*4+12*3+13*3+8*3+15*3+15*3+26*2=2853、過程 8 分，后序序列 2 分，共 10 分 后序序列： DMNGEBHFCA4、快速排序的每一趟的過程： (共 10 分) 初始序列 37 23 42 55 61 36 28 3333 23 28 36 37 61 55 42(2 分) 28 23 33 36 3761 55 42(2 分) 23 28 33 36 37 61 55 42(2 分)23 28 33 36 37 42 55 61( 2 分)23 28 33 36 37 42 55 61(

12、2 分)數據結構綜合測試題一、單選題1. 以下數據結構中哪一個是線性結構？ ( B )A. 有向圖 B. 棧 C. 線索二叉樹 D. B 樹2. 在一個單鏈表HL中，若要向表頭插入一個由指針p指向的結點，則執 行 (B ) 。A. HL=p; p-next=HL;B. p-next=HL; HL=p;C. p-next=HL; p=HL;D. p-next=HL-next; HL-next=p;3. 在一個帶有頭結點的單鏈表HL中，若要向表頭插入一個由指針p指向 的結點，則執行 ( D ) 。A. HL=p; p-next=HL;B. p-next=HL; HL=p;C. p-next=HL;

13、 p=HL;D. p-next=HL-next; HL-next=p;4. 單鏈表的每個結點中包括一個指針 next ，它指向該結點的后繼結點。 現要將指針q指向的新結點插入到指針p指向的單鏈表結點之后，下面的操作 序列中哪一個是正確的？( C )A q= p-next; p-next=q-next;B.p-next=q-next;q=p-nextC. q-next=p-next; p-next=q;D. P-next=q; q-next=p-next;5. 在一個循環順序存儲的隊列中，隊首指針指向隊首元素 的( B )位置。A 前一個B. 后一個 C. 當前6. 以下哪一個不是隊列的基本運算

14、？( B )A. 從隊尾插入一個新元素B. 從隊列中刪除第 i 個元素C. 判斷一個隊列是否為空D. 讀取隊頭元素的值7. 用鏈接方式存儲的隊列，在進行刪除運算時 (D ).A. 僅修改頭指針B. 僅修改尾指針C. 頭、尾指針都要修改D. 頭、尾指針可能都要修改8. 對線性表，在下列哪種情況下應當采用鏈表表示？ ( B )A. 經常需要隨機地存取元素B. 經常需要進行插入和刪除操作C. 表中元素需要占據一片連續的存儲空間D. 表中元素的個數不變9.字符 A、 B、 C 依次進入一個棧，按出棧的先后順序組成不同的字符串，至多可以組成 ( A ) 個不同的字符串？A.5 B.4 C.6 D.1 1

15、0. 下述哪一條是順序存儲方式的優點？( A )A.存儲密度大B.插入運算方便C.刪除運算方便D.可方便地用于各種邏輯結構的存儲表示11. 從二叉搜索樹中查找一個元素時，其時間復雜度大致為 ( C ) 。A. O(n) B. O(1)C. O(log 2n)D. O(n 2)12. 由權值分別為 3,8,6,2,5 的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為 D。A 24 B 48C 72D 5313. 下列關于二叉樹遍歷的敘述中，正確的是 ( D ) 。A. 若一個結點是某二叉樹的中序遍歷的最后一個結點，則它必是該 二叉樹的前序最后一個結點B. 若一個點是某二叉樹的前序遍歷最后一個結點，

16、則它必是該二 叉樹的中序遍歷的最后一個結點C. 若一個樹葉是某二叉樹的中序遍歷的最后一個結點，則它必是 該二叉樹的前序遍歷最后一個結點D. 若一個樹葉是某二叉樹的前序最后一個結點，則它必是該 二叉樹的中序遍歷最后一個結點14. 高度 k 的二叉樹的最大結點數為 (A ).A.2k-1B.2K+1C.2K-1D. 2 k-115. 下面關于圖的存儲的敘述中正確的是 ( C ).A. 用鄰接表法存儲圖，占用的存儲空間大小只與圖中結點 個數有關，而與邊數無關B. 用鄰接表法存儲圖，占用的存儲空間大小只與圖中邊數 有關，而與結點個數無關C. 用鄰接矩陣法存儲圖，占用的存儲空間大小只與圖中結點個數有 關

17、，而與邊數無關D. 用鄰接矩陣法存儲圖，占用的存儲空間大小只與圖中邊數 有關，而與結點個數無關中, 用二分法查找關鍵碼值 10,16. 在順序表 (2,5,7,10,14,15,18,23,35,41,52) 所需的關鍵碼比較次數為 BA.2 B.3 C.4 D.517. 對線性表進行二分法查找，其前提條件是 (A ).A. 線性表以順序方式存儲，并且按關鍵碼值排好序B. 線性表以順序方式存儲，并且按關鍵碼值的檢索頻率排好序C. 線性表以鏈接方式存儲，并且按關鍵碼值排好序D. 線性表以鏈接方式存儲，并且按關鍵碼值的檢索頻率排好序18.下列哪一個關鍵碼序列不符合堆的定義？（C）A. a、c、d、

18、 g、h、m、p、q、r、xB. a、 c 、m、d、h、p、x、g、o、rC.a、d、p、r 、c、q、x、 m、h、 gD.a、d、c、m、p、g、h、x、r、q19.對n 個記錄的文件進行快速排序，所需要的輔助存儲空間為BA. O （1)B. O（1og2n）C.O（ n）D.O(n2)20. 在待排序文件已基本有序的前提下，下述排序方法中效率 最高的是 AA.直接插入排序B.直接選擇排序C.快速排序D.歸并排序21. 設有關鍵碼序列 (q ， g， m， z， a， n， p， x， h) ，下面哪一個序列是從 上述序列出發建堆的結果 ?A.a， g， h， m， n， p， q， x

19、， zzC. g ， m， q， a， n， p， x ， h， zB.D.a ， g ， m， h ，q， n， p， x，h ， g ， m， p ， a ， n ， q ，x， z22. 下列關于數據結構的敘述中，正確的是 ( A ).A. 數組是同類型值的集合B. 遞歸算法的程序結構比迭代算法的程序結構更為精煉C. 樹是一種線性結構D. 用一維數組存儲二叉樹，總是以先序遍歷的順序存儲各結點二、填空題1. 數據的邏輯結構被分為 、 、和四種。2. 數據的物理結構被分為 順序、_鏈表、索引和散列 四種。3. 一個算法的時間復雜度為 (3 n +2nlog 2 n +4n-7)/(5 n)

20、，其數量級表示為。4. 對于一個長度為 n 的單鏈存儲的線性表，在表頭插入元素的時間復雜度為 ，在表尾插入元素的時間復雜度為 。5. 對于一個長度為 n 的順序存儲的線性表，在表頭插入元素的時間復雜度為 ，在表尾插入元素的時間復雜度為 。6. 在以 HL 為表頭指針的帶表頭附加結點的單鏈表和循環單鏈 表中，鏈表為空的條件分別為 和 。7. 一個廣義表中的元素分為 單元素和 表元素兩類。8. 從一個鏈棧中刪除一個結點時，需要把棧頂結點的_指針 域的值賦給 _棧頂指針 。9. 進行函數調用時，需要把每個實參的值和調用后的_返回地址傳送給被調用的函數中。10. 設W為一個二維數組，其每個數據元素占用

21、 6個字節，行下標i從0到8，列下標j從0到3 ,則二維數組 W的數據元素共占用個字節。 W中第6行的元素和第4列的元素共占用個字節。若按行順序存放二維數組W其起始地址為100,則二維數組W勺最后一個數據元素的起始地址為。11. 在線性表的單鏈存儲中，若一個元素所在的結點地址為 p,則其后繼結點的地址為 若假定p為一個數組a中的下標，則其后繼結點的下標為 。12. 在稀疏矩陣所對應的三元組線性表中，每個三元組元素按 行號為主序、 列號為輔序的次序排列。13. 棧又稱為 表，隊列又稱為 表。14. 中綴算式（ 3+4）*2/ （8-5）所對應的后綴算式為15. 后綴算式 4 2 3 * + 10

22、 5 / - 的值為。16. 對于一棵具有n個結點的二叉樹，一個結點的編號為i（1 i n），若它有左孩子則左孩子結點的編號為 ，若它有右孩子，則右孩子結點的編號為 ，若它有雙親，則雙親結點的編號為 _i/2_ 。17. 在一棵高度為 5 的理想平衡樹中，最少含有 16個結點，最多含有個結點。18. 假定一棵樹的廣義表表示為 A（B（C， D（E， F， G）， H（I ， J），則樹中所含的結點數為 個，樹的深度為 ，樹的度為 。19. 若一棵二叉樹中只有葉子結點和左、右子樹皆非空的結點，設葉結點的個數為K,則左、右子樹皆非空的結點個數是 。20. 在樹中，一個結點的直接后繼結點的個數稱為該

23、結點的 。21. 在 n 個帶權葉子結點構造出的所有二叉樹中，帶權路徑長度最小的二叉樹稱為霍夫曼樹。WPL稱為帶權路徑長度。22. 對一棵二叉搜索樹進行中序遍歷時，得到的結點序列是一個_有序序列 。23. 當向一個小根堆插入一個具有最小值的元素時，需要逐層 向上調整，直到被調整到 根位置為止。24. 在一個堆的順序存儲中，若一個元素的下標為 i（0 i Wn-1），貝U它的左孩子元素的下標為 ，右孩子元素的下標為 。25. 在一個具有 n 個頂點的無向完全圖中，包含有 條邊，在一個具有 n 個頂點的有向完全圖中，包含有 條邊。26. 對于一個具有 n 個頂點和 e 條邊的有向圖和無向圖，若采用

24、邊集數組表示，則存于數組中的邊數分別為 和條。27. 以二分查找方法從長度為12的有序表中查找一個元素時，平均查找長度為。28. 假定一個線性表為(12,23,74,55,63,40,82,36) ，若按Key % 3條件進行劃分，使得同一余數的元素成為一個子表，則得到的三個子表分別為 、和。29. 在線性表的散列存儲中，裝填因子 a又稱為裝填系數，若用m表示散列表的長度，n表示待散列存儲的元素的個數，則a等于。30. 在一棵m階BJ樹上，每個非樹根結點的關鍵字數目最少為 個,最多為 ，其子樹數目最少為 最多為。31. 表示圖的三種常用的存儲結構為 、和。32. 對于一個具有n個頂點和e條邊的

25、有向圖和無向圖，在其對應的鄰接表中，所含邊結點分別有和。33. 對用鄰接矩陣表示的有向圖進行任一種遍歷時，其時間復雜度為 。對用鄰接表表示的有向圖進行任一種遍歷時，其時間復雜度為。34. 對于線性表(70，34，55, 23, 65，41, 20，100)進行散列存儲時，若選用H( K)=K %9作為散列函數，貝U散列地址為1的元素有 ，散列地址為7的有 。35. 在索引表中，若一個索引項對應主表的一個記錄，則此索引為 引，若對應主表的若干條記錄，則稱此索引為 引。36. 向一棵BJ樹插入元素的過程中，若最終引起樹根結點的分裂，則新樹比原樹的高度。37. 在堆排序的過程中，對任一分支結點進行篩

26、運算的時間復雜度為，整個堆排序過程的時間復雜度為 。38. 快速排序在平均情況下的時間復雜度為 在最壞情況下的時間復雜度為。39. 在歸并排序中，進行每趟歸并的時間復雜度為 ，整個排序過程的時間復雜度為 ，空間復雜度為 。40. 在快速排序、堆排序、歸并排序中， 卡序是穩定的。三、運算題1. 在如下數組A中鏈接存儲了一個線性表，表頭指針為A 0.next ，試寫出該線性表。a 01234567data605078903440n ext43025712. 假定一棵二叉樹廣義表表示為a(b(c),d(e,f)，分別寫出對它進行先 序、中序、后序、按層遍歷的結果。先序：中序：后序：按層：3. 已知一

27、棵二叉樹的先序遍歷的結果是 ABECDFGHIJ,中序遍歷的結果是 EBCDAFHIG J試畫出這棵二叉樹。4. 鐵路進行列車調度時 , 常把站臺設計成棧式結構的站臺，如下圖 1 所示 試問：(1) 設有編號為 1,2,3,4 的四輛列車 , 順序開入棧式結構的站臺 , 則可能的出棧序列有多少種 ?(2) 若進站的四輛列車順序如上所述 , 那么是否能夠得到4123這樣的出棧序列？ 如果不能 , 說明為什么不能。如果能 , 說明如何得到 該序列的(即寫出“進棧”或“出棧”的序列)。(3) 若進站的四輛列車順序如上所述 , 那么是否能夠得到 3421這樣的出棧序列？ 如果不能 , 說明為什么不能。

28、如果能 , 說明如何得到 該序列的(即寫出“進棧”或“出棧”的序列)。圖15. 寫出下列中綴表達式的后綴形式：(1) A * B * C(2) A + B - C + D(3) A* B + C(4) (A + B) * D + E / (F + A * D) + C6. 畫出下列廣義表的帶有附加表頭結點的鏈接存儲結構圖，并給出它們的 長度和深度。(1) D= (a,b),(c,d )(2) A= (a, (b,c ), ( d) ,e )7. 將一組元素 37,56,23,65,22,10,29 依次插入一棵空二叉搜索樹中，請 畫出該二叉搜索樹。8. 設有序順序表中的元素依次為 017, 0

29、94, 154, 170, 275,503, 509,512, 553, 612, 677, 765, 897, 908 。試畫出對其進行折半搜索時的判定樹 , 并計算搜索成功的平均搜索長度和搜索不成功的平均搜索長度。9. 已知一個圖的頂點集 V 和邊集 E 分別為：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;(1) 按照普里姆算法從頂點 0 出發得到最小生成樹，試寫出在最小生成樹中依 次得到的各條邊。(2) 用克魯斯卡爾算法得到最小生成樹，試寫出在最

30、小生成樹中依次得到的各 條邊。10. 已知一個圖的頂點集V和邊集E分別為：V=1,2,3,4,5,6,7， 8;E=(1,2),(1,3),(2,4),(2,5),(3,6),(3,7),(4,8),(5,8),(6,8),(7,8); 若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結點都是按照終點序號從小 到大的次序鏈接的，則：( 1 )給出從 1 號頂點出發按主教材中介紹的按深度優先搜索遍歷的頂點序列(2) 給出從 1 號頂點出發按主教材中介紹的按廣度優先搜索遍歷的頂點序列 (提示：先畫出對應的圖形，然后再運算)。11. 已知一個圖的頂點集V和邊集E分別為：V=0,1,2,3,4,5,6,7

31、;E=(0,2),(1,3),(1,4),(2,4),(2,5),(3,6),(3,7),(4,7),(4,8), (5,7),(6,7),(7,8);若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結點都是按照終點序號從小 到大的次序鏈接的，按主教材中介紹的拓樸排序算法進行排序，試給出得到的 拓樸排序的序列。(提示：先畫出對應的圖形，然后再運算)。12. 散列表的地址區間為0-16，散列函數為H( K) =K % 17,采用線性探查法處 理沖突，并已將關鍵字序列26、25、72、38、& 18、59依次存儲到了散列表 中：(1) 元素59存放在散列表中的地址是多少？(2) 搜索元素59需要比較的

32、次數是多少？13. 已知待散列的線性表為(36，15, 40，63, 22)，散列用的一維地址空間為 0.6，假定選用的散列函數是H( K)=K % 7,若發生沖突采用線性探查法處 理，試：(1) 計算出每一個元素的散列地址并在下圖中填寫出散列表；(2) 求出在查找每一個元素概率相等情況下的平均查找長度。012345614. 假定一組記錄的排序碼為(46,79,56,38,40,80,25,34)，試寫出對其進行快 速排序的第一次劃分的結果。四、閱讀算法，回答問題1. void AE(Stack& S)Ini tStack(S);Push(S,30);Push(S,40);Push(S,50)

33、;int x=Pop(S)+2*Pop(S);Push(S,x);int i,a4=5,8,12,15;for(i=0;i4;i+) Push(S,ai); while(!StackEmpty(S) coutPop(S)adjvex;if(!visitedj) coutjnext;該算法的功能為：3. 指出下列算法的功能，并求出時間復雜度：( 1) int sum1(int n)int p=1,s=0;for (int i=1;i=n;i+)p*=i;s+=p;return s;( 2) int sum2(int n)int s=0;for (int i=1;i=n;i+)int p=1;fo

34、r (int j=1;j=i;j+)p*=j;s+=p;return s;4. 在下面的每個程序段中，假定線性表 La 的類型為 List ，元素類型 ElemType為int，并假定每個程序段是連續執行的。試寫出每個程序段執行后 所得到的線性表 La。(1) InitList(La);Int a=48,26,57,34,62,79;For (i=0;i6;i+)Insert(La,ai);TraverseList(La);(2) Insert(La,56);DeleteFront(La);InsertRear(La, DeleteFront(La);TraverseList(La);( 3)

35、 For (i=1;i=3;i+)Int x=GetElem(La,i);If (x%2=0) Delete(La,x);TraverseList(La);( 4) ClearList(La);For (i=0;i6;i+)InsertRear(La,ai);Delete(La,a5);Sort(La);Insert(La,a5/2);TraverseList(La);五、算法填空，在畫有橫線的地方填寫合適的內容。1. 向單鏈表的末尾添加一個元素的算法。 Void InsertRear(LNode*& HL,const ElemType& item) LNode* newptr; newptr

36、=new LNode;If ()cerrMemory allocation failare!data=item;=NULL;if (HL=NULL)HL=newptr;elseLNode* P=HL;While (P-next!=NULL) p-next=newptr;2. 向以 BST 為樹根指針的二叉搜索樹上插入值為 item 的結點的遞歸算法 void Insert(BTreeNode*& BST, const ElemType& item) if(BST=NULL) BTreeNode* p=new BTreeNode; p-data=item;BST=p;else if(itemda

37、ta) ;else ;3. 二分查找的遞歸算法。Int Binsch(ElemType A,int low,int high,KeyType K)if (low=high)int mid=(low+high)/2;if ()return mid; / 查找成功，返回元素的 下標else if (K=n) 。請編寫一個函數將這 個線性表原地逆置，即將數組的前 n 個原址內容置換為 ( en-1, en-2, ,e1,e0) 。void inverse ( ElemType A , int n )3. 試編寫一個算法，在帶表頭結點的單鏈表中尋找第 i 個結點。若找到，則函數返回第 i 個結點的地址

38、；若找不到，則函數返回NULL。LNode* GetANode (LNode* & HL， int i )參考答案一、單選題1. B 2.B 3.D 4.C 5.A 6.B 7.D 8.B 9.A 10.A 11.C 12.D13. D 14.A 15.C 16.B 17.A 18.C 19.B 20.A 21.C 22.A二、填空題1. 集合結構 線性結構 樹結構 圖結構 2.順序 鏈表 索引 散列3. O(n) 4. O(1) O(n)HL-next=NULL HL-next=HL 指針（或 next ） 棧頂指針（或 HS） 310 矩陣元素的）9.返回地址 10. 36*6( 或 21

39、6) 12*6（或 72）11.p-next ap.next 12.(矩陣元素的)行號列號13.先進后出表（或后進先出表） 先進先出表14.5 - /15.8 16.2i 2i+1 ?i/2? (或 i/2 )17.16 3118. 10 4 319.k-1 20.度21.哈夫曼樹木帶權路徑長度 22.有（或升）序序列23.向上 根24. 2i+1 2i+225.n(n-1)/2n(n-1) 26. e e27.37/12 28.(12,63,36) (55,40,82)(23,74)29.n/m 30.em/2u-1m-1em/2um31.鄰接矩陣鄰接表 邊集數組 32. e2e33.O(n

40、2) O(e) 34. 2 235.稠密 稀疏 36. 增加 137.O(log 2n)2O(nlog 2n) 38.O(nlog 2n) O(n 2)39.O(n) O(nlog 2n) O(n) 40.歸并5.7.O(n) O(1) 6. 單 表 8.3 4 + 2 * 8三、運算題1. 【解答】 （90,34,40,60,78,50）2. 先序： a,b,c,d,e,f中序： c,b,a,e,d,f后序： c,b,e,f,d,a按層： a,b,d,c,e,f3. 【解答】當前序序列為ABECDFGH,中序序列為EBCDAFHIG時，逐步形成二叉樹的過 程如下圖 2 所示：EBCDFHIG

41、JAABEFCDHIGJABEFCDGJHIABEFCDGJhI圖24. 【解答】( 1)不同的出棧序列有 14 種。(2)不能得到 4123這樣的出棧序列。因為若在 4 之后再將 1, 2 ，3 出棧，則必有 1, 2 ，3 在 4 前入棧，即 1 先進棧， 2 后進棧， 3 再進棧，此時 3 壓 在 2 上， 2 壓在 1 上。最后 4 進棧。 4 首先出棧，由于 1 壓在最下面，由棧的特 性知此時 1 不可能先于 2 和 3 出棧，所以 4123 種出棧序列不可能出現。(3) 能得到 3421 這樣的出棧序列。即 1 入棧，2 入棧，3 入棧，然后 3 出棧， 再 4 入棧，接著 4 出

42、棧， 2 出棧， 1 出棧。5. 【解答】(1) A B * C *(2) AB + C - D +(3) AB * C +(4) A B + D * E F A D * + / + C +6. 【解答】 (1) D 的長度為 2，深度為 2，其鏈接存儲結構見下圖 3(a)D(2) A 的長度為 1，深度為 4，其鏈接存儲結構見下圖 3(b9. (1)普里姆： (0,3)2, (0,2)5, (0,1)8, (1,5)6, (3,6)10, (6,4)4,(5,7)20(2)克魯斯卡爾： (0,3)2, (4,6 ) 4,(0,2)5,(1,5)6,(0,1)8,(3,6)10,(5,7)20

43、10. (1)DFS：1，2，4，8，5，6，3，7(2)BFS：1，2，3，4，5，6，7，811. 拓撲序列： 1,3,6,0,2,5,4,7,812. (1)11(2)413. (1) H(36)=36 % 7=1H(15)=15 % 7=1 沖突H1(15)=(15+1) % 7=2H (40) =40 % 7=5H (63) =63 %7=0H (22) =22 % 7=1 沖突 H (22) = (22+1) % 7=2 沖突 H2 (22)=(22+2) %7=301234566336152240(2)平均查找長度=(1+2+1+1+3)/5=1.614. 40 34 25 38

44、 46 80 56 79四、閱讀算法，回答冋題1. 輸出結果為：15 12 8 5 130 302. 功能為：從初始點Vi出發廣度優先搜索由鄰接表 GL所表示的圖。3. (1)功能為：s=1!+2!+,n!時間復雜度0(n)(2)功能同(1)，時間復雜度O(n2)4. (1)(26,34,48,57,62,79)(2) (48,56,57,62,79,34)(3) (57,62,79,34)(4) (26,34,39,48,57,62)五、算法填空，在畫有橫線的地方填寫合適的內容。1. n wptr=NULLn ewptr-p=p-n ext;2. p-left=p-right=NULLIn

45、sert(BST-left, item)In sert(BST-right, item)3. K=Amid.keyBinsch(A,mid+1,hight,K)return -1六、編寫算法1. void In sert1(List& L, int i, ElemType x)for(i nt j=L.size-1; j=i-1; j-)L.listj+1=L.listj;L.listi-1=x;/第i個元素的下標為i-1L.size+;2. void in verse ( ElemType A , i nt n )ElemType tmp;for ( int i = 0; i = ( n-1

46、 ) / 2; i+ ) tmp = Ai; Ai = A n-i-1;A n-i-1 = tmp;3. LNode* GetANode (LNode* & HL , int i )/取得帶有頭對點的單鏈表中第i個結點地址(i從1開始計數)。若i 表長時，返回的指針值為 NULLif ( i next; int k = 1;while ( p != NULL & k next;k+; return p; 數據結構試卷(三)(A) q=p-next ；p-data=q-data(B) q=p-next ；q-data=p-datap-next=q-next ；free(q) ； p-next=q

47、-next ；free(q) ；一、選擇題 ( 每題 1分，共 20 分)1設某數據結構的二元組形式表示為A=(D，R)，D=01 ，02，03，04，05，06，07，08，09，R=r ，r=， , , , ，則數據結構 A是()。(A) 線性結構 (B) 樹型結構(C) 物理結構(D) 圖型結構2下面程序的時間復雜為()for (i=1 , s=0； i=n ； i+ )t=1 ；for(j=1；jnext ；p-next=q-next ；free(q) ；(D) q=p-next ；p-data=q-data ；free(q) ；4設有 n 個待排序的記錄關鍵字,則在堆排序中需要()個

48、輔助記錄單元。2(A) 1(B) n(C) nlog 2n(D) n 25設一組初始關鍵字記錄關鍵字為 (20, 15, 14, 18, 21, 36, 40, 10),則以20 為基準記錄的一趟快速排序結束后的結果為 ( ) 。(A) 10 , 15, 14, 18, 20, 36, 40, 21(B) 10, 15, 14, 18, 20, 40,36, 21(C) 10 , 15, 14, 20, 18, 40, 36, 2l (D) 15, 10, 14, 18, 20, 36,40, 216設二叉排序樹中有 n 個結點,則在二叉排序樹的平均平均查找長度為( ) (A) O(1)(B)

49、 O(log 2n) (C)(D) O(n 2)7設無向圖G中有n個頂點e條邊，則其對應的鄰接表中的表頭結點和表結點 的個數分別為( )。(A) n, e(B) e , n (C) 2n , e (D) n , 2e8.設某強連通圖中有n個頂點，則該強連通圖中至少有()條邊。(A) n(n-1)(B) n+1(C) n(D) n(n+1)9設有 5000 個待排序的記錄關鍵字,如果需要用最快的方法選出其中最小的 10個記錄關鍵字,則用下列( )方法可以達到此目的。(A)快速排序(B)堆排序 (C)歸并排序(D)插入排序10. 下列四種排序中( )的空間復雜度最大。(A) 插入排序 (B) 冒泡

50、排序 (C) 堆排序 (D) 歸并排序二、填空殖 ( 每空 1分 共 20 分)1. 數據的物理結構主要包括 和兩種情況。2. 設一棵完全二叉樹中有 500 個結點，則該二叉樹的深度為 ；若用二叉鏈表作為該完全二叉樹的存儲結構，則共有 個空指針域。3. 設輸入序列為 1、2、3，則經過棧的作用后可以得到 種不同的輸出序列。4. 設有向圖G用鄰接矩陣Ann作為存儲結構，則該鄰接矩陣中第i行上所 有元素之和等于頂點 i 的，第 i 列上所有元素之和等于頂點 i 的5. 設哈夫曼樹中共有 n 個結點，則該哈夫曼樹中有 個度數為 1 的結點。6. 設有向圖G中有n個頂點e條有向邊，所有的頂點入度數之和為d，則e和d的關系為。7. 遍歷二叉排序樹中的結點可以得到一個遞增的關鍵字序列(填先序、中序或后序) 。8. 設查找表中有100個元素，如果用二分法查找方法查找數據元素X,則最多需要比較 就可以斷定數據元素 X是否在查找表中。9. 不論是順序存儲結構的棧還是鏈式存儲結構的棧，其入棧和