数据结构题库

考证素材考证素材数据结构(课程代码02331)一、单项选择题(本大题共15小题，每题2分，共30分)在每题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多项选择或未选均无分。1、对顺序存储的线性表，设其长度为n在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的〔A〕个元素。A、n/2B、(n+1)/2C、(n-1)/2D、n2、一个向量(一种顺序表)第一个元素的存储地址是100，每个元素的长度为2，则第5个元素TOC\o"1-5"\h\z的地址是B___。A、100B、108C、110D、1203、一个栈的入栈序列a,b,c,d,e,则栈的不可能的输出序列是_C。A、edcbaB、decbaC、dceabD、abcde4、假设已知一个栈的入栈序列是1,2,3,…，n,其输出序列为p1,p2,p3,…，pn,假设p1=n，则pi为_C。A、iB、n-iC、n-i+1D、n-i-15、判定一个循环队列QU〔最多元素为m〕为空的条件是___C_oA、rear-front==mB、rear-front-1==mC、front==rearD、front==rear+16、判定一个循环队列QU〔最多元素为m,m==MaxsizeT〕为满队列的条件是__A__。A、((rear-front)+Maxsize)%Maxsize==mB、rear-front-1==mC、front==rearD、front==rear+17、循环队列用数组A0,m-1］存放其元素值，已知其头尾指针分别是front和rear,则当前队列中的元素个数是—丄。A、(rear-front+m)%mB、rear-front+1C、rear-front-1D、rear-front8、设串的长度为n,则它的子串个数为oA、nB、n(n+1)C、n(n+1)/2D、n(n+1)/2+19、S1=“ABCD〃，S2=“CD〃则S2在S3中的位置是〔C〕A、1B、2C、3D、410、设数组a7］6］的基地址为1024,每个元素占2个存储单元,假设以行序为主序顺序存储，则元素a2］4］的存储地址是_B_。A、1054B、1056C、1058D、109811、二维数组A中，每个元素A的长度为3个字节，行下标i从0到7,列下标j从0到9,从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A4］7］的起始地址为—亠_。A、SA+141B、SA+180C、SA+222D、SA+22512、二维数组A中，每个元素的长度为3个字节，行下标i从0到7,列下标j从0到9,从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是__C__oA、80B、100C、240D、27013、二维数组A中，每个元素A的长度为3个字节，行下标i从0到7,列下标j从0到9,从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A7]4]的起始地址为丄__。A、SA+141B、SA+144C、SA+222D、SA+22514、假定在一棵二叉树中，双分支结点数为15个，单分支结点数为30个，则叶子结点个数为TOC\o"1-5"\h\zB。A、15B、16C、17D、4715、按照二叉树的定义，具有3个结点的不同形状的二叉树有亠种。A、3B、4C、5D、616、深度为5的二叉树至多有丄—个结点。A、16B、32C、31D、1017、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为__A__oA、2hB、2h-1C、2h+1D、h+118、对一个满二叉树，m个树叶，n个结点，深度为h，则』__。A、n=h+mB、h+m=2nC、m=h-1D、n=2h-119、如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为CoA、uwvtsB、vwutsC、wuvtsD、wutsv20、某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是__D__oA、bdgcefhaB、gdbecfhaC、bdgaechfD、gdbehfca21、已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是__D__oA、acbedB、decabC、deabcD、cedba22、由带权为9,2,5,7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为(D)oTOC\o"1-5"\h\zA、23B、37C、46D、4423•在一棵具有n个结点的二叉树第i层上，最多具有(C)个结点。A、2iB、2i+1C、2i-1D、2n24、在一个图中，全部顶点的度数之和等于全部边数的倍数为亠C__。A、1/2B、1C、2D、425、在一个有向图中，全部顶点的入度之和等于全部顶点的出度之和的__^倍。A、1/2B、1C、2D、426、一个有n个顶点的无向图的边数最多为亠C__。A、nB、n(n-1)C、n(n-1)/2D、2n27、具有4个顶点的无向完全图有__A_—条边。A、6B、12C、16D、2028、具有6个顶点的无向图至少应有_A__条边才能确保是一个连通图。A、5B、6C、7D、829、在一个具有n个顶点的无向图中，要连通全部顶点至少需要_=C=_条边。A、nB、n+1C、n-1D、n/230、对于一个具有n个顶点的无向图，假设采纳邻接矩阵表示，则该矩阵的大小是—_D__。A、nB、(n-1)2C、n-1D、n231、对于一个具有n个顶点和e条边的无向图，假设采纳邻接表表示，则表头向量的大小为—丄。A、nB、n+1C、n-1D、n+e32、判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用_D___。A、求关键路径的方法B、求最短路径的Dijkstra方法C、宽度优先遍历算法D、深度优先遍历算法33、关键路径是事件结点网络中一匸。A、从源点到汇点的最长路径B、从源点到汇点的最短路径C、最长的回路D、最短的回路34、一个有n个顶点的无向连通图，它所包含的连通重量个数为_^。A、0B、1C、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、nB、n(n-1)C、n(n+1)2D、n38、n个顶点的强连通图至少有(A)条边。A、nB、n-1C、n+1D、n(n-1)39、在一个具有n个顶点的有向图中，假设全部顶点的出度之和为s,则全部顶点的入度之和为(A)。A、sB、s-1C、s+1D、n40、在一个无向图中，假设两个顶点之间的路径长度为k,则该路径上的顶点数为(B)。A、kB、k+1C、k+2D、2k41、一个图中包含k个连通重量，假设按深度优先(DFS)搜索方法访问全部结点，则必须调用(A)次深度优先遍历算法。A、kB、1C、k-1D、k+142、设G1=(V1,E1)和G2=(V2,E2)为两个图，V1cV2,E1cE2，则称〔A〕A、G1是G2的子图B、G2是G1的子图C、G1是G2的连通重量D、G2是G1的连通重量43、采纳顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为_C__.A、nB、n/2C、(n+1)/2D、(n-1)/244、采纳二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为亠D__。A、O〔n2〕B、O(nlogn)C、O(n)D、O(logn)45、有一个有序表为｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，当二分查找值82为的结点时，—_C_—次比拟后查找成功。A、1B、2C、4D、846、有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比拟次数为__B__oA、35/12B、37/12C、39/12D、43/1247、对于18个元素的有序表采纳二分(折半)查找，则查找A3］的比拟序列的下标为(D)oA、1、2、3B、9、5、2、3C、9、5、3D、9、4、2、348、一组记录的排序码为〔46,79,56,38,40，84〕，则利用堆排序的方法建立的初始堆为__B__。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，3849、一组记录的关键码为〔4679，56，38，40，84〕，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为COA、38，40，46，56，79，84B、40，38，46，79，56，84C、40，38，46，56，79，84D、40，38，46，84，56，7950、一组记录的排序码为〔瓦48，16,35,79,82,23,40,36,72〕，其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为_A_oA、16，25，35，48，23，40，79，82，36，72B、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，40，72，8251、下述几种排序方法中，要求内存量最大的是丄__。A、插入排序B、选择排序C、快速排序D、归并排序52、在对n个元素进行简单项选择择排序过程中，第i趟需从(A)个元素中选择出最小值元素。A、n-i+1B、n-iC、iD、i+153、n个记录直接插入排序所需的记录最小比拟次数是(A)A、n-1B、2(n-1)C、(n+2)(n-1)/2D、n54、一组记录的关键字为〔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,4(0,42,，85,,贝利用快速排序的方法，以第一个记录为基准得到一次划分结果是(C)qA、〔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〕。TOC\o"1-5"\h\zA,98B,99C,50D,48—组记录的排序码为(48,24,18,53,16,26,40),采纳冒泡排序法进行排序，则第一趟排序需要进行记录交换的次数是〔C〕。A,3B,4C,5D,6采纳分块查找时，如某线性表有256个元素，查找每个元素的概率相同，假设采纳顺序查找来确定元素所在的块，则每块包含〔C,个结点时，平均查找长度最小。A,256B,15(:,16D,18-01疔A=10101059.对于有向图的邻接矩阵,该图共有〔B，条弧。A,5B,4C,3D,2TOC\o"1-5"\h\z60.由带权9、1、3、5、6的五个叶子结点生成的哈夫曼树的带权路径长度为〔C〕。A,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;2、下面程序段的时间复杂度是____O(Qn)一。i=s=0while(s〈n){i++;/Xi=i+1X/s+=i;/Xs=s+iX/}3、下面程序段的时间复杂度是___O(n2>qs=0;for(i=0;i<n;i++)for(j=0;j<n;j++)s+=bi]j];sum=s;4、下面稈序段的时间复杂度是一_Odogp)_一。Oi=1;while(i<=n)i=iX3;5、在顺序表中，假设第一个元素所在的地址为Loc(a1),每个元素在内存中占有L个存储单元,TOC\o"1-5"\h\z贝U元素ai在内存中的地址Loc(ai)=__Loc(a1)+(iT)XL。6、向一个长度为n的顺序表的第i个元素〔1WiWn+1〕之前插入一个元素时，需向后移动亠n-i+l_个元素。7、向一个长度为n的顺序表中删除第i个元素〔IWiWn〕时，需向前移动—n-i—个元素。8、串s='abcdef',s1='cde',si在s中的位置为3。9、已知二维数组Am]n]采纳行序为主方法存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(AO]O])，则Ai]j]的地址是LOC(A0]0])+(nXi+j)Xk。10、二维数组A10]20]采纳列序为主方法存储，每个元素占一个存储单元并且A0]0]的存储地址是200，则A6]12]的地址是__326_。11、二维数组A10…20]5…10]采纳行序为主方法存储，每个元素占4个存储单元，并且A10]5]的存储地址是1000，则A18]9]的地址是_」208一。12、现有一个n阶的对称矩阵an]n]，现将其压缩存储在一个一维数组sm]中，则m=,n(n+l)/2，假设以行序为主序进行存储，则元素ai]j](i〉=j)在s中的下标k=i(i-1)/2+j-1__。13、在一个mXn的矩阵中，假设a0]0]是第一个元素，则ai]j]是第—iXn+j—__个元素。14、在二叉树中，某一结点x的编号为i,x假设有双亲，其双亲编号应为__卩/2」亠；x假设有左孩子，其左孩子编号应为___2Xi___；x假设有右孩子，其右孩子应为__2Xi+l。15、8层完全二叉树至少有—128一个结点，拥有100个结点的完全二叉树的最大层数为7_。16、n个顶点的连诵图至少—nT__条边。17、在无向图G的邻接矩阵A中，假设Ai]j]等于1,则Aj]i]等于=1—_。n18、一个无向图有n个顶点和e条边，则全部顶点的度的和即乞di(表示顶点i的度)=i=12e。19、在有n个顶点的有向图中，每个顶点的度最大可达—2(nT)一。20、对于长度为n的线性表，假设进行顺序查找，则时间复杂度为___O〔〕__；假设采纳折半法查找，则时间复杂度为__O(log2i)__。21、已知有序表为〔12，18，24，35，47，50，62，83，90，115，134〕，当用折半查找90时，需进行一2—次查找可确定成功；查找47时，需进行—次查找成功；查找100时，需进行3次查找才能确定不成功。22、平衡二叉排序树上任一结点的平衡因子只可能是0、丄或-1。23、用起泡法对n个关键码排序，在最好情况下，只需做——n-1次比拟；在最坏的情况下要做n(n-1)/2次比拟。24、设字符串S1=“ABCDEF"，S2=“PQRS"，则运算S=C0NCAT〔SUB〔S1，2，LEN〔S2〕，SUB〔S1，LEN〔S2〕，2,后的串值为“BCDEDE"_。25、在一棵二叉排序树上按___—中序___遍历得到的结点序列是一个有序序列。26、在一个图中，全部顶点的度数之和等于全部边数的___2一—倍。27、在一个具有n个顶点的无向完全图中，包含有__n(n-l)/2______条边，在一个具有n个顶点的有向完全图中，包含有—n(nT)____条边。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个顶点的无向图中，要连通全部顶点则至少需要nT条边。30、假设一个图的顶点集为｛a,b,c,d,e,f｝，边集为｛(a,b),(a,c),(b,c),(d,e)｝，则该图含有_个连通重量。31、对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为_亠____和nT__。32、假定一个顺序表的长度为40，并假定查找每个元素的概率都相同，则在查找成功情况下的平均杳找长度._20.5，在杳找不成功情况下的平均杳找长度一_41.一。33、在索引查找中，假定查找表〔即主表，的长度为96，被等分为8个子表，则进行索引查找的平均查找长度为11__。34、假定对长度n=50的有序表进行折半查找，则对应的判定树高度为__6__，最后一层的结TOC\o"1-5"\h\z点数为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将最终下沉到其后第______个元素的位置。39、假定一组记录为(46,79,56,38,40,80),对其进行快速排序的第一次划分后的结果为___403846567980]。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，请写出该二叉树的后序遍历序列。解：后序序列：ACDBGJKIHFE5、已知一个无向图的邻接表下列图所示，要求：〔1〕画出该无向图；⑵依据邻接表，分别写出用DFS(深度优先搜索)和BFS〔广度优先搜索〕算法从顶点V0开始遍历该图后所得到的遍历序列。解：〔1〕该无向图如下列图所示。〔2〕依据该无向图的邻接表表示，从顶点V0开始的深度优先遍历序列为：VO、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,34)，给出采纳冒泡排序法进行排序时每一趟的排序结果。解：排序过程如下：(0)46745314263886652734](1)46531426387465273486(2)46142638536527347486(3)14263846532734657486(4)14263846273453657486(5)14263827344653657486(6)14262734384653657486(7)142627343846536574869、已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采纳直接插入排序法进行排序时每一趟的排序结果。解：排序过程如下所示：(0)46745314263886652734(1)46745314263886652734(2)46537414263886652734(3)14465374263886652734(4)14264653743886652734(5)14263846537486652734(6)14263846537486652734(7)14263846536574862734(8)14262738465365748634(9)14262734384653657486]10、关键字序列为〔47,7,29,11,16,92,22,8,3,50,37,89,94,21〕，哈希函数为：Hash(key)=keymod11,用拉链表处理冲突。解：建表如下：11、已知如下列图所示的有向图,请给出该图的(1)每个顶点的出/入度；(2)邻接矩阵；(3)邻接表；解：(1)每个顶点的出/入度是：(2)邻接矩阵：(3)邻接表：12、已知图的邻接矩阵如下列图所示。试分别画出自顶点A出发进行遍历所得的深度优先生成树和广度优先生成树。解：〔1〕深度优先搜索如下所示：(2)广度优先搜索如下所示：13、已知一组记录为(46,74,53,14,26,38,86,65,27,34),给出采纳归并排序法进行排序时每一趟的排序结果。解：排序过程如下所示：(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,916、已知如下列图所示的一个网,按照Kruskal方法,求该网的最小生成树的产生过程。解：过程如下列图所示。四、算法设计题(本大题共2小题,每题11分,共22分)1、编写一个单链表类的成员函数，完成删除不带头结点的单链表中数据域值等于X的第一个结点的操作。假设删除成功，则返回被删除结点的位置；否则，返回-1。算法设计如下：publicintremove(Objectx){Nodep=head;//初始化,p指向首结点Nodeq=null;//q用来记录p的前驱结点intj=0;//j为计数器//从单链表中的首结点元素开始查找，直到p.getData()指向元素x或到达单链表的表尾while(p!=null&!p.getData().equals(x)){q=p;p=p.getNext();//指向下一个元素++j;//计数器的值增1}if(p!=null&&q==null)//删除的是单链表中的首结点head=p.getNext();elseif(p!=null){//删除的是单链表中的非首结点q.setNext(p.getNext());}elsereturnT;//值为x的结点在单链表中不存在returnj;}2、编写一个单链表类的成员函数，完成删除带头结点的单链表中数据域值等于x的全部结点的操作。要求函数返回被删除结点的个数。算法设计如下：publicintremoveAll(Objectx){Nodep=head.getNext();//初始化,p指向首结点，j为计数器Nodeq=head;//用来记录p的前驱结点intj=0;//用来记录被删除结点的个数while(p!=null){//从单链表中的首结点开始对整个链表遍历一次if(p.getData().equals(x)){q.setNext(p.getNext());++j;//计数器的值增1}elseq=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.getHead();q=L.getHead().getNext();while(q!=null&(Integer.parseInt((String)q.getData()))<=(Integer.parseInt((String)p.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、试设计算法，用选择排序方法对单链表进行排序。算法设计如下：//单链表选择排序算法publicstaticvoidselectSort(LinkListL){//p为当前最小,r为此过程中最小,q为当前扫描接点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.parseInt((String)q.getNext().getData())<=(Integer.parseInt((String)r.getNext().getData()))){r=q;}q=q.getNext();}if(r!=p){//交换p与rNodeswap=r.getNext();r.setNext(r.getNext().getNext());//r的next指向其后继的后继swap.setNext(p.getNext());p.setNext(swap);//p的后继为swap}p=p.getNext();}//whilep.setNext(null);}5、试设计算法，使用非递归方法完成快速排序。算法设计如下：publicstaticvoidNonrecursiveQuickSort(intary){if(ary.length<2){return;}//数组栈：记录着高位和低位的值int]stack=newint2]ary.length];//栈顶部位置inttop=0;//低位，高位，循环变量，基准点//将数组的高位和低位位置入栈stack1]top=ary.length-1;stack0]top=0;top++;//要是栈顶不空，那么继续while(top!=0){//将高位和低位出栈//低位：排序开始的位置top--;intlow=stack0]top];//高位：排序结束的位置inthigh=stack1]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大的stack1]top=i-1;stack0]top=low;top++;}//当high-i小于等于1的时候，就不往栈中放了，这就是外层while循环能结束的原因//如果从i到高位之间的元素个数多于一个，那么需要再次排序if(high-i>1){//此时不排i的原因是i位置上的元素已经确定了，i前面的都是比i小的，i后面的都是比i大的stack1]top=high;stack0]top=i+1;top++;}}}6、试设计算法，推断完全二叉树是否为大顶堆。算法设计如下：booleancheckmax(BiTreeNodet)//推断完全二叉树是否为大顶堆{BiTreeNodep=t;if(p.getLchild()==null&p.getRchild()==null){returntrue;}else{if(p.getLchild()!=null&p.getRchild()!=null){if((((RecordNode)p.getLchild().getData()).getKey())pareTo(((RecordNode)p.getData()).getKey())<=0&(((RecordNode)p