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

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

2、一個(gè)新元素C. 順序輸出前 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 存儲，初始棧頂指針top 為 n+1 ，則以下元素 x 進(jìn)棧的正確操作是 _ 。A. top+;datatop=xB. datatop=x;top+;D.datatop=x;top -;C.top- ;datatop=x;front 和隊(duì)尾指針rear ，在隊(duì)不滿時(shí)進(jìn)隊(duì)操作僅會(huì)改6.若某循環(huán)隊(duì)列有隊(duì)首指針變 _ 。A.frontB.rearC.front

3、 和 rearD.以上都不隊(duì)7. 設(shè)循環(huán)隊(duì)列中數(shù)組的下標(biāo)是0? N-1 ，其隊(duì)頭、隊(duì)尾指針分別為f 和 r ( f 指向隊(duì)首元素的前一位置， r 指向隊(duì)尾元素 ) ，則其元素個(gè)數(shù)為 _ 。A.99B.100C.101D.199A.r-fB.r-f-1C.(r-f) % N+1D.(r-f+N) % N8.設(shè)樹 T 的度為 4, 其中度為1、 葉子 2、3、4 的結(jié)點(diǎn)個(gè)數(shù)分別為4、 2、 1、1，貝 U T 中結(jié)點(diǎn)個(gè)數(shù)是。的A.5B.6C.7D.89. 一棵哈夫曼樹中共有 199個(gè)結(jié)點(diǎn)，它用于多少個(gè)字符的編碼_10.設(shè)森林 F 中有 4 棵樹，第1、 2、3、 4 棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為a、 b、

4、c、 d，將森林F 轉(zhuǎn)換為一顆二叉樹B, 則二叉樹 B 根結(jié)點(diǎn)的左子樹上的結(jié)點(diǎn)個(gè)數(shù)是_ 。A.a-1B.aC. a+b+cD.b+c+d11. 下列關(guān)于圖的敘述中，正確的是_ 。I.回路是簡單路徑.存儲稀疏圖，用鄰接矩陣比鄰接表更省空間川.若有向圖中存在拓?fù)湫騨列，則該圖不存在回路A. 僅 nB.僅 i、 nC. 僅川D.僅 I、川12. 以下關(guān)于有向圖的說法中，正確的是_ 。A. 強(qiáng)連通圖是任何頂點(diǎn)到其他所有頂點(diǎn)都有邊B. 完全有向圖一定是強(qiáng)連通圖C. 有向圖中任一頂點(diǎn)的入度等于出度D. 有向圖邊集的子集和頂點(diǎn)集的子集可構(gòu)成原有向圖的子圖13. 無向圖的鄰接矩陣是一個(gè)_ 。A. 對稱矩陣B.

5、零矩陣C. 上三角矩陣D.對角矩陣14. 如果從無向圖的任一頂點(diǎn)出發(fā)進(jìn)行一次廣度優(yōu)先遍歷即可訪問所有頂點(diǎn)，則該圖 _. r 曰 疋是。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è)元素具有相同的序號B. 兩個(gè)元素的關(guān)鍵字不同，而其他屬性相同C. 數(shù)據(jù)元素過多D. 兩個(gè)元素的關(guān)鍵字不同，而對應(yīng)的哈希函數(shù)值( 存儲地址 ) 相同17. 適合于折半查

6、找的數(shù)據(jù)組織方式是_ 。A. 以鏈表存儲的線性表B.以順序表存儲的任意線性表C.以鏈表存儲的有序線性表D.以順序表存儲的有序線性表18. 對有 n 個(gè)記錄的表進(jìn)行直接插入排序，在最好情況下需比較_ 次關(guān)鍵字。A.n-1B.n+1C.n/2D.n(n -1)/219. 若數(shù)據(jù)元素序列 11,12,15,7,8,9,23,1,5 是采用下列排序方法之一得到的第二趟排序后的結(jié)果，則該排序算法只能是 _ 。A. 冒泡排序B.直接插入排序C.選擇排序D. 二路歸并排序20. 對一組數(shù)據(jù) (25,84,21,47,15,27,68,35,20) 進(jìn)行排序，前 3 趟的排序結(jié)果如下：第 1 趟： 20, 1

7、5, 21, 25, 47, 27, 68, 35, 84歡迎下載3第 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é)果（注意：按求解的順序給出最小生成樹的所有邊，每條邊用2. （ 10 分）假設(shè)一棵二叉排序樹的關(guān)鍵字為單個(gè)字母，其后序遍歷序列為ACDBFIJH

8、GE ，回答以下問題：（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)酱鎯Y(jié)構(gòu)？（3 分）（2） 設(shè)有一個(gè)小根堆，即堆中任意結(jié)點(diǎn)的關(guān)鍵字均小于它的左孩子和右孩子的關(guān)鍵字。其中具有最大關(guān)鍵字的結(jié)點(diǎn)可能在什么地方？（4分）三、算法設(shè)計(jì)題（共2 小題，共計(jì) 25 分）1.（

9、10 分）某帶頭結(jié)點(diǎn)的非空單鏈表L 中所有元素為整數(shù)，結(jié)點(diǎn)類型定義如下:typedef struct node int 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)值均不相同，采用二叉鏈存儲結(jié)構(gòu)存儲，其結(jié)點(diǎn)類型定義如下：typedef struct node char data;歡迎下載4struct node *lchild,*rchild; BTNode;請完成以下任務(wù)：（1） 設(shè)計(jì)一個(gè)算法，在二叉樹b 中查找

10、x 結(jié)點(diǎn)（指結(jié)點(diǎn)值為x 的結(jié)點(diǎn)），若找到該結(jié)點(diǎn)，返回其地址，否則返回NULL 。給出你設(shè)計(jì)的算法的時(shí)間復(fù)雜度。（8 分）（2） 設(shè)計(jì)一個(gè)算法，利用（1）小題設(shè)計(jì)的算法輸出二叉樹b 中 x 結(jié)點(diǎn)的所有子孫結(jié)點(diǎn)值。（ 7 分）歡迎下載5“數(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. D問答題（共 4 小題， 共計(jì) 35 分）1. （ 10 分）答案：利用普里姆算法從頂點(diǎn)0

11、出發(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 ，則中序遍歷序列為ABCDEFGHIJ ，由后序序列和中序序列構(gòu)造的二叉排序樹如圖2 所示。（ 6 分）(2)ASL 成功 =(1 X1+2X2+4 X 3+2 X 4+1 X 5)/10=3 。 ( 2分)(3)ASL 不成功 =(6 X3+3X4+2X5)/

12、11=40/11=3.64 。 ( 2分)歡迎下載63. （ 8 分）答案：采用二路歸并排序法排序的各趟結(jié)果如圖3 所示。（每趟2 分）歡迎下載7排序前 :15,5, 16,2, 25,8, 20,9, 18,12 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

13、各趟排序結(jié)果4.（ 7 分）答案：（1） 通常堆采用順序存儲結(jié)構(gòu)。（3 分）（2） 小根堆中具有最大關(guān)鍵字的結(jié)點(diǎn)只可能出現(xiàn)在葉子結(jié)點(diǎn)中。因?yàn)樽钚《训淖钚￡P(guā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 分）歡迎下載81. ( 10 分) 答案：void Move(LinkNode *&L) LinkNode *p=L->next,*pre=L; while (p!=NULL && p->data<0) pre=p;p=pre->next;while (p!=

14、NULL) if (p->data<0) pre->next=p->next;p->next=L->next;L->next=p;p=pre->next;else pre=p; p=p->next;2. ( 15 分) 答案：(1)(7 分)BTNode *Findx(BTNode *b,char x) BTNode *p;if (b=NULL)return NULL;/跳過小于 0 的結(jié)點(diǎn)/若*p 結(jié)點(diǎn)值小于 0/從鏈表中刪除 *p 結(jié)點(diǎn)/將*p 結(jié)點(diǎn)插入到頭結(jié)點(diǎn)之后p 指向 *pre 之后結(jié)點(diǎn)， pre 不變/若*p 結(jié)點(diǎn)值不小于0/pre 、p 同步后移一個(gè)結(jié)點(diǎn)/ /在二叉樹 b 中查找 x 結(jié)點(diǎn)歡迎下載9else if (b_>data=x) return b;p=Findx(b->lchild,x);if (p!=NULL)return p;return Findx(b->rchild,x);算法的時(shí)間復(fù)雜度為0( n) ( 1 分) 。(2)( 7 分)void Sons(BTNode *b,char x)/輸出 x