《數(shù)據(jù)結構》模擬試題綜合測試題帶答案 (7)

1、數(shù)據(jù)結構模擬試題07一、單項選擇題（每題 3 分，共30分）1設一維數(shù)組中有n個數(shù)組元素，則讀取第i個數(shù)組元素的平均時間復雜度為（ ）。(A) O(n)(B) O(nlog2n)(C) O(1)(D) O(n2)2設一棵二叉樹的深度為k，則該二叉樹中最多有（ ）個結點。(A) 2k-1(B) 2k(C) 2k-1(D) 2k-13設某無向圖中有n個頂點e條邊，則該無向圖中所有頂點的入度之和為（ ）。(A) n(B) e(C) 2n(D) 2e4在二叉排序樹中插入一個結點的時間復雜度為（ ）。(A) O(1)(B) O(n)(C) O(log2n)(D) O(n2)5設某有向圖的鄰接表中有n個表

2、頭結點和m個表結點，則該圖中有（ ）條有向邊。(A) n(B) n-1(C) m(D) m-16設一組初始記錄關鍵字序列為(345，253，674，924，627)，則用基數(shù)排序需要進行（ ）趟的分配和回收才能使得初始關鍵字序列變成有序序列。(A) 3(B) 4(C) 5(D) 87設用鏈表作為棧的存儲結構則退棧操作（ ）。(A) 必須判別棧是否為滿(B) 必須判別棧是否為空(C) 判別棧元素的類型(D) 對棧不作任何判別8下列四種排序中（ ）的空間復雜度最大。(A) 快速排序(B) 冒泡排序(C) 希爾排序(D) 堆9設某二叉樹中度數(shù)為0的結點數(shù)為N0，度數(shù)為1的結點數(shù)為Nl，度數(shù)為2的結點

3、數(shù)為N2，則下列等式成立的是（ ）。(A) N0=N1+1(B) N0=Nl+N2(C) N0=N2+1(D) N0=2N1+l10.設有序順序表中有n個數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過（ ）。(A) log2n+1(B) log2n-1(C) log2n(D) log2(n+1)二、填空題（每題2分，共26分）1 設有n個無序的記錄關鍵字，則直接插入排序的時間復雜度為_，快速排序的平均時間復雜度為_。2 設指針變量p指向雙向循環(huán)鏈表中的結點X，則刪除結點X需要執(zhí)行的語句序列為_（設結點中的兩個指針域分別為llink和rlink）。3 根據(jù)初始關鍵字序列(19，22

4、，01，38，10)建立的二叉排序樹的高度為_。4 深度為k的完全二叉樹中最少有_個結點。5 設初始記錄關鍵字序列為(K1，K2，Kn)，則用篩選法思想建堆必須從第_個元素開始進行篩選。6 設哈夫曼樹中共有99個結點，則該樹中有_個葉子結點；若采用二叉鏈表作為存儲結構，則該樹中有_個空指針域。7 設有一個順序循環(huán)隊列中有M個存儲單元，則該循環(huán)隊列中最多能夠存儲_個隊列元素；當前實際存儲_個隊列元素（設頭指針F指向當前隊頭元素的前一個位置，尾指針指向當前隊尾元素的位置）。8 設順序線性表中有n個數(shù)據(jù)元素，則第i個位置上插入一個數(shù)據(jù)元素需要移動表中_個數(shù)據(jù)元素；刪除第i個位置上的數(shù)據(jù)元素需要移動表

5、中_個元素。9 設一組初始記錄關鍵字序列為(20，18，22，16，30，19)，則以20為中軸的一趟快速排序結果為_。10 設一組初始記錄關鍵字序列為(20，18，22，16，30，19)，則根據(jù)這些初始關鍵字序列建成的初始堆為_。11 設某無向圖G中有n個頂點，用鄰接矩陣A作為該圖的存儲結構，則頂點i和頂點j互為鄰接點的條件是_。12 設無向圖對應的鄰接矩陣為A，則A中第i上非0元素的個數(shù)_第i列上非0元素的個數(shù)（填等于，大于或小于）。13 設前序遍歷某二叉樹的序列為ABCD，中序遍歷該二叉樹的序列為BADC，則后序遍歷該二叉樹的序列為_。三、算法填空題（每題 8 分，共8分）設散列函數(shù)H

6、(k)=k mod p，解決沖突的方法為鏈地址法。要求在下列算法劃線處填上正確的語句完成在散列表hashtalbe中查找關鍵字值等于k的結點，成功時返回指向關鍵字的指針，不成功時返回標志0。typedef struct node int key; struct node *next; lklist; void createlkhash(lklist *hashtable )int i,k; lklist *s;for(i=0;im;i+)_;for(i=0;ikey=ai;k=ai % p; s-next=hashtablek;_;四、算法設計題（每題12分，共36分）1 設單鏈表中有僅三類字

7、符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符)，要求利用原單鏈表中結點空間設計出三個單鏈表的算法，使每個單鏈表只包含同類字符。2. 設計在鏈式存儲結構上交換二叉樹中所有結點左右子樹的算法。3. 在鏈式存儲結構上建立一棵二叉排序樹。5數(shù)據(jù)結構模擬試題07參考答案一、單項選擇題（每題 3 分，共30分）1C2D3D4B5C6A7B8A9C10A二、填空題（每小題2分，共26分）1. O(n2)，O(nlog2n)2. pllink-rlink=p-rlink; p-rlink-llink=p-rlink3. 34. 2k-15. n/26. 50，517. m-1，(R-F+M)%M8. n+1-i，n

8、-i9. (19，18，16，20，30，22)10. (16，18，19，20，32，22)11. Aij=112. 等于13. BDCA三、算法填空題（每題 8分，共8分）hashtablei=0，hashtablek=s四、算法設計題（每題12分，共36分）1. 設單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符)，要求利用原單鏈表中結點空間設計出三個單鏈表的算法，使每個單鏈表只包含同類字符。typedef char datatype;typedef struct node datatype data; struct node *next;lklist;void split(lk

9、list *head,lklist *&ha,lklist *&hb,lklist *&hc) lklist *p; ha=0,hb=0,hc=0; for(p=head;p!=0;p=head) head=p-next; p-next=0; if (p-data=A & p-datanext=ha; ha=p; else if (p-data=0 & p-datanext=hb; hb=p; else p-next=hc; hc=p; 2. 設計在鏈式存儲結構上交換二叉樹中所有結點左右子樹的算法。typedef struct node int data; struct node *lchil

10、d,*rchild; bitree;void swapbitree(bitree *bt) bitree *p; if(bt=0) return;swapbitree(bt-lchild); swapbitree(bt-rchild);p=bt-lchild; bt-lchild=bt-rchild; bt-rchild=p;3. 在鏈式存儲結構上建立一棵二叉排序樹。#define n 10typedef struct nodeint key; struct node *lchild,*rchild;bitree;void bstinsert(bitree *&bt,int key) if (bt=0)bt=(bitree *)malloc(sizeof(bitree); bt-key=key;bt-lchild=bt-rchil