數(shù)據(jù)結(jié)構(gòu)考試題5

1、要求：所有的題目的解答均寫在答題紙上，需寫清楚題目的序號。每張答題紙都要寫 上姓名和學(xué)號。一、單項(xiàng)選擇題(每小題2分，共20小題，共計(jì)40分)1 .某算法的空間復(fù)雜度為0(1),則。A.該算法執(zhí)行不需要任何輔助空間B.該算法執(zhí)行所需輔助空間大小與問題規(guī)模n無關(guān)C.該算法執(zhí)行不需要任何空間D.該算法執(zhí)行所需全部空間大小與問題規(guī)模n無關(guān)2 .在長度為n的順序表中插入一個(gè)元素，對應(yīng)算法的時(shí)間復(fù)雜度為 。(1) (log 2n)(n)(n2)3 .設(shè)線性表中有n個(gè)元素，以下運(yùn)算中，在單鏈表上實(shí)現(xiàn)要比在順序表上實(shí)現(xiàn) 效率更高。A.刪除指定位置元素的后一個(gè)元素B.在最后一個(gè)元素的后面插入一個(gè)新元素C.順序

2、輸出前k個(gè)元素D.交換第i個(gè)元素和第n-i+1個(gè)元素的值(i=1, 2,，n)4 .以下數(shù)據(jù)結(jié)構(gòu)中元素之間為非線性關(guān)系的是 。A.棧B.隊(duì)列C.線性表D.以上都不是5 .若一個(gè)棧用數(shù)組data1. n存儲(chǔ)，初始棧頂指針top為n+1,則以下元素x進(jìn)棧的 正確操作是。+;datatop=x;top=x;top+;datatop=x;top=x;top-;6 .若某循環(huán)隊(duì)列有隊(duì)首指針front和隊(duì)尾指針rear ,在隊(duì)不滿時(shí)進(jìn)隊(duì)操作僅會(huì)改變。和rearD.以上都不隊(duì)7 .設(shè)循環(huán)隊(duì)列中數(shù)組的下標(biāo)是0M1 ,其隊(duì)頭、隊(duì)尾指針分別為f和r (f指向隊(duì)首元素的前一位置，r指向隊(duì)尾元素)，則其元素個(gè)數(shù)為 。

3、C.(r-f)%N+1D.( r-f+N)%N8 .設(shè)樹T的度為4,其中度為1、2、3、4的結(jié)點(diǎn)個(gè)數(shù)分別為 4、2、1、1,則T中的 葉子結(jié)點(diǎn)個(gè)數(shù)是。9 . 一棵哈夫曼樹中共有 199個(gè)結(jié)點(diǎn)，它用于多少個(gè)字符的編碼 。10 .設(shè)森林F中有4棵樹，第1、2、3、4棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為a、b、c、d,將森林F轉(zhuǎn)換為一顆二叉樹 B,則二叉樹B根結(jié)點(diǎn)的左子樹上的結(jié)點(diǎn)個(gè)數(shù)是 。C. a+b+c+c+d11 .下列關(guān)于圖的敘述中，正確的是 。I .回路是簡單路徑n.存儲(chǔ)稀疏圖，用鄰接矩陣比鄰接表更省空間出.若有向圖中存在拓?fù)湫蛄?，則該圖不存在回路A.僅nB.僅I、nC.僅出D.僅I、出12 .以下關(guān)于有向

4、圖的說法中，正確的是 。A.強(qiáng)連通圖是任何頂點(diǎn)到其他所有頂點(diǎn)都有邊B.完全有向圖一定是強(qiáng)連通圖C.有向圖中任一頂點(diǎn)的入度等于出度D.有向圖邊集的子集和頂點(diǎn)集的子集可構(gòu)成原有向圖的子圖13 .無向圖的鄰接矩陣是一個(gè)矩陣A.對稱矩陣B.零矩陣C.上三角矩陣D.對角14 .如果從無向圖的任一頂點(diǎn)出發(fā)進(jìn)行一次廣度優(yōu)先遍歷即可訪問所有頂點(diǎn)，則該圖A.完全圖B.連通圖C.有回路D. 一棵15.用 Dijkstra算法求一個(gè)帶權(quán)有向圖 G中從頂點(diǎn)0出發(fā)的最短路徑，在算法執(zhí)行的某時(shí)刻，S=0,2,3,4,下一步選取的目標(biāo)頂點(diǎn)可能是A.頂點(diǎn)2B.頂點(diǎn)3C.頂點(diǎn)4D.頂點(diǎn)716 .哈希表中出現(xiàn)沖突是指 。A.兩個(gè)

5、元素具有相同的序號17 兩個(gè)元素的關(guān)鍵字不同，而其他屬性相同C.數(shù)據(jù)元素過多D.兩個(gè)元素的關(guān)鍵字不同，而對應(yīng)的哈希函數(shù)值(存儲(chǔ)地址)相同18 .適合于折半查找的數(shù)據(jù)組織方式是 。A.以鏈表存儲(chǔ)的線性表B.以順序表存儲(chǔ)的任意線性表C.以鏈表存儲(chǔ)的有序線性表D.以順序表存儲(chǔ)的有序線性表19 .對有n個(gè)記錄的表進(jìn)行直接插入排序，在最好情況下需比較 次關(guān)鍵字。+12(m1)/2是采用下列排序方法之一得到的第二20 .若數(shù)據(jù)元素序列11,12,15,7,8,9,23,1,5趟排序后的結(jié)果，則該排序算法只能是A.冒泡排序B.直接插入排序C.選擇排序D.二路歸并排序進(jìn)行排序，前3趟的排序結(jié)果如下:20.對一

6、組數(shù)據(jù)(25,84,21,47,15,27,68,35,20)第 1 趟：20,15,21,25,47,27,68,35,84第 2 趟：15,20,21,25,35,27,47,68,84第 3 趟：15,20,21,25,27,35,47,68,84則所采用的排序方法是A.簡單選擇排序B.希爾排序C.二路歸并排序D.快速排序二、問答題（共4小題，共計(jì)35分）1. （10分）對于如圖1所示的帶權(quán)無向圖，直接給出利用普里姆算法（從頂點(diǎn)0開始構(gòu)造）和克魯斯卡爾算法構(gòu)造出的最小生成樹的結(jié)果（注意：按求解的順序給出最小生成樹的所有邊，每條邊用（i , j）表示）。圖1 一個(gè)帶權(quán)無向圖G2. （10分

7、）假設(shè)一棵二叉排序樹的關(guān)鍵字為單個(gè)字母，其后序遍歷序列為 ACDBFIJHGE回答以下問題：（1）畫出該二叉排序樹。（6分）（2）求在等概率下的查找成功的平均查找長度。（2分）（3）求在等概率下的查找不成功的平均查找長度。（2分）3. （8分）已知序列15,5,16,2,25,8,20,9,18,12,給出采用二路歸并排序法對該序列作升序排序時(shí)的每一趟的結(jié)果。4. （7分）簡要回答下列關(guān)于堆排序中堆的一些問題:（1）通常堆采用順序還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（3分）2 ） 設(shè)有一個(gè)小根堆， 即堆中任意結(jié)點(diǎn)的關(guān)鍵字均小于它的左孩子和右孩子的關(guān)鍵字。其中具有最大關(guān)鍵字的結(jié)點(diǎn)可能在什么地方（ 4 分）三、算法設(shè)

8、計(jì)題（共2 小題，共計(jì)25 分）1. （10 分）某帶頭結(jié)點(diǎn)的非空單鏈表L 中所有元素為整數(shù)，結(jié)點(diǎn)類型定義如下：typedef struct nodeint data;struct node *next; LinkNode;設(shè)計(jì)一個(gè)盡可能高效的算法， 將所有小于零的結(jié)點(diǎn)移到所有大于等于零的結(jié)點(diǎn)的前面。2. （ 15 分）假設(shè)二叉樹中有n 個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)值為單個(gè)字符，而且所有結(jié)點(diǎn)值均不相同，采用二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，其結(jié)點(diǎn)類型定義如下：typedef struct node char data;struct node *lchild,*rchild; BTNode;請完成以下任務(wù)：3. 1 ）設(shè)

9、計(jì)一個(gè)算法，在二叉樹b 中查找 x 結(jié)點(diǎn)（指結(jié)點(diǎn)值為 x 的結(jié)點(diǎn)），若找到該結(jié)點(diǎn)，返回其地址，否則返回NULL給出你設(shè)計(jì)的算法白時(shí)間復(fù)雜度。（8分）4. 2 ）設(shè)計(jì)一個(gè)算法，利用（1 ）小題設(shè)計(jì)的算法輸出二叉樹b 中 x 結(jié)點(diǎn)的所有子孫結(jié)點(diǎn)值。（ 7 分）“數(shù)據(jù)結(jié)構(gòu)”考試試題(A)參考答案單項(xiàng)選擇題(每小題2 分，共20 小題，共計(jì)40 分)1. B2.C3. A4. D5. C6. B7.D8. D9. B10. A11. C12. B13. A14. B15. D16. D17. D18. A19. B20. D4 小題，共計(jì)35 分)1. ( 10分) 答案：利用普里姆算法從頂點(diǎn) 0 出

10、發(fā)構(gòu)造的最小生成樹為： (0,1) ， (0,3) ， (1,2) ， (2,5) ，(5,4) , (5 分)。利用克魯斯卡爾算法構(gòu)造出的最小生成樹為：(0,1) , (0,3) , (1,2) , (5,4) , (2,5),(5 分)。說明：順序錯(cuò)誤不給分。2. (10分)答案:(1)該二叉排序樹的后序遍歷序列為ACDBFIJHGE貝U中序遍歷序歹U為 ABCDEFGHIJ2所示。(6分)圖2 一棵二叉排序樹由后序序列和中序序列構(gòu)造的二叉排序樹如圖(2) ASL成功=(1 X 1+2X 2+4X 3+ 2X 4+1X5)/10=3 。 (2 分)(3) ASL不成功=(6 X 3+3X4

11、+2X 5)/11=40/11= 。 (2 分)3. (8分)答案:采用二路歸并排序法排序的各趟結(jié)果如圖3所示。(每趟2分)排序前：155, 16，45,8, 20,9, 182_length=1:5, 15,2, 16,8, 25,9, 20,12,18 length=2:2, 5,15, 16,8, 9, 20,25,12,18 length=4:2, 5,8, 9, 15,16,20,25,12,18 length=8:2, 5,8, 9, 12,15,16,18,20,25 排序后:2, 5,8, 9, 12,15,16,18,20,25圖3各趟排序結(jié)果4. (7分)答案:1 ）通常堆

12、采用順序存儲(chǔ)結(jié)構(gòu)。 （ 3 分）因?yàn)樽钚《训淖钚￡P(guān)2 ） 小根堆中具有最大關(guān)鍵字的結(jié)點(diǎn)只可能出現(xiàn)在葉子結(jié)點(diǎn)中。鍵字的結(jié)點(diǎn)必是根結(jié)點(diǎn)，而最大關(guān)鍵字的結(jié)點(diǎn)由偏序關(guān)系可知，只有葉子結(jié)點(diǎn)可能是最大關(guān)鍵字的結(jié)點(diǎn)。 ( 4 分)三、算法設(shè)計(jì)題(共2 小題，共計(jì)25 分)1. ( 10分) 答案：void Move(LinkNode *&L) LinkNode *p=L->next,*pre=L;while (p!=NULL && p->data<0)( 15分) 答案：( 1 )( 7 分)BTNode *Findx(BTNode *b,char x) / 在二叉樹 b 中查找 x 結(jié)點(diǎn) BTNode *p;if (b=NULL)return NULL;else if (b->data=x)return b;p=Findx(b->lchild,x);if (p!=NULL)return p;return Findx(b->rchild,x);算法的時(shí)間復(fù)雜度為O(n) ( 1 分) 。( 2 )( 7 分)void Sons(BTNode *b,char x)/ 輸出 x 結(jié)點(diǎn)的子孫，初始時(shí)b 指向 x 結(jié)點(diǎn) if (