2024年4月30日发(作者：)

…………………………………………………………精品自学考试资料推荐………………………………………………

全国2018年1月高等教育自学考试

数据结构试题

课程代码：02331

一、单项选择题（本大题共15小题，每小题2分，共30分）

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的

括号内。错选、多选或未选均无分。

1.逻辑上通常可以将数据结构分为（ ）

A.动态结构和静态结构

C.线性结构和非线性结构

B.顺序结构和链式结构

D.初等结构和组合结构

2.在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是（ ）

A.访问第i个元素的前驱（1<

in

）

B.在第i个元素之后插入一个新元素(

1in

)

C.删除第i个元素(

1in

)

D.对顺序表中元素进行排序

3.假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（ ）

= =NULL

!=NULL

–>next= =NULL

–>next= =head

4.已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,

则可能出现的出栈序列为（ ）

A.5，4，3，2，1，6

C.3，2，5，4，1，6

B.2，3，5，6，1，4

D.1，4，6，5，2，3

5.与线性表相比，串的插入和删除操作的特点是（ ）

A.通常以串整体作为操作对象

C.算法的时间复杂度较高

B.需要更多的辅助空间

D.涉及移动的元素更多

6.假设以三元组表表示稀疏矩阵，则与如图所示三元组表对应的4×5的稀疏矩阵是（注：

矩阵的行列下标均从1开始）（ ）



08



0



7

A.



00





50



060





000



000





400







08



0



7

B.



50





00



1

060





003



400





000





…………………………………………………………精品自学考试资料推荐………………………………………………





08060





08060



C.



00003







D.



70000





70000













50403



50400











00000







7.以下有关广义表的表述中，正确的是（ ）

A.由0个或多个原子或子表构成的有限序列

B.至少有一个元素是子表

C.不能递归定义

D.不能为空表

8.树的先根序列等同于与该树对应的二叉树的（ ）

A.先序序列 B.中序序列

C.后序序列 D.层序序列

9.假设有

．

向图含n个顶点及e条弧，则表示该图的邻接表中包含的弧结点个数为（

A.n B.e

C.2e D.n·e

10.如图所示的有向无环图可以得到的不同拓扑序列的个数为（ ）

A.1 B.2

C.3 D.4

11.下列排序方法中，稳定的排序方法为（ ）

A.希尔排序 B.堆排序

C.快速排序 D.直接插入排序

12.对下列关键字序列进行快速排序时，所需进行比较次数最少的是（ ）

A.（1，2，3，4，5，6，7，8） B.（8，7，6，5，4，3，2，1）

C.（4，3，8，6，1，7，5，2） D.（2，1，5，4，3，6，7，8）

13.含n个关键字的二叉排序树的平均查找长度主要取决于（ ）

A.关键字的个数 B.树的形态

C.关键字的取值范围 D.关键字的数据类型

14.下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是（ ）

2

）

…………………………………………………………精品自学考试资料推荐………………………………………………

A.分块查找

C.二分查找

B.顺序查找

D.散列查找

15.可有效提高次关键字查找效率的文件是（ ）

A.顺序文件

C.散列文件

B.倒排文件

文件

二、填空题（本大题共10小题，每小题2分，共20分）

请在每小题的空格中填上正确答案。错填、不填均无分。

16.数据的存储结构是其逻辑结构___________。

17.输入线性表的n个元素建立带头结点的单链表，其时间复杂度为___________。

18.假设循环队列的元素存储空间大小为m，队头指针f指向队头元素，队尾指针r指向队

尾元素的下一个位置，则在少用一个元素空间的前提下，表示“队满”的条件是

___________。

19.给定串的联接操作函数：

char *strcat(char *to, char *from);

//将串from联接到串to的末尾，并返回联接后的串

若字符串s1=〞point〞,s2=〞of〞,则strcat(s1,strcat)(s2,s1))的操作结果是___________。

20.假设二维数组A[8][10]按行优先顺序存储,若每个元素占2个存储单元,元素A[0][0]的存储

地址为100,则元素A[4][5]的存储地址为___________。

21.假设一棵完全二叉树含1000个结点,则其中度为2的结点数为___________。

22.已知一个有向网如图所示,从顶点1到顶点4的最短路径长度为___________。

23.在快速排序、堆排序和归并排序中，最坏时间复杂度为O(n

2

)的排序算法有___________。

24.假设散列表的表长为11,散列函数为H(key)=key%7,若用线性探测处理冲突,则探查地址序

列hi的计算公式为___________

(i1,2,,10)

。

文件由___________，___________和数据集三部分组成。

三、解答题（本大题共4小题，每小题5分，共20分）

3

…………………………………………………………精品自学考试资料推荐………………………………………………

26.已知广义表的图形表示如图所示,

(1) 写出该广义表L;

(2) 分别写出该广义表的深度和长度。

(1)

(2)

27.已知二叉树的先序序列和中序序列分别为ABDEHCFI和DBHEACIF，

(1) 画出该二叉树的二叉链表存储表示;

(2) 写出该二叉树的后序序列。

(1)

(2)

28.已知有向图的邻接表如图所示,

(1) 写出从顶点A出发,对该图进行广度优先搜索遍历的顶点序列;

(2) 画出该有向图的逆邻接表。

．

(1)

(2)

29.依次读入给定的整数序列{7，16，4，8，20，9，6，18，5}，完成下列操作：

1)构造一棵二叉排序树,计算在等概率情况下该二叉排序树的平均查找长度ASL;

2)若变更序列中元素的排列,可构造出平均查找长度达到最小的二叉排序树。写出满足上

述要求的序列中的第一个元素。

(1)

(2)

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

30.假设以带头结点的单链表表示线性表,阅读下列算法f30,并回答问题:

(1) 设线性表为( a

1

, a

2

, a

3

, a

4

, a

5

, a

6

, a

7

), 写出执行算法f30后的线性表；

4