贵州大学理学院数学系信息与计算科学专业
《数据结构》期末考试试题及答案
20032004学年第2学期
一、单项选择题
1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。
A、正确性B可行性C健壮性D输入性2．设S为C语言的语句计算机执行下面算法时，算法的时间复杂度为（）。
fori
1；i0；iforj0；ji；jS；
A、
2BO
lg
CO
DO
2
3．折半查找法适用于（）。
（A）、有序顺序表（B）、有序单链表
（C）、有序顺序表和有序单链表都可以（D）、无限制
4．顺序存储结构的优势是（）。
（A）、利于插入操作（B）、利于删除操作
（C）、利于顺序访问（D）、利于随机访问
5．深度为k的完全二叉树，其叶子结点必在第（）层上。
（A）、k1（B）、k（C）、k1和k（D）、1至k
6．具有60个结点的二叉树，其叶子结点有12个，则度过1的结点数为（
）
（A）、11（B）、13（C）、48（D）、37
7．图的DepthFirstSearchDFS遍历思想实际上是二叉树（）遍历方法
的推广。
（A）、先序（B）、中序（C）、后序（D）、层序
8．在下列链队列Q中，元素a出队的操作序列为（
）
fro
ta
b
c
d∧
rQear（A）、pQfro
t
extp
extQfro
t
ext
（B）、pQfro
t
extQfro
t
extp
ext
（C）、pQrear
extp
extQrear
ext（D）、pQ
extQ
extp
ext
9．Huffma
树的带权路径长度WPL等于（
）
（A）、除根结点之外的所有结点权值之和（B）、所有结点权值之和
（C）、各叶子结点的带权路径长度之和
（D）、根结点的值
10．线索二叉链表是利用（
）域存储后继结点的地址。
第1页共7页
f（A）、lchild
二、填空题
（B）、data（C）、rchild（D）、root
1．逻辑结构决定了算法的
，而存储结构决定了算法
的
。
2．栈和队列都是一种
的线性表，栈的插入和删除只能在
进行。
3．线性表（a1a2…a
）的顺序存储结构中，设每个单元的长度为L，元素ai的存储地址LOCai为
4．已知一双向链表如下指针域名为
ext和prior：
x
y
q
p
e
现将p所指的结点插入到x和y结点之间，其操作步骤
为：
；
；
；
；
5．
个结点无向完全图的的边数为
，

个结点的生成树的边数为
。
6．已知一有向无环图如下：
B
F
D
A
G
CE
任意写出二种拓扑排序序列：
、
。
7．已知二叉树的中序遍历序列为BCA，后序遍历序列为CBA，则该二叉树的先序
遍历序列为
，层序遍历序列为
。
三、应用题
1．设散列函数Hkk13设关键字系列为221224645781321要求用线性探测r