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

2023年研究生类研究生入学考试专业课计算机学科专业综合基础-数据结构历年高频考题带答案难题附详解（图片大小可自由调整）第1卷一.历年考点试题黑钻版(共50题)1.已知10个数据元素为(54，28，16，34，73，62，95，60，26，43)，对该序列按从小到大排序，经过一趟冒泡排序后的序列为______。A.16，28，34，54，73，62，60，26，43，95B.28，16，34，54，62，73，60，26，43，95C.28，16，34，54，62，60，73，26，43，95D.16，28，34，54，62，60，73，26，43，952.一棵含有n个结点的k叉树，可能达到的最大深度为______，最小深度为logk(n×(k-1)+1)。A.logk(n×(k-1)+1)B.logk(n×k-1)+1C.kD.n3.一个递归算法必须包括______。A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分4.若某表最常用的操作是在最后一个结点之后插入一个结点后再删除最后一个结点，则采用______存储方式最节省运算时间。A.单链表B.双链表C.单循环链表D.带头结点的双循环链表5.设A是n×n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1…n(n+1)/2]中，对上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置为______。A.i(i-1)/2+jB.j(j-1)/2+iC.j(j-1)/2+i-1D.i(i-1)/2+j-16.欲用4种颜色对地图上的国家涂色，有相邻边界的国家不能用同一种颜色(点相交不算相邻)。

(1)试用一种数据结构表示地图上各国相邻的关系；

(2)描述涂色过程的算法。(不要求证明)7.已知单链表A的长度为m，单链表B的长度为n，若将B链接在A的末尾，在没有链尾指针的情况下，算法的时间复杂度应为______。A.O(1)B.O(m)C.O(n)D.O(m+n)8.邻接多重表的存储结构和十字链表类似，也是由顶点表和边表组成，每一条边用一个结点表示，其顶点表结点结构和边表结点结构如下图所示：

关于图中各个域的说明，不正确的是______。A.vertex存储的是结点的数值域的内容B.firstedge域指示第一条依附于该顶点的边C.mark指向下一条依附于结点的边D.info为指向和边相关的各种信息的指针域9.具有10个叶结点的二叉树中有

个度为2的结点。A.8B.9C.10D.1110.现有两栈，其共享空间为V[1..m]，top[i]代表第i个栈(i=1，2)栈顶，栈1的底在V[1]，栈2的底在V[m]，若两栈均采用顺序存储方式存储，则栈满的条件是______。A.|top[2]-top[1]|=0B.top[1]+1=top[2]C.top[1]+top[2]=mD.top[1]=top[2]11.设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是

。A.F，H，C，D，P，A，M，Q，R，S，Y，XB.P，A，C，S，Q，D，F，X，R，H，M，YC.A，D，C，R，F，Q，M，S，Y，P，H，XD.H，C，Q，P，A，M，S，R，D，F，X，Y12.当所有n个待排序记录的排序码都相等时，直接插入排序、堆排序、起泡排序、简单选择排序的排序码比较次数和元素移动次数分别为(①)、O(n)和O(n)、n-1和0、n(n-1)/2和0。A.n-1和0B.n(n-1)/2和nC.n(n-1)/2和0D.O(n)和O(n)13.无向图G=(V，E)，其中：V={a，b，c．d，e，f}，E={(a，b)，

(a，e)，(a，c)，(b，e)，(c，f)，(f，d)，(e．d)}，对该图进行深度优先遍历，得到的顶点序列正确的是

。A.a，b，e，c，d，fB.a，c，f，e，b，dC.a，e，b，c，f，dD.a，e，d，f，c，b14.设森林F对应的二叉树为B，它有m个结点。B的根为p，p的右子树中结点个数为n，则森林F中第一棵树的结点个数是______。A.m-nB.m-n-1C.n+1D.无法确定15.在一棵m阶B树的结点中插入新关键字时，若插入前结点的关键字数为______，则插入新关键字后该结点必须分裂为两个结点。A.mB.m-1C.m+1D.m-216.写出在二叉排序树中删除一个结点的算法，使删除后仍为二叉排序树。设删除结点由指针p所指，其双亲结点由指针f所指，并假设被删除结点是其双亲结点的右孩子。描述上述算法。17.线性表的每一个表元素是否必须类型相同?为什么?18.对给定关键字的序号j(0≤j＜n)，要求在无序记录A[0，…，n-1]中找按关键字从小到大排在第i位上的记录，利用快速排序的划分思想设计上述算法。19.编写一个算法，在一棵中序线索二叉树中以非递归的方式中序正向和中序反向遍历该二叉树。20.有一幅如图所示的藏宝图，设计一个算法要求从入口到出口，必须经过“食品”和“财宝”的地方，不得经过“强盗”的地方。

21.如果将所有中国人按照生日(不考虑年份，只考虑月、日)来排序，那么使用下列排序算法中最快的是______。A.归并排序B.希尔排序C.快速排序D.基数排序22.一棵哈夫曼树共有99个结点，对其进行哈夫曼编码，共能得到______种不同的编码。A.48B.50C.99D.10023.一棵二叉树如下图所示，其中序遍历序列为______。

A.abdgcefhB.dgbaechfC.gdbehfcaD.abcdefgh24.设A是一个线性表(a1，a2，…，an)，采用顺序存储结构，则在等概率的前提下，平均插入一个元素需要移动的元素个数是多少?若元素插入在ai与ai+1之间(1≤i≤n-1)的概率为，则平均每插入一个元素所要移动的元素个数是多少?25.对任何一棵二叉树，如果终端结点数为n0，度为2的结点数为n2，则一定有n0=n2+1。26.对下面的3阶B树，依次执行下列操作，画出各步操作的结果。

(1)插入90

(2)插入25

(3)插入45

(4)删除60

(5)删除80

27.求最短路径的Dijkstra算法的时间复杂度为______。A.O(n)B.O(n+e)C.O(n2)D.O(n×e)28.图的广度优先遍历算法中使用队列作为其辅助数据结构，那么在算法执行过程中每个顶点最多进队______次。A.1B.2C.3D.429.对于具有n(n＞1)个顶点的强连通图，其有向边的条数至少是______。A.n+1B.nC.n-1D.n-230.二又树的叶结点在前序、中序和后序遍历过程中的相对顺序______。A.发生改变B.不发生改变C.无法确定D.以上均不正确31.设有一棵B+树，其结点最多可存放100个索引项。对于高度为1、2、3、4的B+树，最多能存储多少索引项?最少能存储多少索引项?32.对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的______个元素。A.n/2B.(n+1)/2C.(n-1)/2D.n33.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行______操作。A.s→next=p→next;p→next=s;B.p→next=s→next;s→next=p;C.q→next=s;s→next=p;D.p→next=s;s→next=q;34.双向链表中有两个指针域，即prior和next，分别指向前驱及后继，设p指向链表中的一个结点，q指向一个待插入结点，现要求在p前插入q，则正确的插入为______。A.p-＞prior=q;q-＞next=p;p-＞prior-＞next=q;q-＞prior=p-＞prior;B.q-＞prior=p-＞prior;p-＞prior-＞next=q;q-＞next=p;p-＞prior=q;C.q-＞next=p;p-＞next=q;p-＞prior-＞next=q;q-＞next=p;D.p-＞prior-＞next=q;q-＞next=p;q-＞prior=p-＞prior;p-＞prior=q;35.设有一个n阶的三对角线矩阵A的对角元素A[i][j]可存放于一个一维数组B中，要求行下标必须满足0≤i≤n-1，而列下标必须满足______。A.0≤j≤n-1B.i-1≤j≤i+1C.0≤j≤iD.i≤j≤n36.6知一个二叉树，用二叉链表形式存储，给出此二叉树建立过程算法(可不描述结构体)。37.以下有关图的最短路径的说法中正确的是______。A.带权有向图的最短路径一定是简单路径B.在有向图中，从一个顶点到另一个顶点的最短路径是唯一的C.求单源最短路径的Dijkstra算法不适用于有回路的带权有向图D.在用Floyd算法求解各顶点之间的最短路径时，每个表示两个顶点之间路径的path(k-1)[i][j]一定是path(k)[i][j]的子集38.随着散列表的装填因子a的增大，查找表中指定表项的平均查找长度也要增大，但如果采用______法解决冲突，可平稳控制平均查找长度的增大幅度达到最小。A.线性探测B.二次探测C.双散列D.链地址39.编写一个实现连通图G的深度优先遍历(从顶点v出发)的非递归函数，可以用伪代码描述。40.设表达式以字符形式已存入数组E[n]中，‘#’为表达式的结束符，试写出判断表达式中括号(‘(’和‘)’)是否配对的C语言描述算法：EXYX(E)；(注：算法中可调用栈操作的基本算法。)41.对于由n个顶点组成的有向完全图来说，图中共包含______条边，对于由n个顶点组成的无向完全图来说，图中共包含______条边。A.n，n(n-1)B.n，n(n-1)/2C.2n，n(n-1)D.n(n-1)，n(n-1)/242.设下三角矩阵A为：

如果按行序为主序将下三角元素aij存储在一个一维数组B[1..n(n+1)/2]中，则对任一个三角矩阵元素aij，它在一维数组B中的下标为

。A.i(i-1)/2+jB.j(j-1)/2+iC.j(j-1)/2+i-1D.i(i-1)/2+j-143.队尾已到达一维数组的最高下标，不能再插入元素，然而队中元素个数小于队列的长度，这种现象称作______。A.上溢B.下溢C.假溢出D.队列满44.假设一个循环队列Q[maxSize]的队头指针为front，队尾指针为rear，队列的最大容量为maxSize，除此之外，该队列再没有其他数据成员，则该队列的队满条件是______。A.Q.front==Q.rearB.Q.front+Q.rear＞=maxSizeC.Q.front==(Q.rear+1)%maxSizeD.Q.rear==(Q.front+1)%mexSize45.设G是一个非连通无向图，有15条边，则该图至少有______个顶点。A.5B.6C.7D.846.请简要比较顺序表和链表各自的特点。47.线性表(a1，a2，a3，…，an)中元素递增有序且按顺序存储于计算机内。要求设计算法完成以下内容：

(1)用最少的时间在表中查找数值为x的元素。

(2)若找到将其与后继元素位置相交换。

(3)若找不到将其插入表中并使表中元素仍递增有序。48.设森林中有三棵树，第一、第二和第三棵树中的结点个数分别为m1、m2和m3。那么在由该森林转化成的二叉树中根结点的右子树上的结点个数是______。A.m1+m2B.m2+m3C.m3+m1D.m1+m2+m349.假设有n(n＞1)个线性表顺序地存放在顺序表S[1，…，m]中，令F[i]和R[i]指示第i个(1≤i≤n)表的第1个元素和最后1个元素在S中的位置，并设定R[i]＜F[i+1]，F[n+1]=m+1，如图所示。试写出实现下列要求的算法。

(1)在第i个表中的第j项后面插入1个元素，仅当整个顺序表空间填满时，不允许进行插入操作。

(2)删除第i个表中的第j个元素，要求在删除第j个元素后，该表仍为顺序存储的线性表。50.改写顺序栈的结构和进栈函数Push(x)，要求当栈满时执行一个stackFull()操作进行溢出处理。其功能是：动态创建一个比原来的栈数组大一倍的新数组，代替原来的栈数组，原来栈数组中的元素占据新数组的前maxSize个位置。

原顺序栈的程序代码如下：

typedefstruct

{

intdata[maxSize];

//存放栈中元素，maxSize是已定义的常量

inttop;

//栈顶指针

}SqStack;

//顺序栈类型定义

原进栈函数程序代码如下：

intPush(SqStack&st,intx}

{

if(st.top==maxSize-1)

//栈满不能进栈

return0;

++(st.top);

//先移动指针，再进栈

st.data[st.top]=x;

return1;

}第1卷参考答案一.历年考点试题黑钻版1.参考答案：B冒泡排序每趟经过比较、交换，从无序区中产生一个最大的元素，所以选B。2.参考答案：D[解析]让k又树的每层结点个数最少，深度可达最大，这就是单支树的情形，所以该树的深度最大为n；让k叉树的每层结点个数最多，深度可达最小，这相当于平衡树，若设该树的深度为d，上层的d-1层都是满的，而第d层的结点散布在该层的各处，此时有n≤k0+k1+…+kd-1=(kd-1)/(k-1)，d≥logk(n×(k-1)+1)。3.参考答案：B此题考查的知识点是递归算法的组成部分。一个递归算法主要包括终止条件和递归部分，所以选B。A不全面，C、D不是递归算法。4.参考答案：D[解析]本题考查的是各种链表的主要特点，顺序表的主要特点是查找方便，而链表的主要特点是插入和删除元素方便。引入双向循环链表更是为了满足查找、插入、删除多方面的性能。5.参考答案：B[解析]在堆成矩阵中，通常存储其对角线及对角线下方的元素，此时，aij在压缩后的数组中的位置为i(i-1)/2+j。但在本题中，B中存储的是A的对角线及对角线上方的元素，且以列为主存储次序，因此，aij在压缩后的数组中的位置为j(j-1)/2+i。6.参考答案：地图涂色问题可以用“四染色”定理。将地图上的国家编号(1到n)，从编号1开始逐一涂色，对每个区域用1色，2色，3色，4色(下称“色数”)依次试探，若当前所取颜色与周围已涂色区域不重色，则将该区域颜色进栈；否则，用下一颜色。若1至4色均与相邻某区域重色，则需退栈回溯，修改栈顶区域的颜色。用邻接矩阵数据结构C[n][n]描叙地图上国家间的关系。n个国家用n阶方阵表示，若第i个国家与第j个国家相邻，则Cij=1，否则Cij=0。用栈s记录染色结果，栈的下标值为区域号，元素值是色数。

voidMapColor(AdjMatrixC)∥以邻接矩阵C表示的n个国家的地区涂色

{

ints[]；

∥栈的下标是国家编号，内容是色数

s[1]=1；

∥编号01的国家涂1色

i=2；j=1；∥i为国家号，j为涂色号

while(i＜=n)

{

while(j＜=4&&i＜=n)

{

k=1；

∥k指已涂色区域号

while(k＜i&&s[k]*C[i][k]!=j)

k++；

∥判断相邻区是否已涂色

if(k＜i)

j=j+1；∥用j+1色继续试探

else

{

s[i]=j；

l++：

j=1；

}

∥与相邻区不重色，涂色结果进栈，继续对下一区涂色进行试探

}

}

if(j＞4)

{

1——：

j=s[i]+1；

}//变更栈顶区域的颜色

}

}7.参考答案：B[解析]需要搜索并找到A的链尾，遍历表A的m个结点。8.参考答案：C顶点表由两个域组成，vertex域存储和该顶点相关的信息，firstedge域指示第一条依附于该顶点的边。边表结点由六个域组成：mark为标记域，用以标记该条边是否被搜索过；ivex和jvex为该边依附的两个顶点在图中的位置；ilink指向下一条依附于顶点ivex的边；jlink指向下一条依附于顶点jvex的边；info为指向和边相关的各种信息的指针域。9.参考答案：B对任何一棵二叉树，如果终端结点数为n。，度为2的结点数为n：，则一定有n0=n2+1。所以n2=n0-1=9。10.参考答案：B此题考查的知识点是入栈的具体操作。判断栈是否满要看两个栈顶是否相邻，当top[1]+1=top[2]或top[2]-1=top[1]时都表示栈满，所以选B，而A，C没有任何意义。D表示已经出现覆盖了，也是错的。11.参考答案：D解析见6。12.参考答案：A[解析]所有待排序的数据记录的排序码都相等，可按照数据初始排列已经有序的情况来分析。按照本教材所给算法：

直接插入排序的排序码比较次数和元素移动次数受数据的初始排列影响，每趟只比较1次，做n-1趟，排序码比较次数总共为n-l，元素移动次数为0。

起泡排序的排序码比较次数和元素移动次数也受数据的初始排列影响，只比较一趟，排序码比较次数为n-1，元素移动次数为0。

简单选择排序的排序码比较次数不受数据的初始排列影响，比较n-1趟，排序码比较次数为n(n-1)/2；但元素移动次数受数据的初始排列影响，当待排序记录排序码都相等时，元素移动次数为0。

对于堆排序，在形成初始堆时，总共有次排序码比较，次数据移动；在堆排序时，做n-1次对调和重新形成堆，每次对调做3次数据移动，最多做(n-1)×2次排序码比较，(n-1)×(3+2)次数据移动。综上所述，堆排序的排序码比较次数最多为，元素移动次数最多是。13.参考答案：D深度优先遍历的思想类似于树的先序遍历。其遍历过程可以描述为：从图中某个顶点v出发，访问该顶点，然后依次从v的未被访问的邻接点出发继续深度优先遍历图中的其余顶点，直至图中所有与v有路径相通的顶点都被访问完为止。14.参考答案：A[解析]将森林F转化为二叉树表示B，则B的根是第一棵树的根，根的左子树是第一棵树的根的子树森林，根的右子树是森林中除去第一棵树外其他树构成的森林。根据题意，B的根是p，p的右子树中的结点个数为n，则森林F的第一棵树中结点个数为m-n。15.参考答案：B[解析]根据m阶B树的定义，树中每个结点最多有m棵子树，有m-1个关键字，若插入新关键字后该结点的关键字数超过了m-1，则需要进行分裂。16.参考答案：voidDelete(BSTreet,p){

//在二叉排序树t中，删除f所指结点的右孩子(由p所指向)

if(p-＞lchild==null){f-＞rchild=p-＞rchild;free(p);}

//p无左子女

else{

//用p左子树中的最大值代替p结点的值

q=p-＞lchild;s=q;

while(q-＞rchild){s=q;q=q-＞rchild;}

//查P左子树中序序列最右结点

if(s==p-＞lchild)

//p左子树的根结点无右子女

{p-＞data=s-＞data;p-＞lchild=s-＞lchild;free(s);}

else{p-＞data=q-＞data;s-＞rchild=q-＞lchild;free(q);}

}

}17.参考答案：线性表每一个表元素的数据空间要求相同，但如果对每一个元素的数据类型要求不同时可以用等价类型(union)变量来定义可能的数据元素的类型。如

Typedefunion{

//联合

intintegerInfo;

//整型

charcharInfo;

//字符型

floatfloatInfo;

//浮点型

}info;

利用等价类型，可以在同一空间(空间大小相同)indo中存放不同数据类型的元素。但要求用什么数据类型的变量存，就必须以同样的数据类型来取。18.参考答案：本算法不需要将整个记录排序，只进行查找第j个记录(从小到大排序)。

程序代码如下：

voidsplit(intA[],intlow,inthigh,int&i)

{

intj;

elemtypex;

i=low;j=high;x=A[i];

//初始化

while(i＜j)

{

while(A[j]＞=x&&i＜j)

//从右向左遍历

--j;

if(i＜j)

{

A[i]=A[j];++i;

//相当于交换A[i]与A[j]

}

while(A[i]＜=x&&i＜j)

//从左向右遍历

++i;

if(i＜j)

{

A[j]=A[i];--j;

//相当于交换A[i]与A[j]

}

}

A[i]=x;

//x定位在位置i处

}

sort(intA[],intj,intn)

{

ints=0,t=n-1,k;

split(A,s,t,k);

while(k!=j)

if(k＜j)

split(A,k+1,t,k);

//元素在右边，对右边进行划分

else

split(A,s,k-1,k);

//元素在左边，对左边进行划分

returnA[j];

}19.参考答案：根据中序线索二叉树的定义得到求第一个结点(first())、下一个结点(next())、最后一个结点(last())和前一个结点(prior())的函数，再设计中序正向遍历二叉树(forward())和中序反向遍历二叉树(back())的函数。

实现本题功能的程序代码如下：

BTNode*first(BTNode*root)

//返回root为根的中序线索树中的第一个结点

{

while(root→ltag==0)

root=root→left;

returnroot;

}

BTNode*last(BTNode*root)

//返回root为根的中序线索树中的最后一个结点

{

BTNode*p=root→right;

returnpi

}

BTNode*next(BTNode*root,BTNode*q)

//返回q结点的后继结点

{

BTNode*p=q→right,*n;

if(q→rtag==0)

//有右孩子时

while(p→ltag==0)

p=p→left;

n=p;

if(n==root)

//若q为最后一个结点，则返回NULL，否则返回n

returnNULL;

else

returnn;

}

BTNode*prior(BTNode*root,BTNode*q)

//返回q的前驱结点

{

BTNode*p=q→left,*n;

if(q→ltag==0)

while(p→rtag==0)

p=p→right;

n=p;

if(n==root)

//若q为第一个结点，则返回NULL，否则返回n

returnNULL;

else

returnn;

}

voidforward(BTNode*root)

//中序正向遍历二叉树

{

BTNode*p;

for(p=first(root);p!=NULL;p=next(root,p))

visit(p);

//访问p,visit是已经定义的访问函数

}

voidback(BTNode*root)

//中序反向遍历二叉树

{

BTNode*p;

p=last(root);

for(p=last(root);p!=NULL;p=prior(root,p))

visit(p);

//访问p,visit是已经定义的访问函数

}20.参考答案：本题属于条件深度(广度)优先搜索问题，即在通常的搜索算法中加入一定的条件，过滤掉不满足条件的搜索结果。cond函数即为判断题目给出的条件是否满足的函数。程序代码如下：

intvisited[Vnum],A[Vnum];

intcond(intA[],intd,intv1,intv6,intv4)

//判断条件

{

intflag1=0,flag2=0,flag3=1,i;

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

//判断路径中是否有“食品”

if(A[i]==v1)

{

flag1=1;

break;

}

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

//判断路径中是否有“财宝”

if(A[i]==v6)

{

flag2=1;

break;

}

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

//判断路径中是否没有“强盗”

if(A[i]==v4)

{

flag3=0;

break;

}

returnflag1&&flag2&&flag3;

//返回正确条件

}

voiddfs1(graph*g,intvi,intvj,intv1,intv6,intv4,intd)

{

intv,i;

arcnode*p;

visited[vi]=1;

++d;

//d指明DFS所经过的顶点数目

A[d]=vi;

if(vi==vj&&cond(A,d,v1,v6,v4)==1)

{

//按照条件输出路径

cout＜＜"一条路径:";

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

cout＜＜A[i]＜＜"";

}

p=g→adjlist[vi].firstarc;

//找vi的第一个邻接顶点

while(p!=NULL)

{

v=p→adjvex;

//v为vi的邻接顶点

if(visited[v]==0)

//若该顶点未标记访问，则递归访问

dfs1(g,v,vj,v1,v6,v4,d);

p=p→nextarc;

//找vi的下一个邻接顶点

}

visited[v!]=0;

//取消访问标记，以使该顶点可重新使用

--d;

}21.参考答案：D[解析]按照所有中国人的生日(月、日)排序，一方面是n很大，另一方面d不大(d=2，两个排序码)且一个排序码的基数为12(月)，另一排序码的基数为31(日)，都不大，可采用多排序码，即基数排序。其时间复杂度可达O(n)。22.参考答案：B本题考查哈夫曼树的性质。哈夫曼树中只有度为2和度为0的结点，哈夫曼编码是对哈夫曼树中的叶子结点编码。根据树的性质N0=N2+1，故N0=(N2+N0+1)/2=(99+1)/2=50，哈夫曼树共有50个叶子结点，所以共能得到50个不同的码字。23.参考答案：B由中序遍历过程可知本题答案应为B。24.参考答案：A=(a1，a2，…，an)，有n+1个位置可插入元素，即a1之前，a1与a2之间，…，an-1与an之间和an之后，分别需要移动的元素个数为n，n-1，…，1，0，则平均插入一个元素需要移动的元素个数为

若元素插入在ai与ai+1之间(1≤i≤n-1)的概率为，其中移动的元素个数为

则平均每插入一个元素所要移动的元素个数为

25.参考答案：[证明]假设二叉树中度为1的结点个数为n。，结点总数为n。因为二叉树中任何结点的度最大不超过2，因此有：

n=n0+n1+n2

—————(1)

从另一个角度看，我们来研究二叉树的分支数。对所有结点来说，除了根结点，任何其余结点都有一个分支进入(指向)。不妨设B(Branch)为二叉树的分支数，则有：

B=n-1(分支数比结点数少1)

—————(2)

而分支是由度为1的结点和度为2的结点贡献的：每个度为1的结点贡献1个分支，每个度为2的结点贡献2个分支。则有：

B=n1×1+n2×2=n1+2n2。

—————(3)

由(2)、(3)得

n=n1+2n2+1

—————(4)

由(1)、(4)得

n0=n2+1

由此得出结论：二叉树叶子结点个数总是比度为2的结点个数多1。26.参考答案：

27.参考答案：C[解析]用Dijkstra算法求从带权有向图的某个源顶点到其他各个顶点的最短路径，执行n-1次或n-2次选择，每次选择一个顶点后还要计算绕过这个新选出的顶点是否能够缩短从源顶点到其他未选择最短路径的顶点的路径长度，有两层嵌套for循环，所以算法的时间复杂度为O(n2)。28.参考答案：A[解析]根据图的广度优先遍历算法可知，遍历过程中每个顶点最多进队1次。29.参考答案：B[解析]对于有向强连通图，当n等于1时，边为0，否则至少需要n条边才能形成强连通图。此时所有n个顶点都在某一个有向环上，如下图所示。在此情况下，当有向边的条数少于n时，不能构成环，不再是强连通图。

30.参考答案：B[解析]为了解释这个问题，这里规定对于任意一棵二叉树，标记访问根结点为V，标记遍历根的左子树为L，标记遍历根的右子树为R，由此可得前序遍历顺序为VLR，中序遍历顺序为LVR，后序遍历顺序为LRV，可以看出，对于3种遍历方式，遍历指针在二叉树中走过的左、右子树的次序都相同，都是先左后右，由此可知所有叶结点在遍历时访问的先后次序都相同。就是说，它们在各种遍历算法结果序列中的相对次序都相同。31.参考答案：能存储多少索引项，主要看叶结点。非叶结点是对下层最多关键字的复写。

对于高度为1的B+树：根据B+树定义，根结点又是叶结点，最多可存储m=100个索引项，最少可存放1个索引项。

对于高度为2的B+树：最多可存储m×m=1002个索引项，最少可存储101个索引项。因为当根结点关键字个数n达到101，发生结点分裂，其高度才会变为2。

对于高度为3的B+树：最多可存储m×m×m=1003个索引项，最少可存储2×101=202个索引项。因为当第1层的关键字个数达到101做结点分裂，叶结点才会落到第2层，第2层2个结点，每个结点的关键字个数达到101引发结点分裂，叶结点落到第3层。此时，叶结点有51+50+51+50=202个索引项。

对于高度为4的B+树：第4层是叶结点。最多可存储m4=1004个索引项，最少可存储4×101=404个索引项。叶结点有51+50+51+50+51+50+51+50=404个索引项。32.参考答案：A[解析]本题可以根据插入元素的位置列出一个移动元素个数序列，在末尾插入时，移动元素为0；在第n位插入时，移动元素为n-1；…；在起始位置插入时，移动元素为n。由于等概率插入，在每个位置上插入新元素的概率均为1/(n+1)。因此，平均移动元素为(0+1+2+…+n)/(n+1)=n/2。33.参考答案：C34.参考答案：A此题考查的知识点是双向链表的插入操作。在p前插入，要修改p的prior指针、p的prior所指结点的next指针，所以选A。B、C、D都将使地址丢失，连接失败。35.参考答案：B[解析]三对角线矩阵属于带状矩阵，如图所示。带状矩阵下标范围可以表示为i-1≤j≤i+1，因此本题选B。

36.参考答案：二叉树是递归定义的，以递归方式建立最简单。二叉树建立过程如下：

BiTreeCreat(){

//建立二叉树的二叉链表形式的存储结构

ElemTypex;

BiTreebt;

scanf("%d",&x);

//本题假定结点数据域为整型

if(x==0)bt=null;

elseif(x＞0){

bt=(BiNode*)malloc(sizeof(BiNode));

bt-＞data=x;

bt-＞lchild=Creat();

bt-＞rchild=Creat();

}

elseerror("输入错误");

return(bt);

}//结束BiTree37.参考答案：A[解析]简单路径是没有重复顶点的路径。图的最短路径采用贪心法求解，在求从vi到vj的最短路径时，可以绕过那些已经求得最短路径的顶点，缩短从vi到vj的最短路径。有可能最短路径经过许多顶点，但绝不会绕过，所以图的最短路径应是简单路径。其他选项都是错误的。在有向图中从一个顶点到另一个顶点的最短路径不是唯一的，但最短路径长度应是唯一的。Dijkstra算法仅要求边上的权值不能为负值，并未排除有回路的带权有向图，不过它的结果应是简单路径。另外，path(k-1)[i][j]是从顶点vi绕过顶点v0，v1，…，vk-1到达vj的最短路径，path(k)[i][j]是从顶点vi绕过顶点v0，v1，…，vk到达vj的最短路径，路径可能会改变，不是子集。38.参考答案：D[解析]线性探测、二次探测和双散列都属于解决冲突的开地址法，寻找下一个空位的操作仅限于散列表本身的基本存储空间，随着表的装满程度的增加，冲突越来越多，查找某一表项的平均查找次数也越来越多，以线性探测最甚。而链地址法设置溢出存储空间，装填因子a的增大，仅表明基本存储空间装得越来越满，但大多数发生冲突的表项都存放到溢出空间去了，在基本存储空间的冲突没有大幅增加，平均查找次数也不会大幅增长。39.参考答案：本题的算法如下：

将所有顶点置为“未访问”标志；

输出起始顶点v0；

置v0为“已访问”标志；

将v0入栈；

while(栈不空时)

{

取栈顶v；

if(v存在未被访问的邻接顶点，则选择一个顶点v1)

{

输出v1；

置v1为“已访问”标志；

将v1入栈；

}

else当前顶点退栈；

}

c语言代码如下：

voiddfs1(graphg,intv)

{

inti;

arcnode*p;

intvisited[Vnum],top=-1,stack[Vnum];

for(i=0;i＜g.vexnum;i++)

visited[i]=0;

//结点访问标志均置为0

visit(v);

//访问顶点v

top++;

//v入栈

stack[top]=v;

visited[v]=1;

while(top＞=0)

//栈不空时循环

{

v=stack[top];--top;

//取栈顶顶点

p=g.adjlist[v].firstarc;

while(p!=NULL&&visited[p→adjvex]==1)

p=p→nextarc;

if(p==NULL)

//若没有，退到前一个

--top;

else

//若有，选择一个

{

v=p→adjvex;

visit(v);

//访问顶点

visited[v]=1;

top++;

//入栈

stack[top]=v;

}

}

}40.参考答案：判断表达式中括号是否匹配，可通过栈，简单说是左括号时进栈．右括号时退栈。退栈时，若栈顶元素是左括号，则新读入的右括号与栈顶左括号就可消去。如此下去，输入表达式结束时，栈为空则正确，否则括号不匹配

intEXYX(charE[]，intn)

//E[]是有n字符的字符数组，存放字符串表达式，以‘#’结束。本算法判断表达式中圆括号是否匹配

{charsE30]；

∥s是一维数组，容量足够大，用作存放括号的栈

inttop=0；

∥top用作栈顶指针

SEtop]=‘#’；

∥‘#’先入栈，用于和表达式结束符号‘#’匹配

inti=0；

∥字符数组E的工作指针

while(E[l]!=‘#’)

∥逐字符处理字符表达式的数组

switch(E[i])

{caSe‘(’：s[++top]=‘(’；i++；break；

case‘)’：if(s[top]==‘(’{top——；i++；break；)

else{printf(“括号不配对”)；exit(0)；}

case‘#’：if(sEtop]==‘#’){printf(“括号配对＼n”)；return(1)；}

else{printf(“括号不配对\n”)；return(0)；)∥括号不配对

default：i++；

∥读入其他字符，不作处理

}

}

本题是用栈判断括号匹配的特例：只检查圆括号的配对。一般情况下是检查花括号(‘{’，‘}’)、方括号(‘[’，‘]’)和圆括号(‘(’，‘)’)的配对问题。编写算法中如遇左括号(‘{’，‘[’，或‘(’)就压入栈中，如遇右括号(‘)’，‘]’，或‘)’)，则与栈顶元素比较，如是与其配对的括号(左花括号、左方括号或左圆括号)，则弹出栈顶元素；否则，就结论括号不配对。在读入表达式结束符‘#’时，栈中若只剩‘#’，表示括号全部配对成功；否则表示括号不匹配。

另外，由于本题只是检查括号是否匹配，故对从表达式中读入的不是括号的那些字符，一律未作处理。再有，假设栈容量足够大，因此入栈时未判断溢出。41.参考答案：D由完全图的定义可知本题答案为D。42.参考答案：A如何将aij保存在数组B中，保存在哪个位置?也就是说，设k为aij保存在B中时的下标，那么k和i、j有什么关系?

A[i，j]在B中的位置=(A中前i-1行非0元素的个数)

+(A中第i行、第j列之前非0元素的个数，包括第j列)

=(1+2+3+…+(i-1))+j

=i(i-1)/2+j

则A[i，j]存放在B中的元素下标k—i(i一1)/2+j(因为B的数据元素从1开始)。

例如：A[3，3]保存在B中的位置为

k=3×(3=1)/2+3=6，即A[3，3]保存在数据元素B[6]中。43.参考答案：C用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质(队尾插入和队头删除)，容易造成“假溢出”现象，即队尾已到达一维数组的高下标，不能再插入，然而队中元素个数却小于队列的长度(容量)。44.参考答案：C[解析]既然不能附加任何其他数据成员，只能采用牺牲一个队列元素的整除区域的方式来区分队空和队满的条件。因此，选项C是合适的。选项A是判断队列是否空的条件，选项B和选项D都是干扰项。45.参考答案：C[解析]本题根据连通图的性质以及顶点与边数的关系即可求解：设无向图有n个顶点，它的边数e≤n(n-1)/2。若e=15，有15≤n(n-1)/2，解得n>≥6。在连通图情形下至少需有6个顶点，在非连通图情形下则至少需有7个顶点。46.参考答案：(1)基于空间的比较。

1)存储分配的方式：

顺序表的存储空间是静态分配的。

链表的存储空间是动态分配的。

2)存储密度(存储密度=结点值域所占的存储量/结点结构所占的存储总量)：

顺序表的存储密度=1。

链表的存储密度＜1(因为结点中有指针域)。

(2)基于时间的比较。

1)存取方式：

顺序表可以随机存取，也可以顺序存取(对于顺序表一般只答随机存取即可)

链表是顺序存取的。

2)插入/删除时移动元素的个数：

顺序表平均需要移动近一半元素。

链表不需要移动元素，只需要修改指针。47.参考答案：(1)顺序存储的线性表递增有序，可以顺序查找，也可折半查找。题目要求“用最少的时间在表中查找数值为x的元素”，这里应使用折半查找方法。

voidSearchExchangelnsert(ElemTypea[];ElemTypex)

//a是具有n个元素的递增有序线性表，顺序存储。本算法在表中查找数值为x的

//元素，如查到则与其后继交换位置；如查不到，则插入表中，且使表仍递增有序

{

low=0;

high=n-1;

//low和high指向线性表下界和上界的下标

while(low＜=high)

{

mid=(low+high)/2;

//找中间位置

if(a[mid]==x)break;

//找到x，退出while循环

elseif(a[mid]＜x)low=mid+1;

//到中点mid的右半去查

elsehigh=mid-1;

//到中点mid的左半去查

}

if(a[mid]==x&&mid!=n)

//若最后一个元素与x相等，则不存在与其后继交换的操作

{

t=a[mid];

a[mid]=a[mid+1];

a[mid+1]=t;

}

//数值x与其后继元素位置交换

if(low＞high)

//查找失败，插入数据元素x

{

for(i=n-1;i＞high;i--)