數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)題

數(shù)據(jù)結(jié)構(gòu)習(xí)題1

一、選擇題

1、程序段如下：

sum=O；

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

for(j=n;j>=l;j-)

sum++；

其中n為正整數(shù)，則最后一行的語(yǔ)句頻度在最壞情況下是()。

A、O(n)B、O(nlog2n)

C、O(n3)D、O(n2)

2、二維數(shù)組A[8][8]按行優(yōu)先順序存儲(chǔ)，若數(shù)組元素A[2]⑶的存儲(chǔ)地址為1087,

A[4][5]的存儲(chǔ)地址為1159,則數(shù)組元素A[6][7]的存儲(chǔ)地址為()。

A、1223B、1227

C、1231D、1235

3、已知棧的最大容量為4o若進(jìn)棧序列為1,2,3,4,5,6,且進(jìn)棧和出棧可

以穿插進(jìn)行，則不會(huì)出現(xiàn)的出棧序列為()。

A、4,3,2,1,5,6B、3,2,1,6,4,5

C、4,3,2,1,6,5D、3,2,1,6,5,4

4、已知廣義表C=(a,(b,c),d),則:head(1就?/(0))為()

A>dB、c

C、bD、a

5、已知一棵完全二叉樹(shù)有256個(gè)葉子結(jié)點(diǎn)，則該樹(shù)可能達(dá)到的最大深度為()0

A.10B.11

C.8D.9

6、已知森林F={T1,T2,T3,T4,T5,T6},各棵樹(shù)Ti（i=L2,3,4,5,6）中

所含結(jié)點(diǎn)的個(gè)數(shù)分別為18,2,3,4,5,6,將F按照左孩子右兄弟轉(zhuǎn)化為二叉

樹(shù)，則與F對(duì)應(yīng)的二叉樹(shù)的右子樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為（）o

A.19B.20

C.17D.18

7、對(duì)下圖所示的無(wú)向圖，從頂點(diǎn)1開(kāi)始進(jìn)行深度優(yōu)先遍歷，可得到頂點(diǎn)訪問(wèn)序

列（）。

A.1245637B.1243567

C.1243576D.1234576

A.16,72,31,23,94,53

B.94,23,31,72,16,53

C.16,53,23,94,31,72

D.16,23,53,31,94,72

9、對(duì)記錄序列(314,508,298,123,486,145)依次按個(gè)位進(jìn)行一趟基數(shù)排序之

后所得的結(jié)果為()o

A、298,123,508,486,145,314

B、508,314,123,145,486,298

C、123,314,145,486,298,508

D、123,314,145,486,508,298

10、已知關(guān)鍵字序列為(51,22,83,46,75,18,68,30),對(duì)其進(jìn)行快速排序,

第一趟劃分完成后的關(guān)鍵字序列是()o

A、(18,22,30,46,51,75,68,83)

B、(30,22,18,46,51,75,83,68)

C、(30,22,18,46,51,75,68,83)

D、(30,22,18,46,51,83,68,75)

二、填空題

1、使用一個(gè)30個(gè)元素的數(shù)組存儲(chǔ)循環(huán)隊(duì)列，如果采取少用一個(gè)元素空間的方法

來(lái)區(qū)別循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿,約定隊(duì)頭指針front等于隊(duì)尾指針rear時(shí)表示

隊(duì)空。若為front=29,rear=0,則隊(duì)列中的元素個(gè)數(shù)為。

2、一棵二叉樹(shù)有30個(gè)葉子結(jié)點(diǎn)，僅有一個(gè)孩子的結(jié)點(diǎn)有20個(gè)，則該二叉樹(shù)

共有個(gè)結(jié)點(diǎn)；若某棵完全二叉樹(shù)共有100個(gè)結(jié)點(diǎn)，則該葉子結(jié)點(diǎn)數(shù)

為。

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

二叉樹(shù)得到的線性序列為o

4、在有序表(22,34,46,58,70,82,94)中二分查找關(guān)鍵字22時(shí)所需進(jìn)行

的關(guān)鍵字比較次數(shù)為o

5、將整數(shù)序列｛40,50,70,20,10,30｝中的數(shù)依次插入到一棵空的平衡二叉樹(shù)中，畫(huà)

出相應(yīng)的平衡二叉樹(shù)o

三、應(yīng)用題

1、已知字符串'abaabababc',采用KMP算法，計(jì)算每個(gè)字符的next和nextval

函數(shù)的值。

2、假設(shè)某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)5個(gè)字符(a,b,c,d,e),其概率分別為:

0.15,0.30,0.20,0.28,0.07,畫(huà)出構(gòu)造的Huffman樹(shù)和Huffman編碼。

3、設(shè)帶權(quán)有向圖如下所示:

求出源點(diǎn)V1到匯點(diǎn)V9之間的關(guān)鍵路徑。

4、已知Hash函數(shù)為H(K)=Kmod9，哈希表長(zhǎng)為9,用二次探測(cè)再散列

處理沖突,

給出關(guān)鍵字(23,34,56,24,75,12,49,52)在散列表中的分布，并求在等

概率情況下查找成功的平均查找長(zhǎng)度。

5、已知3階B-樹(shù)如右圖所示，畫(huà)出將關(guān)鍵字18、110和120依次插入之后的B-

樹(shù)。

OCDCDCD（6170、）（1001

四、程序閱讀題

i、設(shè)有單鏈表類型定義如下：

voidf41(LinkListhead,intA,intB）

(

LinkListp=head;

while(p!=NULL)

(

if(p->data=>A&&p->data<=B)

printf(,,%d\nn,p->data);

p=p->next;

)

}

已知鏈表h如下圖所示，給出執(zhí)行f41(h,4,8）之后的輸出結(jié)果;

h-------A|61+19〔十』||一|5|1A|

2、寫(xiě)出下面程序運(yùn)行之后的結(jié)果。

voidf42(intn)//n為非負(fù)的十進(jìn)制整數(shù)

int

SeqStackS;

InitStack(&S);〃堆棧初始化

do{

Push(&S,n%2);〃入棧

n=n/2;

Jwhile(n);

while(!StackEmpty(&S))//如果堆棧不空，循環(huán)

(

e=Pop(&S);〃出棧

printf(',%ld/,,e);

}

)

main()

{

f42(100);

)

3、假設(shè)以二叉鏈表作為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，其類型定義如下:

typedefstructnode{

chardata;

structnode*lchild,*rchild;//左右孩子指針

}BinTNode,*BinTree；

已知如圖所示的二叉樹(shù)以T為指向根結(jié)點(diǎn)

的指針，畫(huà)出執(zhí)行f43(T)

后的二叉樹(shù)；

voidf43(BinTreeT){

BinTreetemp;

if(T){

f43(T->lchild);

if((T->Ichild)&&T->rchild)

temp=T->ichild->data;

T->lchild=T->rchild;

T->rchild=temp;

)

f43(T->rchild);

)

)

4、下面程序?qū)崿F(xiàn)二分查找算法。

Typedefstruct{

KeyTypekey；

InfoTypeotherinfo；

}SeqList[N+l]；

intBinSearch(SeqListR,intn,KeyTypeK)

{intlow=l,high=n；

while((1)){

mid=(low+high)/2；

if((2))

returnmid；

if(R[mid].key>K)

high=mid-l；

else

⑶；

)

returnO；

}//BinSearch

請(qǐng)?jiān)诳瞻滋幪顚?xiě)適當(dāng)內(nèi)容，使該程序功能完整