第一篇:數(shù)據(jù)結(jié)構(gòu)試卷及參考答案_2
數(shù)據(jù)結(jié)構(gòu)試卷
(二)一、選擇題(24分)1.下面關(guān)于線性表的敘述錯誤的是()。
(A)線性表采用順序存儲必須占用一片連續(xù)的存儲空間
(B)線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲空間(C)線性表采用鏈?zhǔn)酱鎯Ρ阌诓迦牒蛣h除操作的實現(xiàn)(D)線性表采用順序存儲便于插入和刪除操作的實現(xiàn)
2.設(shè)哈夫曼樹中的葉子結(jié)點總數(shù)為m,若用二叉鏈表作為存儲結(jié)構(gòu),則該哈夫曼樹中總共有()個空指針域。
(A)2m-1(B)2m(C)2m+1(D)4m 3.設(shè)順序循環(huán)隊列Q[0:M-1]的頭指針和尾指針分別為F和R,頭指針F總是指向隊頭元素的前一位置,尾指針R總是指向隊尾元素的當(dāng)前位置,則該循環(huán)隊列中的元素個數(shù)為()。
(A)R-F(B)F-R(C)(R-F+M)%M(D)(F-R+M)%M 4.設(shè)某棵二叉樹的中序遍歷序列為ABCD,前序遍歷序列為CABD,則后序遍歷該二叉樹得到序列為()。
(A)BADC(B)BCDA(C)CDAB(D)CBDA 5.設(shè)某完全無向圖中有n個頂點,則該完全無向圖中有()條邊。
(A)n(n-1)/2(B)n(n-1)(C)n2(D)n2-1 6.設(shè)某棵二叉樹中有2000個結(jié)點,則該二叉樹的最小高度為()。
(A)9(B)10(C)11(D)12 7.設(shè)某有向圖中有n個頂點,則該有向圖對應(yīng)的鄰接表中有()個表頭結(jié)點。
(A)n-1(B)n(C)n+1(D)2n-1 8.設(shè)一組初始記錄關(guān)鍵字序列(5,2,6,3,8),以第一個記錄關(guān)鍵字5為基準(zhǔn)進行一趟快速排序的結(jié)果為()。
(A)2,3,5,8,6(B)3,2,5,8,6(C)3,2,5,6,8(D)2,3,6,5,8
二、填空題(24分)1.為了能有效地應(yīng)用HASH查找技術(shù),必須解決的兩個問題是____________________和__________________________。
2.下面程序段的功能實現(xiàn)數(shù)據(jù)x進棧,要求在下劃線處填上正確的語句。
typedef struct {int s[100];int top;} sqstack;void push(sqstack &stack,int x){ if(stack.top==m-1)printf(“overflow”);else {____________________;_________________;} } 3.中序遍歷二叉排序樹所得到的序列是___________序列(填有序或無序)。4.快速排序的最壞時間復(fù)雜度為___________,平均時間復(fù)雜度為__________。
5.設(shè)某棵二叉樹中度數(shù)為0的結(jié)點數(shù)為N0,度數(shù)為1的結(jié)點數(shù)為N1,則該二叉樹中度數(shù)為2的結(jié)點數(shù)為_________;若采用二叉鏈表作為該二叉樹的存儲結(jié)構(gòu),則該二叉樹中共有_______個空指針域。6.設(shè)某無向圖中頂點數(shù)和邊數(shù)分別為n和e,所有頂點的度數(shù)之和為d,則e=_______。7.設(shè)一組初始記錄關(guān)鍵字序列為(55,63,44,38,75,80,31,56),則利用篩選法建立的初始堆為___________________________。
8. 已知一有向圖的鄰接表存儲結(jié)構(gòu)如下:從頂點1出發(fā),DFS遍歷的輸出序列是,BFS遍歷的輸出序列是
三、應(yīng)用題(36分)1. 設(shè)一組初始記錄關(guān)鍵字序列為(45,80,48,40,22,78),則分別給出第4趟簡單選擇排序和第4趟直接插入排序后的結(jié)果。
2. 設(shè)指針變量p指向雙向鏈表中結(jié)點A,指針變量q指向被插入結(jié)點B,要求給出在結(jié)點A的后面插入結(jié)點B的操作序列(設(shè)雙向鏈表中結(jié)點的兩個指針域分別為llink和rlink)。3. 設(shè)一組有序的記錄關(guān)鍵字序列為(13,18,24,35,47,50,62,83,90),查找方法用二分查找,要求計算出查找關(guān)鍵字62時的比較次數(shù)并計算出查找成功時的平均查找長度。
4. 設(shè)一棵樹T中邊的集合為{(A,B),(A,C),(A,D),(B,E),(C,F(xiàn)),(C,G)},要求用孩子兄弟表示法(二叉鏈表)表示出該樹的存儲結(jié)構(gòu)并將該樹轉(zhuǎn)化成對應(yīng)的二叉樹。5. 設(shè)有無向圖G,要求給出用普里姆算法構(gòu)造最小生成樹所走過的邊的集合。
6. 設(shè)有一組初始記錄關(guān)鍵字為(45,80,48,40,22,78),要求構(gòu)造一棵二叉排序樹并給出構(gòu)造過程。
四、算法設(shè)計題(16分)
1. 設(shè)有一組初始記錄關(guān)鍵字序列(K1,K2,…,Kn),要求設(shè)計一個算法能夠在O(n)的時間復(fù)雜度內(nèi)將線性表劃分成兩部分,其中左半部分的每個關(guān)鍵字均小于Ki,右半部分的每個關(guān)鍵字均大于等于Ki。
2. 設(shè)有兩個集合A和集合B,要求設(shè)計生成集合C=A∩B的算法,其中集合A、B和C用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示。
數(shù)據(jù)結(jié)構(gòu)試卷
(二)參考答案
一、選擇題
1.D 2.B 3.C 4.A 5.A 6.C
二、填空題
1.構(gòu)造一個好的HASH函數(shù),確定解決沖突的方法 2.stack.top++,stack.s[stack.top]=x 3.有序
4.O(n2),O(nlog2n)5.N0-1,2N0+N1
6.d/2 7.(31,38,54,56,75,80,55,63)8.(1,3,4,5,2),(1,3,2,4,5)
三、應(yīng)用題
1.(22,40,45,48,80,78),(40,45,48,80,22,78)2.3.4.5.6.q->llink=p;q->rlink=p->rlink;p->rlink->llink=q;p->rlink=q;2,ASL=91*1+2*2+3*4+4*2)=25/9 樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)略,二叉樹略
E={(1,3),(1,2),(3,5),(5,6),(6,4)} 略
7.B
8.C
四、算法設(shè)計題
1.設(shè)有一組初始記錄關(guān)鍵字序列(K1,K2,…,Kn),要求設(shè)計一個算法能夠在O(n)的時間復(fù)雜度內(nèi)將線性表劃分成兩部分,其中左半部分的每個關(guān)鍵字均小于Ki,右半部分的每個關(guān)鍵字均大于等于Ki。void quickpass(int r[], int s, int t){
int i=s, j=t, x=r[s];
while(i while(i } r[i]=x;} 2.設(shè)有兩個集合A和集合B,要求設(shè)計生成集合C=A∩B的算法,其中集合A、B和C用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示。 typedef struct node {int data;struct node *next;}lklist;void intersection(lklist *ha,lklist *hb,lklist *&hc){ lklist *p,*q,*t;for(p=ha,hc=0;p!=0;p=p->next){ for(q=hb;q!=0;q=q->next)if(q->data==p->data)break;if(q!=0){ t=(lklist *)malloc(sizeof(lklist));t->data=p->data;t->next=hc;hc=t;} } } 一、選擇題(每小題2分,共30分)1.數(shù)據(jù)結(jié)構(gòu)是(D)。 A.一種數(shù)據(jù)類型 B.?dāng)?shù)據(jù)的存儲結(jié)構(gòu) C.一組性質(zhì)相同的數(shù)據(jù)元素的集合 D.相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合 2.以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是(D)。 A.鏈隊列 B.鏈表 C.順序表 D.棧 3.以下數(shù)據(jù)結(jié)構(gòu)中,(A)是非線性數(shù)據(jù)結(jié)構(gòu) A.樹 B.字符串 C.隊 D.棧 4.一個順序存儲線性表的第一個元素的存儲地址是90,每個元素的長度是2,則第6個元素的存儲地址是(B)。 A.98 B.100 C.102 D.106 5.在線性表的下列運算中,不改變數(shù)據(jù)元素之間結(jié)構(gòu)關(guān)系的運算是(D)。A.插入 B.刪除 C.排序 D.查找 6.線性表采用鏈?zhǔn)酱鎯r,其地址(D)。 A.必須是連續(xù)的 B.一定是不連續(xù)的 C.部分地址必須連續(xù) D.連續(xù)與否均可以 7.線性表是(A)。 A.一個有限序列,可以為空 B.一個有限序列,不可以為空 C.一個無限序列,可以為空 D.一個無限序列,不可以為空 8.若進棧序列為1,2,3,4,5,6,且進棧和出棧可以穿插進行,則可能出現(xiàn)的出棧序列為(B)。 A.3,2,6,1,4,5 B.3,4,2,1,6,5 C.1,2,5,3,4,6 D.5,6,4,2,3,1 9.若一個棧的輸人序列是1,2,3,…,n,輸出序列的第一個元素是n,則第k個輸出元素是(C)。 A.k B.n-k-1 C.n-k+1 D.不確定 10.對于隊列操作數(shù)據(jù)的原則是(A)。 A.先進先出 B.后進先出 C.先進后出 D.不分順序 11.棧和隊列的共同點是(C)。 A.都是先進先出 B.都是先進后出 C.只允許在端點處插入和刪除元素 D.沒有共同點 12.在一個鏈隊列中,假定front和rear分別為頭指針和尾指針,刪除一個結(jié)點的操作是(A)。 A.front=front->next B.rear=rear->next C.rear->next=front D.front->next=rear 13.空串與空格串(B)。 A.相同 B.不相同 C.可能相同 D.無法確定 14.串與普通的線性表相比較,它的特殊性體現(xiàn)在(C)。A.順序的存儲結(jié)構(gòu) B.鏈接的存儲結(jié)構(gòu) C.?dāng)?shù)據(jù)元素是一個字符 D.?dāng)?shù)據(jù)元素可以任意 15.串的長度是指(B)。 A.串中所含不同字母的個數(shù) B.串中所含字符的個數(shù) C.串中所含不同字符的個數(shù) D.串中所含非空格字符的個數(shù) 二、填空題(每空2分,共20分) 1. 線性表、棧和隊列,串都是__線性_____結(jié)構(gòu)。2. 數(shù)據(jù)的基本單位是__數(shù)據(jù)元素_______________。 3. 當(dāng)線性表的元素總數(shù)基本穩(wěn)定,且很少進行插入和刪除操作,但要求以最快的速度存取線性表中的元素時,應(yīng)采用_順序______存儲結(jié)構(gòu)。4. 已知具有n個元素的一維數(shù)組采用順序存儲結(jié)構(gòu),每個元素占k個存儲單元,第一個元素的地址為Loc(a1),那么,第i個元素的存儲地址Loc(ai)= Loc(a1)+(i-1)*k。5. 棧(stack)是限定在表尾進行插人或刪除操作的線性表。在棧中,允許插人和刪除操作的一端稱為__棧頂________,而另一端稱為_棧底________。6. 一個循環(huán)隊列Q中,頭指針和尾指針分別為Q.front和Q.rear,且最大隊列長度為MaxQSize,則判斷隊空的條件為 Q.rear==Q.front,判斷隊滿的條件為(Q.rear+1)%MaxQSize==Q.front。隊列的長度為(.rear-Q.front+MaxQSize)%MaxQSize 7. 兩個串相等的充分必要條件是 兩個串的長度相等,且各個對應(yīng)位置的字符都相等。 三、程序填空題(每空3分,共30分) 1.在帶頭結(jié)點的單鏈表L中第i個數(shù)據(jù)元素之前插入數(shù)據(jù)元素e的C語言描述算法如下,其中L為鏈表頭結(jié)點指針。請?zhí)畛渌惴ㄖ袠?biāo)出的空白處,完成其功能。 typedef struct node {int data; struct node *next; }linknode,*link; int ListInsert_L(link &L, int i, int e){ Linknode *p;int j; p = L; j = 0; while(p && j < i-1){ p=p->next ; ++j; } // 尋找第i-1個結(jié)點 if(!p || j > i-1)return 0; s=(link)malloc(sizeof(linknode));// 生成新結(jié)點s s->data = e; s->next=p->next ; p->next = s; // 插入L中 return 1; } 2.對順序棧的C語言描述算法如下,其中top為棧頂指針,請?zhí)畛渌惴ㄖ袠?biāo)出的空白處,插入元素e為新的棧頂元素。 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct{ char *base;char *top;int stacksize;}SqStack; int Push(SqStack &S, char e){ // if((s.top-s.base)>=s.stacksize)//棧滿,追加存儲空間 { S.base=(SElemType *)realloc(S.base,S.stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!S.base)return 0; S.top = s.base+s.stacksize ; //修改棧頂指針 S.stacksize += STACKINCREMENT; } *s.top++=e ;//插入元素 return 1; } 3.對鏈隊列的C語言描述算法如下,請?zhí)畛渌惴ㄖ袠?biāo)出的空白處,刪除隊列Q 的隊頭元素并用e返回其值。typedef struct QNode{ QElemType data; struct QNode *next; }QNode, *QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; }LinkQueue; int DeQueue(LinkQueue &Q, QElemType &e){ Linknode *p; if(Q.front==Q.rear)retrun 0;//隊列空,返回 p = Q.front-> next; e = p->data; Q.front-> next=p->next;//修改指針 if(Q.rear==p)Q.rear= Q.front ; //隊列只有一個元素的情況 free(p);//釋放結(jié)點空間 return 1; } 三、算法設(shè)計與分析題(每題10分,共20分) 1、簡述下列算法實現(xiàn)的功能:(每題5分,共10分)(1)typedef struct LNode{ Char data; struct LNode *next;}LNode,*LinkList;LinkList Demo(LinkList &L){ // L 是無頭結(jié)點單鏈表 LNode *Q,*P;if(L&&L->next){ Q=L;L=L->next;P=L;while(P->next)P=P->next; P->next=Q;Q->next=NULL; } return L;}// Demo 答:將單鏈表的第一個結(jié)點刪除,放到鏈尾。 ——————————————————————————————————————————————————— (2)#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct{ int *base;int *top;int stacksize; } Stack;void Demo1(Stack &S, int m){ Stack T;int i; InitStack(T);//初始化棧 while(!StackEmpty(S))//判斷棧是否為空 if((i=Pop(S))!=m)Push(T,i);//入棧操作 while(!StackEmpty(T)) { i=Pop(T);//出棧操作 Push(S,i); } } 答:刪除棧S中所有值為m的數(shù)據(jù)元素 2.有一個帶頭結(jié)點的單鏈表,頭指針為head,編寫一個算法計算所有數(shù)據(jù)域為X的結(jié)點的個數(shù)(不包括頭結(jié)點)。typedef struct node {int data;struct node *next;}linknode,*link;int sample(link head, int X){ int count=0;link p=head->next;while(p){if(p->data==X)count++;p=p->next;} return count;} 數(shù)據(jù)結(jié)構(gòu)試卷 (一)一、選擇題(20分) 1.組成數(shù)據(jù)的基本單位是()。 (A)數(shù)據(jù)項(B)數(shù)據(jù)類型(C)數(shù)據(jù)元素(D)數(shù)據(jù)變量 2.設(shè)數(shù)據(jù)結(jié)構(gòu)A=(D,R),其中D={1,2,3,4},R={r},r={<1,2>,<2,3>,<3,4>,<4,1>},則數(shù)據(jù)結(jié)構(gòu)A是()。 (A)線性結(jié)構(gòu)(B)樹型結(jié)構(gòu)(C)圖型結(jié)構(gòu)(D)集合 3.?dāng)?shù)組的邏輯結(jié)構(gòu)不同于下列()的邏輯結(jié)構(gòu)。 (A)線性表(B)棧(C)隊列(D)樹 4.二叉樹中第i(i≥1)層上的結(jié)點數(shù)最多有()個。 ii-1(A)2i(B)2(C)2(D)2i-1 5.設(shè)指針變量p指向單鏈表結(jié)點A,則刪除結(jié)點A的后繼結(jié)點B需要的操作為()。 (A)p->next=p->next->next(B)p=p->next (C)p=p->next->next(D)p->next=p 6.設(shè)棧S和隊列Q的初始狀態(tài)為空,元素E1、E2、E3、E4、E5和E6依次通過棧S,一個元素出棧后即進入隊列Q,若6個元素出列的順序為E2、E4、E3、E6、E5和E1,則棧S的容量至少應(yīng)該是()。 (A)6(B)4(C)3(D)2 7.將10階對稱矩陣壓縮存儲到一維數(shù)組A中,則數(shù)組A的長度最少為()。 (A)100(B)40(C)55(D)80 8.設(shè)結(jié)點A有3個兄弟結(jié)點且結(jié)點B為結(jié)點A的雙親結(jié)點,則結(jié)點B的度數(shù)數(shù)為()。 (A)3(B)4(C)5(D)1 9.根據(jù)二叉樹的定義可知二叉樹共有()種不同的形態(tài)。 (A)4(B)5(C)6(D)7 10.設(shè)有以下四種排序方法,則()的空間復(fù)雜度最大。 (A)冒泡排序(B)快速排序(C)堆排序(D)希爾排序 二、填空題(30分)1.設(shè)順序循環(huán)隊列Q[0:m-1]的隊頭指針和隊尾指針分別為F和R,其中隊頭指針F指向當(dāng)前隊頭元素的前一個位置,隊尾指針R指向當(dāng)前隊尾元素所在的位置,則出隊列的語句為F =____________。 2.設(shè)線性表中有n個數(shù)據(jù)元素,則在順序存儲結(jié)構(gòu)上實現(xiàn)順序查找的平均時間復(fù)雜度為___________,在鏈?zhǔn)酱鎯Y(jié)構(gòu)上實現(xiàn)順序查找的平均時間復(fù)雜度為___________。3.設(shè)一棵二叉樹中有n個結(jié)點,則當(dāng)用二叉鏈表作為其存儲結(jié)構(gòu)時,該二叉鏈表中共有________個指針域,__________個空指針域。 4.設(shè)指針變量p指向單鏈表中結(jié)點A,指針變量s指向被插入的結(jié)點B,則在結(jié)點A的后面插入結(jié)點B的操作序列為______________________________________。 5.設(shè)無向圖G中有n個頂點和e條邊,則其對應(yīng)的鄰接表中有_________個表頭結(jié)點和_________個表結(jié)點。 6.設(shè)無向圖G中有n個頂點e條邊,所有頂點的度數(shù)之和為m,則e和m有______關(guān)系。7.設(shè)一棵二叉樹的前序遍歷序列和中序遍歷序列均為ABC,則該二叉樹的后序遍歷序列為__________。 8.設(shè)一棵完全二叉樹中有21個結(jié)點,如果按照從上到下、從左到右的順序從1開始順序編號,則編號為8的雙親結(jié)點的編號是___________,編號為8的左孩子結(jié)點的編號是_____________。 9.下列程序段的功能實現(xiàn)子串t在主串s中位置的算法,要求在下劃線處填上正確語句。 int index(char s[ ], char t[ ]){ i=j=0;while(i 三、應(yīng)用題(30分) 1.設(shè)完全二叉樹的順序存儲結(jié)構(gòu)中存儲數(shù)據(jù)ABCDE,要求給出該二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)并給出該二叉樹的前序、中序和后序遍歷序列。 2.設(shè)給定一個權(quán)值集合W=(3,5,7,9,11),要求根據(jù)給定的權(quán)值集合構(gòu)造一棵哈夫曼樹并計算哈夫曼樹的帶權(quán)路徑長度WPL。 3.設(shè)一組初始記錄關(guān)鍵字序列為(19,21,16,5,18,23),要求給出以19為基準(zhǔn)的一趟快速排序結(jié)果以及第2趟直接選擇排序后的結(jié)果。 4.設(shè)一組初始記錄關(guān)鍵字集合為(25,10,8,27,32,68),散列表的長度為8,散列函數(shù)H(k)=k mod 7,要求分別用線性探測和鏈地址法作為解決沖突的方法設(shè)計哈希表。5.設(shè)無向圖G(所右圖所示),要求給出該圖的深度優(yōu)先和廣度優(yōu)先遍歷的序列并給出該圖的最小生成樹。 四、算法設(shè)計題(20分)1.設(shè)計判斷單鏈表中結(jié)點是否關(guān)于中心對稱算法。2.設(shè)計在鏈?zhǔn)酱鎯Y(jié)構(gòu)上建立一棵二叉樹的算法。3.設(shè)計判斷一棵二叉樹是否是二叉排序樹的算法。 數(shù)據(jù)結(jié)構(gòu)試卷 (一)參考答案 一、選擇題 1.C 2.C 3.D 4.C 5.A 6.C 7.C 8.B 9.B 10.B 二、填空題 1.(F+1)% m 2.O(n),O(n)3.2n,n+1 4.s->next=p->next;s->next=s 5.n, 2e 6.m=2e 7.CBA 8.4,16 9.i-j+1,0 10.n-1 三、應(yīng)用題 1.鏈?zhǔn)酱鎯Y(jié)構(gòu)略,前序ABDEC,中序DBEAC,后序DEBCA。2.哈夫曼樹略,WPL=78 3.(18,5,16,19,21,23),(5,16,21,19,18,23) h0h1??8h2012345674.線性探測: 鏈地址法:h3??10 ?8?1025322768h4??25??32h5??68h6??275.深度:125364,廣度:123456,最小生成樹T的邊集為E={(1,4),(1,3),(3,5),(5,6),(5,6)} 四、算法設(shè)計題 1.設(shè)計判斷單鏈表中結(jié)點是否關(guān)于中心對稱算法。 typedef struct {int s[100];int top;} sqstack;int lklistsymmetry(lklist *head){ sqstack stack;stack.top=-1;lklist *p; for(p=head;p!=0;p=p->next){stack.top++;stack.s[stack.top]=p->data;} for(p=head;p!=0;p=p->next)if(p->data==stack.s[stack.top])stack.top=stack.top-1;else return(0); return(1);} 2.設(shè)計在鏈?zhǔn)酱鎯Y(jié)構(gòu)上建立一棵二叉樹的算法。 typedef char datatype;typedef struct node {datatype data;struct node *lchild,*rchild;} bitree;void createbitree(bitree *&bt){ char ch;scanf(“%c”,&ch); if(ch=='#'){bt=0;return;} bt=(bitree*)malloc(sizeof(bitree));bt->data=ch;createbitree(bt->lchild);createbitree(bt->rchild);} 3.設(shè)計判斷一棵二叉樹是否是二叉排序樹的算法。 int minnum=-32768,flag=1;typedef struct node{int key;struct node *lchild,*rchild;}bitree;void inorder(bitree *bt){ if(bt!=0) {inorder(bt->lchild);if(minnum>bt->key)flag=0;minnum=bt->key;inorder(bt->rchild);} } 廣東海洋大學(xué) 2013 —— 2014 學(xué)年第 1 學(xué)期 《數(shù)據(jù)結(jié)構(gòu)與算法》課程試題 一、選擇題(6小題,每題3分) 1.若某線性表中最常用的操作是取第i個元素和找第i個元素的前驅(qū),則采用(A)存儲方法最節(jié)省時間 A 順序表 B單鏈表 C 雙鏈表 D單循環(huán)鏈表 2.一個棧的入棧序列是1,2,3,4,5,則不可能的出棧序列是(C)A 5,4,3,2,1 B 4,5,3,2,1 C 4,3,5,1,2 D 1,2,3,4,5 3.深度為k的完全二叉樹至多有(C)個結(jié)點 A 2k?2? 1B 2k?1 C D 2k?1?1 k4.G是一個非連通無向圖,共28條邊,則該圖至少有(D)個頂點2A 6 B 7 C 8 D 9 ?1 5.在平衡二叉樹中插入一個結(jié)點后造成不平衡,設(shè)最低的不平衡結(jié)點為A,并已知A的左孩子平衡因子為0,右孩子平衡因子為1,則應(yīng)該做(C)型調(diào)整以使其平衡 A LL B LR C RL D RR 6.下述排序方法中,時間性能和待排序記錄的初始狀態(tài)無關(guān)的是(C)A 插入排序和快速排序 B 歸并排序和快速排序 C 選擇排序和歸并排序 D 插入排序和歸并排序 二、填空題 1.數(shù)組Q[n]用來表示一個循環(huán)隊列,front為隊頭元素的前一個位置,rear為隊尾元素位置,計算隊列中元素個數(shù)的公式為______(rear-front+n)%n______________。 2.已知一棵度為3的樹有2個度為1的結(jié)點,3個度為2的結(jié)點,4個度為3的結(jié)點。則該樹中有__12_________個葉子結(jié)點。 3.已知無向圖的頂點數(shù)為n,邊數(shù)為e,其鄰接表表示的空間復(fù)雜度為____________O(n+e)____。4.假定一個數(shù)列{25,43,62,31,48,56},采用散列函數(shù)為H(k)=k mod 7,則元素48的同義詞是____62_______。5.利用簡單選擇排序?qū)個記錄進行排序,最壞情況下,記錄交換次數(shù)為_____n-1_______。 三、(15分)已知一棵二叉樹的中序遍歷序列為DBKEHJAFCIG,后序遍歷序列為DKJHEBFIGCA,試畫出該二叉樹并給出其前序遍歷序列 四、(15分)設(shè)用于通信的電文由字符集{a,b,c,d,e,f,g,h}中的字母構(gòu)成,它們在電文中出現(xiàn)的頻度分別為{0.02,0.30,0.08,0.14,0.17,0.11,0.12, 0.06},回答下面問題:(1)為這八個字符設(shè)計哈夫曼編碼(2)對這八個字符進行等長編碼需要幾位二進制數(shù),哈夫曼編碼比等長編碼電文總長壓縮多少? 五、(20分)已知一個長度為11的線性表List=(12, 24, 36, 90, 52, 30, 41, 8, 10, 38, 61),試回答下面問題(1)將線性表元素依次插入一個空的平衡二叉樹,畫出所得平衡二叉樹,如果假設(shè)每個元素查找概率相同,則平均查找長度為多少? (2)如果對線性表元素排序后進行折半查找,畫出折半查找判定樹,假設(shè)每個元素查找概率相同,計算平均查找長度。 六、(12分)已知數(shù)據(jù)序列為(11,4,8,19,6,31,23),寫出快速排序及堆排序每一趟的結(jié)果 解: 七、(11分)設(shè)單鏈表以非遞減有序排列,設(shè)計算法實現(xiàn)在單鏈表中刪除值相同的多余結(jié)點。 數(shù)據(jù)結(jié)構(gòu)試卷 (八)一、選擇題(30分)1.字符串的長度是指()。 (A)串中不同字符的個數(shù)(B)串中不同字母的個數(shù) (C)串中所含字符的個數(shù)(D)串中不同數(shù)字的個數(shù) 2.建立一個長度為n的有序單鏈表的時間復(fù)雜度為()(A)O(n)(B)O(1)(C)O(n)(D)O(log2n)3.兩個字符串相等的充要條件是()。 (A)兩個字符串的長度相等(B)兩個字符串中對應(yīng)位置上的字符相等 (C)同時具備(A)和(B)兩個條件(D)以上答案都不對 4.設(shè)某散列表的長度為100,散列函數(shù)H(k)=k % P,則P通常情況下最好選擇()。 (A)99(B)97(C)91(D)93 5.在二叉排序樹中插入一個關(guān)鍵字值的平均時間復(fù)雜度為()。(A)O(n)(B)O(1og2n)(C)O(nlog2n)(D)O(n)6.設(shè)一個順序有序表A[1:14]中有14個元素,則采用二分法查找元素A[4]的過程中比較元素的順序為()。 (A)A[1],A[2],A[3],A[4](B)A[1],A[14],A[7],A[4](C)A[7],A[3],A[5],A[4](D)A[7],A[5],A[3],A[4] 7.設(shè)一棵完全二叉樹中有65個結(jié)點,則該完全二叉樹的深度為()。 (A)8(B)7(C)6(D)5 8.設(shè)一棵三叉樹中有2個度數(shù)為1的結(jié)點,2個度數(shù)為2的結(jié)點,2個度數(shù)為3的結(jié)點,則該三叉鏈權(quán)中有()個度數(shù)為0的結(jié)點。 (A)5(B)6(C)7(D)8 9.設(shè)無向圖G中的邊的集合E={(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)},則從頂點a出發(fā)進行深度優(yōu)先遍歷可以得到的一種頂點序列為()。 (A)aedfcb(B)acfebd(C)aebcfd(D)aedfbc 10.隊列是一種()的線性表。 (A)先進先出(B)先進后出(C)只能插入(D)只能刪除 二、判斷題(20分)1.如果兩個關(guān)鍵字的值不等但哈希函數(shù)值相等,則稱這兩個關(guān)鍵字為同義詞。()2.設(shè)初始記錄關(guān)鍵字基本有序,則快速排序算法的時間復(fù)雜度為O(nlog2n)。()3.分塊查找的基本思想是首先在索引表中進行查找,以便確定給定的關(guān)鍵字可能存在的塊號,然后再在相應(yīng)的塊內(nèi)進行順序查找。()4.二維數(shù)組和多維數(shù)組均不是特殊的線性結(jié)構(gòu)。() 5.向二叉排序樹中插入一個結(jié)點需要比較的次數(shù)可能大于該二叉樹的高度。()6.如果某個有向圖的鄰接表中第i條單鏈表為空,則第i個頂點的出度為零。()7.非空的雙向循環(huán)鏈表中任何結(jié)點的前驅(qū)指針均不為空。()8.不論線性表采用順序存儲結(jié)構(gòu)還是鏈?zhǔn)酱鎯Y(jié)構(gòu),刪除值為X的結(jié)點的時間復(fù)雜度均為O(n)。() 9.圖的深度優(yōu)先遍歷算法中需要設(shè)置一個標(biāo)志數(shù)組,以便區(qū)分圖中的每個頂點是否被訪問過。()10.稀疏矩陣的壓縮存儲可以用一個三元組表來表示稀疏矩陣中的非0元素。() 三、填空題(30分)1. 設(shè)一組初始記錄關(guān)鍵字序列為(49,38,65,97,76,13,27,50),則以d=4為增量的一趟希爾排序結(jié)束后的結(jié)果為_____________________________。2. 下面程序段的功能是實現(xiàn)在二叉排序樹中插入一個新結(jié)點,請在下劃線處填上正確的內(nèi)容。 typedef struct node{int data;struct node *lchild;struct node *rchild;}bitree;void bstinsert(bitree *&t,int k){ if(t==0){____________________________;t->data=k;t->lchild=t->rchild=0;} else if(t->data>k)bstinsert(t->lchild,k);else__________________________;} 3. 設(shè)指針變量p指向單鏈表中結(jié)點A,指針變量s指向被插入的結(jié)點X,則在結(jié)點A的后面插入結(jié)點X需要執(zhí)行的語句序列:s->next=p->next;_________________。4. 設(shè)指針變量head指向雙向鏈表中的頭結(jié)點,指針變量p指向雙向鏈表中的第一個結(jié)點,則指針變量p和指針變量head之間的關(guān)系是p=_________和head=__________(設(shè)結(jié)點中的兩個指針域分別為llink和rlink)。 5. 設(shè)某棵二叉樹的中序遍歷序列為ABCD,后序遍歷序列為BADC,則其前序遍歷序列為__________。 6. 完全二叉樹中第5層上最少有__________個結(jié)點,最多有_________個結(jié)點。 7. 設(shè)有向圖中不存在有向邊 8. 設(shè)一組初始記錄關(guān)鍵字序列為(49,38,65,97,76,13,27,50),則第4趟直接選擇排序結(jié)束后的結(jié)果為_____________________________。 9. 設(shè)連通圖G中有n個頂點e條邊,則對應(yīng)的最小生成樹上有___________條邊。10. 設(shè)有一組初始記錄關(guān)鍵字序列為(50,16,23,68,94,70,73),則將它們調(diào)整成初始堆只需把16與___________相互交換即可。 四、算法設(shè)計題(20分)1.設(shè)計一個在鏈?zhǔn)酱鎯Y(jié)構(gòu)上統(tǒng)計二叉樹中結(jié)點個數(shù)的算法。2.設(shè)計一個算法將無向圖的鄰接矩陣轉(zhuǎn)為對應(yīng)鄰接表的算法。 數(shù)據(jù)結(jié)構(gòu)試卷 (八)參考答案 一、選擇題 1.C 2.C 3.C 4.B 5.B 6.C 7.B 8.C 9.A 10.A 二、判斷題 1.對 2.錯 3.對 4.錯 5.錯 6.對 7.對 8.對 9.對 10.對 三、填空題 1.(49,13,27,50,76,38,65,97)2.t=(bitree *)malloc(sizeof(bitree)),bstinsert(t->rchild,k)3.p->next=s 4.head->rlink,p->llink 5.CABD 6.1,16 7.0 8.(13,27,38,50,76,49,65,97)9.n-1 10.50 四、算法設(shè)計題 1.設(shè)計一個在鏈?zhǔn)酱鎯Y(jié)構(gòu)上統(tǒng)計二叉樹中結(jié)點個數(shù)的算法。 void countnode(bitree *bt,int &count){ if(bt!=0) {count++;countnode(bt->lchild,count);countnode(bt->rchild,count);} } 2.設(shè)計一個算法將無向圖的鄰接矩陣轉(zhuǎn)為對應(yīng)鄰接表的算法。 typedef struct {int vertex[m];int edge[m][m];}gadjmatrix;typedef struct node1{int info;int adjvertex;struct node1 *nextarc;}glinklistnode;typedef struct node2{int vertexinfo;glinklistnode *firstarc;}glinkheadnode;void adjmatrixtoadjlist(gadjmatrix g1[ ],glinkheadnode g2[ ]){ int i,j;glinklistnode *p;for(i=0;i<=n-1;i++)g2[i].firstarc=0;for(i=0;i<=n-1;i++)for(j=0;j<=n-1;j++)if(g1.edge[i][j]==1){ p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=j;p->nextarc=g[i].firstarc;g[i].firstarc=p;p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=i;p->nextarc=g[j].firstarc;g[j].firstarc=p;} }第二篇:數(shù)據(jù)結(jié)構(gòu)期中試卷及答案
第三篇:數(shù)據(jù)結(jié)構(gòu)試卷(一)及答案
第四篇:廣東海洋大學(xué)數(shù)據(jù)結(jié)構(gòu)試卷及答案
第五篇:數(shù)據(jù)結(jié)構(gòu)試卷(八)及答案