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

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

一、填空題(每小題2分，共20分)

1、數(shù)據(jù)及其聯(lián)系在計算機內(nèi)存中的存儲稱為數(shù)據(jù)的物理(存儲)結(jié)構(gòu)，基本的物理結(jié)構(gòu)有

和0

2、數(shù)據(jù)結(jié)構(gòu)中評價算法的兩個重要指標是和。

3、堆棧是操作受限的線性結(jié)構(gòu)，只能在插入和刪除元素；不能進行插入和刪

除元素的一端稱為-

4、有一個10階對稱矩陣A,采用壓縮存儲方式(以行為主存儲)，A[0]⑼的地址是100,若

每個元素占3個基本存儲單元，則A[5][8]的地址是-

5、設有一棵深度為n的二叉樹，它至少有個結(jié)點，至生有

個結(jié)點。

6、動態(tài)存儲管理主要是解決系統(tǒng)如何、的兩大問題。

7、對線性表進行二分查找時，要求線性表必須是__________________，且要

求O

8、對于內(nèi)部排序，有多種排序方法。按排序基本思想(策略)，可分為____________、

、、歸并排序和基數(shù)排序。

9、索引表是存儲記錄的和記錄的之間的對照表，每個元素稱

為一個索引項。

10、對于文件，按物理結(jié)構(gòu)劃分，可分為順序文件、文件、

文件和多關(guān)鍵字文件。

二、單項選擇題(請將答案寫在題目后的括號中。每題2分，共18分)

1、有如下遞歸函數(shù)fact(n),其時間復雜度是()。

Fact(intn)

{if(n<=l)return1;

elsereturn(n*fact(n-l));

)

2

(A)O(n)(B)O(n)(C)O(hg2n)(D)O(nlog2n)

2、線性表若采用鏈式存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址是()。

(A)必須是連續(xù)的(B)部分地址必須是連續(xù)的

(C)一定是不連續(xù)的(D)是否連續(xù)沒有要求

3、判斷一個循環(huán)隊列Q(最多元素個數(shù)為m)為滿隊列的條件是()。

(A)Q.front==Q.rear；(B)Q.front!=Q.rear；

(C)Q.front==(Q.rear+l)%m；(D)Q.front!=(Q.rear+l)%m；

4、一棵二叉樹，其先序遍歷序列是abdehicfg,中序遍歷序列是dbheiafcg,則其后序遍歷序

列是()o

(A)dhiebafgc(B)dhiebfgca

(C)dhiebfgac(D)dbhiefgca

5、在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的倍，

所有頂點的度之和等于所有頂點的入度之和的倍。()

(A)1/2,1(B)2,1(C)1,2(D)1,4

6、對于有n個頂點e(e>n)條邊的帶權(quán)無向圖，以下關(guān)于該圖的最小生成樹的描述正確的是

(

(A)最小生成樹是唯一的。

(B)最小生成樹中所有邊上的權(quán)值之和是唯一的。

(C)最小生成樹有n條邊。

(D)最小生成樹有n個頂點e-1條邊。

7、設哈希表長m=14,H(key)=keyMOD13,address(19)=6,address(41)=2,address(57)=5,

address(85)=7,其余地址為空。對于關(guān)鍵字31,若用線性探測法解決沖突，其地址

是；若用二次探測法解決沖突,其地址是))

(A)8,4(B)11,4(C)4,8(D)4,11

8、從未排序序列中挑選元素，并將其依次放入到已排序序列中(初始時為空)的一端的方法是

(

(A)直接插入排序(B)選擇排序

(C)快速排序(D)堆排序

9、若以｛3,5,6,8,14｝作為葉子的權(quán)值構(gòu)造Huffman樹(按左子樹根結(jié)點的權(quán)小于等于右子

樹根結(jié)點的權(quán)的次序構(gòu)造)，則其帶權(quán)路徑長度討「1為()。

(A)78(B)80(C)82(D)84

三、分析題(每題6分，共30分)

1、設QU[O,5]是一個靜態(tài)循環(huán)隊列，初始狀態(tài)是front=rear=0,畫出進行下列操作后隊列

的頭、尾指針的狀態(tài)變化情況，若不能入隊，請指出不能入隊的元素，并說明理由。

（1）a,e,b入隊；（2）a,e出隊；

（3）s,t,k,m入隊；（4）b,s,t出隊；（5）r,p,u,v入隊；

2、設有一棵樹如下圖，⑴給出該樹的孩子表示法的復合鏈表存儲結(jié)構(gòu)；⑵將此樹轉(zhuǎn)換為

二叉樹；⑶給出轉(zhuǎn)換后二叉樹的后序遍歷序列。

3、設有如下帶權(quán)有向無環(huán)圖，⑴給出該圖的正鄰接鏈表存儲結(jié)構(gòu)；⑵給出對該圖進行

拓撲排序過程。

4、線性表的關(guān)鍵字集合{31,25,18,29,42,69,95,53,17,16,47,116,87},共有

13個元素，已知散列函數(shù)為：H（k）=kMOD11,采用鏈地址法處理沖突，請給出對應的

散列表結(jié)構(gòu)。

5、已知關(guān)鍵字序列{15,29,12,40,47,39,58,27,73,44,86,55},請給出采用希

爾排序法對該序列做非遞減排序的過程（設增量序列是5,3,Do

四、算法填空(每空2分，共20分)

請在下面各算法的空白處填上相應語句以實現(xiàn)算法功能。每個空白只能填

一個語句。

1、設有一個以L為頭結(jié)點的雙向循環(huán)鏈表，刪除數(shù)據(jù)為key的所有結(jié)點，數(shù)據(jù)結(jié)構(gòu)定義如

下：

typedefstructLnode

{ElemTypekey;/*關(guān)鍵字碼*/

structLnode"prior;/*指向直接前趨結(jié)點的指針域*/

structLnode*next;/*指向直接后繼結(jié)點的指針域*/

JLNode;/*結(jié)點的類型*/

void*Delete_Node(LNodeL,ElemTypekey)

{ElemTypedata;LNode*p;

if(L->next=L)printf(“％s”J鏈表為空!!\n");

else

{p=L->next;

while()

{if(EQ(p->data==key))

free(p);

}/*刪除數(shù)據(jù)為key的結(jié)點*/

)

2、非遞歸中序遍歷二叉樹。

#defineMAXNODE50

voidInorderTraverse(BTNode*T)

{BTNode*stack[MAXNODE],*p=T;

inttop=0,bool=l;

if(T==NULL)printf(uBinaryTreeisEmpty!\n,9);

else{do

{while(p!=NULL)

{;p=p->Lchild;}

if(top==0)bool=0;

else{p=stack[top];top-;

visit(p->data);

while(bool!=0);

以下2題是查找和排序，所使用的記錄類型的定義如下:

#defineMAX_SIZE100

typedefintKeyType;

typedefstructRecType

{KeyTypekey;/*關(guān)鍵字碼*/

infoTypeotherinfo;/*其他域*/

}RecType;

typedefstructSqlist

{RecTypeR[MAX_SIZE];/*順序表*/

intlength;/*實際元素個數(shù)*/

}Sqlist;

3、二叉排序樹的查找

BSTNode*BST_Serach(BSTNode*T,KeyTypekey)

{BSTNode*p=T;

while(p!=NULL&&!EQ(p->key,key))

{if(LT(key,p->key))

elsep=p->Rchild;

)

if(EQ(p->key,key))return(p);

else;

4、選擇排序算法

voidsimple_selection_sort(Sqlist*L)

{intm,n,k;

for(m=l;;m++)

{k=m;

for(n=in+l;n<=L->Iength;n++)

if(LT(L->R[n].key,L->R[k].key))k=n;

if()/*記錄交換*/

{L->R[0]=L->R[m];L->R[m]=L->R[k];

）

五、編寫算法（12分）

設T是指向二叉樹根結(jié)點的指針變量，每個結(jié)點的數(shù)據(jù)都是字符。

⑴寫出輸出樹中度為1及度為0的結(jié)點數(shù)的算法。（6分）

⑵寫出從根結(jié)點開始按層次次序“自上而下，從左至右”輸出樹中的各結(jié)點的算法。（6

分）

提示：為保證是按層次遍歷，必須設置一個隊列，初始化時為空。

《數(shù)據(jù)結(jié)構(gòu)》模擬試題16參考答案

一、填空題（每小題2分，共20分）

1、順序存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu)

2、時間復雜度空間復雜度

3、棧頂棧底

4、274

5>n2n-l

6、存儲空間的分配釋放的存儲空間的回收

7、以順序方式存儲結(jié)點按關(guān)鍵字有序

8、插入排序交換排序選擇排序

9、關(guān)鍵字存儲地址或存儲地址關(guān)鍵字

10、索引文件散列（哈希）文件

二、單項選擇題（請將答案寫在題目后的括號中。每題2分，共18分）

題號123456789

答案ADCBCDABB

三、分析題（每題6分，共30分）

1、解：做完下列操作后隊列的頭尾指針的狀態(tài)變化情況如下面圖形所示。

①a,e,b入隊

（a）隊列初始化

reart

front

front

rear

②a,e出隊

4M八④b,s,t出隊

每圖1分

2、解：⑴該樹的孩子表示法的復合鏈表存儲結(jié)構(gòu)如下圖;（3分）

（1分）

3、

⑵給出對該圖進行拓撲排序過程如下（3分），其拓撲序列是：V°TVI-V2-V4TV3TV5（1

分）

4

V

3V3

②輸出V,后

④輸出V3后

4、解：根據(jù)所給定的散列函數(shù)和處理沖突方法，得到的散列表結(jié)構(gòu)如下:

5、解：采用希爾排序法對該序列做非遞減排序的每一趟結(jié)果如下。（一趟3分，二趟2分,

三趟1分）

初始關(guān)鍵字：152912404739582773448655

1I

5558

4447

一趟排序后：152912404439552773478658

1II_|

4755

272944

5873

二趟排序后：152712402939474458558673

三趟排序后：121527293940444755587386

四、算法填空（每空2分，共20分）

請在下面各算法的空白處填上相應語句實現(xiàn)算法功能。每個空白處只能

填一個語句。

1、設有一個以L為頭結(jié)點的雙向循環(huán)鏈表，刪除數(shù)據(jù)為key的所有結(jié)點。

p->next!=L

p->prior->next=p->next

p->next->prior=p->prior

2、非遞歸中序遍歷二叉樹。

stack[++top]=p

p=p->RchiId

3、二叉排序樹的查找。

p=p->Lchild

return(NULL)

4、選擇排序算法。

m<L->length

k!=m

L->R[k]=L->R[O]

五、編寫算法(12分)

解：

⑴輸出樹中度為1及度為0的結(jié)點數(shù)的算法。(6分)

#defineMAXNODE50

voidcount_nodes(BTNode*T)

{BTNode*Stack[MAXNODE],*p=T;

inttop=0,numl=0,num0=0;

if(T=NULL)printf(uBinaryTreeisEmpty!\n,9);

else

{stack[++top]=p;

while(top>0)(循環(huán)及控制1分)

{p=stack[top-];

if(!(p->Lchild!=NULL&&p->Rchild!=NULL))(判斷部分3分)

{if(p->Lchild==NULL&&p->Rchild==NULL)num0++;

elseif(p->Lchild!=NULL||p->Rchild!=NULL)numl++;}

if(p->Rchild!=NULL)stack[++top]=p->Rchi!d;(進棧部分1分)

if