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

2023年自考类计算机类(工学类)数据结构导论历年高频考题带答案难题附详解（图片大小可自由调整）第1卷一.历年考点试题黑钻版(共50题)1.利用克鲁斯卡尔(Kruskal)算法构造下图的最小生成树，画出它的构造过程。

2.______是顺序存储与链式存储相结合的存储方法。3.算法在发生非法操作时可以作出处理的特性称为

A.正确性B.易读性C.健壮性D.时空性4.假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为______A.(rear-front)%nB.(rear-front-1)%nC.(front-rear+1)%nD.(rear-front+n)%n5.试写出二分查找的递归算法。6.下述矩阵表示一个无向连通网，试画出它所表示的连通网及该连通网的最小生成树。

7.在栈结构中，允许插入和删除的一端称为______。8.若用一个有7个单元的数组来实现循环队列，rear和front的初值分别为0和3，则从队列中删除一个元素，再添加两个元素后，rear和front的值分别为______A.1和4B.5和2C.2和5D.5和29.对于下列一组关键字(46，58，15，45，90，18，10，62)，试写出快速排序每一趟的排序结果，并标出第一趟中各元素的移动方向。10.一个栈的输入序列是12345，则下列序列中不可能是栈的输出序列的是

A.23415B.54132C.23145D.1543211.在无向图G的邻接矩阵A中，若A[i][j]等于0，则A[j][i]等于______。12.从v1出发，对下图按广度优先搜索遍历，则可能得到的一种顶点序列为

A.v1v2v3v5v4v6B.v1v2v3v5v6v4C.v1v5v2v3v6v4D.v1v3v6v4v5v213.除根结点外，树上每个结点______A.可有一个孩子、任意多个双亲B.可有任意多个孩子、任意多个双亲C.可有任意多个孩子、一个双亲D.只有一个孩子、一个双亲14.若一棵度为8的树有9个度为1的结点，有8个度为2的结点，有7个度为3的结点，有6个度为4的结点，有5个度为5的结点，有4个度为6的结点，有3个度为7的结点，有2个度为8的结点，该树一共有多少个叶子结点______A.44B.58C.113D.11515.二分查找算法要求被查找的表是

A.键值有序的链表B.键值不一定有序的链表C.键值有序的顺序表D.键值不一定有序的顺序表16.写出判断带头结点的单链表L的元素值是否是递增的算法。17.对相同输入数据量的不同输入数据，算法时间用量的最大值是指______。18.画出对应于序列{10，20，7，75，41，67，3，9，30，45}的初始堆(堆顶元素取最小值)。19.用来标识数据元素的数据项称为______。20.采用排序算法对n个元素进行排序，其排序趟数肯定为n-1趟的排序方法是______A.选择和插入B.冒泡和快速C.插入和快速D.选择和冒泡21.对于10阶对称矩阵，如果以行序或列序放入内存中，则需要多少个存储单元______A.55B.45C.100D.5022.外部排序是指在排序的整个过程中，全部数据在计算机的哪个中完成的排序______A.内存储器B.外存储器C.寄存器D.内存储器和外存储器23.在栈的输入端，元素的输入顺序为1，2，3，4，5，6，进栈过程中可以退栈，则退栈时能否排成序列3，2，5，6，4，1和1，5，4，6，2，3?若能，写出进栈、退栈过程；若不能，简述理由(用push(x)表示x进栈，pop(x)表示x退栈)。24.已知关键字序列R={11，4，3，2，17，30，19}，请构造一棵哈夫曼树，并计算出它的带权路径长度WPL。25.具有10个顶点的无向图的边数最多为______A.11B.110C.45D.22026.如果值相同的元素或者零元素在矩阵中的分布有一定规律，称此类矩阵为______。27.线性表是一种线性结构，是具有n个______的有限序列。28.冒泡排序的时间复杂度为______A.O(n)B.O(nlog2n)C.O(n2)D.O(log2n)29.排序中关键字比较次数与序列的原始状态有关的排序方法是

A.插入排序法B.希尔排序法C.直接选择排序法D.堆排序法30.具有11个顶点的有向完全图应具有______A.110条弧B.50条弧C.90条弧D.100条弧31.在线性表的下列存储结构中进行插入、删除运算，花费时间最多的是______A.单链表B.顺序表C.双链表D.单循环链表32.已知一棵二叉树的先序遍历序列为ABCDEFGHK，中序遍历序列为CBEDFAGKH，试建立该二叉树并写出它的后序遍历序列。33.除第一个顶点和最后一个顶点相同外，其余顶点不重复的回路，称为______。34.在下述的排序方法中，不属于内部排序方法的是______A.插入排序法B.选择排序法C.拓扑排序法D.归并排序法35.要解决散列引起的冲突问题，最常用的方法是______A.线性探测法、二次探测法、链地址法B.除留余数法、线性探测法、平方取中法C.数字分析法、除留余数法、平方取中法D.除留余数法、线性探测法、二次探测法36.已知森林F={T1，T2，T3，T4，T5}，各棵树Ti(i=1，2，3，4，5)中所含结点的个数分别为7、3、5、1、2，则与F对应的二叉树的右子树中的结点个数为______A.2B.3C.8D.1137.算法能正确地实现预定功能的特性称为______A.正确性B.易读性C.健壮性D.时空性38.二维数组A[12][18]采用行优先的存储方法，若每个元素各占3个存储单元，且第1个元素的地址为150，则元素A[9][7]的地址为______A.654B.657C.635D.63839.图的广度优先搜索遍历的过程类似于树的______A.前序遍历B.中序遍历C.按层次遍历D.后序遍历40.一个10×10阶对称矩阵A，采用行优先顺序压缩存储下三角矩阵，a00为第一个元素，其存储地址为0，每个元素占用1个存储单元，则a33的地址为______。41.试分别写出二叉树的先序遍历和中序遍历的递归算法。42.有10个叶结点的哈夫曼树中共有______A.10个结点B.11个结点C.19个结点D.21个结点43.将下图所示的森林转换为一棵二叉树。

44.在一个具有n个结点的有序单链表中插入一个新结点，并使插入后仍然有序，则该操作的时间复杂度为______A.O(1)B.O(n)C.O(nlog2n)D.O(n2)45.设带头结点的单循环链表的头指针为head，则判断该链表是否为空的条件是______A.head-＞next==headB.head-＞next==NULLC.head!=NULLD.head==NULL46.在一般情况，下用直接插入排序、选择排序和冒泡排序的过程中，所需记录交换次数最少的是______。47.在双链表中某结点(已知其地址)前插入一新结点，其时间复杂度为

A.O(n)B.O(1)C.O(n2)D.O(log2n)48.适用于静态查找表的方法为

A.二分查找、二叉排序树查找B.二分查找、索引顺序表查找C.二叉排序树查找、索引顺序表查找D.二叉排序树查找、散列法查找49.下列表述中，正确的是______A.序列(102，81，55，62，50，40，35，58，20)是堆B.序列(102，81，55，62，50，40，58，35，20)是堆C.序列(102，81，55，58，50，40，35，62，20)是堆D.序列(102，71，55，40，50，62，35，58，20)是堆50.在一个用一维数组A[N]表示的循环队列中，该队列中的元素个数最少为______个，最多为______个。第1卷参考答案一.历年考点试题黑钻版1.参考答案：利用Kruskal算法构造最小生成树的过程如下：

[考点]Kruskal算法构造最小生成树2.参考答案：邻接表3.参考答案：C[解析]本题主要考查的知识点是算法的健壮性。[要点透析]算法的健壮性是指即使输入非法数据，算法也能适当地做出反应或进行处理，不会产生预料不到的运行结果。4.参考答案：A[考点]循环队列数据元素个数的求取[解析](rear-front)%n。5.参考答案：intbinsearch_2(SqtableR,KeyTypek,intlow,inthigh)

{

intmid=(low+high)/2;

if(R.elem[mid].key==k)

returnmid;

elseif(R.elem[mid].key＞k)

returnbinsearch_2(R,k,low,mid-1);

elsereturnbinseareh_2(R,k,mid+1,high);

}[考点]二分查找算法递归实现6.参考答案：连通网的最小生成树如下图所示：

7.参考答案：栈顶[考点]栈[解析]在栈结构中，允许插入和删除的一端称为栈顶。8.参考答案：B[考点]循环队列的删除[解析]

删除后，front指向2，插入2个元素，rear指向5。9.参考答案：第一趟：[46,58,15,45,90,18,10,62]

一次交换之后

二次交换之后

三次交换之后

四次交换之后

以上“○”表示当前经比较不交换位置的元素。“□”表示当前经比较交换位置的元索。

第一趟：[10181545]46[905862]

第二趟：10[181545]46[6258]90

第三趟：10[15]18[45]46[58]6290

结果：101518454658629010.参考答案：B[解析]本题主要考查的知识点是栈的输出序列。[要点透析]此题可用排除法。栈的出入原则是后进先出。选项B中显示5最先输出，说明其余四个元素已经入栈，其输出序列应为54321。11.参考答案：012.参考答案：B[解析]本题主要考查的知识点是广度优先搜索遍历。[要点透析]连通图广度优先搜索的基本思想是：从图中某个顶点vi出发，在访问了vi之后依次访问vi的所有邻接点，然后依次从这些邻接点出发按广度优先搜索方法遍历图的其他顶点，重复这一过程，直至所有顶点都被访问到。结合图形，本题答案应选B。13.参考答案：C[考点]本题主要考查的是树的结点间关系[解析]除根结点外，树上每个结点可有任意多个孩子、一个双亲。14.参考答案：C[考点]树的性质[解析]任意一棵树的结点个数等于所有结点的出度之和加一，所以叶子结点个数=(1*9+2*8+3*7+4*6+5*5+6*4+7*3+8*2)-(9+8+7+6+5+4+3+2)+1=113。15.参考答案：C[解析]本题主要考查的知识点是二分查找算法对被查找表的要求。[要点透析]相比顺序查找而言，二分查找要求表元素是排好序的。当采用的存储结构不是顺序表，或者顺序表中元素未按键值的次序(递增或递减)排列时，则不能进行二分查找。16.参考答案：算法描述如下：

intlist_isrising(LinkListL)

{LinkListp，q；

p=L-＞next；

if(p==NULL)return0；

if(p-＞next==NULL)return1；

//单个元素是递增的

while(p-＞next!=NULL)

{q=p-＞next；

if(q-＞data＜p-＞data)

return0；//单链表L的元素值非递增

else

p=q；

}

return1；//单链表L的元素值是递增

}17.参考答案：最坏时间复杂度18.参考答案：所求初始堆如下图所示：

19.参考答案：关键字20.参考答案：A[考点]排序算法[解析]根据排序算法具体步骤，可知选择和插入排序算法必须进行n-1趟比较。21.参考答案：A[考点]对称矩阵的压缩存储[解析]只需存放上或下三角和主对角线上的元素，共计n(n+1)/2=55个元素。22.参考答案：D[考点]内部排序和外部排序的区别[解析]外部排序是指在排序的整个过程中，全部数据在计算机的内存储器和外存储器中完成的排序。内部排序仅在内存储器中进行。23.参考答案：能排成序列3，2，5，6，4，1。

过程：push(1)；push(2)；push(3)；pop(3)；pop(2)；push(4)；push(5)；pop(5)；push(6)；pop(6)；pop(4)；pop(1)。不能排成序列1，5，4，6，2，3。

理由：在2，3依次进栈后，根据栈结构的特征不能产生排列2，3。[考点]栈存取的原则，即后进先出24.参考答案：所求哈夫曼树如下图所示：

WPL=(30+17+19)×2+11×3+4×4+(2+3)×5=20625.参考答案：C[考点]无向图边的个数[解析]具有n个顶点的无向图的边数最多为n(n-1)/2。26.参考答案：特殊矩阵[考点]特殊矩阵的定义[解析]如果值相同的元素或者零元素在矩阵中的分布有一定规律，称此类矩阵为特殊矩阵。27.参考答案：数据元素[考点]线性表的定义[解析]线性表是具有n个数据元素的有限序列。28.参考答案：C[考点]冒泡排序的时间复杂度[解析]冒泡排序是稳定的排序方法，其时间复杂度是O(n2)。29.参考答案：A[解析]本题主要考查的知识点是插入排序法。[要点透析]在关键字基本有序的情况下，插入排序每趟的关键字比较次数为1次，总共进行n-1次比较，而在初始关键字无序的情况下，最坏的时候，其关键字的比较的总次数为n(n-1)/2次。而选项中的其他三种排序方法中关键字的比较次数，都与初始状态无关。30.参考答案：A[考点]本题主要考查的是一个具有n个顶点的有向完全的弧数[解析]任何两点之间都有弧的有向图称为有向完全图。—个具有n个顶点的有向完全的弧数为n(n-1)=11*10=110条。31.参考答案：B[考点]线性表的不同存储结构中进行插入、删除运算的时间复杂度[解析]线性表的不同存储结构中进行插入、删除运算的时间复杂度，花费时间最多的是顺序表(由于每次插入、删除都需要移动数据)。32.参考答案：由先序遍历序列和中序遍历序列得到如下二叉树：

后序遍历序列为：CEFDBKHGA。[考点]由先序遍历序列和中序遍历序列推断二叉树。对二叉树进行后序遍历，得到后序序列33.参考答案：简单回路或简单环[考点]简单回路或简单环定义[解析]除第一个顶点和最后一个顶点相同外，其余顶点不重复的回路，称为简单回路或简单环。34.参考答案：C[考点]本题主要考查的知识点是内部排序方法。

题目选项中的四种排序方法中，只有拓扑排序是对图中结点进行排序的方法，不属于内部排序方法，而其他的三种排序方法都属于内部排序方法。35.参考答案：A[考点]数字分析法、除留余数法、平方取中法[解析]解决散列引起的冲突问题，最常用的方法是线性探测法、二次探测法、链地址法。36.参考答案：D[考点]本题主要考查的知识点是森林与二叉树的转换。

换二叉树中右子树的结点个数为第二棵至第五棵树中结点之和。故本题答案为D。37.参考答案：A[考点]算法的评价因素[解析]算法的正确性是指能正确地实现预定功能，满足具体问题的需要。38.参考答案：B[考点]本题主要考查的是数组元素地址的运算[解析]对于m*n的数组采取，行先存储，Loc[i,j]=Loc[0,0]+(