《數(shù)據(jù)結(jié)構(gòu)》題庫及答案

《數(shù)據(jù)結(jié)構(gòu)》題庫及答案

一、選擇題

1.線性表的順序存儲(chǔ)結(jié)構(gòu)是一種—的存儲(chǔ)結(jié)構(gòu)，線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種—的存儲(chǔ)結(jié)構(gòu)0

a.隨機(jī)存儲(chǔ)；b.順序存儲(chǔ)；c.索引存取；d.HASH存取

2.一個(gè)棧的入棧序列是a,b,c,d,e,則棧的不可能的輸出序列是—o

a.edcba;b.decba;c.dceab;

3.一個(gè)隊(duì)列的入隊(duì)序列是1,2,3,4,則隊(duì)列的輸出序列是o

a.4,3,2,1;b.1,2,3,4;c.1,4,3,2;,2,4,1

4.在一個(gè)單鏈表中，已知p結(jié)點(diǎn)是q結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，若在p和q之間插入結(jié)點(diǎn)S,則執(zhí)行的操作是一?

a.s->nxet=p->next;p->next=s;

b.?

c.p->next=s->next;s->next=p;

d.q->next=s;s->next=p;

e.p->next=s;s->next=q;

5.設(shè)有兩個(gè)串p,q,求q在p中首次出現(xiàn)的位置的運(yùn)算稱作。

a.聯(lián)接b.模式匹配c.求子串d.求串長

6.二維數(shù)組M的成員是6個(gè)字符(每個(gè)字符占一個(gè)存儲(chǔ)單元)組成的串，行下標(biāo)i的范圍從0到8,列下標(biāo)j

的范圍從1到10,則存放M至少需要個(gè)字節(jié)。

a.90

7.在線索二叉樹中，結(jié)點(diǎn)p沒有左子樹的充要條件是o

a.p->lch==NULL

b.p->ltag-1

c.

d.p->ltag==l且p->lch=NULL

e.以上都不對(duì)

8.在棧操作中，輸入序列為(A,B,C,D),不可能得到的輸出序列為：

A、(A,B,C,D)B、(D,C,B,A)

C、(A,C,D,B)D、(C,A,B,D)

9.已知某二叉樹的后序序列是dabec,中序序列是debac,則它的先序序列是。

A>acbedB>decabC^deabcD、cedba

10.設(shè)矩陣A是一個(gè)對(duì)稱矩陣,為了節(jié)省存儲(chǔ)空間，將其下三角部分(見下圖)按行序存放在一維數(shù)組B[l..n(n-l)/2]

中，對(duì)任一上三角部分元素劭(iY/),在一維數(shù)組B的存放位置是.

a\\

A

ann

%”all2

A、鋁+rB、

C、D、鋁+，

11.圖G中有n個(gè)頂點(diǎn)，n?l條邊，那么圖G一定是一棵樹嗎.

A>一定是B、一定不是C、不一定

12.用某種排序方法對(duì)關(guān)鍵字序列｛25，84,21,47,15,27,68,35,20｝進(jìn)行排序時(shí)，元素序列的變化情況

如下:

①{25,84,21,47,15,27,68,35,20)

②{20,15,21,25,47,27,68,35,84)

③{15,20,21,25,35,27,47,68,84)

④{15,20,21,25,27,35,47,68,84)

則所采用的排序方法是.

A、快速排序B、希爾排序

C、歸并排序D、選擇排序

13.表達(dá)式a*(b+c)-d的后綴表示式是。

a.abcd-*+;b.abc+*d-;c.abc*+d-;d.-*a+bcd;

14.在雙向循環(huán)鏈表中的結(jié)點(diǎn)P之后插入結(jié)點(diǎn)S的操作是

a.p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;

b.p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;

s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;

d.s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;

15.如下圖所示循環(huán)隊(duì)列，其中的數(shù)據(jù)元素個(gè)數(shù)是

in-J.

1

串是一種特殊的線性表，其特殊性體現(xiàn)在一。

a.可以順序存儲(chǔ)

b.數(shù)據(jù)元素是一個(gè)字符

c.可以鏈接存儲(chǔ)

d.<

e,數(shù)據(jù)元素可以是多個(gè)字符

17.數(shù)組A中，每個(gè)元素的長度是3個(gè)字節(jié)，行下標(biāo)i從I到8,列下標(biāo)j從1到10,從首地址SA開始

連續(xù)存放在存儲(chǔ)器內(nèi)，存放該數(shù)組的單元數(shù)是一o

a.80

b.100

c.240

d.270

18.已知某二叉樹的先序遍歷序列是abdgcefh,中序遍歷序列是dgbaechf,則其后序遍歷的結(jié)點(diǎn)訪問順序序列

是O

a.bdgcefha

b.gdbecfha

c.bdgaechf

d.：

e.gdbehfca

19.線索二叉樹是一種結(jié)構(gòu)。

a.邏輯

b.邏輯和存儲(chǔ)

c.物理

d.線性

20.在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的倍。

a.1/2

b.1

c.2

d.

c.3

21.采用分塊查找時(shí)，若線性表中共有625個(gè)元素，查找每個(gè)元素的概率相同，假設(shè)采用順序查找來確定元素所

在的塊時(shí)，則每塊應(yīng)分為個(gè)元素的塊時(shí)，查找效率最佳。

a.10

b.25

6

d.625

22.一個(gè)棧的輸入序列是12345,則棧的不可能輸出序列是

a.54321

b.45321

c.43512

d.,

?.12345

23.完全二叉樹一定是滿二叉樹嗎—o

a.一定是

b.不是

c.不一定

24.線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)其地址。

a.必須是連續(xù)的

b.部分地址必須是連續(xù)的

c.一定是不連續(xù)的

d.連續(xù)不連續(xù)都可以

25.具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是

樹

b.圖

廣義表

d.棧

26.下圖為順序隊(duì)列的初始情況，設(shè)a,b,c相繼出隊(duì)列，e,f相繼入隊(duì)列，則指針和分別為

a.2,5

b.3,5

3,6

d.4,6

二、填空題

1.設(shè)n行n列的下三角陣A已經(jīng)壓縮存儲(chǔ)到一維數(shù)組S［0..空-1］中，若按行序?yàn)橹餍虼鎯?chǔ)，則對(duì)應(yīng)的

在S中的存儲(chǔ)位置是

2.廣義表((a),((b),c),(((d))))的長度是,深度是。

3.深度為k的完全二叉樹至少有一個(gè)結(jié)點(diǎn)，至多有個(gè)結(jié)點(diǎn)，若按自上而下，從左到右的次序給結(jié)點(diǎn)編

號(hào)(從1開始)，則編號(hào)最小的葉子結(jié)點(diǎn)的編號(hào)是0

4.根據(jù)有向圖的寬度優(yōu)先遍歷算法，對(duì)下圖2所示有向圖從頂點(diǎn)vl出發(fā)進(jìn)行搜索，所得到的頂點(diǎn)遍歷序列

是。

圖2

5.有一個(gè)有序表為｛1,3,9,12,32,41,45,62,75,77,82,95,100｝,當(dāng)二分查找值為82的元素時(shí)，需

要經(jīng)過一次比較就找到。

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

7.在雙向鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)是指向，另一個(gè)指向o

8.設(shè)棧ST用順序存儲(chǔ)結(jié)構(gòu)表示，則棧ST為空的條件是。

9.兩個(gè)串相等的充分必要條件是和對(duì)應(yīng)位置上的字符相等。

10.對(duì)于深度為h的二叉樹至多有個(gè)結(jié)點(diǎn)。

11.將一個(gè)A［15115］的對(duì)稱矩陣壓縮存儲(chǔ)到一個(gè)一維數(shù)組中，該數(shù)組的長度至少為。

三、算法應(yīng)用題

I.數(shù)據(jù)集｛4,5,6,7,10,12,18｝為結(jié)點(diǎn)權(quán)值構(gòu)造Huffman樹，請(qǐng)給出構(gòu)造所得的Huffman樹，并求其帶權(quán)

路徑長度。

2.假設(shè)一棵二叉樹的先序序列是EBADCFHGIKJ,中序序歹!］是ABCDEFGHIJK。請(qǐng)畫出該二叉樹。

3.已知一顆二叉排序樹如下圖所示，若依次刪除93、19、87、48結(jié)點(diǎn)，試分別畫出每刪除一個(gè)結(jié)點(diǎn)后得到的二

叉排序樹。

4.已知關(guān)鍵字序列{19,01,23,14,55,20,84,27,68,11,10,77},采用哈希函數(shù):H(key)=key%13,

和開放地址法的線性探測(cè)再散列方法解決沖突，已知其裝填因子a=*2,試對(duì)該關(guān)鍵字序列構(gòu)造哈希表,

3

并求其查找成功時(shí)的平均查找長度。

5.畫出和下列已知序列對(duì)應(yīng)的森林F:

森林的先序遍歷序列是：ABCDEFGHIJKL；

森林的中序遍歷序列是：CBEFDGAJIKLHo

6.假設(shè)用于通訊的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為,，，，，，，。請(qǐng)給這8個(gè)字母設(shè)計(jì)哈夫

曼編碼。

7.對(duì)下圖所示的無向帶權(quán)圖，

①給出其鄰接矩陣，并按Prim算法求其最小生成樹；

②給出其鄰接表，并按Kruskal算法求其最小生成樹。

8.我們已經(jīng)知道對(duì)長度為n的記錄序列進(jìn)行快速排序時(shí)，所需進(jìn)行的比較次數(shù)依賴于這n個(gè)元素的初始排列。

試問：

①n=7時(shí)在最好情況下需進(jìn)行多少次比較請(qǐng)說明理由。

②對(duì)n=7給出一個(gè)最好情況的初始排列實(shí)例。

9.下列算法為斐波那契查找算法：

iniFibSearch(SqLislr,KeyTypek)

(

j=l；

while(fib(j)<n+l)j=j+l;

mid=n-fib(j-1)+1;ey):found=true;break;

case(k<r[mid].key):

if(!f2)mid=O;

else{mid=mid-f2;t=fl-f2;fl=f2;f2=t;}

break;

case(k>r[mid].key):

if(fl==l)mid=O;

else{mid=mid+f2；fl=fl-f2;f2=f2-f1;}

break;

)

iffoundreturnmid;

2

a--

3

1+2+1+41+1+1+3+223

ASLSUCC

12

ViVi

io=2

4NUL

NU

()

4NULL

5

b；(b)

產(chǎn)2

5：g,

(c；6e)6

t

p=p->nex*⑴

?(d)

4.解答：本題涉及的存儲(chǔ)結(jié)構(gòu)描述如下:

單鏈表存儲(chǔ)結(jié)構(gòu)：

typedefstructLnode*LinkList;

typedefstructLnode

DataTypedata;

LinkListnext;

}Lnode,*LinkList;

voidmerge_two_asceding_linklist_to_one_desceding_linklist(LinkList&1c,LinkListla,lb)

(

pa=la->next;

pb=lb->next;

lc=la;

pc=lc;

pc->next=NULL;

while(pa&&pb)

(

if(pa->data<pb->data)

>

(

u=pa->next;

pa->next=pc->next;

pc->next=pa;

pa=u;

)

else

(

u=pb->next;

pb->next=pc->next;

￥

pc->next=pb;

pb=u;

)

)

while(pa)

(

u=pa->next;

pa->next=pc->next;

pc->next=pa;

pa=u;

while(pb)

u=pb->next;

pb->next=pc->next;

pc->next=pb;

pb二u;

)

delete(lb)

)

5.