數據結構復習題1

1、數據結構復習題1 一、選擇題(30分)1設某數據結構的二元組形式表示為A=(D，R)，D=01，02，03，04，05，06，07，08，09，R=r，r=<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>，則數據結構A是（ B）。(A) 線性結構(B) 樹型結構(C) 物理結構(D) 圖型結構2下面程序的時間復雜為（ B ）for（i=1，s=0； i<=n； i+） t=1；for(j=1；j<=i

2、；j+) t=t*j；s=s+t；(A) O(n)(B) O(n2)(C) O(n3)(D) O(n4)3設指針變量p指向單鏈表中結點A，若刪除單鏈表中結點A，則需要修改指針的操作序列為（ A ）。(A) q=p->next；p->data=q->data；p->next=q->next；free(q)；(B) q=p->next；q->data=p->data；p->next=q->next；free(q)；(C) q=p->next；p->next=q->next；free(q)；(D) q=p->next

3、；p->data=q->data；free(q)；4設有n個待排序的記錄關鍵字，則在堆排序中需要（ A ）個輔助記錄單元。(A) 1(B) n(C) nlog2n(D) n25設一組初始關鍵字記錄關鍵字為(20，15，14，18，21，36，40，10)，則以20為基準記錄的一趟快速排序結束后的結果為( A)。(A) 10，15，14，18，20，36，40，21(B) 10，15，14，18，20，40，36，21(C) 10，15，14，20，18，40，36，2l(D) 15，10，14，18，20，36，40，216設二叉排序樹中有n個結點，則在二叉排序樹的平均平均查找長度

4、為（ B ）。(A) O(1)(B) O(log2n)(C)(D) O(n2)7設無向圖G中有n個頂點e條邊，則其對應的鄰接表中的表頭結點和表結點的個數分別為（D ）。(A) n，e(B) e，n(C) 2n，e(D) n，2e8. 設某強連通圖中有n個頂點，則該強連通圖中至少有（ C）條邊。(A) n(n-1)(B) n+1(C) n(D) n(n+1)9設有5000個待排序的記錄關鍵字，如果需要用最快的方法選出其中最小的10個記錄關鍵字，則用下列（ B ）方法可以達到此目的。(A) 快速排序(B) 堆排序(C) 歸并排序(D) 插入排序10.下列四種排序中（ D ）的空間復雜度最大。(A)

5、 插入排序(B) 冒泡排序(C) 堆排序(D) 歸并排序 二、填空殖(48分，其中最后兩小題各6分)1.         數據的物理結構主要包括_順序存儲結構_和_鏈式存儲結構_兩種情況。2.         設一棵完全二叉樹中有500個結點，則該二叉樹的深度為_9_；若用二叉鏈表作為該完全二叉樹的存儲結構，則共有_個空指針域。3.        

6、 設輸入序列為1、2、3，則經過棧的作用后可以得到_種不同的輸出序列。4.         設有向圖G用鄰接矩陣Ann作為存儲結構，則該鄰接矩陣中第i行上所有元素之和等于頂點i的_，第i列上所有元素之和等于頂點i的_。5.         設哈夫曼樹中共有n個結點，則該哈夫曼樹中有_0_個度數為1的結點。6.         設有向圖G中有n個頂點e條有向邊

7、，所有的頂點入度數之和為d，則e和d的關系為_。7.         _遍歷二叉排序樹中的結點可以得到一個遞增的關鍵字序列（填先序、中序或后序）。8.         設查找表中有100個元素，如果用二分法查找方法查找數據元素X，則最多需要比較_次就可以斷定數據元素X是否在查找表中。9.         不論是順序存儲結構的棧還是鏈式存儲結構的棧，其入棧和出

8、棧操作的時間復雜度均為_。10.     設有n個結點的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號，則第i個結點的雙親結點編號為_，右孩子結點的編號為_。11.     設一組初始記錄關鍵字為(72，73，71，23，94，16，5)，則以記錄關鍵字72為基準的一趟快速排序結果為_。12.     設有向圖G中有向邊的集合E=<1，2>，<2，3>，<1，4>，<4，2>，<4，3>，則該圖的一種拓撲序

9、列為_。13.     下列算法實現在順序散列表中查找值為x的關鍵字，請在下劃線處填上正確的語句。struct recordint key; int others;int hashsqsearch(struct record hashtable ,int k)int i,j; j=i=k % p;while (hashtablej.key!=k&&hashtablej.flag!=0)j=(_) %m; if (i=j) return(-1); if (_ ) return(j); else return(-1);14. 

10、60;   下列算法實現在二叉排序樹上查找關鍵值k，請在下劃線處填上正確的語句。typedef struct nodeint key; struct node *lchild; struct node *rchild;bitree;bitree *bstsearch(bitree *t, int k) if (t=0 ) return(0);else while (t!=0)if (t->key=k)_; else if (t->key>k) t=t->lchild; else_; 三、算法設計題(22分)1 設計在單鏈表中刪除值相同的多余

11、結點的算法。2   設計一個求結點x在二叉樹中的雙親結點算法。參考答案 一、選擇題1.B2.B3.A4.A5.A6.B7.D8.C9.B10.D第3小題分析：首先用指針變量q指向結點A的后繼結點B，然后將結點B的值復制到結點A中，最后刪除結點B。第9小題分析：9快速排序、歸并排序和插入排序必須等到整個排序結束后才能夠求出最小的10個數，而堆排序只需要在初始堆的基礎上再進行10次篩選即可，每次篩選的時間復雜度為O(log2n)。 二、填空題1. 1.        順序存儲結構、鏈式存儲結構2.

12、2.        9，5013. 3.        54. 4.        出度，入度5. 5.        06. 6.        e=d7. 7.       

13、中序8. 8.        79. 9.        O(1)10. 10.     i/2，2i+111. 11.     (5，16，71，23，72，94，73)12. 12.     (1，4，3，2)13. 13.     j+1，hashtablej.key=k14. 14.

14、0;    return(t)，t=t->rchild第8小題分析：二分查找的過程可以用一棵二叉樹來描述，該二叉樹稱為二叉判定樹。在有序表上進行二分查找時的查找長度不超過二叉判定樹的高度1+log2n。 三、算法設計題1. 1.        設計在單鏈表中刪除值相同的多余結點的算法。typedef int datatype;typedef struct node datatype data; struct node *next;lklist;void delredundant(

15、lklist *&head) lklist *p,*q,*s; for(p=head;p!=0;p=p->next) for(q=p->next,s=q;q!=0; ) if (q->data=p->data) s->next=q->next; free(q);q=s->next; else s=q,q=q->next; 2. 2.        設計一個求結點x在二叉樹中的雙親結點算法。typedef struct node datatype data; struct

16、 node *lchild,*rchild; bitree;bitree *q20; int r=0,f=0,flag=0;void preorder(bitree *bt, char x) if (bt!=0 && flag=0)if (bt->data=x) flag=1; return;else r=(r+1)% 20; qr=bt; preorder(bt->lchild,x); preorder(bt->rchild,x); void parent(bitree *bt,char x) int i; preorder(bt,x); for(i=f+1

17、; i<=r; i+) if (qi->lchild->data=x | qi->rchild->data) break; if (flag=0) printf("not found xn"); else if (i<=r) printf("%c",bt->data); else printf("not parent");數據結構復習題2 一、選擇題(30分)1設一維數組中有n個數組元素，則讀取第i個數組元素的平均時間復雜度為（ ）。(A) O(n)(B) O(nlog2n)(C)

18、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個表頭結點和m個表結點，則該圖中有（ ）條有向邊。(A) n(B) n-1(C) m(D) m-16設一組初始記錄關鍵字序列為(345，253，674，924，627)，則用基數排序需要進行

19、（ ）趟的分配和回收才能使得初始關鍵字序列變成有序序列。(A) 3(B) 4(C) 5(D) 87設用鏈表作為棧的存儲結構則退棧操作（ ）。(A) 必須判別棧是否為滿(B) 必須判別棧是否為空(C) 判別棧元素的類型(D) 對棧不作任何判別8下列四種排序中（ ）的空間復雜度最大。(A) 快速排序(B) 冒泡排序(C) 希爾排序(D) 堆9設某二叉樹中度數為0的結點數為N0，度數為1的結點數為Nl，度數為2的結點數為N2，則下列等式成立的是（ ）。(A) N0=N1+1(B) N0=Nl+N2(C) N0=N2+1(D) N0=2N1+l10.設有序順序表中有n個數據元素，則利用二分查找法查找數

20、據元素X的最多比較次數不超過（ ）。(A) log2n+1(B) log2n-1(C) log2n(D) log2(n+1) 二、填空題(42分)1 1    設有n個無序的記錄關鍵字，則直接插入排序的時間復雜度為_，快速排序的平均時間復雜度為_。2 2    設指針變量p指向雙向循環(huán)鏈表中的結點X，則刪除結點X需要執(zhí)行的語句序列為_（設結點中的兩個指針域分別為llink和rlink）。3 3    根據初始關鍵字序列(19，22，01，38，10)建立的二叉排序樹的高度為_。4 4 

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

22、#160; 設順序線性表中有n個數據元素，則第i個位置上插入一個數據元素需要移動表中_個數據元素；刪除第i個位置上的數據元素需要移動表中_個元素。9 9    設一組初始記錄關鍵字序列為(20，18，22，16，30，19)，則以20為中軸的一趟快速排序結果為_。10 10設一組初始記錄關鍵字序列為(20，18，22，16，30，19)，則根據這些初始關鍵字序列建成的初始堆為_。11 11設某無向圖G中有n個頂點，用鄰接矩陣A作為該圖的存儲結構，則頂點i和頂點j互為鄰接點的條件是_。12 12設無向圖對應的鄰接矩陣為A，則A中第i上非0元素的個數_第i列上非0元素

23、的個數（填等于，大于或小于）。13 13設前序遍歷某二叉樹的序列為ABCD，中序遍歷該二叉樹的序列為BADC，則后序遍歷該二叉樹的序列為_。14 14設散列函數H(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;i<

24、;m;i+)_;for(i=0;i<n;i+)s=(lklist *)malloc(sizeof(lklist); s->key=ai;k=ai % p; s->next=hashtablek;_; 三、算法設計題(28分)1. 設單鏈表中有僅三類字符的數據元素(大寫字母、數字和其它字符)，要求利用原單鏈表中結點空間設計出三個單鏈表的算法，使每個單鏈表只包含同類字符。2. 設計在鏈式存儲結構上交換二叉樹中所有結點左右子樹的算法。3. 在鏈式存儲結構上建立一棵二叉排序樹。參考答案 一、選擇題1C2D3D4B5C6A7B8A9C10A 二、填空題1.

25、 1.        O(n2)，O(nlog2n)2. 2.        p>llink->rlink=p->rlink; p->rlink->llink=p->rlink3. 3.        34. 4.        2k-15. 5.   

26、     n/26. 6.        50，517. 7.        m-1，(R-F+M)%M8. 8.        n+1-i，n-i9. 9.        (19，18，16，20，30，22)10. 10.     (1

27、6，18，19，20，32，22)11. 11.     Aij=112. 12.     等于13. 13.     BDCA14. 14.     hashtablei=0，hashtablek=s 三、算法設計題1. 1.       設單鏈表中有僅三類字符的數據元素(大寫字母、數字和其它字符)，要求利用原單鏈表中結點空間設計出三個單鏈表的算法，使每個單鏈表只包

28、含同類字符。typedef char datatype;typedef struct node datatype data; struct node *next;lklist;void split(lklist *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->data<=

29、'Z') p->next=ha; ha=p; else if (p->data>='0' && p->data<='9') p->next=hb; hb=p; else p->next=hc; hc=p; 2. 2.        設計在鏈式存儲結構上交換二叉樹中所有結點左右子樹的算法。typedef struct node int data; struct node *lchild,*rchild; bitree;vo

30、id 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. 3.       在鏈式存儲結構上建立一棵二叉排序樹。#define n 10typedef struct nodeint key; struct node *lchild,*rchild;bitree;void b