2016年4月高等教育自学考试全国统一命题考试
数据结构导论试卷
课程代码02142
本试卷共6页。满分l00分，考试时间l50分钟。考生答题注意事项：1．本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸。2．第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。3．第二部分为非选择题。必须注明大、小题号，使用0．5毫米黑色字迹签字笔作答。4．合理安排答题空间，超出答题区域无效。
第一部分选择题共30分
一、单项选择题本大题共l5小题。每小题2分，共30分
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题卡”的相应代码涂黑。错涂、多
涂或未涂均无分。
1．一个公司的组织机构是1名公司经理领导若于名部门负责人、每个部门负责人领导若干名部门员工，则适合于
描述该公司组织机构的逻辑结构是
A．线性表
B．队列
C．树
D．图
2．计算
整数
≥0的递归算法是：i
tFactoriali
t
if
oretur
l；elseretur

Factorial
1；其时闯复杂度为
A．0

B．0log2

C．O
0
D．O
2
3．将一个由指针q指向的结点插在单链表中由指针P所指向的结点之后的操作是
A．pq；
B．p：
extq；
C．q一
extp：
ext；p
extq；
D．p一
extq；q
extp：
ext；
4设初始栈为空，s表示人栈操作，x表示出栈操作，则合法的操作序列是
A．sxxssxxs
B．ssxsxxxs
C．ssxxxssx
D．sssxxxsx
5．将递归形式描述的算法改写为功能等价的非递归形式描述的算法，通常应设置的辅助结构是
A．顺序表
B．单链表
C．栈
D．队列
6．设长度为
的队列用单循环链表表示假设表尾结点为当前队列的队尾元素，若只设头指针，则入队操作、出
队操作的时间复杂度分别为
A．O
、O1
B．O1、O1
C．O1、O

D．0
、0

7．若采用顺序存储一维数组结构存储一棵如题7图所示的二叉树，根结点1的下标为l，剥结点4的下标为
A．4
B．5
C．6
D．7
8．按层序自顶向下、从左到右遍历二叉树时需借助队列作辅助结构。对高度为3的满二叉树进行层序遍历时，
队列中所出现的元素个数最多是
A．1
B．2
C．3
D4
9．一个数组的第一个元素的存储地址是i00，每个元素占2个存储单元，则第5个元素的存储地址是
A．120
B．110
C．108
D100
10．已知含6个顶点v0，v1，v2，v3，v4，v5的无向图的邻接矩阵如题10图所示，则从顶点V0出发进行深度优先搜
索可能得到的顶点访问序列为
fA．v0，v1，v2，v5，v4，v3
B．v0，v1，v2，v3，v4，v5
C．v0，vr