​2022年4月自考02142数据结构导论真题试卷

下文是希赛自考频道整理的2022年4月自考02142数据结构导论真题试卷，想要查看更多自考真题，可以查阅【自考历年真题】【2022年自考真题汇总】【自考题库app下载】。

2022年4月高等教育自学考试全国统一命题考试数据结构导论试题

(课程代码：02142)

注意事项:

1.本试卷分为两部分,第一部分为选择题,第二部分为非选择题。

2.应考者必须按试题顺序在答题卡(纸)指定位置上作答，答在试卷上无效。

3.涂写部分、画图部分必须使用2B铅笔,书写部分必须使用黑色字迹签字笔。

一、 单项选择题:本大题共15小题，每小题2分,共30分。在每小题列出的备选项中只有一项是最符合题目要求的，请将其选出。

1.算法时间复杂度指的是

A.一个算法需要的存储量

B.一个程序的确切执行时间

C.算法在给定输人下的计算量

D.算法在给定时间下的计算量

2.双向循环链表结点结构为

A. data .next、node.

B. prior idata ,next

C. rear、data、next.

D. prior、data、rear

3.设顺序表有9个元素,则在第3个元素前插人一个元索所需移动元素的个数为

A.5

B.6

C.7

D.9

4.队列可以实现

A.函數的嵌套调用和操作系统中进程调度

B.函数的嵌套调用和程序递妇的处理

C.程序递归的处理和操作系统中进程调度

D.操作系统中进程调度和网络管理中的打印服务

5.在单链表中,释放已移出结点p的空间使用语句

A. malloc(p)

B. sizeof(p)

C. free(p)

D. p= NULL

6.循环队列空条件为

A. CQ. tear= = CQ. front

B. CQ. rear= CQ. front

C. CQ. rear+1== CQ. front+1

D. CQ. rear+1=CQ. front

7.元索的进栈次序为A,B,C.D,E,则出栈中不可能的序列是

A. A,B,C,D,E

B. B,C,D,E,A

C. E,A,B,C,D

D. E,D,C,B,A

8.满二叉树需满足条件

A.深度为k(k≥0)

B.有+1个结点

C.深度为k(k≥0)且有个结点，

D.深度为k(k≥1)且有一1个结点

9.若二叉树采用二叉链表作为存储结构,要交换其所有分支结点左右子树的位置，最合适的

遍历方法是

A.先序遍历

B.中序遍历

C.后序遍历

D.层次遍历

10.把特殊矩阵A[10][10]的下三角矩阵压缩存储到一个一维数组M中,则A中元素a[4][3]在M中所对应的下标位置是

A.8

B.12

C.13

D.55

11.任何一个带权的无向连通图的最小生成树

A.只有一棵

B.一定有多棵

C.有一棵或多棵

D.可能不存在

12.有关解决冲突的方法中，描述正确的是.

A.多重散列法不易产生“堆积”

B.线性探测法生成后继散列地址计算复杂

C.二次探测法生成的后继散列地址是连续的

D.二次探测法容易探测到整个散列表的所有空间

13,依次输人键值序列50,72,43, 85.75.20,35,45,65,30,建立对应的二叉排序树以后查找元素35要进行元素间的比较次数为

A.4

B.5

C.7

D.10

14.在散列函数H(k)=k MOD m中，一般来讲,m应取

A.奇数

B.偶数

C.素数

D.合数

15. 下列序列中,符合堆定义的是

A. (100.80.55.60.50.40.58.35.20)

B. (100.80.55.60.50.40.35.58.20)

C. (100.80.55.58.50.40.60.35.20)

D. (100.70.55.60.50.40.58.35.20)

二、填空题:本大题共13空,每空2分,共26分。

16.数据及数据的组织方式称为数据的_________。

17.设r指向单链表的最后一个结点,要在最后一个结点之后插人s所指的结点，需执行的语句序列是_________；r=s;r->next= NULL。

18.栈初始化时,生成一个结点,将该结点的next域设置为_________。

19.链队列中，单链表的头结点的next域指向队列_________结点。

20.数组采用_________存储结构来存储数据元素。

21.-棵树中所有结点的度的_________称为该树的度。

22.由先序序列的第一一个结 点可以确定这棵树的_________结点。

23.一棵树的最少结点个数为_________。

24.任何两点之间都有边的无向图称为无向_________图。

25.已知完全二叉树的第7层有20个结点,则整个完全二叉树的叶子结点数是_________。

26.任何一个无环有向图,其全部顶点可以排成一个_________序列。

27.稀疏矩阵可以采用_________表示法进行压缩存储。

28.相同键值的两个记录在排序前后相对位置的变化情况是排序算法研究中经常关注的一个问题,这个问题称为排序算法的_________。

三、应用题:本大题共5小题,每小题6分,共30分。

29.二叉树的五种基本形态如题29图所示。(1)子树用什么形状表示? (2)分别写出题29-1图、题29-2图和题29-5图的形态。

30.给定无向图如题30图所示。

(1)计算D(V1 )和D(V2)。

(2)写出以顶点Vo为起点到V3的所有简单路径。

31.给定一组键值{45,38,66 ,90 ,88,10,25.45}，假设在排序过程中,前4个记录已按键值递增

顺序重新排列,构成了一个有序序列为{38,45,66,90}.

(1)请写出应用直接插人排序方法对剩余键值排序的排序过程。

(2)直接插人排序方法是否稳定?

32,设有m个顶点的无向图G,采用邻接矩阵作存储结构，在邻接矩阵上判断下列有关问题，

给出简单的算法描述。

(1)图中有多少条边?

(2)任意两个顶点i和j是否有边相连?

(3)任意一个顶点的度是多少?

33.已知散列西数为H(key)=keymod7,构造散列表如题33表,并用线性探测法解决冲突。

若要用该散列表查找元索25,32,68,请分别给出所需的比较次数。

题33表

四、算法设计题:本大题共2小题,每小题7分,共14分。

34,写出实现对一个nX n阶矩阵进行转置的算法。

35.已知二叉链表的类型定义如下:

假定visit(bt)是一个已定义的过程,其功能是访问指针bt所指结点。设计在二叉链表上的先序遍历算法和中序遍历算法。