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

2023年自考类计算机类(工学类)数据结构历年高频考题带答案难题附详解（图片大小可自由调整）第1卷一.历年考点试题黑钻版(共50题)1.图的邻接表的类型定义如下所示：

#defineMaxVertexNum50

typedefstructnode{

intadjvex;

structnode*next;

}EdgeNode;

typedefstruct{

VertexTypevertex;

EdgeNode*firstedge;

}VertexNode;

typedefVertexNodeAdjList[MaxVertexNum];

typedefstruct{

AdjListadjiist;

intn,e;

}ALGraph;

为便于删除和插入图的顶点的操作，可将邻接表的表头向量定义为链式结构，两种定义的存储表示实例如下图所示，请写出重新定义的类型说明。

2.对于一个二维数组A[m][n]，若按行序为主序存储，则任一元素A[i][j]相对于A[0][0]的地址为______。3.一个队列的输入序列是1,2,3,4，则队列的输出序列是

A.4,3,2,1B.1,2,3,4C.1,4,3,2D.3,2,4,14.树(A(B(E，(F(J，K)))，C(G)，D(H，I)))的度和深度分别是______A.3；3B.2；4C.3；4D.4；45.两个字符串相等的条件是

A.串的长度相等B.含有相同的字符集C.都是非空串D.串的长度相等且对应的字符相同6.若对关键字序列(43,02,80,48,26,57,15,73,21,24,66)进行一趟增量为3的希尔排序，则得到的结果为______。7.已知图G共有4个结点，其各个顶点的度分别为2、4、3、1，那么该图的边数为______A.3B.6C.4D.58.用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为

A.n-1B.nC.n+1D.2n9.设有一顺序栈S，元素s1，s2，s3，s4，s5，s6依次进栈，如果6个元素出栈的顺序是s2，s3，s4，s5，s6，s1，则栈的容量至少应该是

A.2B.3C.5D.610.对序列(8，13，26，55，29，44)从小到大进行基数排序，第一趟排序的结果是______A.(13，44，55，26，8，29)B.(13，26，55，44，8，29)C.(8，13，26，29，44，55)D.(29，26，8，44，55，13)11.设有一个用线性探测法解决冲突得到的散列表：

散列函数为H(k)=Kmod11

若要查找元素14，探测的次数(比较的次数)是A.8B.9C.3D.612.设无向图的顶点个数为n，则该图边的数目最多为______A.n-1B.n(n-1)/2C.n(n+1)/2D.n213.广义表的深度是指______。14.二维数组A[12][18]采用列优先的存储方法，若每个元素各占3个存储单元，且第1个元素的地址为150，则元素A[9][7]的地址为

A.429B.432C.435D.43815.以下是图的广度优先搜索算法，请在______处填充适当的语句。

Bfs(GraphTpg,intv)

{QueptrTpQ;

ArcNodeTp*P;

InitQueue(&Q);

printf("%"”,v);

visited[v]=1;

______

while(!EmptyQueue(Q))

{______;

p=g.adjlist[v].firstarc;

while(p!=NULL)

{if(!visited[p—＞adjvex])

{printf("%"”,p—＞adjvex);

visited[p—＞adjvex]=1);

EnQueue(&Q，p—＞adjvex);

}

______;

}

}

}16.算法的时间复杂度表征的是______A.算法的可读性B.算法的难易程度C.执行算法所耗费的时间D.执行算法所耗费的存储空间17.______的邻接矩阵不一定是不对称的。18.从树的根结点到树中的其余结点之间的路径______惟一的。19.若一棵二叉树中只有叶结点和左、右子树皆非空的结点，设叶结点的个数为1，则左右子树皆非空的结点个数为______。20.ISAM文件采用______索引结构，而VSAM文件采用______索引结构。21.已知下面的一个图，请根据普里姆算法构出它的一棵最小生成的树。

22.一个栈的人栈序列是a,b,c,d,e，则栈的不可能的输出序列是

A.edcbaB.decbaC.dceabD.abcde23.数组的长度是______，线性表的长度是______。24.具有24个记录的序列，采用冒泡排序最少的比较次数是

A.1B.23C.24D.52925.在用p访问循环链表(其中，head为头指针)时，判断不是访问表结束的条件是______A.p!=headB.p-＞next!=NULLC.p!=NULLD.p-＞next!=head26.Aarr和Barr两个数组的说明如下：

VAR

Aarr:Array[O··7]ofchar;

Barr:Array[-5··2,3,··8]ofchar;这两个数组分别能存放的字符的最大个数是

A.7和35B.1和5C.8和48D.1和627.已知一采用开放地址法解决Hash表冲突，要从此Hash表中删除一个记录，正确的做法是

A.将该元素所在的存储单元清空B.将该元素用一个特殊的元素替代C.将与该元素有相同Hash地址的后继元素顺次前移一个位置D.用与该无素有相同Hash地址的最后插入表中的元素替代28.如果一个图中有n条边，则此图的生成树含有______条边，所以生成树是图的边数______的连通图。29.下列线性表中，能使用二分查找的是A.顺序存储(2，12，5，6，9，3，89，34，25)B.链式存储(2，12，5，6，9，3，89，34，25)C.顺序存储(2，3，5，6，9，12，25，34，89)D.链式存储(2，3，5，6，9，12，25，34，89)30.在一棵二叉树中，度为O的结点个数与度为2的结点个数和度数之间有什么关系?在一棵完全二叉树中，如果共有200个结点，则能判断出叶结点的个数吗?如果能，请指出会有多少个叶结点，多少个度为2的结点?多少个度为1的结点?如果有201个结点呢?31.以下运算实现在链队上的出队列，请在______处用适当的语句予以填充。

intOutQueue(QueptrTp*lq,DataType*x)

{LqueueTp*s;

if(1q—＞front==lq—＞rear){error("队空");return(0);}

else{s=(lq—＞front)—＞next;

______=s—＞data;

(lq—＞front)—＞next______;

if(s—＞next==NULL)lq—＞rear=lq—＞front;

free(s);

return(1);

}

}32.已知广义表G，head(G)与tail(G)的深度分别为4和6，则G的深度是______。33.设树T的度为4，其中度为1、2、3和4的结点个数分别是4、2、1和1，则T中叶子结点的个数是：______。34.一个字符串相等的充要条件是______和______。35.对同一个基本有序的待排序列分别进行堆排序、快速排序和冒泡排序，最省时间的算法是______。36.对序列(48,37,63,96,22,31,50,55,11)进行升序的堆排序，写出构建的初始(大根)堆及前两趟重建堆之后的序列状态。

初始堆：

第1趟：

第2趟：37.堆是一个键值序列(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)38.在分块查找法中，首先查找______，然后再查找相应的______。39.在下面的程序中，语句S的执行次数为

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

{for(j=n;j＞=i;j--)

{S;

}

40.假设以列优先顺序存储二维数组A[5][8]，其中元素A[0][0]的存储地址为LOC(a00)，且每个元素占4个存储单元，则数组元素A[i][j]的存储地址为______。41.判断一个没有头结点的单链表head为空的条件是______。42.对图采用邻接矩阵表示法，那么无向图的邻接矩阵是一个______矩阵。43.由字符集{s,t,a,e,i)及其在电文中出现的频度构建的哈夫曼树如图所示。已知某段电文的哈夫曼编码为111000010100，请根据该哈夫曼树进行译码，写出原来的电文。

44.图的遍历方法有很多，但主要常用的是深度优先遍历和______。45.以下为单链表按序号查找的运算，分析算法，请在______处填上正确的语句。

pointerfind_lklist(1klisthead,inti)

{

p=head;j=0;

while(______)

{p=p—＞next;j++;}

if(i==j)return(p);

elsereturn(NULL);

}46.在图的邻接表表示中，每个顶点邻接表中的顶点数，对于有向图来说是______，对于无向图来说是______。47.算法分析的目的是

A.辨别数据结构的合理性B.评价算法的效率C.研究算法中输入与输出的关系D.鉴别算法的可读性48.假设一棵具有12个结点的二叉树的存储结构如下图所示，其中left和right分别表示此结点左、右孩子的序号，data表示此结点的数据，根结点为编号为4的结点。请根据此存储结构画出对应的二叉树，然后回答下面的问题：

(1)写出前序遍历、中序遍历和后序遍历此二叉树时的遍历序列。

(2)求出此树的高度并分析叶结点的个数。

(3)结点E的双亲及子孙分别是什么?49.有m个叶子结点(又称外结点)的哈夫曼树，其结点总数是______。50.画出下图所示树的孩子链表。

第1卷参考答案一.历年考点试题黑钻版1.参考答案：typeclefstructArcNode{

VNode*adjvex;

//该弧所指向的顶点的位置

structArcNode*nextarc;

//指向下一条弧的指针

}ArcNode;

typedefstructVNode{

VertexTypedata;

//顶点信息

structVNode*nextVertex;

//指向下一个顶点的指针

ArcNode*firstarc;

//指向第一条依附该顶点的弧

}VNode.*AdjList;

typedefstruct{

AdjListadjList;

intn,e;

}ALGraph;2.参考答案：i×j+i全元素位置3.参考答案：B4.参考答案：C[考点]树的广义表表示法以及树的度和深度的定义

[解析]根据所给树的广义表，可以画出树形图，从树形图中可以看出结点的最大度为3，所以树的度为3；同时，该树具有4层，也就是深度为4。5.参考答案：D6.参考答案：15,02,21,24,26,57,43,66,80,48,737.参考答案：D[考点]图形结构中顶点的度和图的边数的关系

[解析]根据图的边数等于所有顶点度数和的一半可知，该图的边数为5。8.参考答案：C9.参考答案：B10.参考答案：A[考点]基数排序

[解析]根据基数排序的方法，第一趟先按个位数排序，得到排序结果为(13，44，55，26，8，29)。11.参考答案：D12.参考答案：B[考点]无向图的边数的问题

[解析]无向图的边数最多为n(n-1)/2。13.参考答案：广义表展开后所含括号的最大层数14.参考答案：A15.参考答案：EnQueue(&Q,v)OutQueue(&Q,&v)p=p—＞nextarc16.参考答案：C[考点]算法的时间复杂度定义

[解析](1)执行算法所耗费的时间，即时间复杂性；(2)执行算法所耗费的存储空间，主要是辅助空间，即空间复杂性；(3)算法应易于理解、易于编程、易于调试等，即可读性和可操作性。因此表征算法时间复杂度的是执行算法耗费的时间，C正确。17.参考答案：有向图18.参考答案：是19.参考答案：1-120.参考答案：静态

动态21.参考答案：构造最小生成树的过程如下：

22.参考答案：C23.参考答案：固定的

可变的24.参考答案：B25.参考答案：A[考点]循环链表结束条件的判断

[解析]在用p访问循环链表(其中，head为头指针)时，p-＞next!=NULL，p!=NULL或者p-＞next!=head是判断表结束的条件。26.参考答案：C27.参考答案：B28.参考答案：n-1

最少29.参考答案：C[考点]二分法查找的使用条件

[解析]二分法查找要求查找对象的线性表必须是顺序存储结构的有序表，因此排除B和D，又因为A选项中不是有序表，因此答案选C。30.参考答案：在一棵二叉树中，度数为0的结点(叶结点)的个数总是比度为2的结点的个数多1。根据完全二叉树的定义：若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干住置上，则我们可以得出这样一个结论：在一棵完全二叉树上，或者没有度为1的结点。则根据以上分析，我们可以这样计算此题：设度数为2的结点有n个，则必有n+1个度为0的结点，即度数为2和度数为0的结点数之和为2n+1(是奇数)，于是得出，如果一棵完全二叉树的结点总数为奇数，则此树中必然不存在度为1的结点，若完全二叉树中结点总数为偶数，则必然有1个度为1的结点存在，于是若完全二叉树中有200个结点，就必有100个对结点，99个度数为2的结点，12个度数为1的结点，如果二叉树中有201个结点，则必有101个叶结点，100个度数为2的结点，没有度数为1的结点。31.参考答案：*xs—＞next32.参考答案：6[考点]广义表的深度

[解析]若表尾深度大于表头深度，那么线性表的深度为表尾的深度。33.参考答案：8个34.参考答案：两个字符串的长度相等

对应位置的字符相等35.参考答案：冒泡排序[考点]排序方法的选择

[解析]当待排序记录关键字基本有序时，宜采用直接插入排序或冒泡排序。36.参考答案：初始堆：(96,55,63,48,22,3