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

2023年自考类计算机类(工学类)数据结构导论历年高频考题带答案难题附详解（图片大小可自由调整）第1卷一.历年考点试题黑钻版(共50题)1.已知数据序列为(14，4，9，20，6，31，24)，对该数据序列进行排序，试写出插入排序和冒泡排序每趟的结果。2.从v1出发，对下图按深度优先搜索遍历，则可能得到的一种顶点序列为______

A.v1v2v3v5v4v6(不变)B.v1v2v3v5v6v4C.v1v5v2v3v6v4D.v1v3v6v4v5v23.有一字符串的次序为-3*y+a/y!2，试利用栈将输出次序改变为3y*-ay!2/+，试写出进栈和退栈的操作步骤(用push(x)表示x进栈，pop(x)表示x退栈)。4.有一份电文中共使用五个字符：a，b，c，d，e，它们的出现频率依次为8，14，10，4，18，请构造相应的哈夫曼树。5.顺序查找算法的平均查找长度为______A.log2nB.(n-1)/2C.n/2D.(n+1)/26.在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为______。7.深度为9的二叉树最多拥有的结点数目是______A.255B.512C.256D.5118.逻辑关系是指数据元素的______A.存储方式B.数据项C.结构D.关联方式9.具有10个顶点的无向图的边数最多为______A.11B.110C.45D.22010.深度为k的完全二叉树至少有______个结点。11.设一个栈的输入序列是a，b，c，d，则所得到的输出序列(输入过程中允许出栈)不可能出现的是______A.a，b，c，dB.c，d，a，bC.d，c，b，aD.a，b，d，c12.______是指将两个或两个以上的有序表合并成一个新的有序表，其算法时间复杂度为______。13.已知一棵完全二叉树中共有768结点，则该树中共有______个叶子结点。14.写出计算方阵A[n][n]与B[n][n]乘积C[n][n]的算法，分析算法的时间复杂度。15.一组记录的键值为(46，74，18，53，14，20，40，38，86，65)，利用堆排序的方法建立的初始堆为______A.(14，18，38，46，65，40，20，53，86，74)B.(14，38，18，46，65，20，40，53，86，74)C.(14，18，20，38，40，46，53，65，74，86)D.(14，86，20，38，40，46，53，65，74，18)16.在队列中存取数据的原则是______A.后进先出B.先进先出C.先进后D.随意进出17.在待排序的n个记录中任取一个记录，以该记录的键值作为标准，将所有记录分为两组，使得第一组中各记录的键值均小于或等于该键值，第二组中的各记录的键值均大于该键值；然后将该记录排在两组中间。再对所分成的两组分别使用上述方法，直到所有记录都排在适当位置为止。这种排序方法称为______。18.对序列{55，46，13，05，94，17，42}进行冒泡排序，第一趟排序后的结果是______。19.二叉排序树中，根的______A.左子树是二叉排序树、右子树不一定是二叉排序树B.左子树是二叉排序树、右子树也是二叉排序树C.左子树不一定是二叉排序树、右子树是二叉排序树D.左子树不一定是二叉排序树、右子树也不一定是二叉排序树20.循环链表中一个结点有多少个指针______A.1B.2C.3D.021.静态查找表的运算包括______A.建表、删除B.建表、查找和读表中元素C.查找和读表中元素D.建表、查找和插入22.已知含五个顶点A，B，C，D，E的连通带权图的邻接矩阵如下图所示，试画出它所表示的连通带权图及该连通带权图的最小生成树。

23.若某二叉树中度为1的结点数为4，度为2的结点数为6，则该树叶子结点数为______。24.三角矩阵可压缩存储到数组哪个中______A.M[n(n+1)/2+1]B.M[n(n+1)/2]C.M[n/2]D.M[(n+1)/2]25.已知一组键值序列(30，45，35，42，53，60，34，22)，试给出采用直接插入排序法对该组序列作升序排序的每一趟结果。26.采用二分查找法，若当前取得的中间位置MID的元素值小于被查找值，则表明待查元素可能在表的后半部分，下次查找的起始位置通常应______A.从MID/2位置开始B.从MID位置开始C.从MID+1位置开始D.从MID-1位置开始27.设有向图G的邻接矩阵为A，如果＜Vi，Vj＞是图中的一条弧，则A[i][j]的值为______。28.一棵完全二叉树上有1001个结点，其中叶子结点的个数是

A.250B.500C.501D.50529.在一个用一维数组A[N]表示的循环队列中，该队列中的元素个数最少为______个，最多为______个。30.设一个链栈的输入序列为X，Y，Z，试写出出栈的所有可能的输出序列及其操作步骤。31.一棵深度为6的满二叉树有______A.63个结点B.64个结点C.127个结点D.128个结点32.元素的进栈次序为1，2，3，…，n，出栈的第一个元素是n，则第k个出栈的元素是______。33.由带权为9，2，5，7，11的5个叶子结点构成的一棵哈夫曼树的带权路径长度是______A.65B.75C.70D.7334.试写出判断带头结点的单链表head中的元素值是否递减的算法。35.从宏观上看，数据组织应分成三个不同的层次，即数据、______和数据项。36.二叉树如下图所示，分别写出其先序遍历、中序遍历和后序遍历的结点访问序列。

37.深度为6的二叉树最多拥有的结点数目是

A.64B.63C.32D.3138.一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为

A.(38，40，46，56，79，84)B.(40，38，46，79，56，84)C.(40，38，46，56，79，84)D.(40，38，46，84，56，79)39.对于具有n个元素的数据序列，若采用二分查找法，当n的值较大时其平均查找长度为______。40.试分别画出下图所示树的孩子链表、孩子兄弟链表。

41.对特殊矩阵采用压缩存储的目的主要是为了______A.表达变得简单B.对矩阵元素的存取变得简单C.去掉矩阵中多余元素D.减少不必要的存储空间42.线性表是一种线性结构，是具有n个______的有限序列。43.无向图中，所有顶点的度数之和是所有边数的______A.0.5倍B.1倍C.2倍D.4倍44.一个有序表A含有15个数据元素，且第一个元素的下标为1，按二分查找算法查找元素A[14]，所比较的元素下标依次是______。45.给定表(85，95，55，75，80，65，45，100)，试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树，并画出插入完成后的二叉排序树。46.对所有相同输入数据量的不同输入数据，算法时间用量的平均值是指______。47.与单链表相比，双链表的优点之一是

A.插入、删除操作更简单B.可以进行随机访问C.可以省略表头指针或表尾指针D.前后访问相邻结点更灵活48.若进栈次序为a，b，c，且进栈和出栈可以穿插进行，则可能出现的含3个元素的出栈序列个数是______A.3B.5C.6D.749.设二叉树根结点的层次为0，一棵高度为h的满二叉树中的结点个数是______A.2hB.2h-1C.2h-1D.2h+1-150.树在数据结构中常采用______、孩子兄弟链表表示法、______三种存储结构表示。第1卷参考答案一.历年考点试题黑钻版1.参考答案：(1)插入排序的每趟结果：

初始值键值序列14

4

9

20

6

31

24

i=2

[4]

14

9

20

6

31

24

i=3

[4

9]

14

20

6

31

24

i=4

[4

9

14]

20

6

3124

i=5

[4

6

914]

20

31

24

i=6

[4

6

914

20]

31

24

i=7

[4

6

914

20

24]

31

(2)冒泡排序的每趟结果：

初始键值序列[14

4

9

20

6

31

24]

第一趟之后

[4

9

14

6

20

24]

31

第二趟之后

[4

9

6

14

20]

24

31

第三趟之后

[4

6

9

14]

20

24

31

第四趟之后

4

6

9

14

20

24

31[考点]插入排序、冒泡排序2.参考答案：D[考点]图的深度优先搜索[解析]本题主要考查的知识点为深度优先搜索遍历。连通图深度优先搜索的基本思想是：从图中某个顶点v1出发，在访问了vi之后，次访问vi的某个vj邻接点，然后从邻接点vj出发按深度优先搜索方法遍历图的其他顶点，重复这一过程，直至所有顶点都被访问到。结合图形，本题答案应选D。3.参考答案：push(-)，push(3)，pop(3)，push(*)，push(y)，pop(y)，pop(*)

pop(-)，push(+)，push(a)，pop(e)，push(/)，push(y)，pop(y)

push(!)，pop(!)，push(2)，pop(2)，pop(/)，pop(+)[考点]栈的存取规则：先进后出4.参考答案：所求哈夫曼树如图所示：

5.参考答案：D[考点]顺序查找算法长度[解析]ASL=(n+1)/2。6.参考答案：图形结构[考点]图形结构的定义[解析]在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为图形结构。7.参考答案：D[考点]二叉树的性质[解析]深度为k(k≥1)的二叉树至多有2k-1个结点。8.参考答案：D[考点]逻辑关系[解析]所谓逻辑关系是指数据元素之间的关联方式或者“邻接关系”。9.参考答案：C[考点]无向图边的个数[解析]具有n个顶点的无向图的边数最多为n(n-1)/2。10.参考答案：2k-111.参考答案：B[考点]元素的进栈操作[解析]元素的进栈操作。12.参考答案：二路归并O(nlog2n)[考点]二路归并定义[解析]二路归并是指将两个或者两个以上的有序表合成—个新的有序表，其算法复杂度为O(nlog2n)。13.参考答案：384[考点]完全二叉树性质[解析]完全二叉树的深度为第九层的结点个数为29-1=256个，前9层的结点个数为2k-1=29-1=511，最后一层结点个数为768-511=257，则叶子结点个数=14.参考答案：算法描述如下：

voidmatrixmultiply(intA[][n]，intB[][n]，intC[][n]，intn)

//求n阶方阵A与B的乘积C

{inti，j；

for(i=0；i＜n；i++)

for(j=0；j＜n；j++)

{c[i][j]=0；

for(k=0；k＜n；k++)

C[i][j]+=A[i][k]*B[k][j]；

}

}

以方阵阶数n作为输入规模。易知第二层循环中的第一条赋值语句共执行n2次，第三层循环体中的乘法和赋值语句共执行n3次，故此算法的计算量为n3+n2，算法时间复杂度T(n)=O(n3)。15.参考答案：B16.参考答案：B17.参考答案：快速排序18.参考答案：46，13，05，55，17，42，94[考点]冒泡排序算法[解析]对序列{55，46，13，05，94，17，42}进行冒泡排序，第一趟排序后的结果是46，13，05，55，17，42，94。19.参考答案：B[考点]二叉排序树的定义[解析]二叉排序树的根的左右子树也分别为二叉排序树。20.参考答案：A[考点]循环链表的特点[解析]循环链表即是将单链表的最后一个结点的指针域指向第一个结点。21.参考答案：B[考点]静态查找表的元素[解析]静态查找表是以具有相同特性的数据元素集合为逻辑结构，包括三种基本运算：建表、查找和读表中元素。22.参考答案：连通带权图如下：

最小生成树如下：

[考点]带权图的邻接矩阵与对应图的转换，带权最小生成树[解析]一个图的最小生成树是图所有生成树中权总和最小的生成树。可用Prim算法构造最小生成树。23.参考答案：724.参考答案：B[考点]三角矩阵的存储[解析]为存储三角矩阵，采用数组M[n(n+1)/2]，把矩阵中上或下三角部分的n(n+1)/2个元素存储在数组M[0]～M[n(n+1)/2-1]的n(n+1)/2个单元中，其中n若非0，则存放在数组M[n(n+1)/2]中。25.参考答案：初始

[30]

45

35

42

53

60

34

22

i=2

[30

45]

35

42

53

60

34

22

i=3

[30

35

45]

42

53

60

34

22

i=4

[30

35

42

45]

53

60

34

22

i=5

[30

35

42

45

53]

60

34

22

i=6

[30

35

42

45

53

60]

34

22

i=7

[30

34

35

42

45

53

60]

22

i=8

[22

30

34

35

42

45

53

60][考点]直接插入排序算法26.参考答案：C[考点]二分查找算法[解析]二分查找算法，由题意可知，当判定在后半部分时，应该将MID+1作为起始位置，再进行二分查找。27.参考答案：1[考点]有向图与邻接矩阵转换[解析]如果＜Vi，Vj＞是图中的一条弧，则A[i][j]的值为1。28.参考答案：C[解析]本题主要考查的知识点是完全二叉树。[要点透析]由二叉树结点的公式：n=n0十n1+n2=n0+n1+(n0-1)=2n0+n1-1，因为n=1001，所以1002=2n0+n1，在完全二叉树中，n1只能取0或1，在本题中只能取0(如果取1则n0=500.5是不可能的)，故n=501。29.参考答案：O

N-130.参考答案：

(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出。31.参考答案：A[考点]满二叉树的定义[解析]一颗深度为k且有2k-1个结点的二叉树称为满二叉树。32.参考答案：n-k+1[考点]出栈操作[解析]出栈第一个是n，第二个是n-1……第k个是n-k+1。n\k为斜体。33.参考答案：B[考点]哈夫曼树WPL[解析]见下图，WPL=(2+5)×3+(7+9+11)×2=21+54=75。

34.参考答案：算法如下：intlist_isfall(LinkListhead)

{LinkListp,q;

p=head-＞next;

if(p==NULL)return0;

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

while(p-＞next!=NULL)

{q=p-＞next;

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

return0;

elsep=q;

}

return1;

}[考点]单链表35.参考答案：数据元素[考点]数据组织的三个不同层次[解析]数据组织应分为三个不同的层次，即数据、数据元素、数据项。36.参考答案：先序遍历：ABDEFC。

中序遍历：BEFDAC。

后序遍历：FEDBCA。[考点]二叉树的先序、中序、后序遍历算法37.参考答案：B[解析]本题主要考查的知识点是二叉树的性质。[要点透析]深度为k(k≥1)的二叉树至多有2k-1个结点。38.参考答案：C[解