第一篇：數(shù)據(jù)結(jié)構(gòu)試題及答案10

《數(shù)據(jù)結(jié)構(gòu)》自考復(fù)習(xí)思考試題

一、單項選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。

1.若將數(shù)據(jù)結(jié)構(gòu)形式定義為二元組(K，R)，其中K是數(shù)據(jù)元素的有限集合，則R是K上（）

A.操作的有限集合B.映象的有限集合 C.類型的有限集合D.關(guān)系的有限集合

2.在長度為n的順序表中刪除第i個元素(1≤i≤n)時，元素移動的次數(shù)為（）A.n-i+1

B.i C.i+1

D.n-i 3.若不帶頭結(jié)點的單鏈表的頭指針為head，則該鏈表為空的判定條件是（）A.head==NULL

B.head->next==NULL C.head!=NULL

D.head->next==head 4.引起循環(huán)隊列隊頭位置發(fā)生變化的操作是（）A.出隊

B.入隊

C.取隊頭元素

D.取隊尾元素

5.若進棧序列為1，2，3，4，5，6，且進棧和出?？梢源┎暹M行，則不可能出現(xiàn)的出棧序列是（）A.2，4，3，1，5，6

B.3，2，4，1，6，5 C.4，3，2，1，5，6

D.2，3，5，1，6，4 6.字符串通常采用的兩種存儲方式是（）A.散列存儲和索引存儲

B.索引存儲和鏈式存儲 C.順序存儲和鏈式存儲

D.散列存儲和順序存儲

7.設(shè)主串長為n，模式串長為m(m≤n)，則在匹配失敗情況下，樸素匹配算法進行的無效位移次數(shù)為（）A.m

B.n-m C.n-m+1

D.n 8.二維數(shù)組A［12］［18］采用列優(yōu)先的存儲方法，若每個元素各占3個存儲單元，且第1個元素的地址為150，則元素A［9］［7］的地址為（）A.429

B.432 C.435

D.438 9.對廣義表L=((a,b),(c,d),(e,f))執(zhí)行操作tail(tail(L))的結(jié)果是（）A.(e,f)

B.((e,f))C.(f)

D.()10.下列圖示的順序存儲結(jié)構(gòu)表示的二叉樹是（）11.n個頂點的強連通圖中至少含有（）A.n-1條有向邊

B.n條有向邊 C.n(n-1)/2條有向邊

D.n(n-1)條有向邊

12.對關(guān)鍵字序列(56，23，78，92，88，67，19，34)進行增量為3的一趟希爾排序的結(jié)果為（）A.(19，23，56，34，78，67，88，92)

B.(23，56，78，66，88，92，19，34)C.(19，23，34，56，67，78，88，92)

D.(19，23，67，56，34，78，92，88)13.若在9階B-樹中插入關(guān)鍵字引起結(jié)點分裂，則該結(jié)點在插入前含有的關(guān)鍵字個數(shù)為（）

A.4

B.5 C.8

D.9 14.由同一關(guān)鍵字集合構(gòu)造的各棵二叉排序樹（）A.其形態(tài)不一定相同，但平均查找長度相同

B.其形態(tài)不一定相同，平均查找長度也不一定相同 C.其形態(tài)均相同，但平均查找長度不一定相同 D.其形態(tài)均相同，平均查找長度也都相同

15.ISAM文件和VSAM文件的區(qū)別之一是（）A.前者是索引順序文件，后者是索引非順序文件 B.前者只能進行順序存取，后者只能進行隨機存取 C.前者建立靜態(tài)索引結(jié)構(gòu)，后者建立動態(tài)索引結(jié)構(gòu) D.前者的存儲介質(zhì)是磁盤，后者的存儲介質(zhì)不是磁盤

二、填空題(本大題共10小題，每空2分，共20分)16.數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲器內(nèi)的表示，稱為數(shù)據(jù)的____________。17.刪除雙向循環(huán)鏈表中*p的前驅(qū)結(jié)點(存在)應(yīng)執(zhí)行的語句是____________。18.棧下溢是指在____________時進行出棧操作。

19.已知substr(s,i,len)函數(shù)的功能是返回串s中第i個字符開始長度為len的子串，strlen(s)函數(shù)的功能是返回串s的長度。若s=″ABCDEFGHIJK″,t=″ABCD″,執(zhí)行運算substr(s,strlen(t), strlen(t))后的返回值為____________。

20.去除廣義表LS=(a1,a2,a3,??，an)中第1個元素，由其余元素構(gòu)成的廣義表稱為LS的____________。

21.已知完全二叉樹T的第5層只有7個結(jié)點，則該樹共有____________個葉子結(jié)點。22.在有向圖中，以頂點v為終點的邊的數(shù)目稱為v的____________。

23.當關(guān)鍵字的取值范圍是實數(shù)集合時，無法進行箱排序和____________排序。24.產(chǎn)生沖突現(xiàn)象的兩個關(guān)鍵字稱為該散列函數(shù)的____________。

25.假設(shè)散列文件中一個桶能存放m個記錄，則桶“溢出”的含義是，當需要插入新的記錄時，該桶中____________。

三、解答題(本大題共4小題，每小題5分，共20分)26.假設(shè)以數(shù)組seqn［m］存放循環(huán)隊列的元素，設(shè)變量rear和quelen分別指示循環(huán)隊列中隊尾元素的位置和元素的個數(shù)。(1)寫出隊滿的條件表達式；(2)寫出隊空的條件表達式；

(3)設(shè)m=40,rear=13,quelen=19,求隊頭元素的位置；(4)寫出一般情況下隊頭元素位置的表達式。

27.已知一棵二叉樹的中序序列為ABCDEFG，層序序列為BAFEGCD，請畫出該二叉樹。28.畫出下圖所示有向圖的所有強連通分量。

29.對7個關(guān)鍵字進行快速排序，在最好的情況下僅需進行10次關(guān)鍵字的比較。(1)假設(shè)關(guān)鍵字集合為{1,2,3,4,5,6,7}，試舉出能達到上述結(jié)果的初始關(guān)鍵字序列；(2)對所舉序列進行快速排序，寫出排序過程。

四、算法閱讀題(本大題共4小題，每小題5分，共20分)30.閱讀下列算法，并回答問題：(1)設(shè)順序表L=(3,7,11,14,20,51)，寫出執(zhí)行f30(&L,15)之后的L；(2)設(shè)順序表L=(4,7,10,14,20,51)，寫出執(zhí)行f30(&L,10)之后的L；(3)簡述算法的功能。

void f30(SeqList*L, DataType x){

int i =0, j;

while(ilength && x>L->data［i］)i++;

if(ilength && x==L->data［i］){

for(j=i+1;jlength;j++)

L->data［j-1］=L->data［j］;

L->length--;

} else {

for(j=L->length;j>i;j--)

L->data［j］=L->data［j-1］;

L->data［i］=x;

L->length++;

} } 31.已知圖的鄰接表表示的形式說明如下：

#define MaxNum

//圖的最大頂點數(shù) typedef struct node {

int

adjvex;

//鄰接點域

struct node *next;

//鏈指針域

} EdgeNode;

//邊表結(jié)點結(jié)構(gòu)描述 typedef struct {

char vertex;

//頂點域

EdgeNode

*firstedge;

//邊表頭指針 } VertexNode;

//頂點表結(jié)點結(jié)構(gòu)描述 typedef struct {

VertexNode adjlist［MaxNum］;

//鄰接表

int n, e;

//圖中當前的頂點數(shù)和邊數(shù) } ALGraph;

//鄰接表結(jié)構(gòu)描述

下列算法輸出圖G的深度優(yōu)先生成樹(或森林)的邊。閱讀算法，并在空缺處填入合適的內(nèi)容，使其成為一個完整的算法。

typedef enum {FALSE, TRUE} Boolean;Boolean visited［MaxNum］;void DFSForest(ALGraph *G){

int i;

for(i=0;in;i++)visited［i］=

(1)

;

for(i=0;in;i++)if(!visited［i］)DFSTree(G,i);} void DFSTree(ALGraph *G, int i){

EdgeNode *p;

visited［i］=TRUE;

p=G->adjlist［i］.firstedge;

while(p!=NULL){

if(!visited［p->adjvex］){

printf(″<%c,%c>″,G->adjlist［i］.vertex，G->adjlist［p->adjvex］.vertex);

(2)

;

}

(3)

;

} } 32.閱讀下列算法，并回答問題：

(1)假設(shè)數(shù)組L［8］={3,0,5,1,6,4,2,7}，寫出執(zhí)行函數(shù)調(diào)用f32(L，8)后的L；(2)寫出上述函數(shù)調(diào)用過程中進行元素交換操作的總次數(shù)。void f32(int R［］,int n){

int i,t;

for(i=0;i

while(R［i］!=i){

t=R［R［i］］;

R［R［i］］=R［i］;

R［i］=t;

} } 33.已知帶頭結(jié)點的單鏈表中的關(guān)鍵字為整數(shù)，為提高查找效率，需將它改建為采用拉鏈法處理沖突的散列表。設(shè)散列表的長度為m，散列函數(shù)為Hash(key)=key%m。鏈表的結(jié)點結(jié)構(gòu)為：。請在空缺處填入適當內(nèi)容，使其成為一個完整算法。void f33(LinkList L, LinkList H［］, int m){//由帶頭結(jié)點的單鏈表L生成散列表H，散列表生成之后原鏈表不再存在 int i,j;

LinkList p,q;

for(i=0;i

H［i］=

(1)

;

p=L->next;

while(p)

{

q=p->next;

j=p->key%m;

(2)

;

H［j］=p;

(3)

;

}

free(L);

}

五、算法設(shè)計題(本大題10分)34.假設(shè)以帶雙親指針的二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，其結(jié)點結(jié)構(gòu)的類型說明如下所示： typedef char DataType;typedef struct node {

DataType data;

struct node *lchild, *rchild;

//左右孩子指針

struct node *parent;

//指向雙親的指針 } BinTNode;typedef BinTNode *BinTree;若px為指向非空二叉樹中某個結(jié)點的指針，可借助該結(jié)構(gòu)求得px所指結(jié)點在二叉樹的中序序列中的后繼。

(1)就后繼的不同情況，簡要敘述實現(xiàn)求后繼操作的方法；

(2)編寫算法求px所指結(jié)點的中序序列后繼，并在算法語句中加注注釋。數(shù)據(jù)結(jié)構(gòu)標準答案

一、單項選擇題 1.(B)2.(D)3.(A)4.(A)5.(D)6.(C)7.(C)8.(A)9.(B)10.(A)11.(B)12.(D)13.(C)14.(B)15.(C)

二、填空題(本大題共10小題，每空2分，共20分)16.存儲結(jié)構(gòu) 17.q = p->pre;q->pre->next = p;p->pre = q->pre;free(q);18.?？?/p>

19.“DEFG” //注意雙引號不能少 20.表尾

21.２^(I-2)+M/2 葉子結(jié)點． 22.入度 23.基數(shù) 24.同義詞

25.已有m個同義詞記錄

三、解答題(本大題共4小題，每小題5分，共20分)26.(1)quelen == m(2)quelen == 0(3)(13quelen + m)% m 27.B

/

A F

/

E G

/

C

D 28.3個: a、bce、dfg 29.我們知道，對n個關(guān)鍵自序列進行一趟快速排序，要進行n-1次比較，也就是基準和其他n-1個關(guān)鍵字比較。

這里要求10次，而71)= 10，這就要求2趟快速排序后，算法結(jié)束。所以，列舉出來的序列，要求在做partition的時候，正好將序列平分(1)4 1 3 2 6 5 7

或 4 1 3 7 6 5 2 或 4 5 3 7 6 1 2 或 4 1 3 5 6 2 7.......(2)自己列吧 :)

四、算法閱讀題(本大題共4小題，每小題5分，共20分)30.(1)L=(3,7,11,14,15,20,51)(2)L=(4,7,14,20,51)(3)在順序表L中查找數(shù)x, 找到，則刪除x，沒找到，則在適當?shù)奈恢貌迦離，插入后，L依然有序.31.(1)FALSE //初始化為未訪問

(2)DSFTree(G, p->adjvex);//從相鄰結(jié)點往下繼續(xù)深度搜索(3)p = p->next;//下一個未訪問的相鄰結(jié)點

32.(1)L = { 0, 1, 2, 3, 4, 5, 6, 7 };(2)5次

33.(1)NULL

//初始化

(2)p->next = H[ j ] //和下面一句完成頭插法(3)p = q;

//繼續(xù)遍歷L

五、算法設(shè)計題(本大題10分)34.1)

a)*px 有右孩子，則其右孩子為其中序序列中的后繼

b)*px 無右孩子，從*px開始回溯其祖先結(jié)點，找到第1個身份為左孩子的結(jié)點，找到，則該結(jié)點的父結(jié)點為*px的中序序列中的后繼。找不到，則無后繼。2)BinTNode * fintNext(BinTNode * px){ if(px-> rchild)return px->rchild;//*px 有右孩子

BinTNode *q, *qp;

q = px;while(qp = q->parent){ //未回溯到根結(jié)點

if(qp->lchild == q)return qp;//找到1)b)所述結(jié)點

q = qp;//往上回溯 }

return NULL;//未找到 }

第二篇：數(shù)據(jù)結(jié)構(gòu)試題及答案

數(shù)據(jù)結(jié)構(gòu)試卷

（二）一、選擇題(24分)1．下面關(guān)于線性表的敘述錯誤的是（）。

(A)線性表采用順序存儲必須占用一片連續(xù)的存儲空間

(B)線性表采用鏈式存儲不必占用一片連續(xù)的存儲空間(C)線性表采用鏈式存儲便于插入和刪除操作的實現(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總是指向隊尾元素的當前位置，則該循環(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)n

2(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為基準進行一趟快速排序的結(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.1.為了能有效地應(yīng)用HASH查找技術(shù)，必須解決的兩個問題是____________________和__________________________。

2.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.3.中序遍歷二叉排序樹所得到的序列是___________序列（填有序或無序）。4.4.快速排序的最壞時間復(fù)雜度為___________，平均時間復(fù)雜度為__________。5.5.設(shè)某棵二叉樹中度數(shù)為0的結(jié)點數(shù)為N0，度數(shù)為1的結(jié)點數(shù)為N1，則該二叉樹中度數(shù)為2的結(jié)點數(shù)為_________；若采用二叉鏈表作為該二叉樹的存儲結(jié)構(gòu)，則該二叉樹中共有_______個空指針域。

6.6.設(shè)某無向圖中頂點數(shù)和邊數(shù)分別為n和e，所有頂點的度數(shù)之和為d，則e=_______。

7.7.設(shè)一組初始記錄關(guān)鍵字序列為(55，63，44，38，75，80，31，56)，則利用篩選法建立的初始堆為___________________________。

v1??3??2??4v2??1??3v3??1??4??28.8.設(shè)某無向圖G的鄰接表為v4??1??3，則從頂點V1開始的深度優(yōu)先遍歷序列為___________；廣度優(yōu)先遍歷序列為____________。

三、應(yīng)用題(36分)1． 1． 設(shè)一組初始記錄關(guān)鍵字序列為(45，80，48，40，22，78)，則分別給出第4趟簡單選擇排序和第4趟直接插入排序后的結(jié)果。

2． 2． 設(shè)指針變量p指向雙向鏈表中結(jié)點A，指針變量q指向被插入結(jié)點B，要求給出在結(jié)點A的后面插入結(jié)點B的操作序列（設(shè)雙向鏈表中結(jié)點的兩個指針域分別為llink和rlink）。

3． 3． 設(shè)一組有序的記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求計算出查找關(guān)鍵字62時的比較次數(shù)并計算出查找成功時的平均查找長度。

4． 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． 5． 設(shè)有無向圖G（如右圖所示），要求給出用普里姆算法構(gòu)造最小生成樹所走過的邊的集合。

6． 6． 設(shè)有一組初始記錄關(guān)鍵字為(45，80，48，40，22，78)，要求構(gòu)造一棵二叉排序樹并給出構(gòu)造過程。

數(shù)據(jù)結(jié)構(gòu)試卷

（二）參考答案

一、選擇題 1.D 2.B 3.C 4.A 5.A 6.C 7.B 8.C

二、填空題

1.1.構(gòu)造一個好的HASH函數(shù)，確定解決沖突的方法 2.2.stack.top++，stack.s[stack.top]=x 3.3.有序

4.4.O(n2)，O(nlog2n)5.5.N0-1，2N0+N1 6.6.d/2 7.7.(31，38，54，56，75，80，55，63)8.8.(1，3，4，2)，(1，3，2，4)

三、應(yīng)用題

1.1.(22，40，45，48，80，78)，(40，45，48，80，22，78)2.2.q->llink=p;q->rlink=p->rlink;p->rlink->llink=q;p->rlink=q;3.3.2,ASL=91*1+2*2+3*4+4*2)=25/9 4.4.樹的鏈式存儲結(jié)構(gòu)略，二叉樹略

5.5.E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)} 6.6.略

數(shù)據(jù)結(jié)構(gòu)試卷

（三）一、選擇題(30分)1．設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為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>}，則數(shù)據(jù)結(jié)構(gòu)A是（）。

(A)線性結(jié)構(gòu)(B)樹型結(jié)構(gòu)(C)物理結(jié)構(gòu)(D)圖型結(jié)構(gòu) 2．下面程序的時間復(fù)雜為（）

for（i=1，s=0； i<=n； i++）{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；}(A)O(n)(B)O(n2)(C)O(n3)(D)O(n4)3．設(shè)指針變量p指向單鏈表中結(jié)點A，若刪除單鏈表中結(jié)點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；p->data=q->data；free(q)；

4．設(shè)有n個待排序的記錄關(guān)鍵字，則在堆排序中需要（）個輔助記錄單元。

(A)1(B)n(C)nlog2n(D)n2

5．設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(20，15，14，18，21，36，40，10)，則以20為基準記錄的一趟快速排序結(jié)束后的結(jié)果為()。(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，21 6．設(shè)二叉排序樹中有n個結(jié)點，則在二叉排序樹的平均平均查找長度為（）。(A)O(1)(B)O(log2n)(C)(D)O(n)7．設(shè)無向圖G中有n個頂點e條邊，則其對應(yīng)的鄰接表中的表頭結(jié)點和表結(jié)點的個數(shù)分別為（）。

(A)n，e(B)e，n(C)2n，e(D)n，2e 8.設(shè)某強連通圖中有n個頂點，則該強連通圖中至少有（）條邊。

(A)n(n-1)(B)n+1(C)n(D)n(n+1)9．設(shè)有5000個待排序的記錄關(guān)鍵字，如果需要用最快的方法選出其中最小的10個記錄關(guān)鍵字，則用下列（）方法可以達到此目的。

(A)快速排序(B)堆排序(C)歸并排序(D)插入排序 10.下列四種排序中（）的空間復(fù)雜度最大。

(A)插入排序(B)冒泡排序(C)堆排序(D)歸并排序

二、填空殖(48分，其中最后兩小題各6分)1.1.數(shù)據(jù)的物理結(jié)構(gòu)主要包括_____________和______________兩種情況。

2.2.設(shè)一棵完全二叉樹中有500個結(jié)點，則該二叉樹的深度為__________；若用二叉鏈表作為該完全二叉樹的存儲結(jié)構(gòu)，則共有___________個空指針域。

3.3.設(shè)輸入序列為1、2、3，則經(jīng)過棧的作用后可以得到___________種不同的輸出序列。

4.4.設(shè)有向圖G用鄰接矩陣A[n][n]作為存儲結(jié)構(gòu)，則該鄰接矩陣中第i行上所有元素之和等于頂點i的________，第i列上所有元素之和等于頂點i的________。

5.5.設(shè)哈夫曼樹中共有n個結(jié)點，則該哈夫曼樹中有________個度數(shù)為1的結(jié)點。6.6.設(shè)有向圖G中有n個頂點e條有向邊，所有的頂點入度數(shù)之和為d，則e和d的關(guān)系為_________。

7.7.__________遍歷二叉排序樹中的結(jié)點可以得到一個遞增的關(guān)鍵字序列（填先序、中序或后序）。

8.8.設(shè)查找表中有100個元素，如果用二分法查找方法查找數(shù)據(jù)元素X，則最多需要比較________次就可以斷定數(shù)據(jù)元素X是否在查找表中。

9.9.不論是順序存儲結(jié)構(gòu)的棧還是鏈式存儲結(jié)構(gòu)的棧，其入棧和出棧操作的時間復(fù)雜度均為____________。

10.10.設(shè)有n個結(jié)點的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號，則第i個結(jié)點的雙親結(jié)點編號為____________，右孩子結(jié)點的編號為___________。11.11.設(shè)一組初始記錄關(guān)鍵字為(72，73，71，23，94，16，5)，則以記錄關(guān)鍵字72為基準的一趟快速排序結(jié)果為___________________________。

12.12.設(shè)有向圖G中有向邊的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，則該圖的一種拓撲序列為____________________。

13.13.下列算法實現(xiàn)在順序散列表中查找值為x的關(guān)鍵字，請在下劃線處填上正確的語句。

struct record{int key;int others;};int hashsqsearch(struct record hashtable[ ],int k){ int i,j;j=i=k % p;while(hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____)%m;if(i==j)return(-1);}

if(_______________________)return(j);else return(-1);} 14.14.下列算法實現(xiàn)在二叉排序樹上查找關(guān)鍵值k，請在下劃線處填上正確的語句。

typedef struct node{int 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_____________;}

數(shù)據(jù)結(jié)構(gòu)試卷

（三）參考答案

一、選擇題

1.B 2.B 3.A 4.A 5.A 6.B 7.D 8.C 9.B 10.D 第3小題分析：首先用指針變量q指向結(jié)點A的后繼結(jié)點B，然后將結(jié)點B的值復(fù)制到結(jié)點A中，最后刪除結(jié)點B。

第9小題分析：9快速排序、歸并排序和插入排序必須等到整個排序結(jié)束后才能夠求出最小的10個數(shù)，而堆排序只需要在初始堆的基礎(chǔ)上再進行10次篩選即可，每次篩選的時間復(fù)雜度為O(log2n)。

二、填空題

1.1.順序存儲結(jié)構(gòu)、鏈式存儲結(jié)構(gòu) 2.2.9，501 3.3.5 4.4.出度，入度 5.5.0 6.6.e=d 7.7.中序 8.8.7 9.9.O(1)10.10.i/2，2i+1 11.11.(5，16，71，23，72，94，73)12.12.(1，4，3，2)13.13.j+1，hashtable[j].key==k 14.14.return(t)，t=t->rchild 第8小題分析：二分查找的過程可以用一棵二叉樹來描述，該二叉樹稱為二叉判定樹。在有序表上進行二分查找時的查找長度不超過二叉判定樹的高度1+log2n。

}

數(shù)據(jù)結(jié)構(gòu)試卷

（四）一、選擇題(30分)1．設(shè)一維數(shù)組中有n個數(shù)組元素，則讀取第i個數(shù)組元素的平均時間復(fù)雜度為（）。(A)O(n)(B)O(nlog2n)(C)O(1)(D)O(n)2．設(shè)一棵二叉樹的深度為k，則該二叉樹中最多有（）個結(jié)點。

(A)2k-1(B)2k(C)2k-1(D)2k-1 3．設(shè)某無向圖中有n個頂點e條邊，則該無向圖中所有頂點的入度之和為（）。

(A)n(B)e(C)2n(D)2e 4．在二叉排序樹中插入一個結(jié)點的時間復(fù)雜度為（）。

(A)O(1)(B)O(n)(C)O(log2n)(D)O(n2)5．設(shè)某有向圖的鄰接表中有n個表頭結(jié)點和m個表結(jié)點，則該圖中有（）條有向邊。

(A)n(B)n-1(C)m(D)m-1 6．設(shè)一組初始記錄關(guān)鍵字序列為(345，253，674，924，627)，則用基數(shù)排序需要進行（）趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。

(A)3(B)4(C)5(D)8 7．設(shè)用鏈表作為棧的存儲結(jié)構(gòu)則退棧操作（）。

(A)必須判別棧是否為滿(B)必須判別棧是否為空

(C)判別棧元素的類型(D)對棧不作任何判別 8．下列四種排序中（）的空間復(fù)雜度最大。

(A)快速排序(B)冒泡排序(C)希爾排序(D)堆

9．設(shè)某二叉樹中度數(shù)為0的結(jié)點數(shù)為N0，度數(shù)為1的結(jié)點數(shù)為Nl，度數(shù)為2的結(jié)點數(shù)為N2，則下列等式成立的是（）。

(A)N0=N1+1(B)N0=Nl+N2(C)N0=N2+1(D)N0=2N1+l 10.設(shè)有序順序表中有n個數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過（）。

(A)log2n+1(B)log2n-1(C)log2n(D)log2(n+1)

二、填空題(42分)1． 1． 設(shè)有n個無序的記錄關(guān)鍵字，則直接插入排序的時間復(fù)雜度為________，快速排序的平均時間復(fù)雜度為_________。

2． 2． 設(shè)指針變量p指向雙向循環(huán)鏈表中的結(jié)點X，則刪除結(jié)點X需要執(zhí)行的語句序列為_________________________________________________________（設(shè)結(jié)點中的兩個指針域分別為llink和rlink）。3． 3． 根據(jù)初始關(guān)鍵字序列(19，22，01，38，10)建立的二叉排序樹的高度為____________。4． 4． 深度為k的完全二叉樹中最少有____________個結(jié)點。5． 5． 設(shè)初始記錄關(guān)鍵字序列為(K1，K2，…，Kn)，則用篩選法思想建堆必須從第______個元素開始進行篩選。

6． 6． 設(shè)哈夫曼樹中共有99個結(jié)點，則該樹中有_________個葉子結(jié)點；若采用二叉鏈表作為存儲結(jié)構(gòu)，則該樹中有_____個空指針域。

7． 7． 設(shè)有一個順序循環(huán)隊列中有M個存儲單元，則該循環(huán)隊列中最多能夠存儲________個隊列元素；當前實際存儲________________個隊列元素（設(shè)頭指針F指向當前隊頭元素的前一個位置，尾指針指向當前隊尾元素的位置）。

8． 8． 設(shè)順序線性表中有n個數(shù)據(jù)元素，則第i個位置上插入一個數(shù)據(jù)元素需要移動表中_______個數(shù)據(jù)元素；刪除第i個位置上的數(shù)據(jù)元素需要移動表中_______個元素。9． 9． 設(shè)一組初始記錄關(guān)鍵字序列為(20，18，22，16，30，19)，則以20為中軸的一趟快速排序結(jié)果為______________________________。

10．10．設(shè)一組初始記錄關(guān)鍵字序列為(20，18，22，16，30，19)，則根據(jù)這些初始關(guān)鍵字序列建成的初始堆為________________________。

11．11．設(shè)某無向圖G中有n個頂點，用鄰接矩陣A作為該圖的存儲結(jié)構(gòu)，則頂點i和頂點j互為鄰接點的條件是______________________。

12．12．設(shè)無向圖對應(yīng)的鄰接矩陣為A，則A中第i上非0元素的個數(shù)_________第i列上非0元素的個數(shù)（填等于，大于或小于）。

13．13．設(shè)前序遍歷某二叉樹的序列為ABCD，中序遍歷該二叉樹的序列為BADC，則后序遍歷該二叉樹的序列為_____________。

14．14．設(shè)散列函數(shù)H(k)=k mod p，解決沖突的方法為鏈地址法。要求在下列算法劃線處填上正確的語句完成在散列表hashtalbe中查找關(guān)鍵字值等于k的結(jié)點，成功時返回指向關(guān)鍵字的指針，不成功時返回標志0。

typedef struct node {int key;struct node *next;} lklist;void createlkhash(lklist *hashtable[ ]){ int i,k;lklist *s;for(i=0;ikey=a[i];k=a[i] % p;s->next=hashtable[k];_______________________;} }

數(shù)據(jù)結(jié)構(gòu)試卷

（四）參考答案

一、選擇題

1．C 2．D 3．D 4．B 5．C 6．A 7．B 8．A 9．C 10．A

二、填空題

1.1.O(n2)，O(nlog2n)2.2.p>llink->rlink=p->rlink;p->rlink->llink=p->rlink 3.3.3 4.4.2k-1 5.5.n/2 6.6.50，51 7.7.m-1，(R-F+M)%M 8.8.n+1-i，n-i 9.9.(19，18，16，20，30，22)10.10.(16，18，19，20，32，22)11.11.A[i][j]=1 12.12.等于 13.13.BDCA 14.14.hashtable[i]=0，hashtable[k]=s

數(shù)據(jù)結(jié)構(gòu)試卷

（五）一、選擇題(30分)

1．數(shù)據(jù)的最小單位是（）。

(A)數(shù)據(jù)項(B)數(shù)據(jù)類型(C)數(shù)據(jù)元素(D)數(shù)據(jù)變量

2．設(shè)一組初始記錄關(guān)鍵字序列為(50，40，95，20，15，70，60，45)，則以增量d=4的一趟希爾排序結(jié)束后前4條記錄關(guān)鍵字為（）。

(A)40，50，20，95(B)15，40，60，20(C)15，20，40，45(D)45，40，15，20 3．設(shè)一組初始記錄關(guān)鍵字序列為(25，50，15，35，80，85，20，40，36，70)，其中含有5個長度為2的有序子表，則用歸并排序的方法對該記錄關(guān)鍵字序列進行一趟歸并后的結(jié)果為（）。

(A)15，25，35，50，20，40，80，85，36，70(B)15，25，35，50，80，20，85，40，70，36(C)15，25，35，50，80，85，20，36，40，70(D)15，25，35，50，80，20，36，40，70，85 4．函數(shù)substr(“DATASTRUCTURE”，5，9)的返回值為（）。

(A)“STRUCTURE”(B)“DATA”

(C)“ASTRUCTUR”(D)“DATASTRUCTURE” 5．設(shè)一個有序的單鏈表中有n個結(jié)點，現(xiàn)要求插入一個新結(jié)點后使得單鏈表仍然保持有序，則該操作的時間復(fù)雜度為（）。

(A)O(log2n)(B)O(1)(C)O(n2)(D)O(n)6．設(shè)一棵m叉樹中度數(shù)為0的結(jié)點數(shù)為N0，度數(shù)為1的結(jié)點數(shù)為Nl，……，度數(shù)為m的結(jié)點數(shù)為Nm，則N0=（）。

(A)Nl+N2+……+Nm

(B)l+N2+2N3+3N4+……+(m-1)Nm(C)N2+2N3+3N4+……+(m-1)Nm(D)2Nl+3N2+……+(m+1)Nm

7．設(shè)有序表中有1000個元素，則用二分查找查找元素X最多需要比較（）次。

(A)25(B)10(C)7(D)1 8．設(shè)連通圖G中的邊集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點序列為（）。

(A)abedfc(B)acfebd(C)aebdfc(D)aedfcb 9．設(shè)輸入序列是1、2、3、……、n，經(jīng)過棧的作用后輸出序列的第一個元素是n，則輸出序列中第i個輸出元素是（）。

(A)n-i(B)n-1-i(C)n+1-i(D)不能確定 設(shè)一組初始記錄關(guān)鍵字序列為(45，80，55，40，42，85)，則以第一個記錄關(guān)鍵字45為基準而得到一趟快速排序的結(jié)果是（）。

(A)40，42，45，55，80，83(B)42，40，45，80，85，88(C)42，40，45，55，80，85(D)42，40，45，85，55，80

二、填空題(共30分)1.1.設(shè)有一個順序共享棧S[0：n-1]，其中第一個棧項指針top1的初值為-1，第二個棧頂指針top2的初值為n，則判斷共享棧滿的條件是____________________。

2.2.在圖的鄰接表中用順序存儲結(jié)構(gòu)存儲表頭結(jié)點的優(yōu)點是____________________。

3.3.設(shè)有一個n階的下三角矩陣A，如果按照行的順序?qū)⑾氯蔷仃囍械脑兀ò▽蔷€上元素）存放在n(n+1)個連續(xù)的存儲單元中，則A[i][j]與A[0][0]之間有_______個數(shù)據(jù)元素。

4.4.棧的插入和刪除只能在棧的棧頂進行，后進棧的元素必定先出棧，所以又把棧稱為__________表；隊列的插入和刪除運算分別在隊列的兩端進行，先進隊列的元素必定先出隊列，所以又把隊列稱為_________表。

5.5.設(shè)一棵完全二叉樹的順序存儲結(jié)構(gòu)中存儲數(shù)據(jù)元素為ABCDEF，則該二叉樹的前序遍歷序列為___________，中序遍歷序列為___________，后序遍歷序列為___________。

6.6.設(shè)一棵完全二叉樹有128個結(jié)點，則該完全二叉樹的深度為________，有__________個葉子結(jié)點。

7.7.設(shè)有向圖G的存儲結(jié)構(gòu)用鄰接矩陣A來表示，則A中第i行中所有非零元素個數(shù)之和等于頂點i的________，第i列中所有非零元素個數(shù)之和等于頂點i的__________。

8.8.設(shè)一組初始記錄關(guān)鍵字序列(k1，k2，……，kn)是堆，則對i=1，2，…，n/2而言滿足的條件為_______________________________。

9.9.下面程序段的功能是實現(xiàn)冒泡排序算法，請在下劃線處填上正確的語句。void bubble(int r[n]){ for(i=1;i<=n-1;i++){ for(exchange=0,j=0;j<_____________;j++)

if(r[j]>r[j+1]){temp=r[j+1];______________;r[j]=temp;exchange=1;} if(exchange==0)return； } } 10.10.下面程序段的功能是實現(xiàn)二分查找算法，請在下劃線處填上正確的語句。struct record{int key;int others;};int bisearch(struct record r[ ], int k){

int low=0,mid,high=n-1;

while(low<=high){

________________________________;

if(r[mid].key==k)return(mid+1);else if(____________)high=mid-1;else low=mid+1;

}

return(0);}

三、應(yīng)用題(24分)

1.1.設(shè)某棵二叉樹的中序遍歷序列為DBEAC，前序遍歷序列為ABDEC，要求給出該二叉樹的的后序遍歷序列。2.2.設(shè)無向圖G（如右圖所示），給出該圖的最小生成樹上邊的集合并計算最小生成樹各邊上的權(quán)值之和。

3.3.設(shè)一組初始記錄關(guān)鍵字序列為(15，17，18，22，35，51，60)，要求計算出成功查找時的平均查找長度。

4.4.設(shè)散列表的長度為8，散列函數(shù)H(k)=k mod 7，初始記錄關(guān)鍵字序列為(25，31，8，27，13，68)，要求分別計算出用線性探測法和鏈地址法作為解決沖突方法的平均查找長度。

數(shù)據(jù)結(jié)構(gòu)試卷

（五）參考答案

一、選擇題 1．A 2．B 3．A 4．A 5．D 6．B 7．B 8．B 9．C 10．C

二、填空題

1.1.top1+1=top2 2.2.可以隨機訪問到任一個頂點的簡單鏈表

3.3.i(i+1)/2+j-1 4.4.FILO，F(xiàn)IFO 5.5.ABDECF，DBEAFC，DEBFCA 6.6.8，64 7.7.出度，入度

8.8.ki<=k2i && ki<=k2i+1 9.9.n-i，r[j+1]=r[j] 10.10.mid=(low+high)/2，r[mid].key>k

三、應(yīng)用題

1.1.DEBCA 2.2.E={(1,5),(5,2),(5,3),(3,4)},W=10 3.3.ASL=(1*1+2*2+3*4)/7=17/7 4.4.ASL1=7/6，ASL2=4/3

數(shù)據(jù)結(jié)構(gòu)試卷

（六）一、選擇題(30分)1． 設(shè)一組權(quán)值集合W={2，3，4，5，6}，則由該權(quán)值集合構(gòu)造的哈夫曼樹中帶權(quán)路徑長度之和為（）。

(A)20(B)30(C)40(D)45 2．執(zhí)行一趟快速排序能夠得到的序列是（）。

(A)[41，12，34，45，27] 55 [72，63](B)[45，34，12，41] 55 [72，63，27](C)[63，12，34，45，27] 55 [41，72](D)[12，27，45，41] 55 [34，63，72] 3．設(shè)一條單鏈表的頭指針變量為head且該鏈表沒有頭結(jié)點，則其判空條件是（）。(A)head==0(B)head->next==0(C)head->next==head(D)head!=0 4．時間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog2n)的是（）。

(A)堆排序(B)冒泡排序(C)希爾排序(D)快速排序

5．設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（）。

(A)空或只有一個結(jié)點(B)高度等于其結(jié)點數(shù)

(C)任一結(jié)點無左孩子(D)任一結(jié)點無右孩子

6．一趟排序結(jié)束后不一定能夠選出一個元素放在其最終位置上的是（）。

(A)堆排序(B)冒泡排序(C)快速排序(D)希爾排序 7．設(shè)某棵三叉樹中有40個結(jié)點，則該三叉樹的最小高度為（）。

(A)3(B)4(C)5(D)6 8．順序查找不論在順序線性表中還是在鏈式線性表中的時間復(fù)雜度為（）。

21/2(A)O(n)(B)O(n)(C)O(n)(D)O(1og2n)9．二路歸并排序的時間復(fù)雜度為（）。(A)O(n)(B)O(n)(C)O(nlog2n)(D)O(1og2n)10.深度為k的完全二叉樹中最少有（）個結(jié)點。

(A)2k-1-1(B)2k-1(C)2k-1+1(D)2k-1 11.設(shè)指針變量front表示鏈式隊列的隊頭指針，指針變量rear表示鏈式隊列的隊尾指針，指針變量s指向?qū)⒁腙犃械慕Y(jié)點X，則入隊列的操作序列為（）。

(A)front->next=s；front=s；(B)s->next=rear；rear=s；

(C)rear->next=s；rear=s；(D)s->next=front；front=s；

12.設(shè)某無向圖中有n個頂點e條邊，則建立該圖鄰接表的時間復(fù)雜度為（）。(A)O(n+e)(B)O(n)(C)O(ne)(D)O(n)13.設(shè)某哈夫曼樹中有199個結(jié)點，則該哈夫曼樹中有（）個葉子結(jié)點。

(A)99(B)100(C)101(D)102 14.設(shè)二叉排序樹上有n個結(jié)點，則在二叉排序樹上查找結(jié)點的平均時間復(fù)雜度為（）。(A)O(n)(B)O(n)(C)O(nlog2n)(D)O(1og2n)15.設(shè)用鄰接矩陣A表示有向圖G的存儲結(jié)構(gòu)，則有向圖G中頂點i的入度為（）。

(A)第i行非0元素的個數(shù)之和(B)第i列非0元素的個數(shù)之和

(C)第i行0元素的個數(shù)之和(D)第i列0元素的個數(shù)之和

二、判斷題(20分)1．調(diào)用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點。（）

2．分塊查找的平均查找長度不僅與索引表的長度有關(guān)，而且與塊的長度有關(guān)。（）3．冒泡排序在初始關(guān)鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。（）4．滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。（）

5．設(shè)一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。（）6．層次遍歷初始堆可以得到一個有序的序列。（）

7．設(shè)一棵樹T可以轉(zhuǎn)化成二叉樹BT，則二叉樹BT中一定沒有右子樹。（）8．線性表的順序存儲結(jié)構(gòu)比鏈式存儲結(jié)構(gòu)更好。（）

9．中序遍歷二叉排序樹可以得到一個有序的序列。（）10.快速排序是排序算法中平均性能最好的一種排序。（）

三、填空題(30分)1．for(i=1，t=1，s=0；i<=n；i++){t=t*i；s=s+t；}的時間復(fù)雜度為_________。

2．設(shè)指針變量p指向單鏈表中結(jié)點A，指針變量s指向被插入的新結(jié)點X，則進行插入操作的語句序列為__________________________（設(shè)結(jié)點的指針域為next）。3．設(shè)有向圖G的二元組形式表示為G =（D，R），D={1，2，3，4，5}，R={r}，r={<1,2>，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>}，則給出該圖的一種拓撲排序序列__________。4．設(shè)無向圖G中有n個頂點，則該無向圖中每個頂點的度數(shù)最多是_________。5．設(shè)二叉樹中度數(shù)為0的結(jié)點數(shù)為50，度數(shù)為1的結(jié)點數(shù)為30，則該二叉樹中總共有_______個結(jié)點數(shù)。

6．設(shè)F和R分別表示順序循環(huán)隊列的頭指針和尾指針，則判斷該循環(huán)隊列為空的條件為_____________________。

7．設(shè)二叉樹中結(jié)點的兩個指針域分別為lchild和rchild，則判斷指針變量p所指向的結(jié)點為葉子結(jié)點的條件是_____________________________________________。8．簡單選擇排序和直接插入排序算法的平均時間復(fù)雜度為___________。

9．快速排序算法的空間復(fù)雜度平均情況下為__________，最壞的情況下為__________。10.散列表中解決沖突的兩種方法是_____________和_____________。

數(shù)據(jù)結(jié)構(gòu)試卷

（六）參考答案

一、選擇題 1．D 2．A 3．A 4．A 5．D 6．D 7．B 8．A 9．C 10．B 11．C 12．A 13．B 14．D 15．B

二、判斷題

1．錯 2．對 3．對 4．對 5．錯 6．錯 7．對 8．錯 9．對 10．對

三、填空題

1.1.O(n)2.2.s->next=p->next;p->next=s 3.3.(1，3，2，4，5)4.4.n-1 5.5.129 6.6.F==R 7.7.p->lchild==0&&p->rchild==0 8.8.O(n2)9.9.O(nlog2n)，O(n)10.10.開放定址法，鏈地址法

數(shù)據(jù)結(jié)構(gòu)試卷

（七）一、選擇題(30分)1．設(shè)某無向圖有n個頂點，則該無向圖的鄰接表中有（）個表頭結(jié)點。

(A)2n(B)n(C)n/2(D)n(n-1)2．設(shè)無向圖G中有n個頂點，則該無向圖的最小生成樹上有（）條邊。

(A)n(B)n-1(C)2n(D)2n-1 3．設(shè)一組初始記錄關(guān)鍵字序列為(60，80，55，40，42，85)，則以第一個關(guān)鍵字45為基準而得到的一趟快速排序結(jié)果是（）。

(A)40，42，60，55，80，85(B)42，45，55，60，85，80(C)42，40，55，60，80，85(D)42，40，60，85，55，80 4．（）二叉排序樹可以得到一個從小到大的有序序列。

(A)先序遍歷(B)中序遍歷(C)后序遍歷(D)層次遍歷

5．設(shè)按照從上到下、從左到右的順序從1開始對完全二叉樹進行順序編號，則編號為i結(jié)點的左孩子結(jié)點的編號為（）。

(A)2i+1(B)2i(C)i/2(D)2i-1 6．程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的時間復(fù)雜度為（）。(A)O(n)(B)O(nlog2n)(C)O(n)(D)O(n/2)7．設(shè)帶有頭結(jié)點的單向循環(huán)鏈表的頭指針變量為head，則其判空條件是（）。

(A)head==0(B)head->next==0(C)head->next==head(D)head!=0 8．設(shè)某棵二叉樹的高度為10，則該二叉樹上葉子結(jié)點最多有（）。

(A)20(B)256(C)512(D)1024 9．設(shè)一組初始記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90，115，134),則利用二分法查找關(guān)鍵字90需要比較的關(guān)鍵字個數(shù)為（）。

(A)1(B)2(C)3(D)4 10.設(shè)指針變量top指向當前鏈式棧的棧頂，則刪除棧頂元素的操作序列為（）。

(A)top=top+1;(B)top=top-1;(C)top->next=top;(D)top=top->next;

三、填空題(30分)1.1.設(shè)指針變量p指向雙向鏈表中的結(jié)點A，指針變量s指向被插入的結(jié)點X，則在結(jié)點A的后面插入結(jié)點X的操作序列為_________=p；s->right=p->right；__________=s； p->right->left=s；（設(shè)結(jié)點中的兩個指針域分別為left和right）。2.2.設(shè)完全有向圖中有n個頂點，則該完全有向圖中共有________條有向條；設(shè)完全無向圖中有n個頂點，則該完全無向圖中共有________條無向邊。

3.3.設(shè)關(guān)鍵字序列為(Kl，K2，…，Kn)，則用篩選法建初始堆必須從第______個元素開始進行篩選。

4.4.解決散列表沖突的兩種方法是________________和__________________。

5.5.設(shè)一棵三叉樹中有50個度數(shù)為0的結(jié)點，21個度數(shù)為2的結(jié)點，則該二叉樹中度數(shù)為3的結(jié)點數(shù)有______個。

6.6.高度為h的完全二叉樹中最少有________個結(jié)點，最多有________個結(jié)點。7.7.設(shè)有一組初始關(guān)鍵字序列為(24，35，12，27，18，26)，則第3趟直接插入排序結(jié)束后的結(jié)果的是__________________________________。

8.8.設(shè)有一組初始關(guān)鍵字序列為(24，35，12，27，18，26)，則第3趟簡單選擇排序結(jié)束后的結(jié)果的是__________________________________。

9.9.設(shè)一棵二叉樹的前序序列為ABC，則有______________種不同的二叉樹可以得到這種序列。

10.10.下面程序段的功能是實現(xiàn)一趟快速排序，請在下劃線處填上正確的語句。

struct record {int key;datatype others;};void quickpass(struct record r[], int s, int t, int &i){

int j=t;struct record x=r[s];i=s;

while(i

while(ix.key)j=j-1;if(i

while(____________________)i=i+1;if(i

}

_________________;}

數(shù)據(jù)結(jié)構(gòu)試卷

（七）一、選擇題 1．B 2．B 3．C 4．B 6．A 7．C 8．C 9．B

三、填空題

1.1.s->left=p，p->right 2.2.n(n-1)，n(n-1)/2 3.3.n/2 4.4.開放定址法，鏈地址法 5.5.14 6.6.2h-1，2h-1 7.7.(12，24，35，27，18，26)8.8.(12，18，24，27，35，26)9.9.5 10.10.i

5．B 10．D

數(shù)據(jù)結(jié)構(gòu)試卷

（八）一、選擇題(30分)1.1.字符串的長度是指（）。

(A)串中不同字符的個數(shù)(B)串中不同字母的個數(shù)

(C)串中所含字符的個數(shù)(D)串中不同數(shù)字的個數(shù) 2.2.建立一個長度為n的有序單鏈表的時間復(fù)雜度為（）

(A)O(n)(B)O(1)(C)O(n2)(D)O(log2n)3.3.兩個字符串相等的充要條件是（）。

(A)兩個字符串的長度相等(B)兩個字符串中對應(yīng)位置上的字符相等

(C)同時具備(A)和(B)兩個條件(D)以上答案都不對 4.4.設(shè)某散列表的長度為100，散列函數(shù)H(k)=k % P，則P通常情況下最好選擇（）。

(A)99(B)97(C)91(D)93 5.5.在二叉排序樹中插入一個關(guān)鍵字值的平均時間復(fù)雜度為（）。(A)O(n)(B)O(1og2n)(C)O(nlog2n)(D)O(n)6.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.7.設(shè)一棵完全二叉樹中有65個結(jié)點，則該完全二叉樹的深度為（）。

(A)8(B)7(C)6(D)5 8.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.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.10.隊列是一種（）的線性表。

(A)先進先出(B)先進后出(C)只能插入(D)只能刪除

三、填空題(30分)1． 1． 設(shè)一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27，50)，則以d=4為增量的一趟希爾排序結(jié)束后的結(jié)果為_____________________________。

2． 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． 3． 設(shè)指針變量p指向單鏈表中結(jié)點A，指針變量s指向被插入的結(jié)點X，則在結(jié)點A的后面插入結(jié)點X需要執(zhí)行的語句序列：s->next=p->next;_________________。4． 4． 設(shè)指針變量head指向雙向鏈表中的頭結(jié)點，指針變量p指向雙向鏈表中的第一個結(jié)點，則指針變量p和指針變量head之間的關(guān)系是p=_________和head=__________（設(shè)結(jié)點中的兩個指針域分別為llink和rlink）。

5． 5． 設(shè)某棵二叉樹的中序遍歷序列為ABCD，后序遍歷序列為BADC，則其前序遍歷序列為__________。

6． 6． 完全二叉樹中第5層上最少有__________個結(jié)點，最多有_________個結(jié)點。7． 7． 設(shè)有向圖中不存在有向邊，則其對應(yīng)的鄰接矩陣A中的數(shù)組元素A[i][j]的值等于____________。

8． 8． 設(shè)一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27，50)，則第4趟直接選擇排序結(jié)束后的結(jié)果為_____________________________。

9． 9． 設(shè)連通圖G中有n個頂點e條邊，則對應(yīng)的最小生成樹上有___________條邊。10． 10． 設(shè)有一組初始記錄關(guān)鍵字序列為(50，16，23，68，94，70，73)，則將它們調(diào)整成初始堆只需把16與___________相互交換即可。

數(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.1.(49，13，27，50，76，38，65，97)2.2.t=(bitree *)malloc(sizeof(bitree))，bstinsert(t->rchild,k)3.3.p->next=s 4.4.head->rlink，p->llink 5.5.CABD 6.6.1，16 7.7.0 8.8.(13，27，38，50，76，49，65，97)9.9.n-1 10.10.50

第三篇：2013臺灣省數(shù)據(jù)結(jié)構(gòu)試題及答案（推薦）

1、串的邏輯結(jié)構(gòu)與（D）的邏輯結(jié)構(gòu)不相同。A）線性表 B）棧 C）隊列 D）集合

2、廣義表head(((a,b),(c,d)))的運算結(jié)果為（A）。A）(a,b)B）(c,d)C）空表 D）（（a,b）,(c,d)）

3、鏈式存儲的存儲結(jié)構(gòu)所占存儲空間（A）。

A）分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針 B）只有一部分，存放結(jié)點值

C）只有一部分，存儲表示結(jié)點間關(guān)系的指針

D）分兩部分，一部分存放結(jié)點值，另一部分存放結(jié)點所占單元數(shù)

4、設(shè)單鏈表中指針p指向結(jié)點m，若要刪除m之后的結(jié)點（若存在），則需修改指針的操作為（A）。

A）p->next=p->next->next;B）p=p->next;C）p=p->next->next;D）p->next=p;

5、在一個具有n個單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，當做出棧處理時，top變化為（C）。

A）top不變 B）top=0 C）top--D）top++

6、數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容是（D）。

A）數(shù)據(jù)的邏輯結(jié)構(gòu) B）數(shù)據(jù)的存儲結(jié)構(gòu)

C）建立在相應(yīng)邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)上的算法 D）包括以上三個方面

7、向一個棧頂指針為hs的鏈棧中插入一個s結(jié)點時，應(yīng)執(zhí)行（D）。A)hs->next=s;

B)s->next=hs->next;hs->next=s;C)s->next=hs;hs=s;D)s->next=hs;hs=hs->next;

8、設(shè)一數(shù)列的順序為1，2，3，4，5，6，通過棧結(jié)構(gòu)不可能排成的順序數(shù)列為（B）。A）3，2，5，6，4，1 B）1，5，4，6，2，3 C）2，4，3，5，1，6 D）4，5，3，6，2，1

9、廣義表head(((a,b),(c,d)))的運算結(jié)果為（A）。A）(a,b)B）(c,d)C）空表 D）（（a,b）,(c,d)）

10、若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點的個數(shù)是(B)。A）9 B）11 C）15 D）不能確定

11、在一個鏈隊列中，假定front和rear分別為隊首和隊尾指針，則刪除一個結(jié)點的操作為（B）。A)rear=rear->next;B)front=front->next;C)rear=front->next;

D)front=rear->next;

12、n個頂點的圖的最小生成樹必定（D），是不正確的描述。A）不唯一 B）權(quán)的總和唯一 C）不含回路 D）有n條邊

13、串的邏輯結(jié)構(gòu)與（D）的邏輯結(jié)構(gòu)不同。A）線性表 B）棧 C）隊列 D）樹

第四篇：數(shù)據(jù)結(jié)構(gòu)試卷及參考答案_10

數(shù)據(jù)結(jié)構(gòu)試卷

（十）一、選擇題(24分)1．下列程序段的時間復(fù)雜度為（）。

i=0，s=0； while(s

(A)單向鏈表

(B)單向循環(huán)鏈表(C)雙向鏈表

(D)雙向循環(huán)鏈表

3．設(shè)指針q指向單鏈表中結(jié)點A，指針p指向單鏈表中結(jié)點A的后繼結(jié)點B，指針s指向被插入的結(jié)點X，則在結(jié)點A和結(jié)點B插入結(jié)點X的操作序列為（）。(A)s->next=p->next；p->next=-s；(B)q->next=s； s->next=p；(C)p->next=s->next；s->next=p；(D)p->next=s；s->next=q；

4．設(shè)輸入序列為1、2、3、4、5、6，則通過棧的作用后可以得到的輸出序列為（）。(A)5，3，4，6，1，2(B)3，2，5，6，4，1(C)3，1，2，5，4，6(D)1，5，4，6，2，3 5．設(shè)有一個10階的下三角矩陣A（包括對角線），按照從上到下、從左到右的順序存儲到連續(xù)的55個存儲單元中，每個數(shù)組元素占1個字節(jié)的存儲空間，則A[5][4]地址與A[0][0]的地址之差為（）。

(A)10(B)19(C)28(D)55 6．設(shè)一棵m叉樹中有N1個度數(shù)為1的結(jié)點，N2個度數(shù)為2的結(jié)點，……，Nm個度數(shù)為m的結(jié)點，則該樹中共有（）個葉子結(jié)點。

(A)?(i?1)Ni?1mi(B)

?Ni?1mi(C)

?Ni?2mi(D)1??(i?1)Ni?2mi

7.二叉排序樹中左子樹上所有結(jié)點的值均（）根結(jié)點的值。

(A)<(B)>(C)=(D)!= 8.設(shè)一組權(quán)值集合W=(15，3，14，2，6，9，16，17)，要求根據(jù)這些權(quán)值集合構(gòu)造一棵哈夫曼樹，則這棵哈夫曼樹的帶權(quán)路徑長度為（）。

(A)129(B)219(C)189(D)229 9.設(shè)有n個關(guān)鍵字具有相同的Hash函數(shù)值，則用線性探測法把這n個關(guān)鍵字映射到HASH表中需要做（）次線性探測。

(A)n2(B)n(n+1)(C)n(n+1)/2(D)n(n-1)/2 10.設(shè)某棵二叉樹中只有度數(shù)為0和度數(shù)為2的結(jié)點且度數(shù)為0的結(jié)點數(shù)為n，則這棵二叉中共有（）個結(jié)點。

(A)2n(B)n+l(C)2n-1(D)2n+l

11.設(shè)一組初始記錄關(guān)鍵字的長度為8，則最多經(jīng)過（）趟插入排序可以得到有序序列。

(A)6(B)7(C)8(D)9 12.設(shè)一組初始記錄關(guān)鍵字序列為(Q，H，C，Y，P，A，M，S，R，D，F(xiàn)，X)，則按字母升序的第一趟冒泡排序結(jié)束后的結(jié)果是（）。(A)F，H，C，D，P，A，M，Q，R，S，Y，X(B)P，A，C，S，Q，D，F(xiàn)，X，R，H，M，Y(C)A，D，C，R，F(xiàn)，Q，M，S，Y，P，H，X(D)H，C，Q，P，A，M，S，R，D，F(xiàn)，X，Y

二、填空題(48分，其中最后兩小題各6分)1.設(shè)需要對5個不同的記錄關(guān)鍵字進行排序，則至少需要比較_____________次，至多需要比較_____________次。

2.快速排序算法的平均時間復(fù)雜度為____________，直接插入排序算法的平均時間復(fù)雜度為___________。

3.設(shè)二叉排序樹的高度為h，則在該樹中查找關(guān)鍵字key最多需要比較_________次。4.設(shè)在長度為20的有序表中進行二分查找，則比較一次查找成功的結(jié)點數(shù)有_________個，比較兩次查找成功有結(jié)點數(shù)有_________個。

5.設(shè)一棵m叉樹脂的結(jié)點數(shù)為n，用多重鏈表表示其存儲結(jié)構(gòu)，則該樹中有_________個空指針域。

6.設(shè)指針變量p指向單鏈表中結(jié)點A，則刪除結(jié)點A的語句序列為：

q=p->next；p->data=q->data；p->next=___________；feee(q)；

7.數(shù)據(jù)結(jié)構(gòu)從邏輯上劃分為三種基本類型：___________、__________和___________。8.設(shè)無向圖G中有n個頂點e條邊，則用鄰接矩陣作為圖的存儲結(jié)構(gòu)進行深度優(yōu)先或廣度優(yōu)先遍歷時的時間復(fù)雜度為_________；用鄰接表作為圖的存儲結(jié)構(gòu)進行深度優(yōu)先或廣度優(yōu)先遍歷的時間復(fù)雜度為_________。

9.設(shè)散列表的長度為8，散列函數(shù)H(k)=k %7，用線性探測法解決沖突，則根據(jù)一組初始關(guān)鍵字序列(8，15，16，22，30，32)構(gòu)造出的散列表的平均查找長度是________。10.設(shè)一組初始關(guān)鍵字序列為(38，65，97，76，13，27，10)，則第3趟冒泡排序結(jié)束后的結(jié)果為_____________________。

11.設(shè)一組初始關(guān)鍵字序列為(38，65，97，76，13，27，10)，則第3趟簡單選擇排序后的結(jié)果為______________________。

12.設(shè)有向圖G中的有向邊的集合E={<1，2>，<2，3>，<1，4>，<4，5>，<5，3>，<4，6>，<6，5>}，則該圖的一個拓撲序列為_________________________。

13.下面程序段的功能是建立二叉樹的算法，請在下劃線處填上正確的內(nèi)容。

typedefstruct node{int data;struct node*lchild;________________;}bitree;void createbitree(bitree *&bt){ scanf(“%c”,&ch);if(ch=='#')___________;else { bt=(bitree*)malloc(sizeof(bitree));bt->data=ch;________;createbitree(bt->rchild);} } 14.下面程序段的功能是利用從尾部插入的方法建立單鏈表的算法，請在下劃線處填上正確的內(nèi)容。

typedef struct node {int data;struct node *next;} lklist;void lklistcreate(_____________ *&head){

for(i=1;i<=n;i++){ p=(lklist *)malloc(sizeof(lklist));scanf(“%d”,&(p->data));p->next=0;if(i==1)head=q=p;else {q->next=p;____________;} } }

三、算法設(shè)計題(22分)1． 設(shè)計在鏈式存儲結(jié)構(gòu)上合并排序的算法。2． 設(shè)計在二叉排序樹上查找結(jié)點X的算法。

3． 設(shè)關(guān)鍵字序列(k1，k2，…，kn-1)是堆，設(shè)計算法將關(guān)鍵字序列(k1，k2，…，kn-1，x)調(diào)整為堆。

數(shù)據(jù)結(jié)構(gòu)試卷

（十）參考答案

一、選擇題 1．A 2．D 7．A 8．D 3．B 9．D 4．B 10．C 5．B 11．B 6．D 12．D

二、填空題 1.4，10 2.O(nlog2n)，O(n2)3.n 4.1，2 5.6.7.8.n(m-1)+1 q->next 線性結(jié)構(gòu)，樹型結(jié)構(gòu)，圖型結(jié)構(gòu) O(n2)，O(n+e)9.8/3 10.(38，13，27，10，65，76，97)11.(10，13，27，76，65，97，38)12.124653 13.struct node *rchild，bt=0，createbitree(bt->lchild)14.lklist，q=p

三、算法設(shè)計題

1.設(shè)計在鏈式存儲結(jié)構(gòu)上合并排序的算法。

void mergelklist(lklist *ha,lklist *hb,lklist *&hc){

lklist *s=hc=0;

while(ha!=0 && hb!=0)

if(ha->datadata){if(s==0)hc=s=ha;else {s->next=ha;s=ha;};ha=ha->next;}

else {if(s==0)hc=s=hb;else {s->next=hb;s=hb;};hb=hb->next;}

if(ha==0)s->next=hb;else s->next=ha;} 2.設(shè)計在二叉排序樹上查找結(jié)點X的算法。

bitree *bstsearch1(bitree *t, int key){

bitree *p=t;

while(p!=0)if(p->key==key)return(p);else if(p->key>key)p=p->lchild;else p=p->rchild;

return(0);} 3.設(shè)關(guān)鍵字序列(k1，k2，…，kn-1)是堆，設(shè)計算法將關(guān)鍵字序列(k1，k2，…，kn-1，x)調(diào)整為堆。

void adjustheap(int r[ ],int n){

int j=n,i=j/2,temp=r[j-1];

while(i>=1)if(temp>=r[i-1])break;else{r[j-1]=r[i-1];j=i;i=i/2;}

r[j-1]=temp;}

第五篇：2012廣西壯族自治區(qū)JAVA版數(shù)據(jù)結(jié)構(gòu)試題及答案

1、下列序列中，執(zhí)行第一趟快速排序后得到的序列是（A）。A）[d,a,e,d,b]f[h,g] B)[c,e,a,d]f[h,g,b] C)[g,a,e,c,b]f[d,h] D)[a,b,c,d,]f[e,g,h]

2、設(shè)給定問題的規(guī)模為變量n，解決該問題的算法所需時間為Tn=O(f(n)),Tn表示式中記號O表示（A）。

A）一個數(shù)量級別 B）一個平均值 C）一個最大值 D）一個均方值

3、（C）在進行插入操作時，常產(chǎn)生假溢出現(xiàn)象。A）順序棧 B）循環(huán)隊列 C）順序隊列 D）鏈隊列

4、設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a??11為第一個元素，其存儲地址為1，每元素占1個地址空間，則a85的地址為（B）。A）13 B）33 C）18 D）40

5、n個頂點的圖的最小生成樹必定（D），是不正確的描述。A）不唯一 B）權(quán)的總和唯一

C）不含回路 D）有n條邊

6、用一維數(shù)組A進行順序存儲時，若起始地址為loc(A1)，元素長度為c，則A的第i個數(shù)組單元在存放地址loc(Ai)，等于（B）。A）loc(A1)+i*c B）loc(A1)+(i-1)*c C）loc(A1)+i*c+1 D）loc(A1)+(i+1)*c

7、與無向圖相關(guān)的術(shù)語有（C）。A）強連通圖 B）入度 C）路徑 D）弧

8、鏈式存儲的存儲結(jié)構(gòu)所占存儲空間（A）。

A）分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針 B）只有一部分，存放結(jié)點值

C）只有一部分，存儲表示結(jié)點間關(guān)系的指針

D）分兩部分，一部分存放結(jié)點值，另一部分存放結(jié)點所占單元數(shù)

9、若采用鄰接矩陣法存儲一個n個頂點的無向圖，則該鄰接矩陣是一個（D）。A）上三角矩陣 B)稀疏矩陣 C)對角矩陣 D)對稱矩陣

10、在一個具有n個單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，當做出棧處理時，top變化為（C）。

A）top不變 B）top=0 C）top--D）top++

11、棧進行插入和刪除操作的特點是（A）。A）LIFO B）FIFO C）FCFS D）HPF

12、與無向圖相關(guān)的術(shù)語有（C）。A）強連通圖 B）入度 C）路徑 D）弧

13、n個頂點，e條邊的有向圖的鄰接矩陣中非零元素有（C）個。A）n B）2e C）e D）n+e

14、已知棧的最大容量為4。若進棧序列為1，2，3，4，5，6，且進棧和出?？梢源┎暹M行,則可能出現(xiàn)的出棧序列為（C）。

A)5，4，3，2，1，6

B)2，3，5，6，1，4 C)3，2，5，4，1，6

D)1，4，6，5，2，3

15、在一個鏈隊列中，假定front和rear分別為隊首和隊尾指針，則刪除一個結(jié)點的操作為（B）。

A)rear=rear->next;B)front=front->next;C)rear=front->next;

D)front=rear->next;