数据结构题库

考证素材

数据结构课程代码02331)

一、单项选择题本大题共15小题，每题2分，共30分)在每题列出的四个备选项中惟独一个是符合题

目要求的，请将其代码填写在题后的括号内。错选、多项选择或者未选均无分。

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、判定一个循环队列QU(最多元素为m)为空的条件是—C_o

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

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

6、判定一个循环队列QU(最多元素为m,m二二MaxsizeT)为满队列的条件是_A—。

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

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

7、循环队列用数组A0,mT］存放其元素值，已知其头尾指针分别是front和rear,则当前队列

中的元素个数是一工。

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

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

8、设串的长度为n,则它的子串个数为一。

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、设数组a7:6］的基地址为1024,每一个元素占2个存储单元,假设以行序为主序顺序存储，

则元

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

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

11、二维数组A中，每一个元素A的长度为3个字节，行下标i从0到7,列下标j从0到9,从

首地址SA开始连续存放在存储器内，该数组按列存放时，元素A417］的起始地址为」-0

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

考证素材

考证素材

12、二维数组A中，每一个元素的长度为3个字节，行下标i从0到7,列下标j从0到9,从首

地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是一土一。

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

13、二维数组A中，每一个元素A的长度为3个字节，行下标i从0到7,列下标j从0到9,从首

地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A7]4]的起始地址为工

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

14、假定在一棵二叉树中，双分支结点数为15个，单分支结点数为30个，则叶子结点个数为B

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

15、按照二叉树的定义，具有3个结点的不同形状的二叉树有一，一种。

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

16、深度为5的二叉树至多有J一个结点。

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

17、设高度为h的二叉树上惟独度为0和度为2的结点，则此类二叉树中所包含的结点数至少为

_A_____。

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

18、对一个满二叉树，m个树叶，n个结点，深度为h,则皂。

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

19、如果某二叉树的前根次序遍历结果为stuwv,中序遍历为uwtvs那末该二叉树的后序为_C…

A、uwvtsB、vwutsC、wuvtsD、wutsv

20、某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其

后序遍历的结点访问顺序是一_1一。

A、bdgcefhaB、gdbecfhaC、bdgaechfD、gdbehfca

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

A、acbedB、decabC、deabcD>cedba

22、由带权为9,2,5,7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为(D)。

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

23、在一棵具有n个结点的二叉树第i层上，最多具有(C)个结点。

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

24、在一个图中，全部顶点的度数之和等于全部边数的倍数为——

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

25、在一个有向图中，全部顶点的入度之和等于全部顶点的出度之和的一具二一倍。

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

26、一个有n个顶点的无向图的边数最多为一"

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、求关键路径的方法B、求最短路径的Dijkstra方法

C、宽度优先遍历算法D、深度优先遍历算法

33、关键路径是事件结点网络中

A、从源点到汇点的最长路径B、从源点到汇点的最短路径

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

34、一个有n个顶点的无向连通图,它所包含的连通分量个数为Ji

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

35.对于一个有向图，假设一个顶点的入度为kl,、出度为k2,则对应邻接表中该顶点单链表中

的结点数为B->

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

36、对于一个有向图，假设一个顶点的入度为kl,、出度为k2,则对应逆邻接表中该顶点单链表

中的结点数为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,则该路径上的顶点数为(B)

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

41、一个图中包含k个连通分量，假设按深度优先(DFS)搜索方法访问全部结点，则必须调用

(A)

次深度优先遍历算法。

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为的结点时,.次比拟后查找成功。

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

46、有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找

成功所需的平均比拟次数为一#一。

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一组记录的关键码为(46,5638,40,84),则利用快速排序的方法，以第一个记录

7Q

为基准得到的一次划分结果为—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的有序表,按归并排序的方法对该序列进行一趟归并后的结果为一，一。

A16253548234079,82,3672

B16253548798223,36,4072

C16254835798223,36,4072

D16253548792336,40,7282

51、下述几种排序方法中,要求内存量最大的是4

A、插入排序B、选择排序C、快速排序D、归并排序

52、在对n个元素进行简单项选择择排序过程中，第i趟需从(A)个元素中选择出最小值元素。

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

53、n个记录直接插入排序所需的记录最小比拟次数是(A)

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

考证素材

考证素材

54、一组记录的关键字为(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、一组记录的关键字为(45,80,55,40,42,85),则利用快速排序的方法，以第一个记录

为基准得到一次划分结果是(

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个结点的彻底二叉树从根这一层开始，每一层上从左到右挨次对结点进行编

号，根结点的编号为1,则编号为49的结点的左孩子编号为(A1

A)98B)99C)5048

57.一组记录的排序码为(48,24,18,53,16,26,,4咪纳冒泡排序法进行排序，则第一趟排序

需要进行记录交换的次数是(C1

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

58.采用分块查找时，如某线性表有256个元素，查找每一个元素的概率相同，假设采用顺序查

找来确定元素所在的块，则每块包含()个结点时，平均查找长度最

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

59.对于有向图的邻接矩阵“该图共有(B)条弧。

A)5B)4D)2

60由带权9、1、3、5、6的五个叶子结点生成的哈夫曼树的带权路径长度为(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),每一个元素在内存中占有L个存储单元，

则元素ai在内存中的地址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、已知二维数组Am]n]采用行序为主方法存储，每一个元素占k个存储单元，并且第一个元素的

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

10、二维数组A10]20]采用列序为主方法存储，每一个元素占一个存储单元并且A0]0]的存储地址

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

11、二维数组A10...20]5...10]采用行序为主方法存储，每一个元素占4个存储单元并且A10]5]

的存储地址是1000,则A1819]的地址是一「208。

12>现有一个n阶的对称矩阵an]n],现将其压缩存储在一个一维数组sm]中，则m=-二n(n+l)

/2,假设以行序为主序进行存储，则元素=j)在s中的下标k二—i(iT)/2+jT—。

13、在一个mXn的矩阵中，假设a0[0]是第一个元素，则ai[j]是第---iXn+i个元素。

14、在二叉树中，某一结点x的编号为i,x假设有双亲，其双亲编号应为一一i/2一4x假设有

左孩子，其左孩子编号应为一一2Xi-;x假设有右孩子，其右孩子应为一2Xi+l--------o

15、8层彻底二叉树至少有128个结点,拥有100个结点的彻底二叉树的最大层数为

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、平衡二叉排序树上任一结点的平衡因子只可能是。、，或者To

23、用起泡法对n个关键码排序，在最好情况下，只需做一心次比拟；在最坏的情况下

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

24、设字符串Sl="ABCDEF,S2="PQRS,则运算S=C0NCAT(SUB(SI,2,LEN(S2)),SUB

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

25、在一棵二叉排序树上按一一一一中序遍历得到的结点序列是一个有序序列。

26、在一个图中，全部顶点的度数之和等于全部边数的-----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的顶点个数为____二一入度为1的顶点个数为一『____。

29、在一个具有n个顶点的无向图中，要连通全部顶点则至少需要n-1一条边。

30、假设一个图的顶点集为{a,b,c,d,e,f},边集为{(a,b),(a,c),(b,c),(d,e)},则该图含有

_-3_个连通分量。

31、对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为______n-

和nT-o

32、假定一个顺序表的长度为40,并假定查找每一个元素的概率都相同，则在查找成功情况下的

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

33、在索引查找中，假定查找表(即主表)的长度为96,被等分为8个子表，则进行索引查找

的平均查找长度为一」1一—。

34、假定对长度n=50的有序表进行折半查找，则对应的判定树高度为一，一一，最后一层的结

点数为--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),在冒泡排序的过程中进行第一趟排序后的结果为(46.

56.38.40.79.84)....

考证素材

考证素材

38、假定一组记录为(46,79,56,64,38,40,84,43),在冒泡排序的过程中进行第一趟排序时，元素79

将最终下沉到其后第_!一个元素的位置。

39、假定一组记录为(46,79,56,38,40,80)，对其进行快速排序的第一次划分后的结果为一=40

38465679801。

40、假定一组记录为(46,79,56,38,40,80,46,75,28,46)，对其进行归并排序的过程中，第二趟

归并后的子表个数为一一3——。

三、应用题本大题共4小题，每题7分，共28分)

1、分别画出具有3个结点的树和三个结点的二叉树的全部不同形态。

解：具有3个结点的树有两种不同形态。

具有3个结点的二叉树有以下五种不同形态。

2、如下列图所示的二叉树，试分别写出它的顺序表示和链接表示(二叉链表)。解：(1)顺序表

(2)该二叉树的二叉链表表示。

3、假定用于通信的电文由8个字符A、B、C、D、E、F、G、H组成，各字母在电文中浮现的概率为

5%、25%、4%、7%、9%、12%,30%、8%,试以这8个字母构造哈夫曼树。

解：依据题意，设这8个字母对应的权值分别为(5,25,4,7,9,12,30,8),并且n=8。步骤

如下：

4、假设一棵二叉树的先序序列为EBADCFHGIKJ,中序序列为ABCDEFGHIJK,请写出该二叉树的后序

遍历序列。

解：后序序列：ACDBGJKIHFE

5、已知一个无向图的邻接表下列图所示，要求：

(1)画出该无向图；

(2)依据邻接表，分别写出用DFS(深度优先搜索)和BFS(广度优先搜索)算法从顶点V0开始遍历

该图后所得到的遍历序列。

解：(D该无向图如下列图所示。

(2)依据该无向图的邻接表表示，从顶点V0开始的深度优先遍历序列为：V0、V2、V3、VI、V4、

V6、V5»广度优先遍历序列为VO、V2、V5、V6、VI、V3、V4。

6、如下列图所示的一个网，按照Prim方法，从顶点VI出发，求该网的最小生成树的产生过程。解：

步骤如下：

7、记录的关键字序列为：63,90,70,55,67,42,98,83,10,45,58,则画出构造一棵二叉排序

树的过程。

解：构造二叉排序树的过程如下列图所示。

8、已知一组记录为(46,74,53,14,26,38,86,65,27,给出采用冒泡排序法进行排序时每一趟的排序结

果。

解：排序过程如下：

(0)46745314263886652734

⑴46531426387465273486

⑵46142638536527347486

⑶14263846532734657486

(4)14263846273453657486

⑸14263827344653657486

(6)14262734384653657486

考证素材

考证素材

(7)14262734384653657486

9、已知一组记录为(46,74,53,14,26,38,86,65,27,给出采用直接插入排序法进行排序时每一趟的排

序结果。

解：排序过程如下所示：

(0)46745314263886652734

(1)46745314263886652734

(2)46537414263886652734

(3)14465374263886652734

(4)14264653743886652734

(5)14263846537486652734

(6)14263846537486652734

⑺14263846536574862734

(8)14262738465365748634

(9)14262734384653657486]

1(X关键字序列为(47,7,1116,92,22,8,3,50,37,89,94,21),哈希函数为:

mod11,用拉链表处理冲突。

解：建表如下：

11、已知如下列图所示的有向图，请给出该图的

(1)每一个顶点的出/入度；⑵邻接矩阵；

⑶邻接表；

解：(1)每一个顶点的出/入度是：

⑵邻接矩阵：

⑶邻接表：12、已知图的邻接矩阵如下列图所示。试分别画出自顶点A出发进行遍历所得的深度优先

生成树和广度优先生成树。

解：(1)深度优先搜索如下所示：

(2)广度优先搜索如下所示：

13、已知一组记录为(46,74,53,14,26,38,86,65,27,给出采用归并排序法进行排序时每一趟的排序结

果。

解：排序过程如下所示：

(0)46745314263886652734]

(1)46741453263865862734]

(2)14465374263865862734]

(3)14263846536574862734]

(4)14262734384653657486]14、假定一个待哈希存储的线性表为(32,75,29,63,

48,94,25,36,18,70,49,80),哈希地址空间为

HT12],假设采用除留余数法构造哈希函数和拉链法处理冲突，试画出最后得到的哈希表，并求出平均

查找长度。

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

15、对于一个无向图如下所示，假定采用邻接矩阵表示，试分别写出从顶点0出发按深度优先搜索遍

历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。

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

(2)广度优先搜索序列：0,1,4,2,7,3,8,6,5,9

16、已知如下列图所示的一个网，按照Kruskal方法，求该网的最小生成树的产生过程。解：过程如

下列图所示。

考证素材

考证素材

四、算法设计题本大题共2小题，每题11分，共22分)

1、编写一个单链表类的成员函数，完成删除不带头结点的单链表中数据域值等于X的第一个结点的操

作。假设删除成功，则返回被删除结点的位置；否则，返回T。

算法设计如下：

publicintremove(Objectx){

Nodep=head;〃初始化,p指向首结点

Nodeq=null;〃q用来记录p的前驱结点

intj=0;〃上为计数器

〃从单链表中的首结点元素开始查找，直到p.getDataO指向元素X或者到达单链表的表尾while(p!=null

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

q二P；

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

++j；〃计数器的值增1

)

if(p!=null&&q==null)〃删除的是单链表中的首结点head二p.getNext();

elseif(p!=null){〃删除的是单链表中的非首结点q.setNext(p.getNext());

}

else

returnT;〃值为x的结点在单链表中不存在

returnj;

}

2、编写一个单链表类的成员函数，完成删除带头结点的单链表中数据域值等于x的全部结点的操

作。要求函数返回被删除结点的个数。

算法设计如下：

publicintremoveAll(Objectx){

Nodep=head.getNextO;〃初始化，p指向首结点」为计数器

Nodeq=head;〃用来记录p的前驱结点

intj=0;〃用来记录被删除结点的个数

while(p!二null){〃从单链表中的首结点开始对整个链表遍历一次

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

++j；〃计数器的值增1

}else

q二p;

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

)

returnj;〃返回被删除结点的个数

)

3、试设计算法，用插入排序方法对单链表进行排序。

算法设计如下：

publicstaticvoidinsertSort(LinkListL){

考证素材

考证素材

Nodep,q,r,u;

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

L.getHead().setNext(null);

〃置空表，然后将原链表结点逐个插入到有序表中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结点在链表中的插入位置，这时q是工作指针

r=q；

q=q.getNext();

)

u=p.getNext();

p.setNext(r.getNextO);

r.setNext(p);

P二u;

〃将P结点链入链表中，r是q的前驱，u是下一个待插入结点的指针

)

)

4、试设计算法，用选择排序方法对单链表进行排序。

算法设计如下：

〃单链表选择排序算法

publicstaticvoidselectSort(LinkListL){

〃P为当前最小，［为此过程中最小〜为当前扫描接点

Nodep,r,q;

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

〃创造一个最前面的节点newNode,解决第一个节点的没有前续节点需要单独语句的问题。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;

)

〃数组栈：记录着高位和低位的值int]stacl=newint2]ary.length];

〃栈顶部位置

inttop=0;

〃低位，高位，循环变量，基准点

〃将数组的高位和低位位置入栈stackl]top=ary.length-1;

stackO]top=0;

top++;

〃要是栈顶不空，那末继续

while(top!=0){

〃将高位和低位出栈

〃低位：排序开始的位置

top—;

intlow=stackO]top];

〃高位：排序结束的位置

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位置上的元素已经确定了，i前面的都是比i小的，i后面

的都是比i大的

stackl]top=i-1;

stackO]top=low;

top++;

)

〃当high-i小于等于1的时候，就不往栈中放了，这就是外层while循环能结束的原因

〃如果从i到高位之间的元素个数多于一个，那末需要再次排序

if(high-i>1)(

〃此时不排i的原因是i位置上的元素已经确定了，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