![2023年研究生类研究生入学考试专业课计算机学科专业综合基础-数据结构历年高频考题带答案难题附详解_第1页](http://file4.renrendoc.com/view/f01807322bf97b21b9ce6e9e490e2c35/f01807322bf97b21b9ce6e9e490e2c351.gif)
![2023年研究生类研究生入学考试专业课计算机学科专业综合基础-数据结构历年高频考题带答案难题附详解_第2页](http://file4.renrendoc.com/view/f01807322bf97b21b9ce6e9e490e2c35/f01807322bf97b21b9ce6e9e490e2c352.gif)
![2023年研究生类研究生入学考试专业课计算机学科专业综合基础-数据结构历年高频考题带答案难题附详解_第3页](http://file4.renrendoc.com/view/f01807322bf97b21b9ce6e9e490e2c35/f01807322bf97b21b9ce6e9e490e2c353.gif)
![2023年研究生类研究生入学考试专业课计算机学科专业综合基础-数据结构历年高频考题带答案难题附详解_第4页](http://file4.renrendoc.com/view/f01807322bf97b21b9ce6e9e490e2c35/f01807322bf97b21b9ce6e9e490e2c354.gif)
![2023年研究生类研究生入学考试专业课计算机学科专业综合基础-数据结构历年高频考题带答案难题附详解_第5页](http://file4.renrendoc.com/view/f01807322bf97b21b9ce6e9e490e2c35/f01807322bf97b21b9ce6e9e490e2c355.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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)
{
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 非贵金属制毛巾挂环市场需求与消费特点分析
- 二手车鉴定评估交易手册读书笔记
- 焊接质量控制及缺陷分析检验读书札记
- 大数据背景下追踪公司复杂股权关系的算法创新研究
- 农业用叉手工具产品原材料供应与需求分析
- 全民消防安全普法手册读书随笔
- 高处坠落事故的原因分析及防范措施
- 旅游行业智能化旅游目的地宣传与推广方案
- 旅游安全应急救援预案
- 基础场地布置与管理考核试卷
- (完整文本版)货物验收单
- “红歌”融入思政课教学的思考
- “一会三卡”工作制度(经典版)
- 【物理学史与物理教学结合的理论与实践分析2800字】
- 施工组织设计完整版
- 盲盒销售营业执照范本
- 第四章第3节运用选择结构描述问题求解过程说课 课件 2023-2024学年粤教版(2019)高中信息技术必修1
- 说课-推拿治疗课程介绍课件整理
- 市政公路工程之路基质量通病及防治措施
- 宣传栏施工方案
- 2023年IDSA念珠菌病治疗指南
评论
0/150
提交评论