2022年10月重庆自考02331 《数据结构》 真题

1 .请考生按规定将所有问题的答案用钢笔涂掉并写在答案纸上。

2 .答题前，考生必须用黑字签字笔或钢笔将自己的考试课程名称、姓名、准考证号填写在答题纸上的规定位置。

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

1 .在以下选项中，以链式保存的是

a .序列堆栈

b .三元组

c .二叉链表

d .邻接矩阵

2 .在线性表中采用顺序存储的好处是

a .插入运算容易

b .便于删除运算

c .存储空间不必是连续的

d .可随机访问各要素

3 .起始节点的单链接列表l的起始指针为head，节点结构如下。

，求出l不为空时的判定条件为“真”，则正确的公式为

a .头下一步！=空

B. head-next=NULL

C. head！=头

D. head=NULL

4. n阶方阵a是对称矩阵。 现在，使用一维排列b逐行优先存储a的上三角部分。 b的要素数至少

a.NX(n1 )/2

b.NX(n-1 )/2

C. nxn/2

D. n

5 .广义表是已知的

LS的深度是

A.5

B.4

C.3

D.2

6 .具有20个节点的二叉树t依次被收纳在数组b中。 假设在B[7]中保存了的节点v，则保存v的父节点是因为

A. B[0]。

B. B[2]。

C. B[3]。

D. B[4]。

7 .在非空二叉树中顺序扫描序列中，位于根节点之后的是

a .左侧子树的部分节点

b .右子树的部分节点

c .左侧子树的所有节点

d .右子树的所有节点

8 .在以下关于二叉树和森林相互转换的描述中，正确的是

a .将二叉树转换为森林时，获得的森林不是唯一的

b .将二叉树转换为森林时，得到的森林一定是唯一的

c .将森林转换为二叉树时，得到的二叉树不是唯一的

D .将森林转换为二叉树时，得到的二叉树可能不是唯一的

9 .在有向图g中，如果顶点v的出度和入度都是2，则g中的弧数最少

A.5

B.4

C.3

D.2

10 .对下图进行拓扑排序后，可以获得以下拓扑顺序

a.3、1、2、4、5、6

b.3、1、2、4、6、5

c.3、1、4、2、5、6

d.3、1、4、2、6、5

11 .如果初始关键字序列为15、10、12、5、48、30，按升序直接进行插入排序，则三次排序的结果为

a.5、10、12、15、48和30

b.5、10、12、15、30和48

c.10、15、12、5、48和30

d.10、12、15、5、48和30

12 .在以下排序方法中，排序期间使用的辅助区域不是0(1)的是

a .直接插入排序

b .冒泡排序

c .希尔排序

d .基数排序

13 .在以下关于二叉树t操作的描述中，正确的是

在A.T中删除一个关键词时，树的高度一定要减去1

即使在b.t中删除一个关键词，树的高度也不会改变

在c.t中插入新关键词时，树的高度必须加1

d .用t寻找某个关键词时，树的高度不变

14 .哈希表长度m=7，哈希函数h(key )=key %7，用线性探测方法处理冲突。 表中保存了h(21 )=0，h )8)=1，h ) 25 )=4这三个关键词，剩下的地址都是开放地址。 在此插入关键字14。 散列表的下标地址是

A.0

B. 1

C.2

D.3

15 .当按顺序搜索数据序列时，必须满足以下条件

a .数据必须保存在数组中

b .数据必须保存在链表中

c .数据必须按升序排列

d .数据应可进行比较操作

二、填空题：本大题共10小题，每小题2分，共20分。

16 .数据运算在数据的________结构中定义。

17 .在非空线性表中，没有前导的元素称为_ _ _ _ _ _。

18 .使用数组保存的堆栈为_________。

19 .如果设置广义表l(a，b )、c，d，e )、f )、g )、h )，则head ) head(l ) )的结果为_____。

20 .在非空二叉树t的前(先)序扫描序列中，第一个元素是_ _ _ _ _ _。

21 .图g的遍历过程实际上是对各个顶点搜索_________的过程。

22 .如果有向图g中存在拓扑序列，则序列中第一个顶点的入度值为_ _ _ _ _ _。

23 .快速排序划分数据序列。 为此，请选择元素作为________。

24 .要按升序对数据序列进行排序，请首先创建初始序列，作为_ _ _ _ _ _。

25 .散列方式中，实现关键字到存储地址的映射是_ _ _ _ _ _。

三、解答题：本大题共4小题，每小题5分，共20分。

26 .二叉树t的前相遍历序列为ABDEHCFGI，中相遍历序列为DBHEAFCIG。 请画一棵树t。

27 .问题27求解图27所示连通网的最小生成树，计算最小生成树的权重。

28 .有以下关键词序列( 25、30、14、2、21、36、51、3 ) )，采用双路归并排序进行升序排序，给出归并过程。

29 .有一组关键字( 2、13、18、25、30、33、36、55 )。 请绘制描述二叉树以描述二叉树搜索过程。

四、算法阅读题：本大题共4小题，每小题5分，共20分。

30 .链表的类型定义如下：