2022年4月自考02142数据结构导论试题及答案含解析

数据结构导论年月真题

0214220224

1、【单选题】算法时间复杂度指的是

一个算法需要的存储量

一个程序的确切执行时间

A:

算法在给定输入下的计算量

B:

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

C:

答D:案：C

2、【单选题】双向循环链表结点结构为

data、next、node

prior、data、next

A:

rear、data、next

B:

prior、data、rear

C:

答D:案：B

3、【单选题】设顺序表有9个元素.则在第3个元素前插入一个元素所需移动元素的个数为

5

6

A:

7

B:

9

C:

答D:案：C

4、【单选题】队列可以实现

函数的嵌套调用和操作系统中进程调度

函数的嵌套调用和程序递归的处理

A:

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

B:

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

C:

答D:案：D

解析：函数的嵌套调用和程序递归的处理都是使用栈来实现的,操作系统中进程调度、网

络管理中的打印服务等都是用队列来实现的。

5、【单选题】在单链表中，释放已移出结点p的空间使用语句

malloc(p)

sizeof(p)

A:

free(p)

B:

p=NULL

C:

答D:案：C

6、【单选题】循环队列空条件为

CQ.rear==CQ.front

CQ.rear=CQ.front

A:

CQ.rear+1==CQ.front-1

B:

CQ.Rear+1=CQ.front

C:

答D:案：A

7、【单选题】元素的进栈次序为A.B.C,D.E.则出栈中不可能的序列是

A，B，C，D，E

B，C，D，E，A

A:

E，A，B，C，D

B:

E，D，C，B，A

C:

答D:案：C

8、【单选题】满二叉树需满足条件

深度为k(k≥0)

有2K+1个结点

A:

深度为k(k≥0)且有2K个结点

B:

深度为k(k≥1)且有2K-1个结点

C:

答D:案：D

9、【单选题】若二叉树采用二叉链表作为存储结构，要交换其所有分支结点左右子树的位

置，最合适的遍历方法是

先序遍历

中序遍历

A:

后序遍历

B:

层次遍历

C:

答D:案：C

10、【单选题】把特殊矩阵A[10][10]的下三角矩阵压缩存储到一个一维数组M中，则A中

元素a[4][3]在M中所对应的下标位置是

8

12

A:

13

B:

55

C:

答D:案：C

11、【单选题】任何一个带权的无向连通图的最小生成树

只有一棵

一定有多棵

A:

有一棵或多棵

B:

可能不存在

C:

答D:案：C

12、【单选题】有关解决冲突的方法中，描述正确的是

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

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

A:

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

B:

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

C:

答D:案：A

13、【单选题】依次输入键值序列50,72,43,85,75,20,35,45,65,30，建立对应的二叉排序

树以后，查找元素35要进行元素间的比较次数为

4

5

A:

7

B:

10

C:

答D:案：A

14、【单选题】在散列函数H(k)=kMODm中，一般来讲,m应取

奇数

偶数

A:

素数

B:

合数

C:

答D:案：C

15、【单选题】下列序列中，符合堆定义的是

(100,80,55,60,50,40,58,35,20)

(100,80,55,60,50,40,35,58,20)

A:

(100,80,55,58,50,40,60,35,20)

B:

(100,70,55,60,50,40,58,35,20)

C:

答D:案：B

16、【问答题】二叉树的五种基本形态如题29图所示。(1)子树用什么形状表示?(2)分别

写出题29-1图、题29-2图和题29-5图的形态。

答案：(1)方块。(2)空二叉树；左右子树均为空的二叉树；左、右子树都非空的二叉

树。

17、【问答题】给定无向图如题30图所示。(1)计算D(v1)和D(v2)(2)写出以顶点

v0为起点到v3的所有简单路径。

答案：(1)D(v1)=2,D(v2)=3。(2)v0→v1→v2→v3,v0→v2→v3。

18、【问答题】给定一组键值{45,38,66,90,88,10,25,_45_}，假设在排序过程中，前4个

记录已按键值递增顺序重新排列，构成了一个有序序列为(38,45,66,90}。(1)请写出应用

直接插入排序方法对剩余键值排序的排序过程。(2)直接插入排序方法是否稳定？

答案：(1)[3845668890]1025_45_[103845668890]25_45_[10253845

668890]_45_[10253845_45_668890](2)稳定

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

有关问题，给出简单的算法描述。(1)图中有多少条边？(2)任意两个顶点i和j是否有

边相连？(3)任意一个顶点的度是多少？

答案：(1)图中边数等于矩阵中值为1的元素个数除以2。(2)矩阵中第i行和第j列的

元素是否为1。(3)任意一个顶点的度是该顶点所在行（或列）的元素值之和。

20、【问答题】已知散列函数为H(key)=keymod7，构造散列表如题33表，并用线性探测

法解决冲突。若要用该散列表查找元素25,32,68，请分别给出所需的比较次数。

答案：H(25)=25%7=4,比较1次；H(32)=32%7=4与25冲突，探测5，成功。比较2次；

H(68)=68%7=5与32冲突，探测地址6，与48冲突，探测地址0，成功。比较次数3次。

21、【问答题】写出实现对一个n×n阶矩阵进行转置的算法。

答案：

22、【问答题】已知二叉链表的类型定义如下：

假定visit(bt)是一个已定

义的过程，其功能是访问指针bt所指结点。设计在二叉链表上的先序遍历算法和中序遍

历算法。

答案：

23、【填空题】数据及数据的组织方式称为数据的______。

答案：逻辑结构

24、【填空题】设r指向单链表的最后一个结点，要在最后一个结点之后插人s所指的结

点，需执行的语句序列是______；r=s;r->next=NULL。

答案：r->next=s

25、【填空题】栈初始化时，生成一个结点，将该结点的next域设置为______。

答案：NULL

26、【填空题】链队列中，单链表的头结点的next域指向队列______结点。

答案：首

27、【填空题】数组采用______存储结构来存储数据元素。

答案：顺序

28、【填空题】一棵树中所有结点的度的______称为该树的度。

答案：最大值

29、【填空题】由先序序列的第一个结点可以确定这棵树的______结点。

答案：根

30、【填空题】一棵树的最少结点个数为______。

答案：0

31、【填空题】任何两点之间都有边的无向图称为无向______图。

答案：完全

32、【填空题】已知完全二叉树的第7层有