自考数据结构02331历年试题及答案20092015个人整理版
全国2009年1月自学考试数据结构试题
一、单项选择题本大题共15小题，每小题2分，共30分
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无
分。
1下列程序段的时间复杂度为
9
s0；
fori1；i
；i
forj1；j
；j
sij；
AO1CO2

BO
DO
2
2假设某个带头结点的单链表的头指针为head，则判定该表为空表的条件是
22
AheadNULL；
Bhead
extNULL；
CheadNULL；
Dhead
exthead；
3栈是一种操作受限的线性结构，其操作的主要特征是
32
A先进先出
B后进先出
C进优于出
D出优于进
4假设以数组A
存放循环队列的元素，其头、尾指针分别为fro
t和rear。若设定尾指针指向队列中的队尾元素，头指
针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为

Arearfro
t1％

Brearfro
t％

Cfro
trear1％

Drearfro
t
％

5判断两个串大小的基本准则是
52
A两个串长度的大小
B两个串中首字符的大小
C两个串中大写字母的多少
D对应的第一个不等字符的大小
6二维数组A45按行优先顺序存储，若每个元素占2个存储单元，且第一个元素A00的存储地址为1000，则数组
元素A32的存储地址为
60
A1012
B1017
C1034
D1036
a00
a01
a02
a03
a04
a32
7高度为5的完全二叉树中含有的结点数至少为
72
A16
B17
C31
D32
8已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为

A5
B8
C11
D18
9下列所示各图中是中序线索化二叉树的是A81A
10已知含6个顶点v0，v1，v2，v3，v4，v5的无向图的邻接矩阵如图所示，则从顶点v0出发进行深度优先遍历可能得到的
顶点访问序列为
108
Av0，v1，v2，v5，v4，v3
Bv0，v1，v2，v3，v4，v5
Cv0，v1，v5，v2，v3，v4
Dv0，v1，v4，v5，v2，v3
f11如图所示有向图的一个拓扑序列是

AABCDEF
BFCBEAD
CFEDCBA
DDAEBCF
12下列关键字序列中，构成大根堆的是

A5，8，1，3，9，6，2，7
B9，8，1，7，5，6，2，33
C9，8，6，3，5，l，2，7
D9，8，6，7，5，1，2，3
13对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关键字比较次
数的平均值为
172
A3915
B4915
C5115
D5515
14已知一个散列表如图所示，其散列函数为Hkeykey％11，采用二次探查法处理冲突，则下一个插入的关键字49的地
址为Dd197
15数据库文件是由大量带有结构的A记录r