【正文】 ) (B) O(log2n) (C) (D) O(n2)7．設無向圖G中有n個頂點e條邊，則其對應的鄰接表中的表頭結點和表結點的個數(shù)分別為（ ）。 (A) n(n1) (B) n+1 (C) n (D) n(n+1)9．設有5000個待排序的記錄關鍵字，如果需要用最快的方法選出其中最小的10個記錄關鍵字，則用下列（ ）方法可以達到此目的。 (A) 插入排序 (B) 冒泡排序 (C) 堆排序 (D) 歸并排序二、填空殖(每空1分 共20分)1. 數(shù)據(jù)的物理結構主要包括_____________和______________兩種情況。3. 設輸入序列為3，則經過棧的作用后可以得到___________種不同的輸出序列。5. 設哈夫曼樹中共有n個結點，則該哈夫曼樹中有________個度數(shù)為1的結點。7. __________遍歷二叉排序樹中的結點可以得到一個遞增的關鍵字序列（填先序、中序或后序）。9. 不論是順序存儲結構的棧還是鏈式存儲結構的棧，其入棧和出棧操作的時間復雜度均為____________。11. 設一組初始記錄關鍵字為(72，73，71，23，94，16，5)，則以記錄關鍵字72為基準的一趟快速排序結果為___________________________。13. 下列算法實現(xiàn)在順序散列表中查找值為x的關鍵字，請在下劃線處填上正確的語句。 int others。int hashsqsearch(struct record hashtable[ ],int k){int i,j。while (hashtable[j].key!=kamp。hashtable[j].flag!=0){j=(____) %m。} if (_______________________ ) return(j)。}14. 下列算法實現(xiàn)在二叉排序樹上查找關鍵值k，請在下劃線處填上正確的語句。 struct node *lchild。}bitree。else while (t!=0)if (tkey==k)_____________。 else_____________。2．已知待散列的線性表為（36，15，40，63，22），散列用的一維地址空間為[0..6]，假定選用的散列函數(shù)是H（K）= K mod 7，若發(fā)生沖突采用線性探查法處理，試：（1）計算出每一個元素的散列地址并在下圖中填寫出散列表： ` 0 1 2 3 4 5 6（2）求出在查找每一個元素概率相等情況下的平均查找長度。四、算法設計題(每題15分，共30分)1． 設計在單鏈表中刪除值相同的多余結點的算法。數(shù)據(jù)結構試卷（四）一、選擇題(每題1分共 20分)1．設一維數(shù)組中有n個數(shù)組元素，則讀取第i個數(shù)組元素的平均時間復雜度為（ ）。 (A) 2k1 (B) 2k (C) 2k1 (D) 2k13．設某無向圖中有n個頂點e條邊，則該無向圖中所有頂點的入度之和為（ ）。 (A) O(1) (B) O(n) (C) O(log2n) (D) O(n2)5．設某有向圖的鄰接表中有n個表頭結點和m個表結點，則該圖中有（ ）條有向邊。 (A) 3 (B) 4 (C) 5 (D) 87．設用鏈表作為棧的存儲結構則退棧操作（ ）。 (A) 快速排序 (B) 冒泡排序 (C) 希爾排序 (D) 堆9．設某二叉樹中度數(shù)為0的結點數(shù)為N0，度數(shù)為1的結點數(shù)為Nl，度數(shù)為2的結點數(shù)為N2，則下列等式成立的是（ ）。 (A) log2n+1 (B) log2n1 (C) log2n (D) log2(n+1)二、填空題(每空1分共 20分)1． 設有n個無序的記錄關鍵字，則直接插入排序的時間復雜度為________，快速排序的平均時間復雜度為_________。3． 根據(jù)初始關鍵字序列(19，22，01，38，10)建立的二叉排序樹的高度為____________。5． 設初始記錄關鍵字序列為(K1，K2，…，Kn)，則用篩選法思想建堆必須從第______個元素開始進行篩選。7． 設有一個順序循環(huán)隊列中有M個存儲單元，則該循環(huán)隊列中最多能夠存儲________個隊列元素；當前實際存儲________________個隊列元素（設頭指針F指向當前隊頭元素的前一個位置，尾指針指向當前隊尾元素的位置）。9． 設一組初始記錄關鍵字序列為(20，18，22，16，30，19)，則以20為中軸的一趟快速排序結果為______________________________。11． 設某無向圖G中有n個頂點，用鄰接矩陣A作為該圖的存儲結構，則頂點i和頂點j互為鄰接點的條件是______________________。13． 設前序遍歷某二叉樹的序列為ABCD，中序遍歷該二叉樹的序列為BADC，則后序遍歷該二叉樹的序列為_____________。要求在下列算法劃線處填上正確的語句完成在散列表hashtalbe中查找關鍵字值等于k的結點，成功時返回指向關鍵字的指針，不成功時返回標志0。 struct node *next。 void createlkhash(lklist *hashtable[ ]){int i,k。for(i=0。i++)_____________________。in。 skey=a[i]。 snext=hashtable[k]。}}三、計算題(每題10分，共30分)畫出廣義表LS=(( ) , (e) , (a , (b , c , d )))的頭尾鏈表存儲結構。四、算法設計題(每題10分，共30分)1． 設單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符)，要求利用原單鏈表中結點空間設計出三個單鏈表的算法，使每個單鏈表只包含同類字符。3. 在鏈式存儲結構上建立一棵二叉排序樹。 (A) 數(shù)據(jù)項 (B) 數(shù)據(jù)類型 (C) 數(shù)據(jù)元素 (D) 數(shù)據(jù)變量2．設一組初始記錄關鍵字序列為(50，40，95，20，15，70，60，45)，則以增量d=4的一趟希爾排序結束后前4條記錄關鍵字為（ ）。(A) 15，25，35，50，20，40，80，85，36，70(B) 15，25，35，50，80，20，85，40，70，36(C) 15，25，35，50，80，85，20，36，40，70(D) 15，25，35，50，80，20，36，40，70，854．函數(shù)substr(“DATASTRUCTURE”，5，9)的返回值為（ ）。 (A) O(log2n) (B) O(1) (C) O(n2) (D) O(n)6．設一棵m叉樹中度數(shù)為0的結點數(shù)為N0，度數(shù)為1的結點數(shù)為Nl，……，度數(shù)為m的結點數(shù)為Nm，則N0=（ ）。 (A) 25 (B) 10 (C) 7 (D) 18．設連通圖G中的邊集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點序列為（ ）。 (A) ni (B) n1i (C) n+1i (D) 不能確定10 設一組初始記錄關鍵字序列為(45，80，55，40，42，85)，則以第一個記錄關鍵字45為基準而得到一趟快速排序的結果是（ ）。2. 在圖的鄰接表中用順序存儲結構存儲表頭結點的優(yōu)點是____________________。4. 棧的插入和刪除只能在棧的棧頂進行，后進棧的元素必定先出棧，所以又把棧稱為__________表；隊列的插入和刪除運算分別在隊列的兩端進行，先進隊列的元素必定先出隊列，所以又把隊列稱為_________表。6. 設一棵完全二叉樹有128個結點，則該完全二叉樹的深度為________，有__________個葉子結點。8. 設一組初始記錄關鍵字序列(k1，k2，……，kn)是堆，則對i=1，2，…，n/2而言滿足的條件為_______________________________。void bubble(int r[n]){for(i=1。 i++){for(exchange=0,j=0。j++) if (r[j]r[j+1]){temp=r[j+1]。r[j]=temp。}if (exchange==0) return；}}10. 下面程序段的功能是實現(xiàn)二分查找算法，請在下劃線處填上正確的語句。 int others。int bisearch(struct record r[ ], int k){ int low=0,mid,high=n1。 if(r[mid].key==k) return(mid+1)。else low=mid+1。}三、應用題(32分)1. 設某棵二叉樹的中序遍歷序列為DBEAC，前序遍歷序列為ABDEC，要求給出該二叉樹的的后序遍歷序列。3. 設一組初始記錄關鍵字序列為(15，17，18，22，35，51，60)，要求計算出成功查找時的平均查找長度。四、算法設計題(28分)1． 設計判斷兩個二叉樹是否相同的算法。數(shù)據(jù)結構試卷（一）參考答案一、 選擇題（每題2分，共20分） 二、填空題（每空1分，共26分）1. 正確性 易讀性 強壯性 高效率2. O(n)3. 9 3 34. 1 3 4 X * + 2 Y * 3 / 5. 2n n