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

考證素材

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

一、單項選擇題本大題共15小題，每題2分，共30分)在每題列出的四個備選項中惟獨一個是符合題

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

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

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

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

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

的地址是--B―o

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

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

A、edcbaB、decbaC、dceabD、abode

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

則pi為_C_一_o

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

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

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

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

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

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

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

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

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

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

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

8、設串的長度為n,則它的子串個數(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ù)組a7:6］的基地址為1024,每一個元素占2個存儲單元,假設以行序為主序順序存儲，

則元

素a2］4］的存儲地址是_

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

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

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

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

考證素材

考證素材

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

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

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

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

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

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

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

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

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

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

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

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

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

_A_____。

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

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

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

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

A、uwvtsB、vwutsC、wuvtsD、wutsv

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

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

A、bdgcefhaB、gdbecfhaC、bdgaechfD、gdbehfca

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

A、acbedB、decabC、deabcD>cedba

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

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

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

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

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

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

25、在一個有向圖中，全部頂點的入度之和等于全部頂點的出度之和的一具二一倍。

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

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

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

考證素材

考證素材

27、具有4個頂點的無向徹底圖有條邊。

考證素材

考證素材

A、B、12C、16D、20

28、具有6個頂點的無向圖至少應有一L一條邊才干確保是一個連通圖。

A、B、C、D、

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

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

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

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

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

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

32、判定一個有向圖是否存在回路除了可以利用拓撲排序方法外，還可以利用A…

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

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

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

A、從源點到匯點的最長路徑B、從源點到匯點的最短路徑

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

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

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

35.對于一個有向圖，假設一個頂點的入度為kl,、出度為k2,則對應鄰接表中該頂點單鏈表中

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

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

36、對于一個有向圖，假設一個頂點的入度為kl,、出度為k2,則對應逆鄰接表中該頂點單鏈表

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

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

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

2

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

38、n個頂點的強連通圖至少有(A)條邊。

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

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

為(A)。

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

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

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

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

(A)

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

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

考證素材

考證素材

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

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

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

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

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

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

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

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

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

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

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

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

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

47、對于18個元素的有序表采用二分(折半)查找，則查找A3]的比擬序列的下標為(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),則利用快速排序的方法，以第一個記錄

7Q

為基準得到的一次劃分結(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、一組記錄的排序碼為(應16,塵，理82,23,40,36,72)，其中含有5個長度為

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

A16253548234079,82,3672

B16253548798223,36,4072

C16254835798223,36,4072

D16253548792336,40,7282

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

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

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

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

53、n個記錄直接插入排序所需的記錄最小比擬次數(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),則利用快速排序的方法，以第一個記錄

為基準得到一次劃分結(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個結(jié)點的徹底二叉樹從根這一層開始，每一層上從左到右挨次對結(jié)點進行編

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

A)98B)99C)5048

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

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

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

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

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

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

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

A)5B)4D)2

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

50B:60C:52D)65

、填空題本大題共10小題，每題2分，共20分)請在每題的空格中填上正確答案。錯填、不填均無

分。

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

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

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

ai]j]=0;

n

2、下面程序段的時間復雜度是——0!tL-o

i=s=0

while(s<n)

(

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

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

)

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

考證素材

考證素材

s=0;

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

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

s+=bi]j];

sum二s;

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

i二l；

while(i<=n)

i二iX3;

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

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

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

+1個元素。

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

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

9、已知二維數(shù)組Am]n]采用行序為主方法存儲，每一個元素占k個存儲單元，并且第一個元素的

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

10、二維數(shù)組A10]20]采用列序為主方法存儲，每一個元素占一個存儲單元并且A0]0]的存儲地址

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

11、二維數(shù)組A10...20]5...10]采用行序為主方法存儲，每一個元素占4個存儲單元并且A10]5]

的存儲地址是1000,則A1819]的地址是一「208。

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

/2,假設以行序為主序進行存儲，則元素=j)在s中的下標k二—i(iT)/2+jT—。

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

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

左孩子，其左孩子編號應為一一2Xi-;x假設有右孩子，其右孩子應為一2Xi+l--------o

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

7—o

16、n個頂點的連通圖至少nT_條邊。

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

n

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

i1

2eo

考證素材

考證素材

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

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

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

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

需進行2次查找可確定成功；查找47時，需進行一次查找成功；查找100時，需進行工次查找才干

確定不成功。

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

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

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

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

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

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

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

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

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

28、假定一個有向圖的頂點集為{a,b,c,d,e,f},邊集為?a,c>,<a,e>,<c,f>,<d,c>,<e,b>,

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

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

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

_-3_個連通分量。

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

和nT-o

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

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

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

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

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

點數(shù)為--19——“

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

查找長度為.....(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),在冒泡排序的過程中進行第一趟排序后的結(jié)果為(46.

56.38.40.79.84)....

考證素材

考證素材

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

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

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

38465679801。

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

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

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

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

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

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

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

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

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

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

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

如下：

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

遍歷序列。

解：后序序列：ACDBGJKIHFE

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

(1)畫出該無向圖；

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

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

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

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

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

6、如下列圖所示的一個網(wǎng)，按照Prim方法，從頂點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,給出采用冒泡排序法進行排序時每一趟的排序結(jié)

果。

解：排序過程如下：

(0)46745314263886652734

⑴46531426387465273486

⑵46142638536527347486

⑶14263846532734657486

(4)14263846273453657486

⑸14263827344653657486

(6)14262734384653657486

考證素材

考證素材

(7)14262734384653657486

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

序結(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)每一個頂點的出/入度；⑵鄰接矩陣；

⑶鄰接表；

解：(1)每一個頂點的出/入度是：

⑵鄰接矩陣：

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

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

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

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

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

果。

解：排序過程如下所示：

(0)46745314263886652734]

(1)46741453263865862734]

(2)14465374263865862734]

(3)14263846536574862734]

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

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

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

查找長度。

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

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

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

解：(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、已知如下列圖所示的一個網(wǎng)，按照Kruskal方法，求該網(wǎng)的最小生成樹的產(chǎn)生過程。解：過程如

下列圖所示。

考證素材

考證素材

四、算法設計題本大題共2小題，每題11分，共22分)

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

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

算法設計如下：

publicintremove(Objectx){

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

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

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

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

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

q二P；

P=p.getNextO;〃指向下一個元素

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

)

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

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

}

else

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

returnj;

}

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

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

算法設計如下：

publicintremoveAll(Objectx){

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

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

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

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

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

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

}else

q二p;

p二p.getNext。;〃指向下一個元素

)

returnj;〃返回被刪除結(jié)點的個數(shù)

)

3、試設計算法，用插入排序方法對單鏈表進行排序。

算法設計如下：

publicstaticvoidinsertSort(LinkListL){

考證素材

考證素材

Nodep,q,r,u;

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

L.getHead().setNext(null);

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

作指針

r二L.getHeadO;

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

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

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

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

r=q；

q=q.getNext();

)

u=p.getNext();

p.setNext(r.getNextO);

r.setNext(p);

P二u;

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

)

)

4、試設計算法，用選擇排序方法對單鏈表進行排序。

算法設計如下：

〃單鏈表選擇排序算法

publicstaticvoidselectSort(LinkListL){

〃P為當前最小，［為此過程中最小?為當前掃描接點

Nodep,r,q;

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

〃創(chuàng)造一個最前面的節(jié)點newNode,解決第一個節(jié)點的沒有前續(xù)節(jié)點需要單獨語句的問題。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、試設計算法，使用非遞歸方法完成快速排序。

算法設計如下：

publicstaticvoidNonrecursiveQuickSort(intary){

if(ary.length<2){

return;

)

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

〃棧頂部位置

inttop=0;

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

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

stackO]top=0;

top++;

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

while(top!=0){

〃將高位和低位出棧

〃低位：排序開始的位置

top—;

intlow=stackO]top];

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

inthigh=stackl]top];〃將高位作為基準位置〃基準位置

intpivot=high;

inti=low;

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

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

i++；

)

)

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

的值，那末基準位〃的值應該放到i所在的位置上

if(i!=pivot){

inttemp二aryi];

aryi=arypivot];

arypivot=temp;

考證素材

考證素材

)

if(i-low>1)(

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

的都是比i大的

stackl]top=i-1;

stackO]top=low;

top++;

)

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

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

if(high-i>1)(

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

的都是比i大的

stackl]top=high;

stackO]top=i+1;

top++;

)

)

)

6、試設計算法，判斷徹底二叉樹是否為大頂堆。

算法設計如下：

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