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

2023年自考类计算机类(工学类)数据结构导论历年高频考题带答案难题附详解（图片大小可自由调整）第1卷一.历年考点试题黑钻版(共50题)1.数据的逻辑结构通常包括集合、线性结构、______和图状结构。2.试写一个用链表表示的直接插入排序算法。3.向一个不带头结点的栈指针为lst的链栈中插入一个*s所指结点时，则执行语句为______。4.顺序查找算法的平均查找长度为______A.log2nB.(n-1)/2C.n/2D.(n+1)/25.已知一个无向图的顶点集为{a，b，c，d，e}，其邻接矩阵如下图所示

(1)画出该图的图形。

(2)根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。6.将下图所示的一棵树转换为对应的二叉树。

7.一个10×10阶对称矩阵A，采用行优先顺序压缩存储下三角矩阵，a00为第一个元素，其存储地址为0，每个元素占用1个存储单元，则a33的地址为______。8.索引顺序表由______和______两部分组成。9.索引顺序表的索引表在组织形式上是一个______A.顺序表B.单链表C.队列D.栈10.下列序列中，符合堆定义的是______A.(100，80，55，60，50，40，58，35，20)B.(100，80，55，58，50，40，60，35，20)C.(100，80，55，60，50，40，35，58，20)D.(100，70，55，60，50，40，58，35，20)11.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是______A.G中有弧＜Vi，Vj＞B.G中有一条从Vi到Vj的路径C.G中没有弧＜Vi，vj＞D.G中有一条从Vj到Vi的路径12.在一个单链表中，若p所指结点不是最后结点，s指向已生成的新结点，则在p之后插入s所指结点的正确操作是______A.s-＞next=p-＞next；p-＞next=s；B.p-＞next=s-＞next；s->next=p；C.s-＞next=p；p-＞next=s；D.s-＞next=p-＞next；p=s；13.一组记录的键值为(12，38，35，25，74，50，63，90)，按二路归并排序方法对该序列进行一趟归并后的结果为______A.12，38，25，35，50，74，63，90B.12，38，35，25，74，50，63，90C.12，25，35，38，50，74，63，90D.12，35，38，25，63，50，74，9014.设F是一个森林，B是由F转换得到的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有______个。15.在图的邻接表存储结构上执行广度优先搜索遍历类似于二叉树上的

A.先根遍历B.中根遍历C.后根遍历D.按层次遍历16.一维数组又称______，它由一组具有相同类型的数据元素组成。17.一个顺序队列的第5个元素的存储地址是200，第10个元素的存储地址是225。每个元素的长度是5，则第20个元素的地址是______。18.从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是______A.线性结构B.树形结构C.线性结构和树形结构D.线性结构和图状结构19.下列查找中，效率最高的查找方法是______A.顺序查找B.二分查找C.索引顺序查找D.分块查找20.下图所示二叉树的中序遍历序列是______

A.abcdgefB.dbaefcgC.dfebageD.defbagc21.下面关于线性表的叙述中，错误的是______A.线性表采用顺序存储，必须占用一片连续的存储单元B.线性表采用链接存储，不必占用一片连续的存储单元C.线性表采用顺序存储，便于进行插入和删除操作D.线性表采用链接存储，便于进行插入和删除操作22.写出将一个无向图的邻接表转换或邻接矩阵的算法。23.设一个链栈的输入序列为X，Y，Z，试写出出栈的所有可能的输出序列及其操作步骤。24.静态查找表的运算包括______A.建表、删除B.建表、查找和读表中元素C.查找和读表中元素D.建表、查找和插入25.顺序存储实现的队列称为______，是由一个______及两个分别指示队列首元素和队列尾元素的变量组成。26.若用冒泡排序法对序列19，14，6，27，8，12，17，52，10，26，47，29，42，25从小到大进行排序，需要进行比较的次数是______A.33B.91C.70D.4527.在图的邻接表存储结构上执行广度优先搜索遍历类似于二叉树上的______A.按层次遍历B.中序遍历C.后序遍历D.先序遍历28.无向图中一个顶点的度是指图中______A.与该顶点相邻接的顶点数B.通过该顶点的简单路径数C.通过该顶点的回路数D.与该顶点连通的顶点数29.对于循环队列，试写出求队列含有多少个元素的算法。30.将含有80个结点的完全二叉树从根这一层开始，每层从左到右依次对结点编号，根结点的编号为1，则关于编号40的结点的左右孩子的说法正确的是______A.左孩子编号为79，右孩子编号为80B.左孩子不存在，右孩子编号为80C.左孩子编号为80，右孩子不存在D.左孩子不存在，右孩子不存在31.设一个栈的输入序列是a，b，c，d，则所得到的输出序列(输入过程中允许出栈)不可能出现的是______A.a，b，c，dB.c，d，a，bC.d，c，b，aD.a，b，d，c32.假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为______A.(rear-front)%nB.(rear-front-1)%nC.(front-rear+1)%nD.(rear-front+n)%n33.设有一顺序队列sq，容量为5，初始状态时sq.front=sq.rear=0，画出做完下列操作后队列及其头尾指针的状态变化情况，若不能入队，请简述其理由后停止。

(1)d，e，b入队

(2)d，e出队

(3)i，j入队

(4)b出队

(5)n，o，p入队34.假设树采用孩子兄弟链表表示法，其结构定义如下：

typedefstructtnode

{DataTypedata;

structtnode*son,*brother;

}*Tree;

试编写算法voidleveltree(Treeroot)实现树的按层次遍历。35.n个顶点且含有环路的无向连通图中，至少含有______条边。36.以二叉链表作为存储结构，编写求二叉树叶子数的算法。37.算法的便于阅读和理解的特性称为

A.正确性B.易读性C.健壮性D.时空性38.算法的时间性能是指算法包含的______。39.______是顺序存储与链式存储相结合的存储方法。40.下列四种排序方法中，要求附加的内存容量最大的是______A.插入排序B.选择排序C.快速排序D.归并排序41.如下图所示，在栈的输入端依次输入元素A，B，C，试写出在栈的输出端可以得到的所有输出序列，并给出每个序列的操作过程(用push(A)表示A进栈，pop(A)表示A出栈)。

42.双向循环链表找前驱结点和后继结点的时间复杂度为______。43.下列说法正确的是

A.数据是数据元素的基本单位B.数据元素是数据项中不可分割的最小标识单位C.数据可由若干个数据元素构成D.数据项可由若干个数据元素构成44.若某二叉树中度为1的结点数为4，度为2的结点数为6，则该树叶子结点数为______。45.对于一组数据(24，12，22，34，5，44，76，61，100，3，1，120)，写出该数据采用归并算法的排序过程和排序结果。46.以二叉链表作为存储结构，试编写求二叉树中叶子数的算法。47.已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置，则在队列不满的情况下，队列的长度是______。48.关于算法的描述，不正确的是______A.算法最终必须由计算机程序实现B.所谓最坏时间复杂度是指最坏情况下，估算算法执行时间的一个上界C.健壮的算法不会因非法的输入数据而出现莫名其妙的运行结果D.算法的优劣与算法描述语言无关49.满二叉树______是完全二叉树，完全二叉树______是满二叉树。50.分别写出删除单向和双向循环链表中指针p所指结点的直接后继结点(非尾结点)对应的语句。第1卷参考答案一.历年考点试题黑钻版1.参考答案：树形结构[考点]数据的逻辑结构[解析]数据的逻辑结构通常包括集合、线性结构、树形结构和图状结构。2.参考答案：voidsort(DLinkListH)

{pre=H-＞next;

while(p!=H)

{p=pre-＞next;

q=p-＞next;

while((pre!=H)&&(p-＞data＜pre-＞data))

pre=pre-＞prior;

if(pre!=p-＞prior;

{p-＞prior-＞next=p-＞next;

p-＞next-＞prior-＞p-＞prior;

p-＞next=pre-＞next;

pre-＞next-＞prior=p:

p-＞prior=pre;pre-＞next=p;

}

p=q;

}

}[考点]链表的直接插入排序3.参考答案：s-＞next=1st：lst=s：4.参考答案：D[考点]顺序查找算法长度[解析]ASL=(n+1)/2。5.参考答案：见下图

[考点]已知的邻接矩阵与无向图的转换，以及无向图深度优先遍历序和广度优先遍历。6.参考答案：结果见下图：

[考点]一棵树转换为对应的二叉树的算法[解析](1)将所有兄弟结点连接起来。

(2)保留第一个兄弟结点与父结点的连接，断开其他兄弟结点与父结点的连接，然后以根结点为轴心按顺时针方向旋转45°角。7.参考答案：98.参考答案：一个索引表

一个顺序表[考点]索引顺序表[解析]索引顺序表由两部分组成：一个索引表和一个顺序表。9.参考答案：A10.参考答案：C[考点]堆的定义[解析]根据堆的定义以及4个选项可知其是最大堆，根据最大堆的特性，这棵二叉树中任意一结点的值都不小于它的两个孩子的值(若存在孩子的话)，只有C选项符合。11.参考答案：D[考点]本题主要考查的知识点是有向图的拓扑排序序列。

在有向图G中，若有一条从vj到vi的路径，则在它的拓扑排序序列中，顶点vj必须出现在顶点vi之前。12.参考答案：A13.参考答案：A14.参考答案：n+115.参考答案：D[解析]本题主要考查的知识点是广度优先搜索。[要点透析]连通图广度优先搜索的基本思想是：从图中某个顶点vi出发，在访问了vi之后依次访问vi的所有邻接点，然后分别从这些邻接点出发按广度优先搜索遍历图的其他顶点，重复这一过程，直至所有顶点都被访问到。类似于二叉树按层次(同一层从左到右)遍历的算法。16.参考答案：向量17.参考答案：27518.参考答案：C[考点]逻辑结构[解析]从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是线性结构和树形结构。图形结构的直接前驱可能为2，3……大于1的任意个。19.参考答案：B20.参考答案：C[考点]二叉树的中序遍历[解析]二叉树的中序遍历顺序是、左子树、根、右子树。21.参考答案：C[考点]本题主要考查的知识点是线性表。

[解析]顺序存储结构的地址在内存中是连续的，所以可以通过计算地址实现随机存取，而链式存储结构的存储地址不一定是连续的，只能通过第一个结点的指针顺序存取。22.参考答案：算法描述如下：

voidAdjlist_to_Matrix(GraphTP_Adj*ga，GraphTp_Mat*gb)

{inti，j；

ArcNodeTp*p；

gb->vexnum=ga-＞vexnum；

//读入顶点个数和边数

gb-＞arcnum=ga-＞arcnum；

for(i=0；i＜ga-＞vexnum；i++)

for(j=0；j＜ga-＞vexnum；j++)

gb-＞arcs[i][j]=0；

//初始化邻接矩阵

for(i=0；i＜ga-＞vexnum；i++)

{p=ga-＞adjlis[i].firstarc；

while(p!=NULL)

{j=p-＞adjvex；

ga-＞arcs[i][j]=1：

p=p-＞nextarc；

}

}

}23.参考答案：

(1)XYZ

(2)XZY

(3)YZX

(4)YXZ

(5)ZYX[考点]栈的应用[解析](1)X进X出，Y进Y出，Z进Z出；(3)X进X出，Y进，Z进Z出，Y出；(3)X进，Y进Y出，Z进Z出，X出；(4)X进，Y进Y出，X出，Z进Z出。24.参考答案：B[考点]静态查找表的元素[解析]静态查找表是以具有相同特性的数据元素集合为逻辑结构，包括三种基本运算：建表、查找和读表中元素。25.参考答案：顺序队列

一维数组[考点]顺序队列[解析]顺序队列的定义。26.参考答案：B[考点]冒泡排序法[解析]冒泡排序法总的比较次数为n(n-1)/2次，n为待排序列元素个数。27.参考答案：A[考点]广度优先搜索[解析]广度优先搜索的基本思想是：从图中某个顶点出发，在访问该结点后，依次访问该结点的所有邻接点，然后从这些邻接点按广度优先搜索遍历其他顶点，所以类似于二叉树按层次(同一层，从左到右)的遍历算法。28.参考答案：A[考点]无向图顶点的度[解析]无向图顶点的度指与该顶点相邻的顶点数。29.参考答案：假定循环队列的类型定义如下：

constintmaxsize=……；

typedefstructcycqueue

{DataType[maxsize]；

intfront，rear；

}CycqueueTp；

解法一：计数器初始化为0，从队首开始沿着队列顺序搜索，每走过一个元素，计数器加1，直到队尾，计数器的最终值即队列长度。算法描述如下：

intque_length(CycqueueTp*cq)

{intn，k；

n=0；//计数器

k=cq-＞front;

while(k!=cq-＞rear)

{n++；

k=(k+1)%maxsize；

}

returnn；

}

解法二：利用队首和队尾的关系求出队列的长度。

intque_length(CycqueueTp*cq)

{

return(maxsize+cq-＞rear-cq-＞

front)%maxsize；

}30.参考答案：C[考点]完全二叉树某结点的左右孩子编号[解析]因为2×40=80，则左孩子编号为80，没有右孩子。31.参考答案：B[考点]元素的进栈操作[解析]元素的进栈操作。32.参考答案：A[考点]循环队列数据元素个数的求取[解析](rear-front)%n。33.参考答案：

(0)初态

(1)d、e、b入队

(2)d、e出队

(3)i、j入队

(4)b出队

第5步操作无法进行，因为队列已满。34.参考答案：

voidleveltree(Treeroot)

{

InitQueueQ;

If(root)

EnQueue(Q,root);

while(!QueueEmpty(Q))

{

p=DeQueue(Q);

printf(p-＞data);

If(p-＞son)

EnQueue(Q,p-＞son);

r=p-＞brother;

while(r)

{

EnQueue(Q,p-＞brother);

r=r-＞brother;

}

}

}[考点]二叉树的遍历[解析]树的层次遍历，将结点入队列，若队列不空，则出队列，访问，并将son所指结点放入队列，若其brother所指结点存在，则依次放入队列中。循环判断队列是否为空，不空则重复上述过程。35.参考答案：n[考点]有环无向图的特征[解析]n个顶点且含有环路的无向连通图中，至少含有n条边。36.参考答案：算法思想：先求左子树的叶子数，再求右子树的叶子数，两者相加就是根结点的叶子数，也就是对应二叉树的叶子数。具体算法如下：

intleafcount(BinTreeT)

{if(T=NULL)leaf=0;

elseif((T-＞lchild==NULL)&&(T-＞rchild==NULL))

leaf=1;

else{L=leafcount(T-＞lchild);

R=leafcount(T-＞rchild);

leaf=L+R;

}

return(leaf)

}37.参考答案：B[解析]本题主要考查的知识点是算法的易读性。[要点透析]算法的易读性是指易于阅读、理解和交流，便于调试、修改和扩充。38.参考答案：计算量39.参考答案：邻接表40.参考答案：D[考点]本题主要考查的知识点是归并排序的存储开销。

归并排序算法的时间复杂度为O(nlog2n)，由于要用到和待排记录等数量的数组b来存放结果，所以实现归并排序需要附加一倍的存储开销。41.参考答案：共有5种：

(1)push(A)，pop(A)，push(B)，pop(B)，push(C)，pop(C)输出序列为：ABC

(2)push(A)，pop(A)，push(B)，push(C)，pop(C)，pop(B)输出序列为：ACB

(3)push(A)，push(B)，pop(B)，pop(A)，push(C)，pop(C)输出序列为：BAC

(4)push(A)，push(B)，pop(B)，push(C)，pop(C)，pop(A)输出序列为：BCA

(5)push(A)，push(B)，push(C)，pop(C)，pop(B)，pop(A)输出序列为：CBA[考点]栈的存取原则：后进先出42.参考答案：O(1)43.参考答案：C44.参考答案：745.参考答案：[24][12][22][34][5][44][76][61][100][3][1][120]

[12

2