数据结构题库

1、数据结构(课程代码 02331)一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1、对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（A ）个元素。A、n/2 B、(n+1)/2 C、(n 1)/2 D、n2、 一个向量(一种顺序表)第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是_B_。A、100 B、108 C、110 D、1203、一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是_C_。

2、A、 edcba B、 decba C、 dceab D、 abcde 4、若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，若p1=n，则pi为_C_。 A、 i B、 n-i C、 n-i+1 D、 n-i-15、判定一个循环队列QU（最多元素为m）为空的条件是_C_。A、rear - front= =m B、rear-front-1= =mC、front= = rear D、front= = rear+16、 判定一个循环队列QU（最多元素为m, m= =Maxsize-1）为满队列的条件是_A_。A、(rear- front)+ Maxsize)% Maxsi

3、ze = =mB、rear-front-1= =m C、front= =rear D、front= = rear+17、 循环队列用数组A0，m-1存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是_A_。A、 (rear-front+m)%m B、 rear-front+1C、 rear-front-1 D、 rear-front8、设串的长度为n，则它的子串个数为 D 。A、nB、n(n+1)C、n(n+1)/2 D、n(n+1)/2+19、S1=“ABCD”，S2=“CD”则S2在S3中的位置是（C ）A、1 B、2 C、3 D、410、设数组a76的基地址

4、为1024,每个元素占2个存储单元,若以行序为主序顺序存储,则元素a24的存储地址是_B_。A、1054 B、1056 C、1058 D、109811、 二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A47的起始地址为_B_。A、 SA+141 B、 SA+180 C、 SA+222 D、 SA+22512、二维数组A中，每个元素的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是_C_。A、 80 B、 100 C、240 D、 2701

5、3、 二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A74的起始地址为_C_。A、 SA+141 B、 SA+144 C、 SA+222 D、 SA+22514、假定在一棵二叉树中，双分支结点数为15个，单分支结点数为30个，则叶子结点个数为 B 。A、15 B、16 C、17 D、4715、按照二叉树的定义，具有3个结点的不同形状的二叉树有_C_种。A、3 B、 4 C、 5 D、 616、深度为5的二叉树至多有_C_个结点。A、16 B、32 C、31 D、1017、设高度为h的二叉树上只有度为0

6、和度为2的结点，则此类二叉树中所包含的结点数至少为_ A _。A、 2h B、 2h-1 C、 2h+1 D、 h+118、 对一个满二叉树，m个树叶，n个结点，深度为h，则_D_ 。A、 n=h+m B、 h+m=2n C、 m=h-1 D、 n=2 h-119、 如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为_C_。 A、 uwvts B、 vwuts C、 wuvts D、 wutsv20、 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_D_。A、 bdgcefha B、

7、gdbecfha C、 bdgaechf D、 gdbehfca21、 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是_D_。A、 acbed B、 decab C、 deabc D、 cedba22、由带权为9,2,5,7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为( D )。A、 23 B、 37 C、 46 D、 4423.在一棵具有n个结点的二叉树第i层上，最多具有( C )个结点。 A、2i B、 2i+1 C、 2i-1 D、 2n24、在一个图中，所有顶点的度数之和等于所有边数的倍数为_C_。A、 1/2 B、 1 C、 2 D、 4

8、 25、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的_B_倍。A、 1/2 B、 1 C、 2 D、 426、一个有n个顶点的无向图的边数最多为_C_。A、 n B、 n(n-1) C、 n(n-1)/2 D、 2n27、具有4个顶点的无向完全图有_A_条边。A、 6 B、 12 C、 16 D、 2028、具有6个顶点的无向图至少应有_A_条边才能确保是一个连通图。A、 5 B、 6 C、 7 D、 829、在一个具有n个顶点的无向图中，要连通全部顶点至少需要_C_条边。A、 n B、 n+1 C、 n-1 D、 n/230、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则

9、该矩阵的大小是_D_。A、 n B、 (n-1)2 C、 n-1 D、 n231、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_A_。A、 n B、 n+1 C、 n-1 D、 n+e32、判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用_D_。A、 求关键路径的方法 B、 求最短路径的Dijkstra方法C、 宽度优先遍历算法 D、 深度优先遍历算法33、关键路径是事件结点网络中 A 。A、从源点到汇点的最长路径 B、从源点到汇点的最短路径C、最长的回路 D、最短的回路34、一个有n个顶点的无向连通图，它所包含的连通分量个数为 B 。A、0B、1

10、C、nD、n+135对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应邻接表中该顶点单链表中的结点数为 B 。A、k1B、k2C、k1-k2D、k1+k236、对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应逆邻接表中该顶点单链表中的结点数为 A 。A、k1B、k2C、k1-k2D、k1+k237、具有n个顶点的有向图最多有( B )条边。 A、n B、 n(n-1) C、 n(n+1) D、 38、 n个顶点的强连通图至少有( A )条边。 A、 n B、 n-1 C、 n+1 D、 n(n-1)39、 在一个具有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点

11、的入度之和为( A )。 A、s B、 s-1 C、 s+1 D、 n40、 在一个无向图中，若两个顶点之间的路径长度为k，则该路径上的顶点数为( B )。 A、k B、 k+1 C、 k+2 D、 2k41、一个图中包含k个连通分量，若按深度优先(DFS)搜索方法访问所有结点，则必须调用(A )次深度优先遍历算法。 A、k B、 1 C、 k-1 D、 k+142、设G1=(V1,E1)和G2=(V2,E2)为两个图， V1ÍV2,E1ÍE2,则称（A ）A、G1是G2的子图 B、G2是G1的子图C、G1是G2的连通分量 D、G2是G1的连通分量43、采用顺序查找方法查找

12、长度为n的线性表时，每个元素的平均查找长度为_C_.A、 n B、 n/2 C、 (n+1)/2 D、 (n-1)/244、采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为_D_。A、O（n2） B、 O(nlog2n) C、 O(n) D、 O(log2n)45、有一个有序表为1，3，9，12，32，41，45，62，75，77，82，95，100，当二分查找值82为的结点时，_C_次比较后查找成功。A、 1 B、 2 C、 4 D、 846、有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为_B_。A、 35/12 B

13、、 37/12 C、 39/12 D、 43/1247、对于18个元素的有序表采用二分(折半)查找，则查找A3的比较序列的下标为( D )。 A、1、2、3 B、9、5、2、3 C、9、5、3 D、9、4、2、348、 一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为_B_。A、 79，46，56，38，40，80 B、 38，40,56，79，46，84，C、 84，79，56，46，40，38 D、 84，56，79，40，46，3849、 一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次

14、划分结果为_C_。A、 38，40，46，56，79，84 B、 40，38，46，79，56，84C、 40，38，46，56，79，84 D、 40，38，46，84，56，7950、 一组记录的排序码为（25，48，16，35，79，82，23，40，36，72），其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为_A_。A、 16，25，35，48，23，40，79，82，36，72 B、 16，25，35，48，79，82，23，36，40，72C、 16，25，48，35，79，82，23，36，40，72D、 16，25，35，48，79，23，36，4

15、0，72，8251、 下述几种排序方法中，要求内存量最大的是_D_。A、 插入排序 B、 选择排序 C、 快速排序 D、 归并排序52、在对n个元素进行简单选择排序过程中，第i趟需从( A )个元素中选择出最小值元素。A、n-i+1 B、 n-i C、i D、 i+153、n个记录直接插入排序所需的记录最小比较次数是 ( A ) A、 n-1 B、 2(n-1) C、 (n+2)(n-1)/2 D、 n54、一组记录的关键字为（45，80，55，40，42，85），则利用堆排序的方法建立的初始堆为( B )。 A、（80，45，55，40，42，85） B、（85，80，55，40，42，45

16、） C、（85，80，55，45，42，40） D、（85，55，80，42，45，40）55、一组记录的关键字为（45，80，55，40，42，85），则利用快速排序的方法，以第一个记录为基准得到一次划分结果是( C )。 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的结点的左孩子编号为（ A ）。A）98B）99C）50D）4857一组记录的排序

17、码为(48,24,18,53,16,26,40)，采用冒泡排序法进行排序，则第一趟排序需要进行记录交换的次数是（ C ）。A）3B）4C）5D）658采用分块查找时，如某线性表中共有256个元素，查找每个元素的概率相同，假设采用顺序查找来确定元素所在的块，则每块包含（ C ）个结点时，平均查找长度最小。A）256B）15C）16D）1859对于有向图的邻接矩阵，该图共有（ B ）条弧。A）5B）4C）3D）260由带权9、1、3、5、6的五个叶子结点生成的哈夫曼树的带权路径长度为（ C ）。A）50B）60C）52D）65二、填空题(本大题共10小题，每小题2分，共20分)请在每小题的空格中填

18、上正确答案。错填、不填均无分。1、下面程序段的时间复杂度是_ O(m*n) _。for (i=0;i<n;i+)for (j=0;j<m;j+)aij=0;2、下面程序段的时间复杂度是_ O()_。i=s=0while(s<n) i+; /* i=i+1 */ s+=i;/* s=s+i */3、下面程序段的时间复杂度是_ O(n2)_。s=0;for (i=0;i<n;i+)for (j=0;j<n;j+)s+=bij;sum=s;4、下面程序段的时间复杂度是_ O(log3n) _。i=1;while (i<=n)i=i*3;5、在顺序表中，若第一个元素

19、所在的地址为Loc(a1)，每个元素在内存中占有L个存储单元，则元素ai在内存中的地址Loc(ai)=_ Loc(a1)+(i-1)*L _。6、向一个长度为n的顺序表的第i个元素（1in+1）之前插入一个元素时，需向后移动_ n-i+1_个元素。7、向一个长度为n的顺序表中删除第i个元素（1in）时，需向前移动_ n-i _个元素。8、串s=abcdef,s1=cde，s1在s中的位置为_3 _。9、 已知二维数组Amn采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A00)，则Aij的地址是_ LOC (A00)+(n*i+j)*k _。10、 二维数组A1

20、020采用列序为主方式存储，每个元素占一个存储单元并且A00的存储地址是200，则A612的地址是_326_。11、 二维数组A1020510采用行序为主方式存储，每个元素占4个存储单元，并且A105的存储地址是1000，则A189的地址是_1208_。12、现有一个n阶的对称矩阵ann，现将其压缩存储在一个一维数组sm中，则m=_ n(n+1)/2_，若以行序为主序进行存储，则元素aij(i>=j)在s中的下标k=_ i(i-1)/2+j-1_。13、在一个m*n的矩阵中，若a00是第一个元素，则aij是第_ i*n+j _个元素。14、在二叉树中，某一结点x的编号为i，x若有双亲，其

21、双亲编号应为_ _；x若有左孩子，其左孩子编号应为_2*i _；x若有右孩子，其右孩子应为_2*i+1_。15、8层完全二叉树至少有 128 个结点，拥有100个结点的完全二叉树的最大层数为 7 。16、n个顶点的连通图至少_ n-1 _条边。17、在无向图G的邻接矩阵A中，若Aij等于1，则Aji 等于_1_。18、一个无向图有n个顶点和e条边，则所有顶点的度的和即(表示顶点i的度)= 2e 。19、在有n个顶点的有向图中，每个顶点的度最大可达 2(n-1) 。20、 对于长度为n的线性表，若进行顺序查找，则时间复杂度为_ O（n）_；若采用折半法查找，则时间复杂度为_ O(log2n)_。

22、21、已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当用折半查找90时，需进行 2 次查找可确定成功；查找47时，需进行 4 次查找成功；查找100时，需进行 3 次查找才能确定不成功。22、平衡二叉排序树上任一结点的平衡因子只可能是 0 、 1 或 -1 。23、用起泡法对n个关键码排序，在最好情况下，只需做 n-1 次比较；在最坏的情况下要做 n(n-1)/2 次比较。24、设字符串S1= “ABCDEF”，S2= “PQRS”，则运算S=CONCAT（SUB（S1，2，LEN（S2），SUB（S1，LEN（S2），2）后的串值为_“BCDEDE”_

23、。25、在一棵二叉排序树上按_中序_遍历得到的结点序列是一个有序序列。26、在一个图中，所有顶点的度数之和等于所有边数的_2_倍。27、在一个具有n个顶点的无向完全图中，包含有_ n(n-1)/2_条边，在一个具有n个顶点的有向完全图中，包含有_ n(n-1)_条边。28、假定一个有向图的顶点集为a,b,c,d,e,f，边集为<a,c>, <a,e>, <c,f>, <d,c>, <e,b>, <e,d>，则出度为0的顶点个数为_2_，入度为1的顶点个数为_4_。29、在一个具有n个顶点的无向图中，要连通所有顶点则至少需要

24、_ n-1_条边。30、若一个图的顶点集为a,b,c,d,e,f，边集为(a,b),(a,c),(b,c),(d,e)，则该图含有_3_个连通分量。31、对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为_ n _和_ n-1_。32、假定一个顺序表的长度为40，并假定查找每个元素的概率都相同，则在查找成功情况下的平均查找长度_20.5_，在查找不成功情况下的平均查找长度_41_。33、在索引查找中，假定查找表（即主表）的长度为96，被等分为8个子表，则进行索引查找的平均查找长度为_11_。34、假定对长度n=50的有序表进行折半查找，则对应的判定树高度为_6_，最后一层的结

25、点数为_19 _。35、假定在索引查找中，查找表长度为n，每个子表的长度相等，设为s，则进行成功查找的平均查找长度为_(n/s+s)/2+1_。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将最终下沉到其后第_4_个元素的位置。39、假定一组记录

26、为(46,79,56,38,40,80)，对其进行快速排序的第一次划分后的结果为_40 38 46 56 79 80_。40、假定一组记录为(46,79,56,38,40,80,46,75,28,46)，对其进行归并排序的过程中，第二趟归并后的子表个数为_3_。三、应用题(本大题共4小题，每小题7分，共28分)1、分别画出具有3个结点的树和三个结点的二叉树的所有不同形态。解：具有3个结点的树有两种不同形态。具有3个结点的二叉树有以下五种不同形态。2、如下图所示的二叉树，试分别写出它的顺序表示和链接表示（二叉链表）。解：（1）顺序表示。（2）该二叉树的二叉链表表示。3、假定用于通信的电文由8个字

27、符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，请写出该二叉树的后序遍历序列。解：后序序列：ACDBGJKIHFE5、已知一个无向图的邻接表下图所示，要求：（1）画出该无向图；（2）根据邻接表，分别写出用DFS(深度优先搜索)和BFS（广度优先搜索）算法从顶点V0开始遍历该图后所得到的遍历序列。解：（1）该无向图如下图所

28、示。（2）根据该无向图的邻接表表示，从顶点V0开始的深度优先遍历序列为：V0、V2、V3、V1、V4、V6、V5。广度优先遍历序列为V0、V2、V5、V6、V1、V3、V4。6、如下图所示的一个网，按照Prim方法，从顶点V1 出发，求该网的最小生成树的产生过程。 解：步骤如下：7、记录的关键字序列为：63，90，70，55，67，42，98，83，10，45，58，则画出构造一棵二叉排序树的过程。解：构造二叉排序树的过程如下图所示。8、已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用冒泡排序法进行排序时每一趟的排序结果。解：排序过程如下：(0) 46 7

29、4 53 14 26 38 86 65 27 34(1) 46 53 14 26 38 74 65 27 34 86(2) 46 14 26 38 53 65 27 34 74 86(3) 14 26 38 46 53 27 34 65 74 86(4) 14 26 38 46 27 34 53 65 74 86(5) 14 26 38 27 34 46 53 65 74 86(6) 14 26 27 34 38 46 53 65 74 86(7) 14 26 27 34 38 46 53 65 74 869、已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采

30、用直接插入排序法进行排序时每一趟的排序结果。解：排序过程如下所示：(0) 46 74 53 14 26 38 86 65 27 34(1) 46 74 53 14 26 38 86 65 27 34(2) 46 53 74 14 26 38 86 65 27 34(3) 14 46 53 74 26 38 86 65 27 34(4) 14 26 46 53 74 38 86 65 27 34(5) 14 26 38 46 53 74 86 65 27 34(6) 14 26 38 46 53 74 86 65 27 34(7) 14 26 38 46 53 65 74 86 27 34(8)

31、 14 26 27 38 46 53 65 74 86 34(9) 14 26 27 34 38 46 53 65 74 8610、关键字序列为 （47，7，29，11，16，92，22，8，3，50，37，89，94，21），哈希函数为：Hash(key)=key mod 11，用拉链表处理冲突。解：建表如下：11、已知如下图所示的有向图，请给出该图的(1) 每个顶点的出/入度；(2) 邻接矩阵；(3) 邻接表；解：(1) 每个顶点的出/入度是：(2) 邻接矩阵：(3) 邻接表：12、已知图的邻接矩阵如下图所示。试分别画出自顶点A出发进行遍历所得的深度优先生成树和广度优先生成树。解：（1）深

32、度优先搜索如下所示：(2)广度优先搜索如下所示：13、已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用归并排序法进行排序时每一趟的排序结果。解：排序过程如下所示：(0) 46 74 53 14 26 38 86 65 27 34(1) 46 74 14 53 26 38 65 86 27 34(2) 14 46 53 74 26 38 65 86 27 34(3) 14 26 38 46 53 65 74 86 27 34(4) 14 26 27 34 38 46 53 65 74 8614、假定一个待哈希存储的线性表为(32,75,29,63,48,94

33、,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,916、已知如下图所示的一个网，按照Kruskal方法，求该网的最小生成树的产生过程。解：过程如下图所示。四

34、、算法设计题(本大题共2小题，每小题11分，共22分)1、编写一个单链表类的成员函数，实现删除不带头结点的单链表中数据域值等于x的第一个结点的操作。若删除成功，则返回被删除结点的位置；否则，返回-1。算法设计如下： public int remove(Object x) Node p = head;/ 初始化,p指向首结点Node q=null; /q用来记录p的前驱结点 int j = 0; /j为计数器/ 从单链表中的首结点元素开始查找，直到p.getData()指向元素x或到达单链表的表尾while (p != null && !p.getData().equals(x)

35、 q=p; p = p.getNext();/ 指向下一个元素 +j;/ 计数器的值增1 if (p!=null&&q=null) /删除的是单链表中的首结点 head=p.getNext(); else if (p != null) / 删除的是单链表中的非首结点 q.setNext(p.getNext(); else return -1;/值为x的结点在单链表中不存在 return j; 2、编写一个单链表类的成员函数，实现删除带头结点的单链表中数据域值等于x的所有结点的操作。要求函数返回被删除结点的个数。算法设计如下：public int removeAll(Object

36、 x) Node p = head.getNext();/ 初始化,p指向首结点,j为计数器Node q = head; / 用来记录p的前驱结点int j = 0;/ 用来记录被删除结点的个数while (p != null) / 从单链表中的首结点开始对整个链表遍历一次if (p.getData().equals(x) q.setNext(p.getNext();+j;/ 计数器的值增1 elseq = p;p = p.getNext();/ 指向下一个元素return j;/ 返回被删除结点的个数3、试设计算法，用插入排序方法对单链表进行排序。算法设计如下： public static

37、void insertSort(LinkList L) Node p, q, r, u; p = L.getHead().getNext(); L.getHead().setNext(null); /置空表，然后将原链表结点逐个插入到有序表中 while (p != null) /当链表尚未到尾，p为工作指针 r = L.getHead(); q = L.getHead().getNext(); while (q != null && (Integer.parseInt(String) q.getData() <= (Integer.parseInt(String) p.

38、getData() /查P结点在链表中的插入位置，这时q是工作指针 r = q; q = q.getNext(); u = p.getNext(); p.setNext(r.getNext(); r.setNext(p); p = u; /将P结点链入链表中，r是q的前驱，u是下一个待插入结点的指针 4、试设计算法，用选择排序方法对单链表进行排序。算法设计如下：/单链表选择排序算法 public static void selectSort(LinkList L) /p为当前最小,r为此过程中最小,q为当前扫描接点 Node p, r, q; Node newNode = new Node()

39、; 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.parseInt(String) q.getNext().getData() <= (Integer.parseInt(Str

40、ing) r.getNext().getData() r = q; q = q.getNext(); if (r != p) /交换p与r Node swap = r.getNext(); r.setNext(r.getNext().getNext(); /r的next指向其后继的后继 swap.setNext(p.getNext(); p.setNext(swap); /p的后继为swap p = p.getNext(); /while p.setNext(null); 5、试设计算法，使用非递归方法实现快速排序。算法设计如下： public static void Nonrecursive

41、QuickSort(int ary) if (ary.length < 2) return; /数组栈：记录着高位和低位的值 int stack = new int2ary.length; /栈顶部位置 int top = 0; /低位，高位，循环变量，基准点 /将数组的高位和低位位置入栈 stack1top = ary.length - 1; stack0top = 0; top+; /要是栈顶不空，那么继续 while (top != 0) /将高位和低位出栈 /低位：排序开始的位置 top-; int low = stack0top; /高位：排序结束的位置 int high =

42、stack1top; /将高位作为基准位置 /基准位置 int pivot = high; int i = low; for (int j = low; j < high; j+) if (aryj <= arypivot) int temp = aryj; aryj = aryi; aryi = temp; i+; /如果i不是基准位，那么基准位选的就不是最大值 /而i的前面放的都是比基准位小的值，那么基准位 /的值应该放到i所在的位置上 if (i != pivot) int temp = aryi; aryi = arypivot; arypivot = temp; if (

43、i - low > 1) /此时不排i的原因是i位置上的元素已经确定了，i前面的都是比i小的，i后面的都是比i大的 stack1top = i - 1; stack0top = low; top+; /当high-i小于等于1的时候，就不往栈中放了，这就是外层while循环能结束的原因 /如果从i到高位之间的元素个数多于一个，那么需要再次排序 if (high - i > 1) /此时不排i的原因是i位置上的元素已经确定了，i前面的都是比i小的，i后面的都是比i大的 stack1top = high; stack0top = i + 1; top+; 6、试设计算法，判断完全二叉树

44、是否为大顶堆。算法设计如下：boolean checkmax(BiTreeNode t) /判断完全二叉树是否为大顶堆 BiTreeNode p = t; if (p.getLchild() = null && p.getRchild() = null) return true; else if (p.getLchild() != null && p.getRchild() != null) if (RecordNode) p.getLchild().getData().getKey().compareTo(RecordNode) p.getData().getKey() <= 0 && (RecordNode) p.getRchild().getData().getKey().compareTo(RecordNode) p.