2023年研究生类研究生入学考试专业课计算机学科专业综合基础-数据结构历年高频考题带答案难题附详解

2023年研究生类研究生入学考试专业课计算机学科专业综合基础-数据结构历年高频考题带答案难题附详解（图片大小可自由调整）第1卷一.历年考点试题黑钻版(共50题)1.试设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字之前，并分析算法的时间复杂度。2.无向图G有23条边，度为4的顶点有5个，度为3的顶点有4个，其余都是度为2的顶点，则图G最多有______个顶点。A.11B.12C.15D.163.由权值为8，4，5，7的4个叶结点构造一棵哈夫曼树，该树的带权路径长度为______。A.24B.36C.48D.724.多路平衡归并排序是外排序的主要方法，试问多路平衡归并排序包括哪两个相对独立的阶段?每个阶段完成何种工作?5.设某二叉树的前序遍历序列为：ABCDEFGGI，中序遍历序列为：BCAEDGHFI

(1)试画出该二叉树；

(2)写出由给定的二叉树的前序遍历序列和中序遍历序列构造出该二叉树的算法。

(3)设具有四个结点的二叉树的前序遍历序列为abcd；S为长度等于4的由a，b，c，d排列构成的字符序列，若任取S作为上述算法的中序遍历序列，试问是否一定能构造出相应的二叉树?为什么?试列出具有4个结点二叉树的全部形态及相应的中序遍历序列。6.设有一个n×n的上三角矩阵(aij)，将其上三角中的元素按先行后列的顺序存于数组B[m]中，使得B[k]=aij且k=f1(i)+f2(j)+c，请推导出函数f1、f2和常数c，要求f1和f2中不含常数项。7.如下图所示，在下面的5个序列中，符合深度优先遍历的序列有______个。

①aebfdc

②acfdeb

③aedfcb

④aefdbc

⑤aecfdb

A.3B.4C.3D.28.利用双向链表做线性表的存储结构的优点是______。A.便于进行插入和删除的操作B.提高按关系查找数据元素的速度C.节省空间D.便于销毁结构释放空间9.设计一个算法，将一棵以链接方式存储的二叉树按顺序方式存储到数组A中。10.设T是哈夫曼二叉树，具有5个叶结点，树T的高度最高可以是______。A.3B.4C.5D.611.采用顺序结构存储串，编写一个函数index(s1，s2)，用于判定s2是否是s1的子串。若是子串，返回其在主串中的位置；否则返回-1。12.线性表是(

)。A.一个有限序列，可以为空B.一个有限序列，不可以为空C.一个无限序列，可以为空D.一个无限序列，不可以为空13.在一棵表示有序集S的二叉搜索树(binarysearchtree)中，任意一条从根到叶结点的路径将S分为3部分：在该路径左边结点中的元素组成的集合S1；在该路径上的结点中的元素组成的集合S2；在该路径右边结点中的元素组成的集合S3。S=S1∪S2∪S3。若对于任意的a∈S1，b∈S2，c∈S3，是否总有a≤b≤c?为什么?14.已知A和B为两个n×n阶的对称矩阵，输入时，对称矩阵只输入下三角形元素，存入一维数组，如图所示(对称矩阵M存储在一维数组A中)，设计一个算法求对称矩阵A和B的乘积。

15.设循环队列的存储容量为maxSize，队头和队尾指针分别为front和rear。若有一个循环队列Q，则可应用下列______算式计算队列元素个数。A.Q.rear-Q.frontB.Q.rear-Q.front+1C.(Q.rear-Q.front)%maxSize+1D.(Q.rear-Q.front+maxSize)%maxSize16.对于有n个数据元素的顺序存储的表，一个递增有序，另一个无序，查找一个元素时采用顺序算法，对有序表从头开始查找，发现当前运算已小于待查找元素时停止查找，确定查找不成功。已知查找任何一个元素的概率相同，则在两种表中成功查找______。A.平均时间后者小B.无法确定C.平均时间前者小D.平均时间相同17.有5个元素，其入栈次序为A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈的次序不包括______。A.CDEBAB.CDBEAC.CDBAED.CDAEB18.假设以行序为主序存储二维数组A—array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=

。A.808B.818C.1010D.102019.在二叉树的二叉链表中，空指针数有______个，等于非空指针数加2。选项中n为二叉树结点数，n1是单分支结点数，n2是双分支结点数。A.n+1B.n1C.n2D.n1+120.计算出的地址分布最均匀的散列函数是______。A.数字分析法B.除留余数法C.平方取中法D.折叠法21.若一个图的边集为{(A，B)，

(A，C)，

(B，D)，

(C，F)，

(D，E)，

(D，F)}，则从顶点A开始对该图进行广度优先搜索，得到的顶点序列可能为

。A.A，B，C，D，E，FB.A，B，C，F，D，EC.A，B，D，C，E，FD.A，C，B，F，D，E22.由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为

。A.24B.48C.72D.5323.如果一棵有n个结点的满二叉树的高度为h(根结点所在的层次为1)，则求解下列问题。

(1)用高度如何表示结点总数n?用结点总数n如何表示高度h?

(2)若对该树的结点从0开始按中序遍历次序进行编号，则如何用高度h表示根结点的编号?如何用高度h表示根结点的左子女结点的编号和右子女结点的编号?24.下面给出的4种排序方法中，______排序法是不稳定性排序法。A.插入B.冒泡C.二路归并D.堆25.若在一棵完全二叉树中对所有结点按层次自上向下，同一层次自左向右进行编号，根结点的编号为0，现有两个不同的结点，它们的编号是p和q，那么判断它们在同一层的条件应是______。

A．

B．

C．

D．p/2==q/226.以下排序方法中，稳定的排序方法是______。A.直接插入排序B.直接选择排序C.堆排序D.基数排序27.图的D-搜索类似于BFS(广度优先搜索)，不同之处在于用栈代替BFS中的队列，入、出队列的操作改为入、出栈的操作，即当一个顶点的所有邻接点被搜索之后，下一个搜索出发点应该是最近入栈(栈顶)的顶点。请用邻接表作为存储结构，写一个D-搜索算法。28.在对一组记录(50，40，95，20，15，70，60，45，80)进行希尔排序时，假定d0=9，d1=4，d2=2，d3=1，则第二趟排序结束后前4条记录为______。A.(50，20，15，70)B.(60，45，80，50)C.(15，20，50，40)D.(15，20，80，70)29.下述哪一条是顺序存储结构的优点?A.存储密度大B.插入运算方便C.删除运算方便D.可方便地用于各种逻辑结构的存储表示30.关于B-树，下列说法中不正确的是______。A.B-树是一种查找树B.所有的叶结点具有相同的高度C.2-3树中，所有非叶子结点有1或者3个孩子结点D.通常情况下，B-树不是二叉树31.对于无向图的生成树，下列说法错误的是______。A.生成树是遍历的产物B.从同一顶点出发所得的生成树相同C.生成树中不包括环D.不同遍历方法所得的生成树不同32.如果从无向图的任意一个顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是______。A.强连通图B.连通图C.有回路D.一棵树33.已知一棵二叉树，共有n个结点，那么此二叉树的高度为______。

A．nlog2n

B．log2n

C．

D．不确定34.已知单链表A的长度为m，单链表B的长度为n，若将B链接在A的末尾，在没有链尾指针的情况下，算法的时间复杂度应为______。A.O(1)B.O(m)C.O(n)D.O(m+n)35.设计在无头结点的单链表中删除第i个结点的算法。36.试问中序序列及后序序列是否能唯一地建立二叉树?若不能，则说明理由；若能，则对中序序列[)BEAFGC和后序序列DEBGFCA构造二叉树。37.后序序列与层次序列相同的非空二叉树是______。A.满二叉树B.完全二叉树C.单支树D.只有根结点的树38.试编写一个算法，检查一个程序中的花括号、方括号和圆括号是否配对，若能够全部配对则返回1，否则返回0。39.假设按低下标优先存储整型数组A[-3:8，3:5，-4:0，0:7]时，第一个元素的字节存储地址是100，每个整数占4个字节，则A[0，4，-2，5]的存储地址是(

)。A.1783B.1784C.1985D.198440.设有15000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素。

在快速排序、堆排序、归并排序、基数排序和希尔排序中，宜采用哪种方法并说明理由?41.已知连通图如下：

(1)若从顶点B出发对该图进行遍历，分别给出本图的按深度优先搜索和按广度优先搜索的顶点序列；

(2)写出按深度优先搜索的递归程序。42.假定数组A[0，…，n-1]中有多个零元素，试写出一个函数，将A中所有的非零元素依次移到数组A的前端。43.有6个元素按6，5，4，3，2，1的顺序依次进栈，不合法的出栈序列是______。A.543612B.453126C.346521D.23415644.就平均性能而言，目前最好的排序算法是______。A.选择排序B.快速排序C.冒泡排序D.插入排序45.中缀表达式D/C“A+B*E—D*F的前缀表达式为

。A.-+/D^CA*BE*DFB.DCA^/BE*+DF*-C.-C^A+/D*BE*DFD.-+/D^C*ABE*DF46.设计一个算法，判断无向图G是否连通。若连通，则返回1；否则返回0，假设图中顶点标号从0到g.vexnum-1。47.如果T2是由有序树T转换成的二叉树，那么T中结点的后根遍历序列对应T2中结点的______遍历序列。A.前序B.中序C.后序D.层次序48.下面关于m阶B树的说法中，正确的是______。

①每个结点至少有两棵非空子树。

②树中每个结点至多有m-1个关键字。

③所有叶子在同一层上。

④当插入一个数据项引起B树结点分裂后，树长高一层。A.①②③B.②③C.②③④D.③49.设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作，则下面得不到的序列为______。A.fedcbaB.bcafedC.dcefbaD.cabdef50.说明稀疏矩阵的三元组存储结构并实现稀疏矩阵的基本操作。第1卷参考答案一.历年考点试题黑钻版1.参考答案：采用类似于快速排序中的划分思想。算法如下：

voidpart(KeyTypeA[],intn){

inti-1;j=n;

KeyTypetemp;

while(i＜j){

while(i＜j&&A[j]＞=0)j--;

//从右向左找负数

while(i＜j&&A[i]＜0)i++;

//从左向右找非负数

if(i＜j){

//交换元素A[i]和A[j]

temp=A[i];A[i]=A[j];A[j]=temp;

i++;j--;

}

}

}

该算法的时间复杂度为O(n)。2.参考答案：D由于在具有n个顶点e条边的无向图中，有，故可求得度为2的顶点数为7个，从而最多有16个顶点。3.参考答案：C[解析]由权值为8，4，5，7的4个叶结点构造出的一棵哈夫曼树如下图所示。它的带权路径长度WPL的计算有两种方法：一是先求每一个叶结点的带权路径长度，加起来得到WPL=4×2+5×2+7×2+8×2=48；另一种方法是把所有非叶结点的权值加起得到WPL=24+9+15=48。

4.参考答案：多路平衡归并排序由两个相对独立的阶段组成：生成初始归并段和多趟归并排序。生成初始归并段阶段根据内存工作区的大小，将有n个记录的磁盘文件分批读入内存，采用有效的排序方法分别进行排序，生成若干个有序的子文件，即初始归并段。多趟归并排序阶段采用多路归并方法将这些归并段逐趟归并，最后归并成为一个有序文件。5.参考答案：

(1)

(2)设二叉树的前序遍历序列为P1，P2，…，Pm，中序遍历序列为S1，S2，…，Sm。因为前序遍历是“根左右”，中序遍历是“左右根”，则前序遍历序列中第一个结点是根结点(P1)。到中序序列中查询到Si=P1，根据中序遍历时根结点将中序序列分成两部分的原则，有：

若i=1，即S1=P1，则这时的二叉树没有左子树；否则，S1，S2，…，Si-1是左子树的中序遍历序列，用该序列和前序序列P2，P3，…，Pi去构造该二叉树的左子树。

若i=m，即Sm=P1，则这时的二叉树没有右子树；否则，Si+1，Si+2，…，Sm是右子树的中序遍历序列，用该序列和前序序列中Pi+1。，Pi+2，…，Pm，去构造该二叉树的右子树。算法描述请参见下面算法设计第56题。

(3)若前序序列是abcd，则并非由这4个字母的任意组合(4！=24)都能构造出二叉树。因为以abcd为输入序列，通过栈只能得到1/(n+1)*2n!/(n!*n!)=14种，即以abcd为前序序列的二叉树的数目是14。任取以abcd作为中序遍历序列，并不全能与前序的abcd序列构成二叉树，例如中序序列dcab。6.参考答案：上三角矩阵第1行有n个元素，第i-1行有n-(i-1)+1个元素，第1行到第i-1行是等腰梯形，而第i行上第j个元素(即aij)是第i行上第j-i+1个元素，故元素aij在一维数组中的存储位置(下标k)为：

k=(n+(n-(i-1)+1))(i-1)/2+(j-i+1)=(2n-i+2)(i-1)/2+j-i+1

进一步整理为：。则得。此问题考查的知识点是上三角矩阵的存储方式。7.参考答案：D本题中，符合深度优先遍历顺序的是1和5，其他三个序列均不符合。8.参考答案：B[解析]查找直接前驱和直接后继的时间代价都是O(1)。9.参考答案：本题采用递归方法求A的元素值。实现本题功能的程序代码如下：

voidctree(BTNode*t,charA[],inti)

{

if(t!=NULL)

{

A[i-1]=t→data;

ctree(t→left,A,2*i);

ctree(t→right,A,2*i+1);

}

}10.参考答案：C[解析]哈夫曼二叉树是只有度为2和度为0的结点的二叉树，有n个叶结点，就有n-1个非叶结点，其最大高度是n，即从第1层起到次底层止，每层有一个非叶结点，最底层有两个叶结点。例如，下图所示的哈夫曼树，n=5，叶结点的权值为{12，22，32，42，52}，该哈夫曼树的高度是5，所以具有5个叶结点的哈夫曼树的高度最高可以是5。

11.参考答案：本题的算法思想是，设

s1="a1a2…am"

s2="b1b2…bn"

从s1中找与b1匹配的字符ai，若ai=b1，则判断是否ai+1=b2，…，ai+1=bn，若都相等，则s2为s1子串；否则继续比较ai之后的字符。

本题代码如下：

intindex(Str*s1,Str*s2)

{

inti=0,j,k;

while(i＜s1-＞length)

{

j=0;

if(s1-＞ch[i]==s2-＞ch[j])

{

k=i+1;++j;

while(k＜s1-＞length&&j＜s2-＞length&&s1-＞ch[k]==s2-＞ch[j])

{

++k;++j;

}

if(j==s2-＞length)

//s2终止时找到了子串

break;

else++i;

}

else++i;

}

if(i＞=s1-＞length)

return-1;

else

returni+1;

}12.参考答案：A线性表是由相同类型的结点组成的有限序列。如：由n个结点组成的线性表

(a1，a2，…，an)

a1是最前结点，an是最后结点。结点也称为数据元素或者记录。

线性表中结点的个数称为其长度。长度为O的线性表称为空表。

所以答案为A。13.参考答案：不是。如下图所示的二叉搜索树：

取从4到12的路径，则S1={1，2，3，7}，S2={4，8，10，12}，S3为空集，取S1中的元素7和S2中的元素4，令a=7，b=4，有a＞b。则上述命题不成立。14.参考答案：对称矩阵第i行和第j列元素的数据在一维数组中的位置是：

i×(i-i)/2+j

(当i≥j时)

j×(j-1)/2+i

(当i＜j时)

本题实现代码如下：

intvalue(inta[],inti,intj)

{

if(i＞=j)

returna[(i*(i-1))/2+j];

else

returna[(j*(j-1))/2+i];

}

voidmult(inta[],intb[],intc[n][n])

{

inti,j,k,s;

for(i=0;i＜n;++i)

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

{

s=0;

for(k=0;k＜n;++k)

s=s+value(a,i,k)*value(b,k,j)；

c[i][j]=s;

}

}

voiddisp(inta[])

{

inti,j;

for(i=0;i＜n;++i)

{

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

cout＜＜setw(3)＜＜value(a,i,j);

cout＜＜endl;

}

}15.参考答案：D[解析]随着队列中元素的进队出队的交替进行，对于rear与front两指针，其相对位置不定。当rear＜front时，Q.reai-Q.front+maxSize正好是队列元素个数；当rear＞front时，可以用(Q.rear-Q.front+maxSize)%maxSize得到队列元素个数。16.参考答案：D[解析]顺序查找算法的性能与查找表是否有序无关，注意题目中所问是成功查找的效率。17.参考答案：D以元素C，D最先出栈的次序有三个：CDEBA、CDBEA、CDBAE。18.参考答案：B公式：Loc(Aij)=10(基地址)+[(5-1)*100+(5-1)]*2=818。19.参考答案：A[解析]对于有n个结点的二叉树，用二叉链表存储，其二叉链表中有2n个指针，其中有n-1个指针指向二叉树结点，剩下n+1个指针为空，所以空指针数等于非空指针数加2。20.参考答案：B[解析]用除留余数法转换后的散列表在表的装填因子不断趋向1的过程中，查找性能退化速度最慢，说明它产生的冲突最少，散列地址均匀分布在地址空间各处。21.参考答案：D对图的广度优先遍历方法描述为：从图中某个顶点v出发，在访问该顶点v之后，依次访问v的所有未被访问过的邻接点，然后再访问每个邻接点的邻接点，且访问顺序应保持先被访问的顶点其邻接点也优先被访问，直到图中的所有顶点都被访问为止。22.参考答案：D

生成的哈夫曼树如上图所示，路径长度为：3*(2+3)+2*(8+5+6)=53。23.参考答案：按照题意，该满二叉树的高度为h，结点总数为n，则：

(1)按照满二叉树的性质，n=2h-1；反之，h=log2(n+1)。

(2)用高度h确定根结点编号的依据有以下3种。

1)从满二叉树推知，结点数有n=2h-1个，编号从0到n-1，即0～(2h-2)。

2)由于是按中序遍历次序所作的编号，根结点的左、右子树的结点数相等，根结点的编号应位于正中。

3)按照求中点的公式，中点的编号应为mid=(low+high)/2=(0+2h-2)/2=2h-1-1，此即满二叉树根结点的编号。依次类推，根结点左子树有2h-1-1个结点，其结点编号从0到2h-1-2，左子树根结点(即根结点左子女结点)的编号为2h-2-1；而右子女结点的编号为2h-1+(2h-2-1)=3×2h-2-1。24.参考答案：D此题考查的知识点是排序算法的稳定性问题。如果待排序的文件中，存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序是稳定的排序；反之，若具有相同关键字的记录之间的相对次序发生变化，则称这种排序是不稳定的排序。是否稳定与算法有关，相邻数据比较的算法是稳定的，不相邻数据比较会出现不稳定。选项A、B、C都是相邻元素比较，是稳定的。所以选D。25.参考答案：A[解析]由结点层号计算公式可得编号为i(假设结点编号从0开始)的结点所在层号为+1。当两个结点位于同一层时，有，即。注意，如果结点编号从1开始，则。26.参考答案：A下表为各种排序方法的性能比较。由表可知，本题答案为A。27.参考答案：本题直接将BFS算法中的队列改为栈即可，程序代码如下：

voidbfs1(graphg,intV)

{

intstack[Vnum],top=-1;

intvisited[Vnum],i;

arcnode*p;

for(i=0;i＜Vnum;++i)

//赋初值

visited[i]=0;

visit(v);

//假设此函数已经定义，表示对v结点的访问操作

visited[v]=1;

++top;

stack[top]=v;

while(top＞=0)

{

v=stack[top];

--top;

p=g.adjlist[v].firstarc;

while(p!=NULL)

{

if(!visited[p→adjvex])

{

visit(p→adjvex);//访问p

visited[p→adjvex]=1;

++top;

stack[top]=p→adjvex;

}

p=p→nextarc;

}

}

}28.参考答案：Ct=3，d0=9，d1=4，d2=2，d3=1，第1趟(d1=4)后的结果为(15，40，60，20，50，70，95，45，80)，第2趟(d2=2)后的结果为(15，20，50，40，60，45，80，70，95)，本题答案为(15，20，50，40)。29.参考答案：A[解析]本题主要考查的知识点是顺序存储结构的特点。顺序存储的主要优点：可以顺序存取表中任意元素；主要缺点：在插入、删除某一元素时，需要移动大量元素。30.参考答案：CB-树定义如下：

一棵m阶B-树，或者是空树，或者是满足以下性质的m叉树：

(1)根结点或者是叶子，或者至少有两棵子树，至多有m棵子树。

(2)除根结点外，所有非终端结点至少有棵子树，至多有m棵子树。

(3)所有叶子结点都在树的同一层上。

(4)每个结点应包含如下信息：(n，A0，K1，A1，K2，A2，…，Kn，An)。

其中：

·Ki(1≤i≤n)是关键字，且K＜Ki+1(1≤i≤n-1)；

·Ai(i=0，1，…，n)为指向孩子结点的指针，且Ai-1所指向的子树中所有结点的关键字都小于Ki，Ai所指向的子树中所有结点的关键字都大于Ki。

n是结点中关键字的个数，且-1≤n≤m-1，n+1为子树的棵数。31.参考答案：B[解析]生成树不允许有环是显而易见的。生成树是通过遍历图中的顶点得到的；遍历方法不同，所得生成树也不同。从同一顶点开始遍历，如果某一个顶点的邻接顶点有多个可选时，选择不同的邻接顶点，可构成不同的生成树，所以选项B不正确。32.参考答案：B[解析]对无向图作一次深度优先搜索，可遍历连通图的所有顶点。当然，通过深度优先搜索也可以遍历一棵树，不过遍历树通常被称为中序、前序、后序遍历；强连通图是有向图，与题意矛盾；有回路的无向图不一定是连通图，因为回路不一定包含图的所有结点。33.参考答案：D已知一棵二叉树共有n个结点，但二叉树的形式没有给出，因此，二叉树的高度不能确定。34.参考答案：B[解析]需要搜索并找到A的链尾，遍历表A的m个结点。35.参考答案：算法思想为：

(1)应判断删除位置的合法性，当i＜0或i＞n-1时，不允许进行删除操作；

(2)当i=0时，删除第一个结点；

(3)当0＜i＜n时，允许进行删除操作，但在查找被删除结点时，须用指针记住该结点的前趋结点。算法描述如下：

delete(LinkList*q，inti)

{

∥在无头结点的单链表中删除第i个结点

LinkList

*P，*S；

intj；

if(i＜0)

printf(“Can'tdelete”)；

elseif(i==0)

{

s=q；

q=q—＞next；

free(s)；

}

else

{j=0；s=q；

while((j＜i)&&(s!=NULL))

{

p=s；

s=s=＞next；

j++：

}

if(s==NULL)

printf(“Cant'tdelete”)；

else

{

p—＞next=s—＞next；

free(s)；

}

}

}36.参考答案：[证明]

当n=1时，只有一个根结点，由中序序列和后序序列可以确定这棵二叉树。

设当n=m-1时结论成立，现证明当n=m时结论成立。

设中序序列为S1，S2，…，Sm，后序序列是P1，P2，…，Pm。因后序序列最后一个元素Pm是根，则在中序序列中可找到与Pm相等的结点(设二叉树中各结点互不相同)Si(1≤i≤m)，因中序序列是由中序遍历而得，所以Si是根结点，S1，S2，…，Si-1是左子树的中序序列，而Si+1，Si+2，…，Sm是右子树的中序序列。

若i=1，则S1是根，这时二叉树的左子树为空，右子树的结点数是m-1，则{S2，S3，…，Sm}和{P1，P2，…．Pm-1}可以唯一确定右子树，从而也确定了二叉树。

若i=m，则Sm是根，这时二叉树的右子树为空，左子树的结点数是m-1，则{S1，S2，…，Sm-1}和{P1，P2，…，Pm-1}唯一确定左子树，从而也确定了二叉树。

最后，当1＜i＜m时，s，把中序序列分成{S1，S2，…，Si-1}和{Si+1，Si+2，…，Sm}。由于后序遍历是“左子树—右子树—根结点”，所以{P1，P2，…，Pi-1)和{Pi，Pi+1，…Pm-1}是二叉树的左子树和右子树的后序遍历序列。因而由{S1，S2，…，Si-1}和{P1，P2，…，Pi-1}可唯一确定二叉树的左子树，由{Si+1，Si+2，…，Sm}和{Pi，Pi+1，…，Pm-1}可唯一确定二叉树的右子树。

由中序序列DBEAFGC和后序序列DEBGFCA构造的二叉树如下图：

37.参考答案：D[解析]对二叉树进行后序遍历的规则是LRV(左、右、根)，在多数情况下遍历结果显然与层次遍历的结果不同，只有当树中仅含有一个结点的情形下，两者才有相同的遍历结果。38.参考答案：在算法中，扫描程序中的每一个字符，当扫描到花、中、圆左括号时，令其进栈，当扫描到花、中、圆右括号时，则检查栈顶是否为相应的左括号，若是则作退栈处理，若不是则表明出现了语法错误，应返回0。当扫描到程序文件结尾后，若栈为空则表明没有发现括号配对错误，应返回1，否则表明栈中还有未配对的括号，应返回0。另外，对于一对单引号或双引号内的字符不进行括号配对检查。

根据分析，编写出算法如下：

intBracketsCheck(char*f){

//对由f所指字符串中的文本进行括号配对检查

stackS;charch;

//定义一个栈

char*p=f;

while(*p!='\0'){

//顺序扫描字符串中的每一个字符

if(*p==39){

//单引号内的字符不参与配对比较

while(*p!='\0'&&'P!=39)

//39为单引号的ASCII值、p++;

}

elseif(*p!='\0'&&*p==34){

//双引号内的字符不参与配对比较

while(*p!='\0'&&*p!=34)

//34为双引号的ASCII值p++;

}

if(*p!='\0'){

switch(*p){

case'{':case'[':case'(':push(S,*p);break;

//左括号进栈

case'}':getTop(S,ch);

if(ch=='{')pop(S,ch);

//栈顶的左花括号出栈

elsereturn(0);break;

case']':getTop(S,ch);

if(ch=='[')pop(S,ch);

//栈顶的左中括号出栈

elsereturn(0);break;

case')':getTop(S,ch);

if(ch=='(')pop(S,ch);

//栈顶的左圆括号出栈

elsereturn(0);

}

p++;

}

if(isEmpty(S))return(1);

elsereturn(0);

}

}39.参考答案：B40.参考答案：上面所说的几种排序方法中，排序速度都很快，但快速排序、归并排序、基数排序和希尔排序都是在排序结束后才能确定数据元素的全部序列，而排序过程中无法知道部分连续位置上的最终元素。而堆排序则是每次输出一个堆顶元素(即最大或最小值的元素)，然后对堆进行再调整，保证堆顶元素总是当前剩下元素的最大或最小的，从而可知，如果在一个大量数据的文件中，如含有15000个元素的记录文件中选取前10个最大的元素，宜采用堆排序。41.参考答案：

(1)在邻接点按升序排列的前提下，其深度优先搜索和广度优选搜索序列分别为BADCEF和BACEDF。

(2)

voiddfs(v)

{

i=GraphLocateVertex(g，v)；

∥定位顶点

visited[i]=1；

printf(v)；

∥输出顶点信息

p=g[i]．firstarc；

while(p)

{

if(visited[p—＞adjvex]==0)dfs(g[p—＞adjvex]．vertex)；

p=p—＞next；

}

}

voidtraver()

∥深度优先搜索的递归程序；以邻接表表示的图g是全局变量。

{

for(i=1；i＜=n；i++)

visited[i]=0；∥访问数组是全局变量初始化。

for(vi=v1；vi＜=vn；vi++)

if(visited[GraphLocateVertex(g，vi)]==0)

dis(vi)；

}42.参考答案：因为数组是一种直接存取的数据结构，在一维数组中元素不是像顺序表那样集中存放于表的前端，而是根据元素下标直接存放于数组某个位置，所以将非零元素前移时必须检测整个数组空间，并将后面变成零元素的空间清零。函数中设置一个辅助指针free，指示当前可存放的位置，初值为0。算法的程序代码如下：

voidcompact(intA[],intn)

{

intfree=0;

for(inti=0;i＜n;++i)

//检测整个数组

if(A[i]!=0)

//发现非零元素

{

if(i!=free)

//前移非零元素

{

A[free]=A[i];

A[i]=0;

}

++free;

}

}43.参考答案：C此题考查的知识点是栈的后进先出特点。考查出栈序列，要保证先入栈的一定不能在后入栈的前面出栈，C选项中的6在5前入栈，5没有出栈，6却出栈了，所以不合法。其他都符合规律。所以选C。44.参考答案：B[解析]目前，平均性能最好的排序是快速排序。45.参考答案：A第一步：加括号

D/(C^A)+B*E-D*F

(D/(C^A))+B*E-D*F

(D/(C^A))+(B*E)-D*F

(D/(C^A))+(B*E)-(D*F)

((D/(C^A))+(B*E))-(D*F)

(((D/(C-A))+(B*E))-(D*F))