杭州電子科技大學(xué)大二計(jì)算機(jī)專業(yè)數(shù)據(jù)結(jié)構(gòu)試卷及答案

杭州電子科技大學(xué)學(xué)生考試卷(A)卷

考試課程數(shù)據(jù)結(jié)構(gòu)考試日期年月日成績(jī)

課程號(hào)X教師號(hào)任課教師姓名

考生姓名學(xué)號(hào)(8位)年級(jí)專業(yè)座位號(hào)

是非題

1.數(shù)據(jù)結(jié)構(gòu)可用三元式表示(D,S,P)。其中：D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系，P是對(duì)

D的根本操作集。⑴

2簡(jiǎn)單地說(shuō),數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。(t)

3判斷帶頭結(jié)點(diǎn)的非空循環(huán)單鏈表(頭指針為L(zhǎng))中指針p所指結(jié)點(diǎn)是最后一個(gè)元素結(jié)點(diǎn)

的條件是:p->next==Lo(t)

4線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)具有可直接存取表中任一元素的優(yōu)點(diǎn)。⑴

5線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。⑴

6.在單鏈表P指針?biāo)附Y(jié)點(diǎn)之后插入S結(jié)點(diǎn)的操作是：

P->next=S;S->next=P->next;。(f)

7對(duì)于插入、刪除而言，線性表的鏈?zhǔn)酱鎯?chǔ)優(yōu)于順序存儲(chǔ)。⑴

8.順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。⑴

9.棧和隊(duì)列是操作上受限制的線性表。⑴

10.隊(duì)列是與線性表完全不同的一種數(shù)據(jù)結(jié)構(gòu)。⑴

11.隊(duì)列是一種操作受限的線性表，凡對(duì)數(shù)據(jù)元素的操作僅限一端進(jìn)行。⑴

12.棧和隊(duì)列也是線性表。如果需要，可對(duì)它們中的任一元素進(jìn)行操作。⑴

13.棧是限定僅在表頭進(jìn)行插入和表尾進(jìn)行刪除運(yùn)算的線性表。⑴

14.二叉樹(shù)中每個(gè)結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)，而對(duì)一般的樹(shù)，則無(wú)此限制，所以，二叉樹(shù)是樹(shù)的

特殊情形。⑴

15二叉樹(shù)是一棵結(jié)點(diǎn)的度最大為二的樹(shù)。⑴

16赫夫曼樹(shù)中結(jié)點(diǎn)個(gè)數(shù)一定是奇數(shù)。(t)

17在二叉樹(shù)的中序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其左孩子結(jié)點(diǎn)的后面。(t)

18假設(shè)B是一棵樹(shù)，B'是對(duì)應(yīng)的二叉樹(shù)。則B的后根遍歷相當(dāng)于B'的后序遍歷。⑴

19.通常，二叉樹(shù)的第i層上有2"個(gè)結(jié)點(diǎn)。⑴

20.中序線索二叉樹(shù)的優(yōu)點(diǎn)是便于在中序下查找直接前驅(qū)結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)。(t)

21二叉樹(shù)的先序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其孩子結(jié)點(diǎn)的前面。⑴

22由樹(shù)結(jié)點(diǎn)的先根序列和后根序列可以唯一地確定一棵樹(shù)。(t)

23鄰接多重表可以用以表示無(wú)向圖，也可用以表示有向圖。⑴

24可從任意有向圖中得到關(guān)于所有頂點(diǎn)的拓?fù)浯涡?。?/p>

25有向圖的十字鏈表是將鄰接表和逆鄰接表合二為一的鏈表表示形式。⑴

26關(guān)鍵路徑是AOE網(wǎng)中源點(diǎn)到匯點(diǎn)的最短路徑。⑴

27連通圖G的生成樹(shù)是一個(gè)包含G的所有n個(gè)頂點(diǎn)和n-1條邊的子圖。⑴

28一個(gè)無(wú)向圖的連通分量是其極大的連通子圖。(t)

29十字鏈表可以表示無(wú)向圖，也可用以表示有向圖。⑴

30鄰接表可以表示有向圖，也可以表示無(wú)向圖。(t)

31.二叉排序樹(shù)的平均查找長(zhǎng)度為O(k)gn)。(t)

32.二叉排序樹(shù)的最大查找長(zhǎng)度與(LOG2N)同階。⑴

33選用好的HASH函數(shù)可防止沖突。⑴

34折半查找不適用于有序鏈表的查找。(t)

35.對(duì)于目前所知的排序方法，快速排序具有最好的平均性能。⑴

36對(duì)于任何待排序序列來(lái)說(shuō)，快速排序均快于冒泡排序。⑴

37在最壞情況下，堆排序的時(shí)間性能是O(nlogn),比快速排序好(t)

38快速排序具有最好的平均時(shí)間性能，它在任何時(shí)候的時(shí)間復(fù)雜度都是0(nlogn)。(f)

39.字符串是數(shù)據(jù)對(duì)象特定的線性表。⑴

40.空串與空格串是相同的。⑴

41.對(duì)于一棵m階的B.

少有一「m2)個(gè)關(guān)鍵字。⑴

42.當(dāng)二叉排序樹(shù)是一棵平衡二叉樹(shù)時(shí)，其平均查找長(zhǎng)度為O(log2n)。(t)

43.廣義表的表頭和表尾都是廣義表。⑴

44二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表。⑴

選擇題。

1從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成(c)。

A.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.順序組織和鏈接組織

C.線性結(jié)構(gòu)和非線性結(jié)構(gòu)D.根本類型和組合類型

2線性表L在(b)情況下適于使用鏈表結(jié)構(gòu)實(shí)現(xiàn)。

A.不需修改L的結(jié)構(gòu)B.需不斷對(duì)L進(jìn)行刪除、插入

C.需經(jīng)常修改L中結(jié)點(diǎn)值D.L中含有大量結(jié)點(diǎn)

3帶頭結(jié)點(diǎn)的單鏈表L為空的判斷條件是b。

帶頭結(jié)點(diǎn)的循環(huán)鏈表L為空的判斷條件是。

A.L==nullB.L->next==null

C.L->next==LD.L!=null

4假設(shè)順序表中各結(jié)點(diǎn)的查找概率不等，則可用如下策略提高順序查找的效率：假設(shè)找到指

定

的結(jié)點(diǎn)，將該結(jié)點(diǎn)與其后繼(假設(shè)存在)結(jié)點(diǎn)交換位置，使得經(jīng)常被查找的結(jié)點(diǎn)逐漸移至

表尾。以下為據(jù)此策略編寫的算法，請(qǐng)選擇適當(dāng)?shù)膬?nèi)容，完成此功能。

順序表的存儲(chǔ)結(jié)構(gòu)為：

typedefstruct)

ElemType*elem;〃數(shù)據(jù)元素存儲(chǔ)空間,0號(hào)單元作監(jiān)視哨

intlength;〃表長(zhǎng)度

JSSTable;

intsearch_seq(SSTableST,KeyTypekey)

{〃在順序表ST中順序查找關(guān)鍵字等于key的數(shù)據(jù)元素。

//假設(shè)找到，則將該元素與其后繼交換位置，并返回其在表中的位置，否則為0。

ST.elemlOJ.key=key;

i=ST.length;

while(ST.elem|il.key!=key)f:

if(—G—)

{ST.elem[i]一-ST.elem[i+1]；

e

returni;

A.i>0

E.i++F.i-GA和C同時(shí)滿足H.B和D同時(shí)滿足

5假設(shè)入棧順序?yàn)锳、B、C、D、E,則以下(d)出棧序列是不可能的。

A.A、B、C、D、EB.B、C、D、A、E

C.C、D、B、E、AD.D、E、C、A、B

6遞歸程序可借助于(c)轉(zhuǎn)化為非遞歸程序。

a.線性表b.隊(duì)列c:棧d.數(shù)組

7在以下數(shù)據(jù)結(jié)構(gòu)中(c)具有先進(jìn)先出(FIFO)特性，

(b)具有先進(jìn)后出(FILO)特性。

a.線性表b.棧c.隊(duì)列d.廣義表

8假設(shè)對(duì)編號(hào)為1,2,3的列車車廂依次通過(guò)扳道棧進(jìn)行調(diào)度，不能得到(e)的序列。

a:1,2,3b:l,3,2c:2,l,3d:2,3,le:3,l,2f:3,2,l

9在計(jì)算遞歸函數(shù)時(shí)，如不用遞歸過(guò)程，應(yīng)借助于(b)這種數(shù)據(jù)結(jié)構(gòu)。

A.線性表B.棧C.隊(duì)列D.雙向隊(duì)列

10假設(shè)帶頭結(jié)點(diǎn)的鏈表只設(shè)尾結(jié)點(diǎn)指針。以下選擇中(c)最適用于隊(duì)列。

A)單鏈表B)雙向鏈表C循環(huán)單鏈表D)雙向循環(huán)鏈表

11棧和隊(duì)列的一個(gè)共同點(diǎn)是(c)。

A.都是先進(jìn)先出B.都是先進(jìn)后出

C.只允許在端點(diǎn)處插入和刪除元素D.沒(méi)有共同點(diǎn)

12循環(huán)隊(duì)列用數(shù)組存放其元素值，設(shè)頭尾指針?lè)謩e為front和rear,則當(dāng)前隊(duì)列中

的元素個(gè)數(shù)是(c)。

A.rear-front-1B.Rear-front+1

C.(rear-front+m)%mD.Rear-front

13如下關(guān)于串的陳述中，正確的選項(xiàng)是(a,c)。

A.串是數(shù)據(jù)元素類型特殊的線性表B.串中的元素是字母

C.串中假設(shè)干個(gè)元素構(gòu)成的子序列稱為子串D.空串即為空格串

14對(duì)字符串s='data-structure'執(zhí)行操作replace(s,substring(s,6,8),,bas,)

的結(jié)果是(b)。

a:'database'b:'data-base'c:'bas'd:'data-basucture'

15設(shè)有二維數(shù)組A5X7,每一元素用相鄰的4個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址.

A的起始地址為100。則按行存儲(chǔ)時(shí)，元素A院的第一個(gè)字節(jié)的地址是(d)

按列存儲(chǔ)時(shí)，元素Am的第一個(gè)字節(jié)的地址是(a)

a:220b:200c:140d:124

16對(duì)廣義表A=1(a,(b)),(c,()),d)執(zhí)行操作gettail(gethead(gettail(A)))

的結(jié)果是：(b)o

a:()b:[())c:dd:(d)

17假設(shè)用于通訊的電文僅由6個(gè)字符組成,字母在電文中出現(xiàn)的頻率分別為7,19,22,6,32,

14o假設(shè)為這6個(gè)字母設(shè)計(jì)哈夫曼編碼(設(shè)生成新的二叉樹(shù)的規(guī)則是按給出的次序從左

至

右的結(jié)合，新生成的二叉樹(shù)總是插入在最右)，則頻率為7的字符編碼是(g),頻率

為32的字符編碼是(c

a:00b:01c:10d:11

e:011f:110g:1110h:llll

18對(duì)二叉排序樹(shù)(c)可得到有序序列。

a:按層遍歷b:前序遍歷c:中序遍歷d:后序遍歷

19設(shè)一棵二叉樹(shù)BT的存儲(chǔ)結(jié)構(gòu)如下：

12345678

23006))()

ABcDEFGH

054087))

其中Ichild,rchild分別為結(jié)點(diǎn)的左、右孩子指針域，data為結(jié)點(diǎn)的數(shù)據(jù)域。則

該二叉樹(shù)的高度為(db

第3層有(a)個(gè)結(jié)點(diǎn)(根結(jié)點(diǎn)為第1層)。

A.2B.3C.4D.5

20先序遍歷圖示二叉樹(shù)可得到(a)的序列。

(A)

/\

(B)(C)

/\\

(H)(D)(G)

/\

(E)(F)

\

(I)

a)ABHDEFICG

b)HBEDFIACG

c)HEIFDBGCA

21在有n個(gè)結(jié)點(diǎn)的二叉樹(shù)的二叉鏈表表示中，空指針數(shù)(b)。

22假設(shè)某二叉樹(shù)有20個(gè)葉子結(jié)點(diǎn)，有20個(gè)結(jié)點(diǎn)僅有一個(gè)孩子，則該二叉樹(shù)的總結(jié)點(diǎn)數(shù)是

(C)o

A.40B.55C.59D.61

23某二叉樹(shù)的先序遍歷次序?yàn)閍bcdefg中序遍歷次序?yàn)閎adcgfe,

則該二叉樹(shù)的后序遍歷次序?yàn)?c)。層次遍歷次序?yàn)?a

a:abcdefgb:cdebgfac:bdgfecad:edcgfba

.24圖示的三棵二叉樹(shù)中(c)為最優(yōu)二叉樹(shù)。

7524

25某二叉樹(shù)的后序遍歷和中序遍歷次序分別為DBFGECA和BDACFEGo

則其先序遍歷次序?yàn)?b),層次遍歷次序?yàn)?a)o

a:abcdefgb:abdcefgc:abcdfegd:abcdegf

26某樹(shù)的先根遍歷次序?yàn)閍bcdefg后根遍歷次序?yàn)閏debgfao

假設(shè)將該樹(shù)轉(zhuǎn)換為二叉樹(shù)，其后序遍歷次序?yàn)?d)o

a:abcdefgb:cdebgfac:cdegbfad:edcgfba

27設(shè)X和y是二叉樹(shù)中的任意兩個(gè)結(jié)點(diǎn)，假設(shè)在先根序列中x在y之前，而在后根序列中

x

在y之后，則x和y的關(guān)系是(c)。

A.x是y的左兄弟B.x是y的右兄弟

C.x是y的祖先D.x是y的子孫

28用三叉鏈表作二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，當(dāng)二叉樹(shù)中有n個(gè)結(jié)點(diǎn)時(shí)，有(d)個(gè)空指針。

A.n-1B.nC.n+1D.n+2

29對(duì)一棵完全二叉樹(shù)進(jìn)行層序編號(hào)。則編號(hào)為n的結(jié)點(diǎn)假設(shè)存在右孩子，其位序是(d)。

編號(hào)為n的結(jié)點(diǎn)假設(shè)存在雙親，其位置是(a)。

a:n/2b:2nc:2n-ld:2n+le:nf:2(n+l)

30設(shè)森林F中有三棵樹(shù)，第一、第二和第三棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別為ml、m2和m3,則與

森林F對(duì)應(yīng)的二叉樹(shù)根結(jié)點(diǎn)的右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)是⑷。

A.mlB.ml+m2C.m3D.m2+m3

31以下二叉樹(shù)中，(a)可用于實(shí)現(xiàn)符號(hào)不等長(zhǎng)高效編碼。

a:最優(yōu)二叉樹(shù)b:次優(yōu)查找樹(shù)c:二叉平衡樹(shù)d:二叉排序樹(shù)

32鄰接表存儲(chǔ)結(jié)構(gòu)以下圖的深度優(yōu)先遍歷算法類似于二叉樹(shù)的(a)遍歷。

A.先根B.中根C.后根D.層次

33設(shè)無(wú)向圖G=(V,E)和G'=(V',E'),假設(shè)G是G的生成樹(shù)，則下面不正確的說(shuō)法是(b)。

A.G'是G的子圖B.G'是G的連通分量

C.G’是G的無(wú)環(huán)子圖D.G’是G的極小連通子圖且V'=V

34任何一個(gè)連通圖的最小生成樹(shù)

A.只有一棵B,有一棵或多棵C.一定有多棵D.可能不存在

efef

35深度優(yōu)先遍歷圖使用了數(shù)據(jù)結(jié)構(gòu)(b),而廣度優(yōu)先遍歷圖使用了數(shù)據(jù)結(jié)構(gòu)(c

A)數(shù)組B)棧C)隊(duì)列D)線性表

36某有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下圖。

根據(jù)存儲(chǔ)結(jié)構(gòu)依教材中的算法其深度優(yōu)先遍歷次序?yàn)?d)。

廣度優(yōu)先遍歷此序?yàn)?C)。各強(qiáng)連通分量的頂點(diǎn)集為(h

a:abcde.b:edcba.c:ecdab.d:ecadb.

e:abc及edf:be及aedg:ab及cedh:ac及bed

37以下查找方法中(a)適用于查找單鏈表。

A)順序查找B)折半查找C)分塊查找D)hash查找

38以下算法中(c)適用于求圖的最小代價(jià)生成樹(shù)。(b)能對(duì)圖作廣度優(yōu)先遍歷。

A)DFS算法B)BFS算法C)Prim算法D)Dijkstra算法

39關(guān)鍵路徑是指在只有一個(gè)源點(diǎn)和一個(gè)匯點(diǎn)的有向無(wú)環(huán)網(wǎng)中源點(diǎn)至匯點(diǎn)(c)的路徑。

a:弧的數(shù)目最多b:弧的數(shù)目最少c:權(quán)值之和最大d:權(quán)值之和最小

40希表的查找效率取決于(d

a:哈希函數(shù)b:處理沖突的方法。c:哈希表的裝填因子。d:以上都是

41在Hash函數(shù)H(k)=kMODm中，一般來(lái)說(shuō)，m應(yīng)取(c)?

A.奇數(shù)B.偶數(shù)C.素?cái)?shù)D.充分大的數(shù)

42在順序表查找中，為防止查找過(guò)程中每一步都檢測(cè)整個(gè)表是否查找完畢，

可采用a方法。

A.設(shè)置監(jiān)視哨B.鏈表存貯C.二分查找D.快速查找

43靜態(tài)查找表和動(dòng)態(tài)查找表的區(qū)別在于(b)。

A.前者是順序存儲(chǔ)，而后者是鏈?zhǔn)酱鎯?chǔ)

B.前者只能進(jìn)行查找操作，而后者可進(jìn)行查找、插入和刪除操作

C.前者只能順序查找，而后者只能折半查找

D.前者可被排序，而后者不能被排序

44在一個(gè)含有n個(gè)元素的有序表上進(jìn)行折半查找，找到一個(gè)元素最多要進(jìn)行(b)次元素

比擬。

A.Llog2(n)JB.Llog2(n)J+lC.Llog2(n+l)JD.Llog2(n+l)J+l

45設(shè)輸入序列為20,45,30,89,70,38,62,19依次插入到一棵2-3樹(shù)中(初始狀態(tài)為空)，

該B-樹(shù)為(b)。再刪除38,該B-樹(shù)為(f).

[19,20)(3845)(70,89)

a:

d:

(3070)(45)

/IX

(19,20)(4562)(89)

46根據(jù)插入次序(80,90,100,110,85,70,75,60,72)建立二叉排序樹(shù)。

圖1a)是最終變化的結(jié)果。假設(shè)仍以該插入次序建立平衡二叉樹(shù)。圖(c)是

最

終變化的結(jié)果。

72110

a:b:

c:d:

47假設(shè)有序表中關(guān)鍵字序列為：14,20,25,32,34,45,57,69,77,83,92。對(duì)其進(jìn)

行

折半查找，則在等概率情況下，查找成功時(shí)的平均查找長(zhǎng)度是匚￡[。查找32時(shí)需進(jìn)

行(c)次比擬。

A.1B.2C.3D.4

48哈希表地址空間為A[9],哈希函數(shù)為H(k尸kmod7,采用線性探測(cè)再散列處理沖突。

假設(shè)依次將數(shù)據(jù)序列：76,45,88,21,94,77,17存入該散列表中，則元素17存儲(chǔ)的下標(biāo)為

(h)；

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

A.0B.1C.2D.3

E.4F.5G6H.7

49假設(shè)從二叉樹(shù)的根結(jié)點(diǎn)到其它任一結(jié)點(diǎn)的路徑上所經(jīng)過(guò)的結(jié)點(diǎn)序列按其關(guān)鍵字遞增有

序，

則該二叉樹(shù)是(c

A.二叉排序樹(shù)B.赫夫曼樹(shù)C.堆D.平衡二叉樹(shù)

50當(dāng)待排序序列的關(guān)鍵字次序?yàn)榈剐驎r(shí)，假設(shè)需為之進(jìn)行正序排序，以下方案中⑷為佳。

A,起泡排序B.快速排序

C.直接插入排序D.簡(jiǎn)單項(xiàng)選擇擇排序

51以下排序算法中，@算法可能會(huì)出現(xiàn)：初始數(shù)據(jù)有序時(shí)，花費(fèi)的時(shí)間反而最多。

A.堆排序B.起泡排序C.歸并排序D.快速排序

52在以下排序方法中，(c)方法平均時(shí)間復(fù)雜度為O(nlogn),

最壞情況下時(shí)間復(fù)雜度為0(n2)；(d)方法所有情況下時(shí)間復(fù)雜度均為O(nlogn)。

a.插入排序b.希爾排序c.快速排序d.堆排序

53一組待排序的記錄關(guān)鍵字初始排列如下:56,26,86,35,75,19,77,58,48,42

以下選擇中(d)是快速排序一趟排序的結(jié)果。(c)是希爾排序

(初始步長(zhǎng)為3)一趟排序的結(jié)果。(a)是初始堆(大堆頂)。

A)86,75,77,58,42,19,56,35,48,26.

B)26,56,35,75,19,77,58,48,42,86.

C)35,26,19,42,58,48,56,75,86,77.

D)42,26,48,35,19,56,77,58,75,86.

三.填空題

1數(shù)據(jù)結(jié)構(gòu)通常有以下4類根本結(jié)構(gòu)：集合、、樹(shù)型結(jié)構(gòu)、圖型結(jié)構(gòu)。

2設(shè)單鏈表中結(jié)點(diǎn)形式為［data］嬴］,假設(shè)單鏈表長(zhǎng)度大于等于2,指針p指向表中某

個(gè)結(jié)點(diǎn)且p->next非空，此時(shí)假設(shè)要?jiǎng)h除指針p所指的結(jié)點(diǎn)，可以通過(guò)如下方法進(jìn)行：將p

所指結(jié)點(diǎn)的后繼的元素值復(fù)制到該結(jié)點(diǎn)，然后刪除其后繼結(jié)點(diǎn)。相應(yīng)的語(yǔ)句序列為：

3線性表的順序存儲(chǔ)結(jié)構(gòu)是以來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系的。

4P是單鏈表中某一結(jié)點(diǎn)的指針，P既不是首元結(jié)點(diǎn)也不是尾元結(jié)點(diǎn)，Q是P的前驅(qū)

結(jié)點(diǎn)指針。當(dāng)刪除P結(jié)點(diǎn)時(shí)，鏈表的鏈接可用語(yǔ)句()實(shí)現(xiàn)。

5某樹(shù)的先根遍歷次序?yàn)閍bcdefg后根遍歷次序?yàn)閏debgfa。

假設(shè)將該樹(shù)轉(zhuǎn)換為二叉樹(shù)，其后序遍歷次序?yàn)?層次遍歷次序?yàn)?)。

6某二叉樹(shù)的先序遍歷次序?yàn)閍fbcdeg后序遍歷次序?yàn)閏edbgfa。

其后序遍歷次序?yàn)?)o層次遍歷次序?yàn)?)。

7在二叉樹(shù)的第i層上至少有個(gè)結(jié)點(diǎn)，至多有個(gè)結(jié)點(diǎn)，

深度為k的二叉樹(shù)至多有個(gè)結(jié)點(diǎn).

8對(duì)樹(shù)的遍歷有先序遍歷樹(shù)和后序遍歷樹(shù)。假設(shè)以二叉鏈表作樹(shù)的存儲(chǔ)結(jié)構(gòu)，

則樹(shù)的先序遍歷可借用二叉樹(shù)的遍歷算法來(lái)實(shí)現(xiàn)，

而樹(shù)的后序遍歷可借用二叉樹(shù)的遍歷算法來(lái)實(shí)現(xiàn)。

9設(shè)高度為h的二叉樹(shù)上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹(shù)中所包含的結(jié)點(diǎn)數(shù)至少

是,至多是。

10對(duì)任何一棵二叉樹(shù)T,假設(shè)其終端結(jié)點(diǎn)數(shù)為n0.度為2的結(jié)點(diǎn)為n2,則n0與n2的關(guān)系為

()。

11如果對(duì)完全二叉樹(shù)中結(jié)點(diǎn)從1開(kāi)始按層進(jìn)行編號(hào)，設(shè)最大編號(hào)為n；那么，可以斷定編

號(hào)為i(i>l)的結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為()；所有編號(hào)()的結(jié)點(diǎn)為葉子結(jié)點(diǎn)。

12n個(gè)頂點(diǎn)的連通圖至少有條邊，至多有條邊。

13對(duì)于圖的存儲(chǔ)結(jié)構(gòu)有()、()()()等方法。

14在一個(gè)無(wú)向圖的鄰接表中，假設(shè)表結(jié)點(diǎn)的個(gè)數(shù)是m,則圖中邊的條數(shù)是,條。

15假設(shè)有序表中關(guān)鍵字序列為：12,22,33,44,55,66,77,88,99對(duì)其進(jìn)行折半查找,

則在等概率情況下，查找成功時(shí)的平均查找長(zhǎng)度是(查找99時(shí)需進(jìn)行()次比

較。

16在哈希表中，處理沖突的方法有開(kāi)放定址法，________笠。

17在二叉樹(shù)的第i層上至少有個(gè)結(jié)點(diǎn)，至多有個(gè)結(jié)點(diǎn)，深度為k的二叉樹(shù)至多有

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

18對(duì)于一棵高度為K的二叉排序樹(shù)，結(jié)點(diǎn)數(shù)最少可有個(gè)，最多可有個(gè)。

19用遍歷對(duì)二叉排序樹(shù)進(jìn)行訪問(wèn)可得到有序序列。

20Hash函數(shù)為H(K)=Kmod13,散列地址為0-14,用二次探測(cè)再散列

處理沖突，關(guān)鍵字(23,34,56,24,75,12,49,52,36,92)

的分布如圖，則平均成功的查找長(zhǎng)度為()、平均失敗的查找長(zhǎng)度為()。

012345678910II121314

52369256342324751249

21一棵m階的B樹(shù)，第一層至少有一個(gè)結(jié)點(diǎn)；第二層至少有2個(gè)結(jié)點(diǎn),

除根之外的所有非終端結(jié)點(diǎn)至少有()棵子樹(shù)，

樹(shù)中每個(gè)結(jié)點(diǎn)至多有()棵子樹(shù)。

22在哈希表中，處理沖突的方法有開(kāi)放定址法，,—

23哈希表的查找效率取決于()()和(

24高度為4(包含不帶關(guān)鍵字的葉子結(jié)點(diǎn)層)的7?階?B?樹(shù)最少有個(gè)關(guān)鍵字，最多

有個(gè)關(guān)鍵字；如果其中的某結(jié)點(diǎn)正好有2個(gè)兒子，那么，該結(jié)點(diǎn)必定是

_________結(jié)點(diǎn)o

25對(duì)n個(gè)元素的序列進(jìn)行內(nèi)部排序，假設(shè)用起泡排序法，最少的比擬次數(shù)是，

最多的比擬次數(shù)是o

25(算法填空)

StatusPreordertraverse(BitreeT,Status(*Visit)(Telemtypee)){

〃先序非遞歸遍歷二叉樹(shù)。

Initstack(S);Push(S,T);

While(!stackempty(S))

{While(gettop(S,p)&&)

{if(!Visit(p->data))returnERROR;

Pop(S,p);

if()

;push(S,p->rchild);}

returnok;

26(算法填空)

以下算法試圖完成在數(shù)組A中搜索有無(wú)關(guān)鍵字key,假設(shè)有，返回?cái)?shù)組下標(biāo)，假設(shè)無(wú)，返回-1。

在“〃處填上適宜的內(nèi)容,完成該算法。

intBinarySearch(keytypeA[],intlow,inthigh,keytypekey)

(

while()

middle=(low+high)/2;

if(_______________________)

returnmiddle;

if(key<AlmiddleJ)

else

)

return-1;

}//endofBinarySearch

27(算法填空)

以下函數(shù)為堆排序中的堆調(diào)整過(guò)程(調(diào)整H.r[s]的關(guān)鍵字，使H.r[s..m]成為一小頂堆)。請(qǐng)?jiān)?/p>

“〃處填上適宜的內(nèi)容,完成該算法。

Voidheapadjust(heaptype@H,ints,intm){

rc=H.r[s];

for(j=2*s;j<=m;j*=2){

if(j<m&&)++j;

if()break;

H.r[s]=H.r[j];s=j;

}//heapadjust

圖示結(jié)構(gòu)題

1在電文中只出現(xiàn)頻率為(5,26,7,23,20,19)的6個(gè)字符,

畫(huà)出你建的哈夫曼樹(shù)，并給出其哈夫曼編碼。

請(qǐng)畫(huà)出該二叉樹(shù)，并為之建立先序線索。

3某二叉樹(shù)的先序遍歷次序?yàn)椋篴,b,c,d,e,f,g.中序遍歷次序?yàn)椋篵,a,d,f,e,g,c

畫(huà)出該二叉樹(shù)，并在該二叉樹(shù)上建立中序線索。

4某二叉樹(shù)的中序遍歷次序?yàn)锽EGFDAC,先序遍歷次序?yàn)锳BDEFGC。

試畫(huà)出該二叉樹(shù)，并為之建立中序線索(圖示之)。

5某二叉樹(shù)的后序遍歷和中序遍歷次序分別為FBEDGCA和FBADECG,

請(qǐng)構(gòu)造并畫(huà)出該二叉樹(shù)。

6設(shè)某一電文只出現(xiàn)a,b,c,d,e,f,g7個(gè)字母；出現(xiàn)頻率分別為30%,10%,05%,04%,13%,18%

及20%,請(qǐng)給出各字母的哈夫曼編碼。

7將圖示森林轉(zhuǎn)換為二叉樹(shù)，并對(duì)該二叉樹(shù)先序全序線索化。

8將圖示森林轉(zhuǎn)換為二叉樹(shù)，并對(duì)該二叉樹(shù)中序全序線索化。

9某二叉樹(shù)的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲(chǔ)表示如下:

012345678910111213141516171819

ABCDEFGHI

(1)試畫(huà)出此二叉樹(shù)的圖形表示。

(2)將此二叉樹(shù)看作森林的二叉樹(shù)表示，試將它復(fù)原為森林。

10某有向圖如下圖：

1)給出其十字鏈表存儲(chǔ)結(jié)構(gòu)

2)給出其深度優(yōu)先遍歷次序。

3)給出其廣度優(yōu)先遍歷次序。

4)給出各強(qiáng)連通分量。

11設(shè)輸入序列為20,45,30,89,70,溫62,19,依次插入到一棵2-3樹(shù)中(初始狀態(tài)為

空)，請(qǐng)畫(huà)出該B-樹(shù)。

12右圖為一棵3階B一樹(shù)。(20,25)

1)畫(huà)出在該樹(shù)上插入元素15/|\

后的B一樹(shù)。(10,14)(21)(35)

2)接著，再刪除元素35,畫(huà)出刪除后的B—樹(shù)。

13Hash函數(shù)為H(K)=Kmod13,散列地址為074,用線性探測(cè)再散列處理

沖突，給出關(guān)鍵字(56,34,68,23,16,70,48,35,83,12,14,57)

在散列地址的分布。并指出平均成功的查找長(zhǎng)度是多少？

01234567891011121314

14根據(jù)插入次序(20,30,70,60,10,100,110,90,80。)建立平衡的二叉排序樹(shù)。

15設(shè)哈希表長(zhǎng)為16,哈希函數(shù)為H(key)=keymod13,用開(kāi)放定址法的二次探測(cè)再散列

處理沖突(di=l2,-I2,22,0,32,-32……)。依次存入12個(gè)元素：56,82,17,24,

36,21,83,96,13,34,57,50?請(qǐng)畫(huà)出它們?cè)诒碇械姆植记樾巍?/p>

16待排序序列為：25,12,9,20,7,31,24,35,17,10,試寫出:

(1).堆排序初始建堆(大頂堆)的結(jié)果；

(2).以第一個(gè)元素為樞軸的快速排序一趟掃描的結(jié)果；

(3).希爾排序第一趟(增量為5)的結(jié)果。

算法設(shè)計(jì)題

1設(shè)有一個(gè)帶頭結(jié)點(diǎn)、元素按值遞增有序的單鏈表，結(jié)點(diǎn)的類型定義如下：

lypedefstructLNode

{intdata;

structLNode*next;

}LNode,*LinkList;

編寫算法，刪除其中所有值相同的多余元素結(jié)點(diǎn)

2某線性表中元素以降序排列，現(xiàn)要插入一個(gè)元素X,插入后該線性元素仍保持降序。線性

表采用帶頭結(jié)點(diǎn)單鏈表方式存貯。?請(qǐng)編寫該插入算法。

3編寫在一有序順序表中插入數(shù)據(jù)元素X的算法INSERT(L,X)。

4寫一算法，Deletedinklist&L,X),刪除單鏈表中所有值為X的結(jié)點(diǎn)。

單鏈表結(jié)點(diǎn)的類型定義如下：

lypedefstructLNode(

intdata;

structLNode*next;

}LNode,*Linklist;

5寫一算法，Contrarydinklist&L),對(duì)一帶頭結(jié)點(diǎn)且僅設(shè)尾指針L的循環(huán)單鏈表就