數(shù)據(jù)結(jié)構(gòu)題庫

考證素材

數(shù)據(jù)結(jié)構(gòu)課程代碼02331)

一、單項(xiàng)選擇題本大題共15小題，每題2分，共30分)在每題列出的四個(gè)備選項(xiàng)中惟獨(dú)一個(gè)是符合題

目要求的，請將其代碼填寫在題后的括號內(nèi)。錯(cuò)選、多項(xiàng)選擇或者未選均無分。

1、對順序存儲(chǔ)的線性表設(shè)其長度為n,在任何位置上插入或者刪除操作都是等概率的。插入一個(gè)

元素時(shí)平均要挪移表中的(A)個(gè)元素。

A、n/2B、(n+l)/2C、(n1)/2D、n

2、一個(gè)向量(一種順序表)第一個(gè)元素的存儲(chǔ)地址是100,每一個(gè)元素的長度為2,則第5個(gè)元素

的地址是--B―o

A、100B、108C、110D、120

3、一個(gè)棧的入棧序列a,b,c,d,e,則棧的不可能的輸出序列是一C__o

A、edcbaB、decbaC、dceabD、abode

4、假設(shè)已知一個(gè)棧的入棧序列是L2,3,...,n,其輸出序列為pl,p2,p3,...,pn,假設(shè)pl二n,

則pi為_C_一_o

A、iB、niC、n-i+lD、nil

5、判定一個(gè)循環(huán)隊(duì)列QU(最多元素為m)為空的條件是—C_o

A、rear-front=B、rear—front-1=

C、front二二rearD、front==rear+1

6、判定一個(gè)循環(huán)隊(duì)列QU(最多元素為m,m二二MaxsizeT)為滿隊(duì)列的條件是_A—。

A、((rear-front)+Maxsize)%Maxsize==m

B、rear-front-l=C、front二二rearD、front==rear+1

7、循環(huán)隊(duì)列用數(shù)組A0,mT］存放其元素值，已知其頭尾指針分別是front和rear,則當(dāng)前隊(duì)列

中的元素個(gè)數(shù)是一工。

A、(rear-front+m)%mB、rear-front+1

C、rear-front-1D、rear-front

8、設(shè)串的長度為n,則它的子串個(gè)數(shù)為一。

A^nB、n(n+1)C、n(n+1)/2D、n(n+l)/2+1

9Sl="ABCD,S2="CD則S2在S3中的位置是(C)

A1B、2C、3D、4

10、設(shè)數(shù)組a7:6］的基地址為1024,每一個(gè)元素占2個(gè)存儲(chǔ)單元,假設(shè)以行序?yàn)橹餍蝽樞虼鎯?chǔ)，

則元

素a2］4］的存儲(chǔ)地址是_

A、1054B、1056C、1058D、1098

11、二維數(shù)組A中，每一個(gè)元素A的長度為3個(gè)字節(jié)，行下標(biāo)i從0到7,列下標(biāo)j從0到9,從

首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按列存放時(shí)，元素A417］的起始地址為」-0

A、SA+141B、SA+180C、SA+222D、SA+225

考證素材

考證素材

12、二維數(shù)組A中，每一個(gè)元素的長度為3個(gè)字節(jié)，行下標(biāo)i從0到7,列下標(biāo)j從0到9,從首

地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，存放該數(shù)組至少需要的字節(jié)數(shù)是一土一。

A、80B、100C、240D、270

13、二維數(shù)組A中，每一個(gè)元素A的長度為3個(gè)字節(jié)，行下標(biāo)i從0到7,列下標(biāo)j從0到9,從首

地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按行存放時(shí)，數(shù)組元素A7]4]的起始地址為工

A、SA+141B、SA+144C、SA+222D、SA+225

14、假定在一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15個(gè)，單分支結(jié)點(diǎn)數(shù)為30個(gè)，則葉子結(jié)點(diǎn)個(gè)數(shù)為B

A、15B、16C、17D、47

15、按照二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的不同形狀的二叉樹有一，一種。

A、3B、4C、5D、6

16、深度為5的二叉樹至多有J一個(gè)結(jié)點(diǎn)。

A、16B、32C、31D、10

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

_A_____。

A、2hB、2h-lC、2h+lD、h+1

18、對一個(gè)滿二叉樹，m個(gè)樹葉，n個(gè)結(jié)點(diǎn)，深度為h,則皂。

A、n=h+mB、h+m=2nC、m=h-lD、n=2h-l

19、如果某二叉樹的前根次序遍歷結(jié)果為stuwv,中序遍歷為uwtvs那末該二叉樹的后序?yàn)開C…

A、uwvtsB、vwutsC、wuvtsD、wutsv

20、某二叉樹的前序遍歷結(jié)點(diǎn)訪問順序是abdgcefh,中序遍歷的結(jié)點(diǎn)訪問順序是dgbaechf,則其

后序遍歷的結(jié)點(diǎn)訪問順序是一_1一。

A、bdgcefhaB、gdbecfhaC、bdgaechfD、gdbehfca

21、已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷序列是一_

A、acbedB、decabC、deabcD>cedba

22、由帶權(quán)為9,2,5,7的四個(gè)葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長度為(D)。

A、23B、37C、46D、44

23、在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹第i層上，最多具有(C)個(gè)結(jié)點(diǎn)。

A、2’B、2i+1C、2rD、2"

24、在一個(gè)圖中，全部頂點(diǎn)的度數(shù)之和等于全部邊數(shù)的倍數(shù)為——

A、1/2B、1C、2D、4

25、在一個(gè)有向圖中，全部頂點(diǎn)的入度之和等于全部頂點(diǎn)的出度之和的一具二一倍。

A、1/2B、1C、2D、4

26、一個(gè)有n個(gè)頂點(diǎn)的無向圖的邊數(shù)最多為一"

A、nB、n(n-l)C、n(nT)/2D、2n

考證素材

考證素材

27、具有4個(gè)頂點(diǎn)的無向徹底圖有條邊。

考證素材

考證素材

A、B、12C、16D、20

28、具有6個(gè)頂點(diǎn)的無向圖至少應(yīng)有一L一條邊才干確保是一個(gè)連通圖。

A、B、C、D、

29、在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要一條邊。―

*'nB、n+1C、n-lD、n/2

A、nB、(n-l)2C、n-lD、n2

對于一個(gè)具有n個(gè)頂點(diǎn)的無向圖，假設(shè)采用鄰接矩陣表示，則該矩陣的大小是一_L一。

31、對于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，假設(shè)采用鄰接表表示，則表頭向量的大小為一_1一。

A、nB、n+1C、n-lD>n+e

32、判定一個(gè)有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ猓€可以利用A…

A、求關(guān)鍵路徑的方法B、求最短路徑的Dijkstra方法

C、寬度優(yōu)先遍歷算法D、深度優(yōu)先遍歷算法

33、關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中

A、從源點(diǎn)到匯點(diǎn)的最長路徑B、從源點(diǎn)到匯點(diǎn)的最短路徑

C、最長的回路D、最短的回路

34、一個(gè)有n個(gè)頂點(diǎn)的無向連通圖,它所包含的連通分量個(gè)數(shù)為Ji

A、0B、1C、nD、n+1

35.對于一個(gè)有向圖，假設(shè)一個(gè)頂點(diǎn)的入度為kl,、出度為k2,則對應(yīng)鄰接表中該頂點(diǎn)單鏈表中

的結(jié)點(diǎn)數(shù)為B->

A、klB、k2C、kl-k2D、kl+k2

36、對于一個(gè)有向圖，假設(shè)一個(gè)頂點(diǎn)的入度為kl,、出度為k2,則對應(yīng)逆鄰接表中該頂點(diǎn)單鏈表

中的結(jié)點(diǎn)數(shù)為Ao

A、klB、k2C、kl-k2D、kl+k2

37、具有n個(gè)頂點(diǎn)的有向圖最多有(B)條邊。

2

A,nB、n(n-l)C、n(n+l)D、n

38、n個(gè)頂點(diǎn)的強(qiáng)連通圖至少有(A)條邊。

A、nB、n~lC、n+1D、n(n~l)

39、在一個(gè)具有n個(gè)頂點(diǎn)的有向圖中，假設(shè)全部頂點(diǎn)的出度之和為s,則全s,部頂點(diǎn)的入度之和

為(A)。

A、sB、s-1C、s+1D、n

40、在一個(gè)無向圖中，假設(shè)兩個(gè)頂點(diǎn)之間的路徑長度為k,則該路徑上的頂點(diǎn)數(shù)為(B)

A、kB、k+1C、k+2D、2k

41、一個(gè)圖中包含k個(gè)連通分量，假設(shè)按深度優(yōu)先(DFS)搜索方法訪問全部結(jié)點(diǎn)，則必須調(diào)用

(A)

次深度優(yōu)先遍歷算法。

A、kB、C、k-1D、k+1

考證素材

考證素材

42、設(shè)G1=(V1,E1)和G2=(V2,E2)為兩個(gè)圖,VIV2,ElE2,則稱(A)

A、G1是G2的子圖B、G2是G1的子圖

C、G1是G2的連通分量D、G2是G1的連通分量

43、采用順序查找方法查找長度為n的線性表時(shí),每一個(gè)元素的平均查找長度為_C_.

A、nB、n/2C、(n+l)/2D、(n-l)/2

44、采用二分查找方法查找長度為n的線性表時(shí),每一個(gè)元素的平均查找長度為』_c

A、0[m)B、O(nlogn)C、0(n)D、O(logn)

45、有一個(gè)有序表為｛1,3,9,12,32,41,45,62,75,77,82,95,100),當(dāng)

二分查找值82為的結(jié)點(diǎn)時(shí),.次比擬后查找成功。

A、1B、2C、4D、8

46、有一個(gè)長度為12的有序表，按二分查找法對該表進(jìn)行查找，在表內(nèi)各元素等概率情況下查找

成功所需的平均比擬次數(shù)為一#一。

A、35/12B、37/12C、39/12D、43/12

47、對于18個(gè)元素的有序表采用二分(折半)查找，則查找A3]的比擬序列的下標(biāo)為(D)。

A、1、2、3B、9、5、2、3C、9、5、3D>9、4、2、3

48、一組記錄的排序碼為(46,79,56,38,40,84),則利用堆排序的方法建立的初始堆為一—

左一。

A、79,46,56,38,40,80B、38,40,56,79,46,84,

C、84,79,56,46,40,38D、84,56,79,40,46,38

49一組記錄的關(guān)鍵碼為(46,5638,40,84),則利用快速排序的方法，以第一個(gè)記錄

7Q

為基準(zhǔn)得到的一次劃分結(jié)果為—C?

A、38,40,46,56,79,84B、40,38,46,79,56,84

C、40,38,46,56,79,84D、40,38,46,84,56,79

50、一組記錄的排序碼為(應(yīng)16,塵，理82,23,40,36,72)，其中含有5個(gè)長度為

2的有序表,按歸并排序的方法對該序列進(jìn)行一趟歸并后的結(jié)果為一，一。

A16253548234079,82,3672

B16253548798223,36,4072

C16254835798223,36,4072

D16253548792336,40,7282

51、下述幾種排序方法中,要求內(nèi)存量最大的是4

A、插入排序B、選擇排序C、快速排序D、歸并排序

52、在對n個(gè)元素進(jìn)行簡單項(xiàng)選擇擇排序過程中，第i趟需從(A)個(gè)元素中選擇出最小值元素。

A、n-i+1B、n-iC、iD、i+1

53、n個(gè)記錄直接插入排序所需的記錄最小比擬次數(shù)是(A)

A、n-1B>2(n-l)C>(n+2)(n-1)/2D、n

考證素材

考證素材

54、一組記錄的關(guān)鍵字為(45,80,55,40,42,85)，則利用堆排序的方法建立的初始堆為(B)。

A、(80,45,55,40,42,85)B、(85,80,55,40,42,45)

C、(85,80,55,45,42,40)D、(85,55,80,42,45,40)

55、一組記錄的關(guān)鍵字為(45,80,55,40,42,85),則利用快速排序的方法，以第一個(gè)記錄

為基準(zhǔn)得到一次劃分結(jié)果是(

A、(40,42,45,55,80,85)B、(42,40,45,80,55,85)

C、(42,40,45,55,80,85)D、(42,40,45,85,55,80)

56.將一棵有100個(gè)結(jié)點(diǎn)的徹底二叉樹從根這一層開始，每一層上從左到右挨次對結(jié)點(diǎn)進(jìn)行編

號，根結(jié)點(diǎn)的編號為1,則編號為49的結(jié)點(diǎn)的左孩子編號為(A1

A)98B)99C)5048

57.一組記錄的排序碼為(48,24,18,53,16,26,,4咪納冒泡排序法進(jìn)行排序，則第一趟排序

需要進(jìn)行記錄交換的次數(shù)是(C1

A)3B)4C)5D)6

58.采用分塊查找時(shí)，如某線性表有256個(gè)元素，查找每一個(gè)元素的概率相同，假設(shè)采用順序查

找來確定元素所在的塊，則每塊包含()個(gè)結(jié)點(diǎn)時(shí)，平均查找長度最

A)256B)15小。16D)18

59.對于有向圖的鄰接矩陣“該圖共有(B)條弧。

A)5B)4D)2

60由帶權(quán)9、1、3、5、6的五個(gè)葉子結(jié)點(diǎn)生成的哈夫曼樹的帶權(quán)路徑長度為(C±

50B:60C:52D)65

、填空題本大題共10小題，每題2分，共20分)請?jiān)诿款}的空格中填上正確答案。錯(cuò)填、不填均無

分。

1、下面程序段的時(shí)間復(fù)雜度是一O(mXn)。

for(i=0；i<n;i++)

for(j=0;j<m;j++)

ai]j]=0;

n

2、下面程序段的時(shí)間復(fù)雜度是——0!tL-o

i=s=0

while(s<n)

(

i++;/Xi=i+1X/

s+=i;/Xs=s+iX/

)

3、下面程序段的時(shí)間復(fù)雜度是…0(m)—…

考證素材

考證素材

s=0;

for(i=0；i<n;i++)

for(j=0;j<n;j++)

s+=bi]j];

sum二s;

4、下面程序段的時(shí)間復(fù)雜度是一0(lo%n)——。

i二l；

while(i<=n)

i二iX3;

5、在順序表中，假設(shè)第一個(gè)元素所在的地址為Loc(al),每一個(gè)元素在內(nèi)存中占有L個(gè)存儲(chǔ)單元，

則元素ai在內(nèi)存中的地址Loc(ai)=:Loc(al)+(iT)XL-----。

6、向一個(gè)長度為n的順序表的第i個(gè)元素(Ki<n+1)之前插入一個(gè)元素時(shí)，需向后挪移一二n-i

+1個(gè)元素。

7、向一個(gè)長度為n的順序表中刪除第i個(gè)元素(Ki〈n)時(shí)，需向前挪移n-i個(gè)元素。

8、串s-abcdef*,sl=，cde',si在s中的位置為3

9、已知二維數(shù)組Am]n]采用行序?yàn)橹鞣椒ù鎯?chǔ)，每一個(gè)元素占k個(gè)存儲(chǔ)單元，并且第一個(gè)元素的

存儲(chǔ)地址是LOC(AO]O]),則Ai[j]的地址是——_L0C地0[0])+(nXi+i)Xk

10、二維數(shù)組A10]20]采用列序?yàn)橹鞣椒ù鎯?chǔ)，每一個(gè)元素占一個(gè)存儲(chǔ)單元并且A0]0]的存儲(chǔ)地址

是200,則A6]12]的地址是326…

11、二維數(shù)組A10...20]5...10]采用行序?yàn)橹鞣椒ù鎯?chǔ)，每一個(gè)元素占4個(gè)存儲(chǔ)單元并且A10]5]

的存儲(chǔ)地址是1000,則A1819]的地址是一「208。

12>現(xiàn)有一個(gè)n階的對稱矩陣an]n],現(xiàn)將其壓縮存儲(chǔ)在一個(gè)一維數(shù)組sm]中，則m=-二n(n+l)

/2,假設(shè)以行序?yàn)橹餍蜻M(jìn)行存儲(chǔ)，則元素=j)在s中的下標(biāo)k二—i(iT)/2+jT—。

13、在一個(gè)mXn的矩陣中，假設(shè)a0[0]是第一個(gè)元素，則ai[j]是第---iXn+i個(gè)元素。

14、在二叉樹中，某一結(jié)點(diǎn)x的編號為i,x假設(shè)有雙親，其雙親編號應(yīng)為一一i/2一4x假設(shè)有

左孩子，其左孩子編號應(yīng)為一一2Xi-;x假設(shè)有右孩子，其右孩子應(yīng)為一2Xi+l--------o

15、8層徹底二叉樹至少有128個(gè)結(jié)點(diǎn),擁有100個(gè)結(jié)點(diǎn)的徹底二叉樹的最大層數(shù)為

7—o

16、n個(gè)頂點(diǎn)的連通圖至少nT_條邊。

17、在無向圖G的鄰接矩陣A中，假設(shè)Ai]j]等于1,則Aj]i]等于=!

n

18、一個(gè)無向圖有n個(gè)頂點(diǎn)和e條邊，則全部頂點(diǎn)的度的和即di('表示頂點(diǎn)i的度)二

i1

2eo

考證素材

考證素材

19、在有n個(gè)頂點(diǎn)的有向圖中，每一個(gè)頂點(diǎn)的度最大可達(dá)2(nT)。

20、對于長度為n的線性表，假設(shè)進(jìn)行順序查找，則時(shí)間復(fù)雜度為一0(n)一;假設(shè)采用折半

法查找，則時(shí)間復(fù)雜度為一一0(lo%n)

21、已知有序表為(12,18,24,35,47,50,62,83,90,115,134),當(dāng)用折半查找90時(shí)，

需進(jìn)行2次查找可確定成功；查找47時(shí)，需進(jìn)行一次查找成功；查找100時(shí)，需進(jìn)行工次查找才干

確定不成功。

22、平衡二叉排序樹上任一結(jié)點(diǎn)的平衡因子只可能是。、，或者To

23、用起泡法對n個(gè)關(guān)鍵碼排序，在最好情況下，只需做一心次比擬；在最壞的情況下

要做n(nT)/2次比擬。

24、設(shè)字符串Sl="ABCDEF,S2="PQRS,則運(yùn)算S=C0NCAT(SUB(SI,2,LEN(S2)),SUB

(SI,LEN(S2),2))后的串值為."BCDEDE----。

25、在一棵二叉排序樹上按一一一一中序遍歷得到的結(jié)點(diǎn)序列是一個(gè)有序序列。

26、在一個(gè)圖中，全部頂點(diǎn)的度數(shù)之和等于全部邊數(shù)的-----4_一倍。

27、在一個(gè)具有n個(gè)頂點(diǎn)的無向徹底圖中，包含有一n(n-l)/2一條邊,在一個(gè)具有n個(gè)頂

點(diǎn)的有向徹底圖中，包含有一n(n-l)一條邊。

28、假定一個(gè)有向圖的頂點(diǎn)集為{a,b,c,d,e,f},邊集為?a,c>,<a,e>,<c,f>,<d,c>,<e,b>,

<e,d>),則出度為0的頂點(diǎn)個(gè)數(shù)為____二一入度為1的頂點(diǎn)個(gè)數(shù)為一『____。

29、在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)則至少需要n-1一條邊。

30、假設(shè)一個(gè)圖的頂點(diǎn)集為{a,b,c,d,e,f},邊集為{(a,b),(a,c),(b,c),(d,e)},則該圖含有

_-3_個(gè)連通分量。

31、對于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的連通圖，其生成樹中的頂點(diǎn)數(shù)和邊數(shù)分別為______n-

和nT-o

32、假定一個(gè)順序表的長度為40,并假定查找每一個(gè)元素的概率都相同，則在查找成功情況下的

平均查找長度…20.5.....在查找不成功情況下的平均查找長度…41-------。

33、在索引查找中，假定查找表(即主表)的長度為96,被等分為8個(gè)子表，則進(jìn)行索引查找

的平均查找長度為一」1一—。

34、假定對長度n=50的有序表進(jìn)行折半查找，則對應(yīng)的判定樹高度為一，一一，最后一層的結(jié)

點(diǎn)數(shù)為--19——“

35、假定在索引查找中，查找表長度為n,每一個(gè)子表的長度相等，設(shè)為s,則進(jìn)行成功查找的平均

查找長度為.....(n/s+s)/2+l.......o

46、假定一組記錄為(46,79,56,38,40,84),則利用堆排序方法建立的初始小根堆為(38,40,56,

79,46,84)—

37、假定一組記錄為(46,79,56,38,40,84),在冒泡排序的過程中進(jìn)行第一趟排序后的結(jié)果為(46.

56.38.40.79.84)....

考證素材

考證素材

38、假定一組記錄為(46,79,56,64,38,40,84,43),在冒泡排序的過程中進(jìn)行第一趟排序時(shí)，元素79

將最終下沉到其后第_!一個(gè)元素的位置。

39、假定一組記錄為(46,79,56,38,40,80)，對其進(jìn)行快速排序的第一次劃分后的結(jié)果為一=40

38465679801。

40、假定一組記錄為(46,79,56,38,40,80,46,75,28,46)，對其進(jìn)行歸并排序的過程中，第二趟

歸并后的子表個(gè)數(shù)為一一3——。

三、應(yīng)用題本大題共4小題，每題7分，共28分)

1、分別畫出具有3個(gè)結(jié)點(diǎn)的樹和三個(gè)結(jié)點(diǎn)的二叉樹的全部不同形態(tài)。

解：具有3個(gè)結(jié)點(diǎn)的樹有兩種不同形態(tài)。

具有3個(gè)結(jié)點(diǎn)的二叉樹有以下五種不同形態(tài)。

2、如下列圖所示的二叉樹，試分別寫出它的順序表示和鏈接表示(二叉鏈表)。解：(1)順序表

(2)該二叉樹的二叉鏈表表示。

3、假定用于通信的電文由8個(gè)字符A、B、C、D、E、F、G、H組成，各字母在電文中浮現(xiàn)的概率為

5%、25%、4%、7%、9%、12%,30%、8%,試以這8個(gè)字母構(gòu)造哈夫曼樹。

解：依據(jù)題意，設(shè)這8個(gè)字母對應(yīng)的權(quán)值分別為(5,25,4,7,9,12,30,8),并且n=8。步驟

如下：

4、假設(shè)一棵二叉樹的先序序列為EBADCFHGIKJ,中序序列為ABCDEFGHIJK,請寫出該二叉樹的后序

遍歷序列。

解：后序序列：ACDBGJKIHFE

5、已知一個(gè)無向圖的鄰接表下列圖所示，要求：

(1)畫出該無向圖；

(2)依據(jù)鄰接表，分別寫出用DFS(深度優(yōu)先搜索)和BFS(廣度優(yōu)先搜索)算法從頂點(diǎn)V0開始遍歷

該圖后所得到的遍歷序列。

解：(D該無向圖如下列圖所示。

(2)依據(jù)該無向圖的鄰接表表示，從頂點(diǎn)V0開始的深度優(yōu)先遍歷序列為：V0、V2、V3、VI、V4、

V6、V5?廣度優(yōu)先遍歷序列為VO、V2、V5、V6、VI、V3、V4。

6、如下列圖所示的一個(gè)網(wǎng)，按照Prim方法，從頂點(diǎn)VI出發(fā)，求該網(wǎng)的最小生成樹的產(chǎn)生過程。解：

步驟如下：

7、記錄的關(guān)鍵字序列為：63,90,70,55,67,42,98,83,10,45,58,則畫出構(gòu)造一棵二叉排序

樹的過程。

解：構(gòu)造二叉排序樹的過程如下列圖所示。

8、已知一組記錄為(46,74,53,14,26,38,86,65,27,給出采用冒泡排序法進(jìn)行排序時(shí)每一趟的排序結(jié)

果。

解：排序過程如下：

(0)46745314263886652734

⑴46531426387465273486

⑵46142638536527347486

⑶14263846532734657486

(4)14263846273453657486

⑸14263827344653657486

(6)14262734384653657486

考證素材

考證素材

(7)14262734384653657486

9、已知一組記錄為(46,74,53,14,26,38,86,65,27,給出采用直接插入排序法進(jìn)行排序時(shí)每一趟的排

序結(jié)果。

解：排序過程如下所示：

(0)46745314263886652734

(1)46745314263886652734

(2)46537414263886652734

(3)14465374263886652734

(4)14264653743886652734

(5)14263846537486652734

(6)14263846537486652734

⑺14263846536574862734

(8)14262738465365748634

(9)14262734384653657486]

1(X關(guān)鍵字序列為(47,7,1116,92,22,8,3,50,37,89,94,21),哈希函數(shù)為:

mod11,用拉鏈表處理沖突。

解：建表如下：

11、已知如下列圖所示的有向圖，請給出該圖的

(1)每一個(gè)頂點(diǎn)的出/入度；⑵鄰接矩陣；

⑶鄰接表；

解：(1)每一個(gè)頂點(diǎn)的出/入度是：

⑵鄰接矩陣：

⑶鄰接表：12、已知圖的鄰接矩陣如下列圖所示。試分別畫出自頂點(diǎn)A出發(fā)進(jìn)行遍歷所得的深度優(yōu)先

生成樹和廣度優(yōu)先生成樹。

解：(1)深度優(yōu)先搜索如下所示：

(2)廣度優(yōu)先搜索如下所示：

13、已知一組記錄為(46,74,53,14,26,38,86,65,27,給出采用歸并排序法進(jìn)行排序時(shí)每一趟的排序結(jié)

果。

解：排序過程如下所示：

(0)46745314263886652734]

(1)46741453263865862734]

(2)14465374263865862734]

(3)14263846536574862734]

(4)14262734384653657486]14、假定一個(gè)待哈希存儲(chǔ)的線性表為(32,75,29,63,

48,94,25,36,18,70,49,80),哈希地址空間為

HT12],假設(shè)采用除留余數(shù)法構(gòu)造哈希函數(shù)和拉鏈法處理沖突，試畫出最后得到的哈希表，并求出平均

查找長度。

解：H(K)=K%11,哈希表如下列圖所示，平均查找長度17/12

15、對于一個(gè)無向圖如下所示，假定采用鄰接矩陣表示，試分別寫出從頂點(diǎn)0出發(fā)按深度優(yōu)先搜索遍

歷得到的頂點(diǎn)序列和按廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序列。

解：(1)深度優(yōu)先搜索序列：0,1,2,8,3,4,5,6,7,9

(2)廣度優(yōu)先搜索序列：0,1,4,2,7,3,8,6,5,9

16、已知如下列圖所示的一個(gè)網(wǎng)，按照Kruskal方法，求該網(wǎng)的最小生成樹的產(chǎn)生過程。解：過程如

下列圖所示。

考證素材

考證素材

四、算法設(shè)計(jì)題本大題共2小題，每題11分，共22分)

1、編寫一個(gè)單鏈表類的成員函數(shù)，完成刪除不帶頭結(jié)點(diǎn)的單鏈表中數(shù)據(jù)域值等于X的第一個(gè)結(jié)點(diǎn)的操

作。假設(shè)刪除成功，則返回被刪除結(jié)點(diǎn)的位置；否則，返回T。

算法設(shè)計(jì)如下：

publicintremove(Objectx){

Nodep=head;〃初始化,p指向首結(jié)點(diǎn)

Nodeq=null;〃q用來記錄p的前驅(qū)結(jié)點(diǎn)

intj=0;〃上為計(jì)數(shù)器

〃從單鏈表中的首結(jié)點(diǎn)元素開始查找，直到p.getDataO指向元素X或者到達(dá)單鏈表的表尾while(p!=null

&!p.getData().equals(x)){

q二P；

P=p.getNextO;〃指向下一個(gè)元素

++j；〃計(jì)數(shù)器的值增1

)

if(p!=null&&q==null)〃刪除的是單鏈表中的首結(jié)點(diǎn)head二p.getNext();

elseif(p!=null){〃刪除的是單鏈表中的非首結(jié)點(diǎn)q.setNext(p.getNext());

}

else

returnT;〃值為x的結(jié)點(diǎn)在單鏈表中不存在

returnj;

}

2、編寫一個(gè)單鏈表類的成員函數(shù)，完成刪除帶頭結(jié)點(diǎn)的單鏈表中數(shù)據(jù)域值等于x的全部結(jié)點(diǎn)的操

作。要求函數(shù)返回被刪除結(jié)點(diǎn)的個(gè)數(shù)。

算法設(shè)計(jì)如下：

publicintremoveAll(Objectx){

Nodep=head.getNextO;〃初始化，p指向首結(jié)點(diǎn)」為計(jì)數(shù)器

Nodeq=head;〃用來記錄p的前驅(qū)結(jié)點(diǎn)

intj=0;〃用來記錄被刪除結(jié)點(diǎn)的個(gè)數(shù)

while(p!二null){〃從單鏈表中的首結(jié)點(diǎn)開始對整個(gè)鏈表遍歷一次

if(p.getData().equals(x)){q.setNext(p.getNext());

++j；〃計(jì)數(shù)器的值增1

}else

q二p;

p二p.getNext。;〃指向下一個(gè)元素

)

returnj;〃返回被刪除結(jié)點(diǎn)的個(gè)數(shù)

)

3、試設(shè)計(jì)算法，用插入排序方法對單鏈表進(jìn)行排序。

算法設(shè)計(jì)如下：

publicstaticvoidinsertSort(LinkListL){

考證素材

考證素材

Nodep,q,r,u;

p=L.getHead().getNext();

L.getHead().setNext(null);

〃置空表，然后將原鏈表結(jié)點(diǎn)逐個(gè)插入到有序表中while(p!二null){〃當(dāng)鏈表尚未到尾，p為工

作指針

r二L.getHeadO;

q=L.getHead().getNext();

while(q!=null&(Integer,parselnt((String)q.getDataO))<=

(Integer,parselnt((String)p.getDataO))){

〃查P結(jié)點(diǎn)在鏈表中的插入位置，這時(shí)q是工作指針

r=q；

q=q.getNext();

)

u=p.getNext();

p.setNext(r.getNextO);

r.setNext(p);

P二u;

〃將P結(jié)點(diǎn)鏈入鏈表中，r是q的前驅(qū)，u是下一個(gè)待插入結(jié)點(diǎn)的指針

)

)

4、試設(shè)計(jì)算法，用選擇排序方法對單鏈表進(jìn)行排序。

算法設(shè)計(jì)如下：

〃單鏈表選擇排序算法

publicstaticvoidselectSort(LinkListL){

〃P為當(dāng)前最小，［為此過程中最小?為當(dāng)前掃描接點(diǎn)

Nodep,r,q;

NodenewNode二newNode();newNode.setNext(L.getHead());L.setHead(newNode);

〃創(chuàng)造一個(gè)最前面的節(jié)點(diǎn)newNode,解決第一個(gè)節(jié)點(diǎn)的沒有前續(xù)節(jié)點(diǎn)需要單獨(dú)語句的問題。p

二L.getHead();

while(p.getNext().getNext()!二null){

r=p.getNext();

q=p.getNext().getNext();

while(q.getNext()!=null){

if(Integer,parselnt((String)q.getNext0.getData())<=

(Integer,parselnt((String)r.getNext0.getData()))){

r二q；

)

q=q.getNext();

)

if(r!=p){"交換P與r

Nodeswap=r.getNext();

考證素材

考證素材

r.setNext(r.getNext().getNext());//r的next指向其后繼的后繼

swap.setNext(p.getNextO);

p.setNext(swap);//p的后繼為swap

)

p=p.getNext();

)//while

p.setNext(null);

)

5、試設(shè)計(jì)算法，使用非遞歸方法完成快速排序。

算法設(shè)計(jì)如下：

publicstaticvoidNonrecursiveQuickSort(intary){

if(ary.length<2){

return;

)

〃數(shù)組棧：記錄著高位和低位的值int]stacl=newint2]ary.length];

〃棧頂部位置

inttop=0;

〃低位，高位，循環(huán)變量，基準(zhǔn)點(diǎn)

〃將數(shù)組的高位和低位位置入棧stackl]top=ary.length-1;

stackO]top=0;

top++;

〃要是棧頂不空，那末繼續(xù)

while(top!=0){

〃將高位和低位出棧

〃低位：排序開始的位置

top—;

intlow=stackO]top];

〃高位：排序結(jié)束的位置

inthigh=stackl]top];〃將高位作為基準(zhǔn)位置〃基準(zhǔn)位置

intpivot=high;

inti=low;

for(intj=low;j<high;j++){

if(aryj<=arypivot]){inttemp=aryj];aryj=aryi];aryi=temp;

i++；

)

)

〃如果i不是基準(zhǔn)位，那末基準(zhǔn)位選的就不是最大值〃而i的前面放的都是比基準(zhǔn)位小

的值，那末基準(zhǔn)位〃的值應(yīng)該放到i所在的位置上

if(i!=pivot){

inttemp二aryi];

aryi=arypivot];

arypivot=temp;

考證素材

考證素材

)

if(i-low>1)(

〃此時(shí)不排i的原因是i位置上的元素已經(jīng)確定了，i前面的都是比i小的，i后面

的都是比i大的

stackl]top=i-1;

stackO]top=low;

top++;

)

〃當(dāng)high-i小于等于1的時(shí)候，就不往棧中放了，這就是外層while循環(huán)能結(jié)束的原因

〃如果從i到高位之間的元素個(gè)數(shù)多于一個(gè)，那末需要再次排序

if(high-i>1)(

〃此時(shí)不排i的原因是i位置上的元素已經(jīng)確定了，i前面的都是比i小的，i后面

的都是比i大的

stackl]top=high;

stackO]top=i+1;

top++;

)

)

)

6、試設(shè)計(jì)算法，判斷徹底二叉樹是否為大頂堆。

算法設(shè)計(jì)如下：

booleancheckmax(BiTreeNodet)〃判斷徹底二叉樹是否為大頂堆

(

BiTreeNodep=t;

if(p.getLchildO二二null&p.getRchildO=null)(

returntrue;

)else(

if(p.getLchildO!-null&p,getRchildO!=null)(

if((((RecordNode)p.getLchild().getData()).getKey())

pareTo(((RecordNode)p.getData()).getKey())<=0&(((RecordNode)

p.getRchiId().getData()).getKe