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

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

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

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

和0

2、數(shù)據(jù)結(jié)構(gòu)中評(píng)價(jià)算法的兩個(gè)重要指標(biāo)是和。

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

除元素的一端稱為-

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

每個(gè)元素占3個(gè)基本存儲(chǔ)單元，則A[5][8]的地址是-

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

個(gè)結(jié)點(diǎn)。

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

7、對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須是__________________，且要

求O

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

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

9、索引表是存儲(chǔ)記錄的和記錄的之間的對(duì)照表，每個(gè)元素稱

為一個(gè)索引項(xiàng)。

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

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

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

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

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、線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址是()。

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

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

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

(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、在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的倍，

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

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

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

(

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

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

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

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

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

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

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

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

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

(

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

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

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

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

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

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

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

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

（1）a,e,b入隊(duì)；（2）a,e出隊(duì)；

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

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

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

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

拓?fù)渑判蜻^程。

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

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

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

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

爾排序法對(duì)該序列做非遞減排序的過程（設(shè)增量序列是5,3,Do

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

請(qǐng)?jiān)谙旅娓魉惴ǖ目瞻滋幪钌舷鄳?yīng)語句以實(shí)現(xiàn)算法功能。每個(gè)空白只能填

一個(gè)語句。

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

下：

typedefstructLnode

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

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

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

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

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é)點(diǎn)*/

)

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í)際元素個(gè)數(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分）

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

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

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

分）

提示：為保證是按層次遍歷，必須設(shè)置一個(gè)隊(duì)列，初始化時(shí)為空。

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

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

1、順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

2、時(shí)間復(fù)雜度空間復(fù)雜度

3、棧頂棧底

4、274

5>n2n-l

6、存儲(chǔ)空間的分配釋放的存儲(chǔ)空間的回收

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

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

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

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

二、單項(xiàng)選擇題（請(qǐng)將答案寫在題目后的括號(hào)中。每題2分，共18分）

題號(hào)123456789

答案ADCBCDABB

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

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

①a,e,b入隊(duì)

（a）隊(duì)列初始化

reart

front

front

rear

②a,e出隊(duì)

4M八④b,s,t出隊(duì)

每圖1分

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

（1分）

3、

⑵給出對(duì)該圖進(jìn)行拓?fù)渑判蜻^程如下（3分），其拓?fù)湫蛄惺牵篤°TVI-V2-V4TV3TV5（1

分）

4

V

3V3

②輸出V,后

④輸出V3后

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

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

三趟1分）

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

1I

5558

4447

一趟排序后：152912404439552773478658

1II_|

4755

272944

5873

二趟排序后：152712402939474458558673

三趟排序后：121527293940444755587386

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

請(qǐng)?jiān)谙旅娓魉惴ǖ目瞻滋幪钌舷鄳?yīng)語句實(shí)現(xiàn)算法功能。每個(gè)空白處只能

填一個(gè)語句。

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

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é)點(diǎn)數(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;(進(jìn)棧部分1分)

if