數據結構試題及答案免費-資料下載頁

　　

【正文】 ______、___________________、_______________________和__________________________。10. 10. 向一棵B_樹插入元素的過程中，若最終引起樹根結點的分裂，則新樹比原樹的高度___________。11. 11. 在堆排序的過程中，對任一分支結點進行篩運算的時間復雜度為________，整個堆排序過程的時間復雜度為________。12. 12. 在快速排序、堆排序、歸并排序中，_________排序是穩定的。三、 三、 運算題（每題 6 分，共24分）1. 1. 在如下數組A中鏈接存儲了一個線性表，表頭指針為A [0].next，試寫出該線性表。 A 0 1 2 3 4 5 6 7 data605078903440next35720412. 2. 圖10請畫出圖10的鄰接矩陣和鄰接表。3. 3. 已知一個圖的頂點集V和邊集E分別為： V={1,2,3,4,5,6,7}。 E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}。 用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。4. 4. 畫出向小根堆中加入數據4, 2, 5, 8, 3時，每加入一個數據后堆的變化。四、 四、 閱讀算法（每題7分，共14分）1. 1. LinkList mynote(LinkList L) {//L是不帶頭結點的單鏈表的頭指針 if(Lamp。amp。Lnext){ q=L；L=L－next；p=L； S1： while(p－next) p=p－next； S2： p－next=q；q－next=NULL； } return L； } 請回答下列問題： （1）說明語句S1的功能； （2）說明語句組S2的功能； （3）設鏈表表示的線性表為（a1,a2, …,an）,寫出算法執行后的返回值所表示的線性表。2. 2. void ABC(BTNode * BT){ if BT { ABC (BTleft)。 ABC (BTright)。 coutBTdata39。 39。 } } 該算法的功能是：五、 五、 算法填空（共8分）二叉搜索樹的查找——遞歸算法:bool Find(BTreeNode* BST,ElemTypeamp。 item){ if (BST==NULL) return false。 //查找失敗 else { if (item==BSTdata){ item=BSTdata。//查找成功 return ___________。} else if(itemBSTdata) return Find(______________,item)。 else return Find(_______________,item)。 }//if}六、 六、 編寫算法（共8分）統計出單鏈表HL中結點的值等于給定值X的結點數。 int CountX(LNode* HL,ElemType x)數據結構16參考答案一、 一、 單選題（每題2分，共20分） 二、 二、 填空題（每空1分，共26分）1. 1. 正確性 易讀性 強壯性 高效率2. 2. O(n)3. 3. 9 3 34. 4. 1 3 4 X * + 2 Y * 3 / 5. 5. 2n n1 n+16. 6. e 2e7. 7. 有向無回路8. 8. n(n1)/2 n(n1)9. 9. （12，40） （ ） （74） （23,55，63）10. 10. 增加111. 11. O(log2n) O(nlog2n)12. 12. 歸并三、 三、 運算題（每題6分，共24分）1. 1. 線性表為：（78，50，40，60，34，90）2. 2. 鄰接矩陣： 鄰接表如圖11所示：圖113. 3. 用克魯斯卡爾算法得到的最小生成樹為： (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)204. 4. 見圖124444422255285283452843圖12四、 四、 閱讀算法（每題7分，共14分）1. 1. （1）查詢鏈表的尾結點（2）將第一個結點鏈接到鏈表的尾部，作為新的尾結點 （3）返回的線性表為（a2,a3,…,an,a1） 2. 2. 遞歸地后序遍歷鏈式存儲的二叉樹。五、 五、 算法填空（每空2分，共8 分）true BSTleft BSTright 六、 六、 編寫算法（8分）int CountX(LNode* HL,ElemType x) { int i=0。 LNode* p=HL。//i為計數器 while(p!=NULL) { if (Pdata==x) i++。 p=pnext。 }//while, 出循環時i中的值即為x結點個數 return i。 }//CountX 數據結構（十七）一、 一、 單選題（每小題2分，共8分） 在一個長度為n的順序線性表中順序查找值為x的元素時，查找成功時的平均查找長度（即x與元素的平均比較次數，假定查找每個元素的概率都相等）為 ( )。A n B n/2 C (n+1)/2 D (n1)/2 在一個單鏈表中,若q所指結點是p所指結點的前驅結點,若在q與p之間插入一個s所指的結點,則執行( )。 A s→link=p→link。 p→link=s。 B p→link=s。 s→link=q。 C p→link=s→link。 s→link=p。 D q →link=s。 s→link =p。 棧的插入和刪除操作在（ ）進行。A 棧頂 B 棧底 C 任意位置 D 指定位置 由權值分別為11，8，6，2，5的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為（ ） A 24 B 71 C 48 D 53二、 二、 填空題（每空1分，共32分） 數據的邏輯結構被分為__________、 ___________ 、________和________四種。 一種抽象數據類型包括______________和_____________兩個部分。 在下面的數組a中鏈接存儲著一個線性表，表頭指針為a[o].next，則該線性表為_________________________________________________。 a 0 1 2 3 4 5 6 7 8 60 56 42 38 74 25 4 3 7 6 2 0 1datanext 在以HL為表頭指針的帶表頭附加結點的單鏈表和循環單鏈表中，判斷鏈表為空的條件分別為________________和____________________。 用具有n個元素的一維數組存儲一個循環隊列，則其隊首指針總是指向隊首元素的___________，該循環隊列的最大長度為__________。 當堆棧采用順序存儲結構時，棧頂元素的值可用———————表示；當堆棧采用鏈接存儲結構時，棧頂元素的值可用_______________表示。 一棵高度為5的二叉樹中最少含有_________個結點，最多含有________個結點；一棵高度為5的理想平衡樹中，最少含有_________個結點，最多含有_________個結點。 在圖的鄰接表中，每個結點被稱為____________，通常它包含三個域：一是_____________；二是___________；三是_____________。 在一個索引文件的索引表中，每個索引項包含對應記錄的_________和___________兩項數據。 假定一棵樹的廣義表表示為A（B（C，D（E，F，G），H（I，J））），則樹中所含的結點數為_________個，樹的深度為_________,樹的度為________, 結點H的雙親結點為________,孩子結點為_______________ 。1 1 在堆排序的過程中，對任一分支結點進行篩運算的時間復雜度為_________,整個堆排序過程的時間復雜度為________________。1 1 在對m階的B_樹插入元素的過程中，每向一個結點插入一個索引項（葉子結點中的索引項為關鍵字和空指針）后，若該結點的索引項數等于______個，則必須把它分裂為_______個結點。三、 三、 運算題（每小題6分，共24分） 已知一組記錄的排序碼為（46，79，56，38，40，80, 95，24），寫出對其進行快速排序的每一次劃分結果。 一個線性表為B=（12，23，45，57，20，03，78，31，15，36），設散列表為HT[0..12]，散列函數為H（key）= key % 13并用線性探查法解決沖突，請畫出散列表，并計算等概率情況下查找成功的平均查找長度。 已知一棵二叉樹的前序遍歷的結果序列是ABECKFGHIJ，中序遍歷的結果是EBCDAFHIGJ，試寫出這棵二叉樹的后序遍歷結果。 已知一個圖的頂點集V各邊集G如下：V = {0，1，2，3，4，5，6，7，8，9}；E = {（0，1），（0，4），（1，2），（1，7），（2，8），（3，4），（3 ，8），（5，6），（5，8），（5，9），（6，7），（7，8），（8，9）}當它用鄰接矩陣表示和鄰接表表示時，分別寫出從頂點V0出發按深度優先搜索遍歷得到的頂點序列和按廣度優先搜索遍歷等到的頂點序列。假定每個頂點鄰接表中的結點是按頂點序號從大到小的次序鏈接的。圖深度優先序列廣度優先序列鄰接矩陣表示時鄰接表表示時 四、 四、 閱讀算法，回答問題（每小題8分，共16分）假定從鍵盤上輸入一批整數，依次為：78 63 45 30 91 34 –1，請寫出輸出結果。 include include consst