數(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ù)，則最后一行的語句頻度在最壞情況下是()。

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

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

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

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

A、1223B、1227

C、1231D、1235

3、已知棧的最大容量為4o若進棧序列為1,2,3,4,5,6,且進棧和出?？?/p>

以穿插進行，則不會出現(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、已知一棵完全二叉樹有256個葉子結(jié)點，則該樹可能達到的最大深度為()0

A.10B.11

C.8D.9

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

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

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

A.19B.20

C.17D.18

7、對下圖所示的無向圖，從頂點1開始進行深度優(yōu)先遍歷，可得到頂點訪問序

列（）。

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、對記錄序列(314,508,298,123,486,145)依次按個位進行一趟基數(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),對其進行快速排序,

第一趟劃分完成后的關(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、使用一個30個元素的數(shù)組存儲循環(huán)隊列，如果采取少用一個元素空間的方法

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

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

2、一棵二叉樹有30個葉子結(jié)點，僅有一個孩子的結(jié)點有20個，則該二叉樹

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

為。

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

二叉樹得到的線性序列為o

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

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

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

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

三、應(yīng)用題

1、已知字符串'abaabababc',采用KMP算法，計算每個字符的next和nextval

函數(shù)的值。

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

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

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

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

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

處理沖突,

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

概率情況下查找成功的平均查找長度。

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

樹。

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、寫出下面程序運行之后的結(jié)果。

voidf42(intn)//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è)以二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，其類型定義如下:

typedefstructnode{

chardata;

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

}BinTNode,*BinTree；

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

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

后的二叉樹；

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

請在空白處填寫適當(dāng)內(nèi)容，使該程序功能完整