軟件學(xué)院2017年數(shù)據(jù)結(jié)構(gòu)考試試題集

數(shù)據(jù)結(jié)構(gòu)模擬題

及參考答案

2016年

數(shù)據(jù)結(jié)構(gòu)考試復(fù)習(xí)資料

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

一、單選題

1、棧和隊列的共同特點(diǎn)是（A）。

A、只允許在端點(diǎn)處插入和刪除元素B、都是先進(jìn)后出C、都是先進(jìn)先出D、沒有共同點(diǎn)

2、用無頭結(jié)點(diǎn)鏈接方式存儲的隊列，在進(jìn)行插入運(yùn)算時（D）.

A.僅修改頭指針B、頭、尾指針都要修改C.僅修改尾指針D、頭、尾指針可能都要修改

3、以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)？（D）

A、隊列B、棧C、線性表D、二叉樹

4、設(shè)有一個二維數(shù)組冊加，假設(shè)/0][0]存放位置在644（必加2][2]存放位置在676（⑹

每個元素占一個空間，問加3][3]＜助存放在什么位置？腳注表示用10進(jìn)制表示。（C）

A、688B、678C、692D、696

5、樹最適合用來表示（C）。

A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無聯(lián)

系的數(shù)據(jù)

6、二叉樹的第K層的結(jié)點(diǎn)數(shù)最多為（D）.

A、2-1B、2K+1C、2*'+1D、2門

7、若有18個元素的有序表存放在一維數(shù)組A[19]中，第一個元素放A[l]中，現(xiàn)進(jìn)行二分查

找，則查找A[3]的比較序列的下標(biāo)依次為（D）

A、1,2,3B、9,5,2,3C、9,5,3D、9,4,2,3

8、對于線性表（7,34,55,25,64,46,20,10）進(jìn)行散列存儲時，若選用H（K）=K%9

作為散列函數(shù)，則散列地址為1的元素有（D）個，

A、1B、2C,3D、4

10、設(shè)有6個結(jié)點(diǎn)的無向圖，該圖至少應(yīng)有（A）條邊才能確保是一個連通圖。

A、5B、6C、71）、8

二、填空題

1.通常從四個方面評價算法的質(zhì)量：（正確性）、（可讀性）、（健壯性）和（效率與低存儲

量）。

2.一個算法的時間復(fù)雜度為（才+dlog2加14〃）//,其數(shù)量級表示為（O（n）

3.假定一棵樹的廣義表表示為A（C,D（E,F,G）,H（I,J））,則樹中所含的結(jié)點(diǎn)數(shù)為

（9）個，樹的深度為（3）,樹的度為（3）。

4.后綴算式923+-102/-的值為（-1）。中綴算式（3+4X）-2Y/3對應(yīng)的后綴算式

為（34X*+2Y*3/-）。

5.若用鏈表存儲一棵二叉樹時，每個結(jié)點(diǎn)除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個指

針。在這種存儲結(jié)構(gòu)中，n個結(jié)點(diǎn)的二叉樹共有（2n）個指針域，其中有（nT）個指

針域是存放了地址，有（n+1）個指針是空指針。

6.對于一個具有n個頂點(diǎn)和e條邊的有向圖和無向圖，在其對應(yīng)的鄰接表中，所含邊結(jié)點(diǎn)

分別有（e）個和（2e）個。

7.A0V網(wǎng)是一種（有向無回路）的圖。

8.在一個具有n個頂點(diǎn)的無向完全圖中，包含有（n（n-l）/2）條邊，在一個具有n個頂

點(diǎn)的有向完全圖中，包含有（n（n-l））條邊。

9.假定一個線性表為（12,23,74,55,63,40）,若按Key%4條件進(jìn)行劃分，使得同一余數(shù)

的元素成為一個子表，則得到的四個子表分別為（12,40）、（74）、（23,55,63）和（）。

10.在堆排序的過程中，對任一分支結(jié)點(diǎn)進(jìn)行篩選運(yùn)算的時間復(fù)雜度為（0（log2n））,整個

堆排序過程的時間復(fù)雜度為（0（nlog2n））o

11.在快速排序、堆排序、歸并排序中，（歸并）排序是穩(wěn)定的。

三、計算題

1.在如下數(shù)組A中鏈接存儲了一個線性表，表頭指針為A[0].next,試寫出該線性表。

第-1-頁

數(shù)據(jù)結(jié)構(gòu)考試復(fù)習(xí)資料

A01234567

data605078903440

next3572041

參考答案：線性表為：(78,50,40,60,

2、請畫出下圖的鄰接矩陣和鄰接表

參考答案：

-01110'

10101

11011

10101

鄰接矩陣：111°-

鄰接表：

41nMlME

3、已知一個圖的頂點(diǎn)集V和邊集E分別為:V={1,2,3,4,5,6,7};

E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5

,6)18,(6,7)25};用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各

條邊。

參考答案：用克魯斯卡爾算法得到的最小生成樹為：

(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)20

5、畫出向小根堆中加入數(shù)據(jù)4,2,5,8,3時，每加入一個數(shù)據(jù)后堆的變化。

參考答案：

四、閱讀算法

1、LinkListmynote(LinkListL)

第-2-頁

數(shù)據(jù)結(jié)構(gòu)考試復(fù)習(xí)資料

{//L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針

if(L&&L->next){

q=L；L=L—>next；p=L；

SI：while(p—>next)p=p—>next；

S2：p—>next=q；q—>next=NULL；

}

returnL；

}

請回答下列問題：

(1)說明語句SI的功能。(2)說明語句組S2的功能。

(3)設(shè)鏈表表示的線性表為(al,a2,…,an),寫出算法執(zhí)行后的返回值所表示的線性表。

參考答案：

(1)查詢鏈表的尾結(jié)點(diǎn)

(2)將第一個結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)點(diǎn)

(3)返回的線性表為(a2,a3,--,an,ai)o

2、voidABC(BTNode*BT)

(

ifBT{

ABC(BT->left);

ABC(BT->right);

cout<<BT->data?";

)

)

該算法的功能是：

參考答案：遞歸地后序遍歷鏈?zhǔn)酱鎯Φ亩鏄?/p>

五、算法填空

二叉搜索樹的查找——遞歸算法：

BOOLFind(BTreeNode*BST,ElemTypefeitem)

{if(BST==NULL)

returnfalse;〃查找失敗

else{

if(item==BST->data){

item=BST->data;〃查找成功

return(true);}

elseif(item<BST->data)

returnFind(BST->left,item);

elsereturnFind(BST->right,item);

}//if

)

大、編寫算法

統(tǒng)計出單鏈表HL中結(jié)點(diǎn)的值等于給定值X的結(jié)點(diǎn)數(shù)。

第-3-頁

數(shù)據(jù)結(jié)構(gòu)考試復(fù)習(xí)資料

intCountX(LNode*HL,ElemTypex)

參考答案：

intCountX(LNode*HL,ElemTypex)

{inti=0;LNode*p=HL;//i為計數(shù)器

while(p!=NULL)

{if(P->data==x)i++;

p=p->next;

}//while,出循環(huán)時i中的值即為x結(jié)點(diǎn)個數(shù)

returni;

}//CountX

第-4-頁

數(shù)據(jù)結(jié)構(gòu)考試復(fù)習(xí)資料

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

一、選擇題

1.下面關(guān)于線性表的敘述錯誤的是(D)。

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

B、線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲空間

C、線性表采用鏈?zhǔn)酱鎯Ρ阌诓迦牒蛣h除操作的實現(xiàn)

D、線性表采用順序存儲便于插入和刪除操作的實現(xiàn)

2.設(shè)哈夫曼樹中的葉子結(jié)點(diǎn)總數(shù)為m,若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈夫曼樹中總共

有(B)個空指針域。

A、2m-1B、2mC、2m+lD、4m

3.設(shè)順序循環(huán)隊列Q[0：MT]的頭指針和尾指針分別為F和R,頭指針F總是指向隊頭元素

的前一位置，尾指針R總是指向隊尾元素的當(dāng)前位置，則該循環(huán)隊列中的元素個數(shù)為

(C)。

A、R-FB、F-RC、(R-F+M)D、(F-R+M)%M

4.設(shè)某棵二叉樹的中序遍歷序列為ABCD,前序遍歷序列為CABD,則后序遍歷該二叉樹

得到序列為(A)。

A、BADCB、BCDAC、CDABD、CBDA

5.設(shè)某完全無向圖中有n個頂點(diǎn)，則該完全無向圖中有(A)條邊。

A、n(n-l)/2B、n(n-l)C、n2D、n2T

6.設(shè)某棵二叉樹中有2000個結(jié)點(diǎn)，則該二叉樹的最小高度為(C)。

A、9B、10C、11D、12

7.設(shè)某有向圖中有n個頂點(diǎn)，則該有向圖對應(yīng)的鄰接表中有(B)個表頭結(jié)點(diǎn)。

A、n-1B、nC、n+1D、2n-l

8.設(shè)一組初始記錄關(guān)鍵字序列(5,2,6,3,8),以第一個記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快

速排序的結(jié)果為(C)?

A、2,3,5,8,6B、3,2,5,8,6

C^3,2,5,6,8D、2,3,6,5,8

二、填空題

1.為了能有效地應(yīng)用HASH查找技術(shù)，必須解決的兩個問題是(構(gòu)造一個好的HASH函數(shù))

和(確定解決沖突的方法)。

2.下面程序段的功能實現(xiàn)數(shù)據(jù)x進(jìn)棧，要求在括號處填上正確的語句。

typedefstruct{ints[100];inttop;}sqstack;

voidpush(sqstack&stack,intx)

(

if(stack.top==m-l)printff'overflow");

else{(stack,s[stack.top]=x);(stack.top++);}

)

3.中序遍歷二叉排序樹所得到的序列是(有序)序列(填有序或無序)。

4.快速排序的最壞時間復(fù)雜度為(0(rd),平均時間復(fù)雜度為(O(nlogzn))。

第-5-頁

數(shù)據(jù)結(jié)構(gòu)考試復(fù)習(xí)資料

5.設(shè)某棵二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為No,度數(shù)為1的結(jié)點(diǎn)數(shù)為N?則該二叉樹中度數(shù)為

2的結(jié)點(diǎn)數(shù)為(No-1)；若采用二叉鏈表作為該二叉樹的存儲結(jié)構(gòu)，則該二叉樹中共有

(2No+N,)個空指針域。

6.設(shè)某無向圖中頂點(diǎn)數(shù)和邊數(shù)分別為n和e,所有頂點(diǎn)的度數(shù)之和為d,則6=(d/2)。

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

的初始堆為(31,38,44,56,75,80,55,63)。

8.已知一有向圖的鄰接表存儲結(jié)構(gòu)如下：從頂點(diǎn)1出發(fā)，DFS遍歷的輸出序列是

(1,3,4,5,2),BFS遍歷的輸出序列是(1,3,2,4,5)。

圖的鄰接表存儲結(jié)構(gòu)

三、應(yīng)用題

1.設(shè)一組初始記錄關(guān)鍵字序列為(45,80,48,40,22,78),則分別給出第4趟簡單選擇

排序和第4趟直接插入排序后的結(jié)果。

參考答案：(22,40,45,48,80,78),(40,45,48,80,22,78)

2.設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A,指針變量q指向被插入結(jié)點(diǎn)B,要求給出在結(jié)點(diǎn)A

的后面插入結(jié)點(diǎn)B的操作序列(設(shè)雙向鏈表中結(jié)點(diǎn)的兩個指針域分別為llink和rlink)。

參考答案：q->llink=p;q->rlink=p->rlink;p->rlink->llink=q;p->rlink=q;

3.設(shè)一組有序的記錄關(guān)鍵字序列為(13,18,24,35,47,50,62,83,90),查找方法用

二分查找，要求計算出查找關(guān)鍵字62時的比較次數(shù)并計算出查找成功時的平均查找長度。

參考答案：2,ASL=(1*1+2*2+3*4+4*2)=25/9

4.設(shè)有無向圖G,要求給出用普里姆算法構(gòu)造最小生成樹所走過的邊的集合。

參考答案：E={(1,3),(1,2),(3,5),(5,6),(6,4))

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

出構(gòu)造過程。

第-6-頁

數(shù)據(jù)結(jié)構(gòu)考試復(fù)習(xí)資料

參考答案:

四、算法設(shè)計題

1.設(shè)有一組初始記錄關(guān)鍵字序列(K”心，…，K,,),要求設(shè)計一個算法能夠在0(n)的時間

復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個關(guān)鍵字均小于右半部分的每個關(guān)

鍵字均大于等于及。

參考答案：

voidquickpass(intr[],ints,intt)

(

inti=s,j=t,x=r[s];

while(i<j){

while(i<j&&r|j]>x)j=j-l;if(i<j){r[i]=r|j];i=i+l;)

while(i<j&&r[ij<x)i=i+l;if(i<j){r[j]=r[i];j=j-l;}

}

r[i]=x;

}

2.設(shè)有兩個集合A和集合B,要求設(shè)計生成集合C=ACB的算法，其中集合A、B和C用

鏈?zhǔn)酱鎯Y(jié)構(gòu)表示。

參考答案：

typedefstructnode{intdata;structnode*next;)lklist;

voidintersection(lklist*ha,lklist*hb,lklist*&hc)

{

Iklist*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->dala)break;

if(q!=O){t=(lklist*)malloc(sizeof(lklist));t->data=p->data;t->next=hc;hc=t;}

第-7-頁

數(shù)據(jù)結(jié)構(gòu)考試復(fù)習(xí)資料

第-8-頁

數(shù)據(jù)結(jié)構(gòu)考試復(fù)習(xí)資料

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

一、選擇題

1.下面程序的時間復(fù)雜為(B)

for(i=l,s=0：i<=n；i++){t=l；for(j=l：j<=i；j++)t=t*j；s=s+t；}

A、0(n)B、0(n2)C、0(/)D、0(n)

3.設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A,若刪除單鏈表中結(jié)點(diǎn)A,則需要修改指針的操作序

列為（A）。

A、q=p->next；p->data=q->data；p->next=q->next；free(q)；

B、q=p->next；q->dataz: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）個輔助記錄單元。

A、1B、nC>nlog2nD、n2

5.設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為（20,15,14,18,21,36,40,10）,則以20為基準(zhǔn)記

錄的一趟快速排序結(jié)束后的結(jié)果為（A)o

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,21

D、15,10,14,18,20,36,40,21

6.設(shè)二叉排序樹中有n個結(jié)點(diǎn)，則在二叉排序樹的平均平均查找長度為（B）o

A、0(1)B、Odogsn)C、0(n)D、0(n2)

7.設(shè)無向圖G中有n個頂點(diǎn)e條邊,則其對應(yīng)的鄰接表中的表頭結(jié)點(diǎn)和表結(jié)點(diǎn)的個數(shù)分別

為（D）。

A、n,eB、e,nC、2n,eD、n,2e

8.設(shè)某強(qiáng)連通圖中有n個頂點(diǎn)，則該強(qiáng)連通圖中至少有（C）條邊。

A^n(n-l)B、n+1C、nD、n(n+1)

9.設(shè)有5000個待排序的記錄關(guān)鍵字，如果需要用最快的方法選出其中最小的10個記錄關(guān)

鍵字，則用下列（B）方法可以達(dá)到此目的。

A、快速排序B、堆排序C、歸并排序D、插入排序

10.下列四種排序中(D)的空間復(fù)雜度最大。

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

填空題

1數(shù)據(jù)的物理結(jié)構(gòu)主要包括（順序存儲結(jié)構(gòu)）和（鏈?zhǔn)酱鎯Y(jié)構(gòu)）兩種情況。

2設(shè)一棵完全二叉樹中有500個結(jié)點(diǎn)，則該二叉樹的深度為（9）；若用二叉鏈表作為該完

全二叉樹的存儲結(jié)構(gòu)，則共有（501）個空指針域。

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

4設(shè)有向圖G用鄰接矩陣A[n][n]作為存儲結(jié)構(gòu)，則該鄰接矩陣中第i行上所有元素之和

等于頂點(diǎn)i的（出度），第i列上所有元素之和等于頂點(diǎn)i的（入度）。

5設(shè)哈夫曼樹中共有n個結(jié)點(diǎn)，則該哈夫曼樹中有（0）個度數(shù)為1的結(jié)點(diǎn)。

6設(shè)有向圖G中有n個頂點(diǎn)e條有向邊，所有的頂點(diǎn)入度數(shù)之和為d,則e和d的關(guān)系為

（e=d）o

第-9-頁

數(shù)據(jù)結(jié)構(gòu)考試復(fù)習(xí)資料

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

序)。

8.設(shè)查找表中有100個元素，如果用二分法查找方法查找數(shù)據(jù)元素X,則最多需要比較(7)

次就可以斷定數(shù)據(jù)元素X是否在查找表中。

9.不論是順序存儲結(jié)構(gòu)的棧還是鏈?zhǔn)酱鎯Y(jié)構(gòu)的棧，其入棧和出棧操作的時間復(fù)雜度均為

(0(l))o

10.設(shè)有n個結(jié)點(diǎn)的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號，則第

i個結(jié)點(diǎn)的雙親結(jié)點(diǎn)編號為(i/2),右孩子結(jié)點(diǎn)的編號為(2i+l)。

11.設(shè)一組初始記錄關(guān)鍵字為(72,73,71,23,94,16,5),則以記錄關(guān)鍵字72為基準(zhǔn)的

一趟快速排序結(jié)果為((5,16,71,23,72,94,73))。

12.設(shè)有向圖G中有向邊的集合￡={<1,2>,<2,3>,<1,4>,<4,2>,<4,3>},則該圖

的一種拓?fù)湫蛄袨?(1,4,3,2))。

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

structrecord{intkey;intothers;};

inthashsqsearch(structrecordhashtable[],intk)

(

intij;j=i=k%p;

while(hashtablefj].key!=k&&hashtablefj].flag!=O){j=((j+1))%m;

if(i==j)retum(-l);}

if((hashtable[j].key==k))return(j);elsereturn(-l);

)

14.下列算法實現(xiàn)在二叉排序樹上查找關(guān)鍵值k,請在下劃線處填上正確的語句。

typedefstructnode{intkey;structnode*lchild;structnode*rchild;}bitree;

bitree*bstsearch(bitree*t,intk)

(

if(t==0)retum(O);elsewhile(t!=0)

if(t->key==k)(return(t));elseif(t->key>k)t=t->lchild;

else(t=t->rchild);

)

三、計算題

1.已知二叉樹的前序遍歷序列是AEFBGCDHIKJ,中序遍歷序列是EFAGBCHKIJD,畫出此

二叉樹,，并畫出它的后序線索二叉樹。

參考答案：

第-10-頁

數(shù)據(jù)結(jié)構(gòu)考試復(fù)習(xí)資料

2.已知待散列的線性表為(36,15,40,63,22),散列用的一維地址空間為[0..6],假定

選用的散列函數(shù)是H(K)=Kmod7,若發(fā)生沖突采用線性探查法處理，試：

(1)計算出每一個元素的散列地址并在下圖中填寫出散列表：

0123456

(2)求出在查找每一個元素概率相等情況下的平均查找長度。

參考答案:

H(36)=36mod7=1;H1(22)=(l+l)mod7=2;.…沖突

H(15)=15mod7=1;....沖突H2(22)=(2+l)mod7=3;

Hi(15)=(l+l)mod7=2;

H(40)=40mod7=5;

H(63)=63mod7=0;

H(22)=22mod7=1;….沖突

6

6336152240

1+2+1+1+3

(2)ASL==1.6

5

3.己知序列(10,18,4,3,6,12,1,9,]8,8)請用快速排序?qū)懗雒恳惶伺判虻慕Y(jié)果。

參考答案：

(8,9,4,3,6,1),10,(12,18.18)

(1,6,4,3),8,(9),10,12,(18,18)

1,(3,4,6),8,9,10,12,18,(18)

1,3,(4,6),8,9,10,12,18,18

1,3,4,6,8,9,10,12,18,18

四、算法設(shè)計題

1.設(shè)計在單鏈表中刪除值相同的多余結(jié)點(diǎn)的算法。

參考答案：

typedefintdatatype;

typedefstructnode{datatypedata;structnode*next;)lklist;

voiddelredundant(lklist*&head)

第-11-頁

數(shù)據(jù)結(jié)構(gòu)考試復(fù)習(xí)資料

Iklist*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.設(shè)計一個求結(jié)點(diǎn)x在二叉樹中的雙親結(jié)點(diǎn)算法。

參考答案：

typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;

bitree*q[20];intr=0,f=0,flag=0;

voidpreorder(bitree*bt,charx)

(

if(bt!=O&&nag==0)

if(bt->data==x){flag=l;return;}

else{r=(r+l)%20;q|r]=bt;preorder(bt->lchild,x);preorder(bt->rchild,x);}

)

voidparent(bitree*bt,charx)

(

inti;

preorder(bt,x);

for(i=f+1;i<=r;i++)if(q[i]->lchild->data==x||q[i]->rchild->data)break;

if(flag==O)printf(unotfoundx\nM);

elseif(i<=r)printf(n%c",bt->data);elseprintf("notparent");

第-12?頁

數(shù)據(jù)結(jié)構(gòu)考試復(fù)習(xí)資料

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

一、選擇題

1.設(shè)一維數(shù)組中有n個數(shù)組元素，則讀取第i個數(shù)組元素的平均時間復(fù)雜度為（C）。

A、0（n）B、O（nlogzn）C、0（1）D、0（n2）

2.設(shè)一棵二叉樹的深度為k,則該二叉樹中最多有（D）個結(jié)點(diǎn)。

A、2k-lB、2kC、2卜,D、2k-l

3.設(shè)某無向圖中有n個頂點(diǎn)e條邊，則該無向圖中所有頂點(diǎn)的入度之和為（D）。

A、nB、eC、2nD^2e

4.在二叉排序樹中插入一個結(jié)點(diǎn)的時間復(fù)雜度為（B）。

2

A、0（1）B、0（n）C、0（1og2n）D、0（n）

5.設(shè)某有向圖的鄰接表中有n個表頭結(jié)點(diǎn)和m個表結(jié)點(diǎn)，則該圖中有（C）條有向邊。

A、nB、n-lC、mD、m-l

6.設(shè)一組初始記錄關(guān)鍵字序列為（345,253,674,924,627）,則用基數(shù)排序需要進(jìn)行（A）

趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。

A、3B、4C、5D、8

7.設(shè)用鏈表作為棧的存儲結(jié)構(gòu)則退棧操作（B）。

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

C、判別棧元素的類型D、對棧不作任何判別

8.下列四種排序中（A）的空間復(fù)雜度最大。

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

9.設(shè)某二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為No,度數(shù)為1的結(jié)點(diǎn)數(shù)為N?度數(shù)為2的結(jié)點(diǎn)數(shù)為N2,

則下列等式成立的是（C

、No=M+lB、C、D、

ANO=N1+N2NO=N2+1N0=2NI+1

10.設(shè)有序順序表中有n個數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不

超過（A）。

A、logzn+lB、log2n-lC、logznD、log2（n+l）

二、填空題

1.設(shè)有n個無序的記錄關(guān)鍵字，則直接插入排序的時間復(fù)雜度為（0（d））,快速排序的

平均時間復(fù)雜度為（O（nlogzn））。

2.設(shè)指針變量p指向雙向循環(huán)鏈表中的結(jié)點(diǎn)X,則刪除結(jié)點(diǎn)X需要執(zhí)行的語句序列為

（p>11ink->r1ink=p->rlink;p->r1ink->llink=p->r1ink）（設(shè)結(jié)點(diǎn)中的兩個指針域

分別為llink和rlink）o

3.根據(jù)初始關(guān)鍵字序列（19,22,01,38,10）建立的二叉排序樹的高度為（3）。

4.深度為k的完全二叉樹中最少有（2-）個結(jié)點(diǎn)。

5.設(shè)初始記錄關(guān)鍵字序列為（K“⑹，…，K,,）,則用篩選法思想建堆必須從第（n/2）個

元素開始進(jìn)行篩選。

6.設(shè)哈夫曼樹中共有99個結(jié)點(diǎn)，則該樹中有（50）個葉子結(jié)點(diǎn)；若采用二叉鏈表作為存

儲結(jié)構(gòu)，則該樹中有（51）個空指針域。

7.設(shè)有一個順序循環(huán)隊列中有M個存儲單元，則該循環(huán)隊列中最多能夠存儲（m-l）個隊

列元素；當(dāng)前實際存儲（（R-F+M）%M）個隊列元素（設(shè)頭指針F指向當(dāng)前隊頭元素的前

一個位置，尾指針指向當(dāng)前隊尾元素的位置）。

第-13-頁

數(shù)據(jù)結(jié)構(gòu)考試復(fù)習(xí)資料

8.設(shè)順序線性表中有n個數(shù)據(jù)元素，則第i個位置上插入一個數(shù)據(jù)元素需要移動表中

(n+1-i)個數(shù)據(jù)元素；刪除第i個位置上的數(shù)據(jù)元素需要移動表中(n-i)個元素。

9.設(shè)一組初始記錄關(guān)鍵字序列為(20,18,22,16,30,19),則以20為中軸的一趟快速

排序結(jié)果為((19,18,16,20,30,22))。

10.設(shè)一組初始記錄關(guān)鍵字序列為(20,18,22,16,30,19),則根據(jù)這些初始關(guān)鍵字序列

建成的初始堆為((16,18,19,20,32,22))。

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

互為鄰接點(diǎn)的條件是(

12.設(shè)無向圖對應(yīng)的鄰接矩陣為A,則A中第i上非0元素的個數(shù)(等于)第i列上非0元

素的個數(shù)(填等于，大于或小于)。

13.設(shè)前序遍歷某二叉樹的序列為ABCD,中序遍歷該二叉樹的序列為BADC,則后序遍歷

該二叉樹的序列為(BDCA)。

14.設(shè)散列函數(shù)H(k尸kmodp,解決沖突的方法為鏈地址法。要求在下列算法劃線處填上正

確的語句完成在散列表hashtalbe中查找關(guān)鍵字值等于k的結(jié)點(diǎn)，成功時返回指向關(guān)鍵

字的指針，不成功時返回標(biāo)志0。

typedefstructnode{intkey;structnode*next;}Iklist;

voidcreatelkhash(lklist*hashtable[])

(

inti,k;Iklist*s；

for(i=0;i<m;i++)(hashtable[i]=O);

for(i=0;i<n;i++)

(

s=(lklist*)malloc(sizeof(lklist));s->key=a[i];

k=a[ij%p;s->next=hashtable[k];(hashtable[k]=s);

)

)

三、計算題

3、設(shè)散列表的地址范圍是[0..9],散列函數(shù)為H(key)=(key2+2)MOD9,并采用鏈

表處理沖突，請畫出元素7、4、5、3、6、2、8、9依次插入散列表的存儲結(jié)構(gòu)。

參考答案：

H(4)=H(5)=0,H(3)=H(6)=H(9)=2,H(8)=3,H(2)=H(7)=6

0二

1

2二引3|6-)9

3

4

5

6

7

8

9

第-14-頁

數(shù)據(jù)結(jié)構(gòu)考試復(fù)習(xí)資料

四、算法設(shè)計題

1.設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符)，要求利用原單鏈表

中結(jié)點(diǎn)空間設(shè)計出三個單鏈表的算法，使每個單鏈表只包含同類字符。

參考答案：

typedefchardatatype;

typedefstructnode{datatypedata;structnode*next;}lklist;

voidsplit(lklist*head,lklist*&ha,lklist*&hb,lklist*&hc)

{

Iklist*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<='Z'){p->next=ha;ha=p;}

elseif(p->data>='0'&&p->data<='9'){p->next=hb;hb=p;)else{p->next=hc;hc=p;)

)

)

2.設(shè)計在鏈?zhǔn)酱鎯Y(jié)構(gòu)上交換二叉樹中所有結(jié)點(diǎn)左右子樹的算法。

參考答案：

typedefstructnode{intdata;structnode*lchild,*rchild;}bitree;

voidswapbitree(bitree*bl)

(

bitree*p;

if(bt==O)return;

swapbitree(bt->lchild);swapbitree(bt->rchild);

p=bt->lchild;bt->lchild=bt->rchild;bt->rchild=p;

)

3.在鏈?zhǔn)酱鎯Y(jié)構(gòu)上建立一棵二叉排序樹。

參考答案：

#definen10

typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;

voidbstinsert(bitree*&bt,intkey)

(

if(bt==O){bt=(bitree*)malloc(sizeof(bitree));bt->key=key;bt->lchild=bt->rchild=O;}

elseif(bt->key>key)bstinsert(bt->lchild,key);elsebstinsert(bt->rchild,key);

)

voidcreatebsttree(bitree*&bl)

(

inti;

for(i=l;i<=n;i++)bstinsert(bt,random(100));

第-15?頁

數(shù)據(jù)結(jié)構(gòu)考試復(fù)習(xí)資料

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

一、選擇題

1.數(shù)據(jù)的最小單位是(A)。

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)鍵字為(B).

A、40,50,20,95B、15,40,60,20

C、15,20,40,45D、45,40,15,20

3.設(shè)一組初始記錄關(guān)鍵字序列為(25,50,15,35,80,85,20,40,36,70),其中含有5

個長度為2的有序子表，則用歸并排序的方法對該記錄關(guān)鍵字序列進(jìn)行一趟歸并后的結(jié)

果為(A)。

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è)一個有序的單鏈表中有n個結(jié)點(diǎn)，現(xiàn)要求插入一個新結(jié)點(diǎn)后使得單鏈表仍然保持有序,

則該操作的時間復(fù)雜度為(D)。

A、O(logzn)B、0(1)C、0(n2)D、0(n)

6.設(shè)一棵m叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N”度數(shù)為1的結(jié)點(diǎn)數(shù)為N”……，度數(shù)為m的結(jié)

點(diǎn)數(shù)為Nm,則N產(chǎn)(B).

A、NI+N2+...+NmB、I+N2+2N3+3M+....+(m-l)Nm

C、N2+2N3+3N4+...+(m-l)NmD、2NI+3N2+....+(m+l)Nm

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

A、25B、10C、7D、1

8.設(shè)連通圖G中的邊集￡={3，b),(a,e),(a,c),(b,e),(e,d),(d,f)>(f，c)},則從

頂點(diǎn)a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點(diǎn)序列為(B)。

A^abedfcB、acfebdC、aebdfcD、aedfcb

9.設(shè)輸入序列是1、2、3、……、n,經(jīng)過棧的作用后輸出序列的第一個元素是n,則輸出

序列中第i個輸出元素是(C)o

A、n-iB、n-l-iC、n+1-iI)、不能確定

10設(shè)一組初始記錄關(guān)鍵字序列為(45,80,55,40,42,85),則以第一個記錄關(guān)鍵字45

為基準(zhǔn)而得到一趟快速排序的結(jié)果是(C)。

A、40,42,45,55,80,83B,42,40,45,80,85,88

C、42,40,45,55,80,85D、42,40,45,85,55,80

二、填空題

1.設(shè)有一個順序共享棧S[0：n-1],其中第一個棧項指針topi的初值為T,第二個棧頂

指針top2的初值為n,則判斷共享棧滿的條件是(topl+l=top2)。

2.在圖的鄰接表中用順序存儲結(jié)構(gòu)存儲表頭結(jié)點(diǎn)的優(yōu)點(diǎn)是(可以隨機(jī)訪問到任一個頂點(diǎn)的

簡單鏈表)。

3.設(shè)有一個n階的下三角矩陣A,如果按照行的順序?qū)⑾氯蔷仃囍械脑?包括對角線

上元素)存放在n(n+l)個連續(xù)的存儲單元中，則與A[0][0]之間有

(i(i+l)/2+_j-l)個數(shù)據(jù)元素。

第-16■■頁

數(shù)據(jù)結(jié)構(gòu)考試復(fù)習(xí)資料

4.棧的插入和刪除只能在棧的棧頂進(jìn)行，后進(jìn)棧的元素必定先出棧，所以又把棧稱為

(FILO)表；隊列的插入和刪除運(yùn)算分別在隊列的兩端進(jìn)行，先進(jìn)隊列的元素必定先出

隊列，所以又把隊列稱為(FIFO)表。

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

序列為(ABDECF),中序遍歷序列為(DBEAFC),后序遍歷序列為(DEBFCA)。

6.設(shè)一棵完全二叉樹有128個結(jié)點(diǎn)，則該完全二叉樹的深度為(8),有(64)個葉子結(jié)點(diǎn)。

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

于頂點(diǎn)i的(出度)，第i列中所有非零元素個數(shù)之和等于頂點(diǎn)i的(入度)。

8.設(shè)一組初始記錄關(guān)鍵字序列(k“k2,……，k")是堆，則對i=l,2,n/2而言滿足

的條件為(ki<-k2i&&ki<=k2i+1)?

9.下面程序段的功能是實現(xiàn)冒泡排序算法，請在下劃線處填上正確的語句。

voidbubble(intr[n])

(

for(i=1;i<=n-l;i++)

(

fbr(exchange=OJ=O;j<(n-i);j++)

if(r[j]>r[j+l]){temp=r[j+l];(r[j+l]=r[j]);r[j]=temp;exchange=1;}

if(exchange==O)return；

})

10.下面程序段的功能是實現(xiàn)二分查找算法，請在下劃線處填上正確的語句。

structrecord{intkey;intothers;);

intbisearch(structrecordrf],intk)

{

intlow=0,mid,high=n-l;

while(low<=high)

(

(mid=(low+high)/2);

if(r[mid].key==k)retum(mid+l);

elseif((r[mid].key>k))high=mid-l;

elselow=mid+l；)

return(O);}

三、應(yīng)用題

1.設(shè)某棵二叉樹的中序遍歷序列為DBEAC,前序遍歷序列為ABDEC,

要求給出該二叉樹的的后序遍歷序列。

參考答案：DEBCA

2.設(shè)無向圖G(如右圖所示)，給出該圖的最小生成樹上邊的集合并

計算最小生成樹各邊上的權(quán)值之和。

參考答案：E={(1,5),(5,2),(5,3),(3,4)},W=10

3.設(shè)一組初始記錄關(guān)鍵字序列為(15,17,18,22,35,51,60),要求計算出成功查找時

的平均查找長度。

參考答案：ASL=(l*l+2*2+3*4)/7=17/7

4.設(shè)散列表的長度為8,散列函數(shù)H(k)=kmod7,初始記錄關(guān)犍字序列為(25,31,8,27,

13,68),要求分別計算出用線性探測法和鏈地址法作為解決沖突方法的平均查找長度。

參考答案：ASL1=7/6,ASL2=4/3

第-17-頁

數(shù)據(jù)結(jié)構(gòu)考試復(fù)習(xí)資料

四、算法設(shè)計題

1.設(shè)計判斷兩個二叉樹是否相同的算法。

參考答案：

typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;

intjudgebitree(bitree*btl,bitree*bt2)

(

if(btl==O&&bt2==0)return(l);

elseif(btl==O||bt2==0||btI->data!=bt2->data)retum(O);

elseretum(judgebitree(btl->lchild,bt2->lchild)*judgebitree(btl->rchild,bt2->rchild));

)

2.設(shè)計兩個有序單鏈表的合并排序算法。

參考答案：

voidmergelklist(lklist*ha,lklist*hb,lklist*&hc)

(

Ikiist*s=hc=O;

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

if(ha->data<hb->data){if(s==O)hc=s=ha;else{s->next=ha;s=ha;};ha=ha->next;}

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

if(ha==O)s->next=hb