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

2023年研究生类研究生入学考试专业课计算机学科专业综合基础-数据结构历年高频考题带答案难题附详解（图片大小可自由调整）第1卷一.历年考点试题黑钻版(共25题)1.以下算法是在一个有n个数据元素的数组A中删除第i个位置的数组元素，要求当删除成功时数组元素个数减1，求平均删除一个数组元素需要移动的元素个数是多少?其中，数组下标从0至n-1。

intdelete(intA[],intn,inti)

{

intj;

if(i＜0||i＞n)

return0;

for(j=i+1;j＜n;++j)

A[j-1]=A[j];

--n;

return1;

}2.栈和队列的主要区别在于______。A.它们的逻辑结构不一样B.它们的存储结构不一样C.所包含的运算不一样D.插入和删除运算的限定不一样3.以下有关平衡二叉树的说法中正确的是______。A.平衡二叉树是高度最小的二叉排序树B.平衡二叉树一定是丰满树C.平衡二叉树上任一结点的平衡因子不能超过1D.有n个结点的平衡二叉树的高度为O(log2n)4.编写一个算法，将m(m≥2)个有序(从小到大)顺序表合并成一个有序顺序表，合并过程中不另设新的顺序表存储。5.下面函数的功能是实现分块查找，空白处应该添加的内容是______。

intBlkSearch(int*nz,intkey,intblock,intBLK,intlen)

{

inti;

block=block-1;

if(len＜=0)

{

puts("表为空!");

return0;

}

if(BLK＞len)BLK=len;

for(i=block*BLK;i＜(block+1)*BLK&&nz[i]!=0;i++)

{

if(______)

{

printf("找到第%d个数是%d\n",i,key);

return0;

}

}

printf("\n");

printf("查找结束\n");

return0;

}A.nz[i]==keyB.nz[i]==BLKC.nz[1i]==blockD.nz[i]==06.对一个图进行遍历可以得到不同的遍历序列，那么导致得到的遍历序列不唯一的因素有哪些?7.设线性表中有2n个元素，以下操作中，在单链表上实现要比在顺序表上实现效率更高的是______。A.删除指定元素B.在最后一个元素的后面插入一个新元素C.顺序输出前k个元素D.交换第i个元素和第2n-i-1个元素的值(i=0，1，…，n-1)8.就平均性能而言，目前最好的排序算法是______。A.选择排序B.快速排序C.冒泡排序D.插入排序9.二叉排序树采用二叉链表存储。写一个算法，删除结点值是X的结点。要求删除该结点后，此树仍然是一棵二叉排序树，并且高度没有增长(注意：可不考虑被删除的结点是根的情况)。10.设图有n个顶点和e条边，在采用邻接矩阵时，遍历图的顶点所需时间为______；在采用邻接表时，遍历图的顶点所需时间为O(n+e)。A.O(n)B.O(n2)C.O(e)D.O(n×e)11.根据一个结点数据类型为整型的单链表生成两个单链表，第一个单链表中包含原单链表中所有数据值为奇数的结点，第二个单链表中包含原单链表中所有数据值为偶数的结点，原有单链表保持不变。12.使用散列函数：

H(k)=3kmod11

并采用开放地址法处理冲突，所求下一地址函数为

d1=H(k)

di=(di-1+((7kmod10)+1)%11(i=2，3，…)

试在0～10的散列地址空间中对关键字序列(22，41，53，46，30，13，01，67)构造哈希表，求等概率情况下查找成功的平均查找长度，并设计构造哈希表的完整的算法。13.栈在______中应用。A.递归调用B.子程序调用C.表达式求值D.以上都是14.设某棵三叉树中有40个结点，则该三叉树的最小高度为

。A.3B.4C.5D.615.败者树的外结点存放的是各归并段当前参加归并的记录，如下图所示，外结点的编号0，1，2，…，m-1代表各归并段的编号，败者树的内结点存放子女结点两两比较的败者的归并段编号，内结点编号也是0，1，…，m-1。编号为i的外结点的父结点的编号为______。

A．

B．

C．

D．16.关于B-树，下列说法不正确的是______。A.B-树是一种查找树B.所有的叶结点具有相同的高度C.2-3树中，所有非叶子结点有1或者3个孩子结点D.通常情况下，B-树不是二叉树17.已有邻接表表示的有向图，请编程判断从第u顶点至第v顶点是否有简单路径，若有则打印出该路径上的顶点。18.设计一个算法指出一个无序数序中的任意一个元素是第几大元素(从小到大数)，要求比较的次数最少。19.用n个权值构造出来的Huffman树的结点个数是______。A.2n-1B.2nC.2n+1D.n+120.采用顺序结构存储串，编写一个函数index(s1，s2)，用于判定s2是否是s1的子串。若是子串，返回其在主串中的位置；否则返回-1。21.将下图中的二叉树按中序线索化，结点e的右指针和结点g的左指针分别指向______。

A.a，dB.b，cC.d，aD.c，a22.已知一个栈的进栈序列为1，2，3，…，n，其输出序列是p1，p2，p3，…，pn。若p1=3，则p2的值______。A.一定是2B.一定是1C.可能是1D.可能是223.执行完下列语句段后，i值为______。

intf(intx){return((x＞0)?x*f(x-1);2);}

i=f(f(1));A.2B.4C.8D.无限递归24.在下列有关关键路径的说法中错误的是______。A.在AOE网络中可能存在多条关键路径B.关键活动不按期完成就会影响整个工程的完成时间C.任何一个关键活动提前完成，那么整个工程将会提前完成D.所有的关键活动都提前完成，那么整个工程将会提前完成25.自由树(即无环连通图)T=(V，E)的直径是树中所有点对点之间最短路径长度的最大值，即T的直径定义为d(u，v)的最大值(其中u，v∈V)。这里d(u，v)表示顶点u到顶点v的最短路径长度(路径长度为路径中包含的边数)。如图所示为一棵自由树，其直径为18。试写算法求T的直径，并分析算法的时间复杂度。

第1卷参考答案一.历年考点试题黑钻版1.参考答案：当删除最后一个元素时，移动的元素个数为0；当删除倒数第二个元素时，移动的元素个数为1；…；当删除第一个元素时，移动的元素个数为n-1。也就是说，当删除第i个元素时，移动的元素个数为n-i，设P为删除第i个位置上数据元素的概率，则有Pi=1/n，平均删除一个数组元素需要移动的元素个数是

2.参考答案：D栈和队列的逻辑结构都是线性的，都有顺序存储和链式存储，有可能包含的运算不一样，但不是其主要区别。任何数据结构在针对具体问题时所包含的运算都可能不同。所以正确答案是D。3.参考答案：D[解析]有n个结点的平衡二叉树的最小高度hmin=rlog2(n+1)l，最大高度hmax＜1.44×log2(n+1)，因此选项D是正确的。由于平衡二叉树的中低层有可能没有填满，存在度为1的结点，只要每个结点的两棵子树的高度差的绝对值不超过1即可，所以其高度有可能不是最小，因此选项A不对。丰满树即理想平衡树，要求除最底层外其他层都是满的，平衡二叉树没有这样高的要求，因此选项B不对。对于C选项，应该是平衡二叉树上任一结点的平衡因子的绝对值不能超过1。4.参考答案：将线性表A和B合并的过程如下：从A的最后一个元素和B的第一个元素开始分别向前、向后进行比较，将较大的元素先定位在A中。

代码如下：

intComb1(intA[],intna,intB[],intnb)

{

intn=na,m=0;

while(m＜nb)

if(n==0||A[n-1]＜B[m])

{

A[n+nb-m-1]=B[m];

//说明B[m]是第n+nb-m大的元素

++m;

}

else

{

A[n+nb-m-1]=A[n-1];

//说明A[n-1]是第n+nb-m大的元素

--n;

}

returnna+nb;

}5.参考答案：A如果当前的值与所查找关键字相等，则完成查找。6.参考答案：此题考查的知识点是图的遍历。遍历不唯一的因素有：开始遍历的顶点不同；存储结构不同；在邻接表情况下邻接点的顺序不同。7.参考答案：A对于A，删除指定元素，在顺序表中需要移动较多元素，而在单链表上执行同样的操作不需要移动元素，因此单链表的效率要高一些。

对于B，在最后一个元素的后面插入一个新元素不需要移动元素，顺序表的效率和单链表相同。

对于C，顺序输出前k个元素，单链表和顺序表的效率几乎相同。

对于D，交换第i个元素和第2n-i-1个元素的值(i=0，1，…，n-1)，由于顺序表可以实现随机查找，因此顺序表的效率会更高一些。8.参考答案：B[解析]目前，平均性能最好的排序是快速排序。9.参考答案：在二叉排序树上删除结点，首先要查找该结点。查找成功后，若该结点无左子树，则可直接将其右子树的根结点接到其双亲结点上；若该结点有左子树，则将其左子树中按中序遍历的最后一个结点代替该结点，从而不增加树的高度。

voidDelete(BSTreebst,keytypeX){

//在二叉排序树bst上，删除其关键字为X的结点

BSTreef,p=bst;

while(p&&p-＞key!=X)

//查找值为X的结点

if(p-＞key＞X){f=p;p=p-＞lchild;}

else{f=p;p=p-＞rchild;}

if(p==null){printf("无关键字为X的结点\n");exit(0);}

if(p-＞lchild==null){

//被删结点无左子树

if(f-＞lchild==p)f-＞lchild=p-＞rchild;

//将被删结点的右子树接到其双亲上

elsef-＞rchild=p-＞rchild;

}

else{q=p;s=p-＞lchild;

//被删结点有左子树

while(s-＞rchild!=null)

//查左子树中最右下的结点(中序最后结点)

{q=s;s=s-＞rchild;}

p-＞key=s-＞key;

//结点值用其左子树最右下的结点的值代替

if(q==p)p-＞lchild=s-＞lchild;

//被删结点左子树的根结点无右子女

elseq-＞rchild=s-＞lchild;

//s是被删结点左子树中序序列最后一个结点

free(s);

}

}10.参考答案：B[解析]存储结构为邻接矩阵的图的遍历算法要对所有顶点都访问一次，每次访问时为确定下一次要访问哪个顶点，需遍历该顶点的行向量，寻找该顶点的所有邻接顶点，所以遍历的时间复杂度为O(n2)。而对于存储结构为邻接表的图的遍历算法也要对所有顶点访问一次，每次访问时为确定下一次要访问哪个顶点，需遍历该顶点的边链表，所以时间复杂度为O(n+e)。11.参考答案：voidSeparate(LNode*&HL,LNode*&L1,LNode*&L2)

{

//将一个单链表HL按各个结点中数据的奇偶性拆分成两个单链表L1和L2

LNode*r1,*r2,*p,*s;

r1=L1=(LNode*)malloc(sizeof(LNode));

r2=L2=(LNode*)malloc(sizeof(LNode));

p=HL→next;

//链表HL的扫描指针

while(p!=NULL)

//对原链表的结点逐个进行检测

{

s=(LNode*)malloc(sizeof(LNode));

//创建新结点

s→data=p→data;

if(p→data%2==1)

//奇数

{

r1→next=s;

r1=s;

}

else

//偶数

{

r2→next=s;

r2=s;

}

p=p→next;

}

r1→next=NULL;r2→next=NULL;

}12.参考答案：本题的哈希表构造过程如下：

(1)H(22)=3*22mod11=0比较1次

(2)H(41)=3*41mod11=2比较1次

(3)H(53)=3*53mod11=5比较1次

(4)H(46)=3*46mod11=6比较1次

(5)H(30)=3*30mod11=2冲突

d1=H(30)=2

H(30)=(2+(7*30mod10)+1)mod11=3比较2次

(6)H(13)=3*13mod11=6冲突

d1=H(13)=6

H(13)=(6+(7*13mod10)+1)mod11=8比较2次

(7)H(1)=3*01mod11=3冲突

d1=H(1)=3

H(1)=(3+(1*7mod10)+1)mod11=0冲突

d2=H(1)=0

H(1)=(0+(1*7mod10)+1)mod11=8冲突

d3=H(1)=8

H(1)=(8+(1*7mod10)+1)mod11=5冲突

d4=H(1)=5

H(1)=(5+(1*7mod10)+1)mod11=2冲突

d5=H(1)=2

H(1)=(2+(1*7mod10)+1)mod11=10比较6次

(8)H(67)=3*67mod11=3冲突

d1=H(67)=3

H(67)=(3+(7*67mod10)+1)mod11=2冲突

d2=H(67)=2

H(67)=(2+(7*67mod10)+1)mod11=1比较3次

构造本哈希表的程序代码如下：

structhterm

{

intkey;

//关键字值

intsi;

//散列次数

};

structhtermhlist[M];

//假设M=11是已定义的常量

inti,adr,sum,d;

intx[N]={22,41,53,46,30,13,1,67};

//关键字赋值

//假设N=8是已定义的常量

floataverage;

voidchash()

//创建哈希表

{

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

//置初值

{

hlist[i].key=0;

hlist[i].si=0;

}

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

{

sum=0;

adr=(3*x[i])%M;

d=adr;

if(hlist[adr].key==0)

{

hlist[adr].key=x[i];

hlist[adr].si=1;

}

else

{

do

//处理冲突

{

d=(d+(x[i]*7)%10+1)%M;

sum=sum+1;

}while(hlist[d].key!=0);

hlist[d].key=x[i];

hlist[d].si=sum+1;

}

}

}13.参考答案：D[解析]栈的基本应用有数制转换(十转N)，括号匹配的检验，表达式求值，汉诺仪(Hanoi)塔；队列的基本应用是模拟事件发生的顺序。14.参考答案：C由完全二叉树原理可以知道，完全三叉树如有n个叶结点，则高度为

log3n+1。15.参考答案：C[解析]编号为i的外结点的父结点的编号为t=[(i+m)/2]。如下图中外结点0的父结点为编号[(0+5)/2]=2的内结点，外结点4的父结点为[(4+5)/2]=4编号的内结点。

16.参考答案：C[解析]B-树定义如下：

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

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

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

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

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

K(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为子树的棵数。17.参考答案：

voidAllpath(AdjListg,vertypeu,vertypev){

//求有向图g中顶点u到顶点v的所有简单路径，初始调用形式

inttop=0,s[];

s[++top]=u;visited[u]=1;

while(top＞0||p){

p=g[s[top]].firstarc;

//第一个邻接点

while(p!=null&&visited[p-＞adjvex]==1)p=p-＞next;

//下一个访问邻接点表

if(p==null)top--;

//退栈

else{

i=p-＞adjvex;

//取邻接点(编号)

if(i==v){

//找到从u到v的一条简单路径，输出

for(k=1;k＜=top;k++)printf("%3d",s[k]);

printf("%3d\n",v);

}//if

else{visited[i]=1;s[++top]=i;}

//else深度优先遍历

}//else

}//while

}18.参考答案：对于给定的数k，将所有小于它的元素排到其前面，所有大于它的元素排到其后面，该数的位置即为有序中的序号(从0开始数)，这样最大的比较次数为n-1次。

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

intdatai(intr[],intn,intk)

{

inti=0,j=n-1;

inttemp;

while(i＜=j)

{

while(i＜n&&r[i]＜=k)

++i;

while(j＞=0&&r[j]＞k)

--j;

if(i＜j)

{

temp=r[i];r[i]=r[j];r[j]=temp;

++i;

--j;

}

}

returnj;

}19.参考答案：A[解析]用n个权值构造出来的Huffman树共有2n-1个结点，其中叶结点n个，度为2的非叶结点n-1个。20.参考答案：本题的算法思想是，设

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;

}21.参考答案：D[解析]进行中序线索化后得到下图所示的结果。在这棵线索二叉树中结点e的右指针是中序后继线索，它指向结点c；结点g的左指针是中序前驱线索，它指向结点a。

22.参考答案：D[解析]元素3第一个出栈时，元素1，2一定在栈内，下一个出栈的元素是2，不可能是1。当然还可以是元素2暂时不出栈，元素4，5，…进栈。23.参考答案：B此题考查的知识点是递归算法的分析。根据题意可计算f(0)=2，f(1)=2，f(2)=4，所以选B。24.参考答案：C[解析]在AOE网络中可能存在多条关键路径，因此，任何一个关键活动提前完成，只影响到其中某一条关键路径，整个工程不一定能提前完成。但如果AOE网络中存在“桥”，即所有关键路径都要通过的关键活动，它提前完成，整个工程可以提前。25.参考答案：利用深度优先遍历求出一个根结点v到每个叶子结点的距离，这是由diameter(v)函数实现的。该函数的时间复杂度为O(n+e)，n为顶点个数，e为边数。然后，以每个顶点作为根结点调用diameter()函数，其中最大值即为T的直径，本算法的时间复杂度为O(n(n+e))。

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

voiddfs(intparent,intchild,int&len)

//函数执行结束后，len中存放从根结点到child结点所在子树的叶子结点的最大距离

//cost是带权邻接矩阵，visited是已经初始化的访问标记数组

//N是已定义的常量，即顶点个数

{

intclen,v=0,maxlen;

clen=len;

maxlen=len;

while(v＜N&&cost[child][v]==0)

//找与child相邻的第一个顶点v

v++;

while(v＜N)

//存在邻接顶点时循环

{

if(v!=parent)

{