【正文】 t=t*j；s=s+t；} (A) O(n) (B) O(n2) (C) O(n3) (D) O(n4)3．設(shè)指針變量p指向單鏈表中結(jié)點A，若刪除單鏈表中結(jié)點A，則需要修改指針的操作序列為（ ）。 (A) 1 (B) n (C) nlog2n (D) n25．設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(20，15，14，18，21，36，40，10)，則以20為基準記錄的一趟快速排序結(jié)束后的結(jié)果為( )。 (A) O(1) (B) O(log2n) (C) (D) O(n2)7．設(shè)無向圖G中有n個頂點e條邊，則其對應(yīng)的鄰接表中的表頭結(jié)點和表結(jié)點的個數(shù)分別為（ ）。 (A) n(n1) (B) n+1 (C) n (D) n(n+1)9．設(shè)有5000個待排序的記錄關(guān)鍵字，如果需要用最快的方法選出其中最小的10個記錄關(guān)鍵字，則用下列（ ）方法可以達到此目的。 (A) 插入排序 (B) 冒泡排序 (C) 堆排序 (D) 歸并排序二、填空殖(每空1分 共20分)1. 數(shù)據(jù)的物理結(jié)構(gòu)主要包括_____________和______________兩種情況。3. 設(shè)輸入序列為3，則經(jīng)過棧的作用后可以得到___________種不同的輸出序列。5. 設(shè)哈夫曼樹中共有n個結(jié)點，則該哈夫曼樹中有________個度數(shù)為1的結(jié)點。7. __________遍歷二叉排序樹中的結(jié)點可以得到一個遞增的關(guān)鍵字序列（填先序、中序或后序）。9. 不論是順序存儲結(jié)構(gòu)的棧還是鏈式存儲結(jié)構(gòu)的棧，其入棧和出棧操作的時間復(fù)雜度均為____________。11. 設(shè)一組初始記錄關(guān)鍵字為(72，73，71，23，94，16，5)，則以記錄關(guān)鍵字72為基準的一趟快速排序結(jié)果為___________________________。13. 下列算法實現(xiàn)在順序散列表中查找值為x的關(guān)鍵字，請在下劃線處填上正確的語句。 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)在二叉排序樹上查找關(guā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）求出在查找每一個元素概率相等情況下的平均查找長度。四、算法設(shè)計題(每題15分，共30分)1． 設(shè)計在單鏈表中刪除值相同的多余結(jié)點的算法。數(shù)據(jù)結(jié)構(gòu)試卷（四）一、選擇題(每題1分共 20分)1．設(shè)一維數(shù)組中有n個數(shù)組元素，則讀取第i個數(shù)組元素的平均時間復(fù)雜度為（ ）。 (A) 2k1 (B) 2k (C) 2k1 (D) 2k13．設(shè)某無向圖中有n個頂點e條邊，則該無向圖中所有頂點的入度之和為（ ）。 (A) O(1) (B) O(n) (C) O(log2n) (D) O(n2)5．設(shè)某有向圖的鄰接表中有n個表頭結(jié)點和m個表結(jié)點，則該圖中有（ ）條有向邊。 (A) 3 (B) 4 (C) 5 (D) 87．設(shè)用鏈表作為棧的存儲結(jié)構(gòu)則退棧操作（ ）。 (A) 快速排序 (B) 冒泡排序 (C) 希爾排序 (D) 堆9．設(shè)某二叉樹中度數(shù)為0的結(jié)點數(shù)為N0，度數(shù)為1的結(jié)點數(shù)為Nl，度數(shù)為2的結(jié)點數(shù)為N2，則下列等式成立的是（ ）。 (A) log2n+1 (B) log2n1 (C) log2n (D) log2(n+1)二、填空題(每空1分共 20分)1． 設(shè)有n個無序的記錄關(guān)鍵字，則直接插入排序的時間復(fù)雜度為________，快速排序的平均時間復(fù)雜度為_________。3． 根據(jù)初始關(guān)鍵字序列(19，22，01，38，10)建立的二叉排序樹的高度為____________。5． 設(shè)初始記錄關(guān)鍵字序列為(K1，K2，…，Kn)，則用篩選法思想建堆必須從第______個元素開始進行篩選。7． 設(shè)有一個順序循環(huán)隊列中有M個存儲單元，則該循環(huán)隊列中最多能夠存儲________個隊列元素；當前實際存儲________________個隊列元素（設(shè)頭指針F指向當前隊頭元素的前一個位置，尾指針指向當前隊尾元素的位置）。9． 設(shè)一組初始記錄關(guān)鍵字序列為(20，18，22，16，30，19)，則以20為中軸的一趟快速排序結(jié)果為______________________________。11． 設(shè)某無向圖G中有n個頂點，用鄰接矩陣A作為該圖的存儲結(jié)構(gòu)，則頂點i和頂點j互為鄰接點的條件是______________________。13． 設(shè)前序遍歷某二叉樹的序列為ABCD，中序遍歷該二叉樹的序列為BADC，則后序遍歷該二叉樹的序列為_____________。要求在下列算法劃線處填上正確的語句完成在散列表hashtalbe中查找關(guān)鍵字值等于k的結(jié)點，成功時返回指向關(guān)鍵字的指針，不成功時返回標志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 )))的頭尾鏈表存儲結(jié)構(gòu)。四、算法設(shè)計題(每題10分，共30分)1． 設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符)，要求利用原單鏈表中結(jié)點空間設(shè)計出三個單鏈表的算法，使每個單鏈表只包含同類字符。3. 在鏈式存儲結(jié)構(gòu)上建立一棵二叉排序樹。 (A) 數(shù)據(jù)項 (B) 數(shù)據(jù)類型 (C) 數(shù)據(jù)元素 (D) 數(shù)據(jù)變量2．設(shè)一組初始記錄關(guān)鍵字序列為(50，40，95，20，15，70，60，45)，則以增量d=4的一趟希爾排序結(jié)束后前4條記錄關(guān)鍵字為（ ）。(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．設(shè)一棵m叉樹中度數(shù)為0的結(jié)點數(shù)為N0，度數(shù)為1的結(jié)點數(shù)為Nl，……，度數(shù)為m的結(jié)點數(shù)為Nm，則N0=（ ）。 (A) 25 (B) 10 (C) 7 (D) 18．設(shè)連通圖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 設(shè)一組初始記錄關(guān)鍵字序列為(45，80，55，40，42，85)，則以第一個記錄關(guān)鍵字45為基準而得到一趟快速排序的結(jié)果是（ ）。2. 在圖的鄰接表中用順序存儲結(jié)構(gòu)存儲表頭結(jié)點的優(yōu)點是____________________。4. 棧的插入和刪除只能在棧的棧頂進行，后進棧的元素必定先出棧，所以又把棧稱為__________表；隊列的插入和刪除運算分別在隊列的兩端進行，先進隊列的元素必定先出隊列，所以又把隊列稱為_________表。6. 設(shè)一棵完全二叉樹有128個結(jié)點，則該完全二叉樹的深度為________，有__________個葉子結(jié)點。8. 設(shè)一組初始記錄關(guān)鍵字序列(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。}三、應(yīng)用題(32分)1. 設(shè)某棵二叉樹的中序遍歷序列為DBEAC，前序遍歷序列為ABDEC，要求給出該二叉樹的的后序遍歷序列。3. 設(shè)一組初始記錄關(guān)鍵字序列為(15，17，18，22，35，51，60)，要求計算出成功查找時的平均查找長度。四、算法設(shè)計題(28分)1． 設(shè)計判斷兩個二叉樹是否相同的算法。數(shù)據(jù)結(jié)構(gòu)試卷（六）一、選擇題(30分)1． 設(shè)一組權(quán)值集合W={2，3，4，5，6}，則由該權(quán)值集合構(gòu)造的哈夫曼樹中帶權(quán)路徑長度之和為（ ）。 (A) [41，12，34，45，27] 55 [72，63] (B) [45，34，12，41] 55 [72，63，27] (C) [63，12，34，45，27] 55 [41，72] (D) [12，27，45，41] 55 [34，63，72]3．設(shè)一條單鏈表的頭指針變量為head且該鏈表沒有頭結(jié)點，則其判空條件是（ ）。 (A) 堆排序 (B) 冒泡排序 (C) 希爾排序 (D) 快速排序5．設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（ ）。 (A) 堆排序 (B) 冒泡排序 (C) 快速排序 (D) 希爾排序7．設(shè)某棵三叉樹中有40個結(jié)點，則該三叉樹的最小高度為（ ）。 (A) O(n) (B) O(n2) (C) O(n1/2) (D) O(1og2n)9．二路歸并排序的時間復(fù)雜度為（ ）。 (A) 2k11 (B) 2k1 (C) 2k1+1 (D) 2k1，指針變量rear表示鏈式隊列的隊尾指針，指針變量s指向?qū)⒁腙犃械慕Y(jié)點X，則入隊列的操作序列為（ ）。 (A) O(n+e) (B) O(n2) (C) O(ne) (D) O(n3)，則該哈夫曼樹中有（ ）個葉子結(jié)點。 (A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n)，則有向圖G中頂點i的入度為（ ）。（ ）2．分塊查找的平均查找長度不僅與索引表的長度有關(guān)，而且與塊的長度有關(guān)。（ ）4．滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。（ ）6．層次遍歷初始堆可以得到一個有序的序列。（ ）8．線性表的順序存儲結(jié)構(gòu)比鏈式存儲結(jié)構(gòu)更好。（ ）。2．設(shè)指針變量p指向單鏈表中結(jié)點A，指針變量s指向被插入的新結(jié)點X，則進行插入操作的語句序列為__________________________（設(shè)結(jié)點的指針域為next）。4．設(shè)無向圖G中有n個頂點，則該無向圖中每個頂點的度數(shù)最多是_________。6．設(shè)F和R分別表示順序循環(huán)隊列的頭指針和尾指針，則判斷該循環(huán)隊列為空的條件為_____________________。8．簡單選擇排序和直接插入排序算法的平均時間復(fù)雜度為___________。２． 設(shè)計判斷二叉樹是否為二叉排序樹的算法。 (A) 2n (B) n (C) n/2 (D) n(n1)2．設(shè)無向圖G中有n個頂點，則該無向圖的最小生成樹上有（ ）條邊。 (A) 40，42，60，55，80，85 (B) 42，45，55，60，85，80 (C) 42，40，55，60，80，85 (D) 42，40，60，85，55，804．（ ）二叉排序樹可以得到一個從小到大的有序序列。 (A) 2i+1 (B) 2i (C) i/2 (D) 2i16．程序段s=i=0；do {i=i+1； s=s+i；}while(i=n)；的時間復(fù)雜度為（ ）。 (A) head==0 (B) headnext==0 (C) headnext==head (D) head!=08．設(shè)某棵二叉樹的高度為10，則該二叉樹上葉子結(jié)點最多有（ ）。 (A) 1 (B) 2 (C) 3 (D) 4，則刪除棧頂元素的操作序列為（ ）。 (B) top=top1。 (D) top=topnext。（ ）2．當向二叉排序樹中插入一個結(jié)點，則該結(jié)點一定成為葉子結(jié)點。（ ）4．完全二叉樹中的葉子結(jié)點只可能在最后兩層中出現(xiàn)。（ ）6．對連通圖進行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點。（ ）8．由樹轉(zhuǎn)化成二叉樹，該二叉樹的右子樹不一定為空。（