2023年自考类计算机类(工学类)数据结构历年高频考题带答案难题附详解

2023年自考类计算机类(工学类)数据结构历年高频考题带答案难题附详解（图片大小可自由调整）第1卷一.历年考点试题黑钻版(共25题)1.已知一采用开放地址法解决Hash表冲突，要从此Hash表中删除一个记录，正确的做法是

A.将该元素所在的存储单元清空B.将该元素用一个特殊的元素替代C.将与该元素有相同Hash地址的后继元素顺次前移一个位置D.用与该无素有相同Hash地址的最后插入表中的元素替代2.数组A[1..10，-2..6，2..8]以行优先顺序存储，设第一个元素的首地址是100，每个元素占3个存储长度的存储空间，则元素A[5,0,7]的存储地址为______。3.树(A(B(E，(F(J，K)))，C(G)，D(H，I)))的度和深度分别是______A.3；3B.2；4C.3；4D.4；44.求下面算法中变量count的值：(假设n为2的乘幂，并且n＞2)

intTime

{intn

count=0;x=2;

while(x＜n/2)

{x*=2;count++;

}

return(count)

}5.在分块查找法中，首先查找______，然后再查找相应的______。6.堆是一个键值序列(k1，k2，k…，k1…，k0)，对i=1，2…，[n/2]，满足

A.ki≤k2i≤k2i+1B.ki＜k2i＜k2i+1C.ki≤k2i且k≤k2i+1(2i+1≤n)D.ki≤k2i或ki≤k2i+l(2i+1≤n)7.存储在直接存储器上的顺序文件可以用顺序查找法存取，也可以用______和进行查找。8.以下运算实现在链队上的入队列，请在______处用适当的语句予以填充。

voidEnQueue(QueptrTp*lq,DataTypex)

{LqueueTp*P;

p=(LqueueTp*)malloc(sizeof(LqueueTp));

______=x;

p—＞next=NULL;

(1q—＞rear)—＞next=______;

______;

}9.假设对二叉树采用链式存储结构，给出如下计算二叉树深度的算法，试填写以下空白处程序。

intTdepth(BinTreebt)

{

intdepl,depr;

if(bt=NULL)

return______;

else{

depl=Tdepth(______);

depr=Tdepth(______);

if(depl＞depr)

return______;

else

return______;

}10.设有两个串p和q，求q在p中首次出现的位置的运算叫______。11.有一个序列按照A，B，C，D，E的顺序入队，那么其出队的序列为______A.A，B，C，D，EB.A，C，E，B，DC.E，D，C，B，AD.以上都不对12.栈是一种特殊的线性表，其操作原则是______。13.在______遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点之后。14.简述一下算法的功能：

status

A

(1inkedlist

L)

{//L是无表头结点的单链表

if

(L&&L—＞next)

{Q=L;L=L—＞next;P=L;

while(P—＞next)P=P—＞next;

P—＞next=Q;Q—＞next=NULL;

}

returnok;

)//A15.若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是______的。16.假设在树中，如果结点x是结点y的双亲时，用(x,y)来表示树边，已知一棵树的树边的集合为{(i,m)，(i,n)，(e,i)，(b,e)，(b,d)，(a,b)，(g,j)，(g,k)，(c,g)，(c,f)，(h,l)，(c,h)，(a,c))，请用树形结构画出此树，并回答下面的问题。

(1)哪个是根结点?

(2)哪些是叶结点?

(3)哪个是g的双亲?

(4)哪些是g的祖先?

(5)哪些是g的孩子?

(6)哪些是e的子孙?

(7)哪些是e的兄弟?

(8)树的深度是多少?

(9)树的度数是多少?17.在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为

A.n-i+1B.iC.i+1D.n-i18.顺序查找法适用于存储结构为

的线性表。A.散列存储B.压缩存储C.顺序存储或链接存储D.索引存储19.设数组A[0,m]作为循环队列sq的存储空间，front为队头指针，rear为队尾指针，则执行入队操作的语句是

A.sq.front=(sq.front+1)%mB.sq.front=(sq.front+1)%(m+1)C.sq.rear=(sq.rear+1)%mD.sq.rear=(sq.rear+1)%(m+1)20.通常情况下，把对算法所要求解问题的输入量称为______，并用一个正整数n来表示。21.已知串S=‘(xyz)*’，t=‘(x+z)*y’，试利用串的基本运算将s串转化为t串，t串转化为s串。22.以下为顺序表的定位运算，分析算法，请在______处用正确的语句予以填充。

intlocate_sqlist(sqlistL,datatypeX)

/*在顺序表L中查找第一个值等于X的结点。若找到回传该结点序号；否则回传0*/{______；

while((i≤L.last)&&(L.data[i-1]!=x))i++;

if(______)return(i);

elsereturn(0);

}23.已知有一关键字序列为{97,86,53,108,72,34,215,146,11,68}，如果我们采用直接选择排序方法对此序列进行排序(按照升序排列)，请给出每一趟的排序结果。24.数据的链式存储结构的特点是借助______表示数据元素之间的逻辑关系。25.设树T的度为4，其中度为1、2、3和4的结点个数分别是4、2、1和1，则T中叶子结点的个数是：______。第1卷参考答案一.历年考点试题黑钻版1.参考答案：B2.参考答案：9133.参考答案：C[考点]树的广义表表示法以及树的度和深度的定义

[解析]根据所给树的广义表，可以画出树形图，从树形图中可以看出结点的最大度为3，所以树的度为3；同时，该树具有4层，也就是深度为4。4.参考答案：count=log2n5.参考答案：索引表块6.参考答案：C7.参考答案：二分查找法

分块查找8.参考答案：p—＞dataPlq—＞rear=p9.参考答案：0

bt-＞lchild

bt-＞rchild

depl+1

depr+1[考点]二叉树深度的计算算法

[解析]若二叉树为空，则返回0值，若非空分别对左右子树调用深度计算函数，若depl＞depr那么二叉树深度为depl+1，否则为depr+1。10.参考答案：模式匹配11.参考答案：A[考点]队列的应用

[解析]根据队列先进先出的操作原则，按照A，B，C，D，E的顺序入队，那么其出队的序列为A，B，C，D，E。12.参考答案：后进先出[考点]栈的操作原则

[解析]栈的操作原则是后进先出。13.参考答案：先序14.参考答案：本程序实现的功能就是：如果L的长度不小于2，则将首元结点删去并插入到表尾。15.参考答案：稳定16.参考答案：树的结构如下图所示：

(1)a是根结点

(2)m,n,d,f,l,j,k是叶结点

(3)c是g的双亲

(4)a和e是g的祖先

(5)j,k是g的孩子

(6)i,m,n是e的子孙

(7)d是e的兄弟

(8)树的深度是5

(9)树的度数是3

17.参考答案：D18.参考答案：C19.参考答案：D20.参考答案：问题的规模[考点]问题的规模的概念

[解析]通常情况下，把对算法所要求解问题的输入量称为问题的规模，并用一个正整数n来表示。21.参考答案：t=CONCAT(Rep(sup(s,1,5),‘y’,‘+’),Rep(sub(s,6,1),‘*’,‘*y’))

s=CONCAT(Rep(sub(t,1,5),‘+’,‘y’)，Rep(sub(t,6,2),‘*y’,‘*’))22.参考答案：i=1i≤L.last)23.参考答案：直接选择排序的过程为：从第i趟开始时，当前的有序区和无序区分别为R[1…i]和R[1…n](1≤-1≤n-1)，则在该趟排序是从当前无序区中选出关键字最小的记录R[K]，将它与无序区中的第1个记录R[i]交换，使R[1…i]和R[i+1…n]分别变成新的有序区和新的无序区，每次排序都使有序区增加一个记录，无序区减少一个记录，按照以上规则，我们得到各趟结果如下：

初始：97,86,53,108,72,34,215,232,11,68

第1趟：11[86,53,108,72,34,215,232,97,68]

第2趟：11,34[53,108,72,86,215,232,97,68]

第3趟：11,34,531108,72,86,215,232,97,68]

第4趟：11,34,53,68[72,86,215,232,97,108]

第5趟：11,34