学习好资料
《数据结构》期末考试试题及答案
20032004学年第2学期
单项选择题1、C2、D3、A4、D5、C6、D7、A8、B9、C10、C
一、
1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（c）。
A、正确性B可行性C健壮性D输入性2．设S为C语言的语句计算机执行下面算法时，算法的时间复杂度为（d）。
fori
1；i0；iforj0；ji；jS；
A、
2BO
lg
CO
DO
23．折半查找法适用于（a）。
（A）、有序顺序表（B）、有序单链表（C）、有序顺序表和有序单链表都可以（D）、无限制4．顺序存储结构的优势是（d）。（A）、利于插入操作（B）、利于删除操作（C）、利于顺序访问（D）、利于随机访问5．深度为k的完全二叉树，其叶子结点必在第（c）层上。（A）、k1（B）、k（C）、k1和k（D）、1至k6．具有60个结点的二叉树，其叶子结点有12个，则度过1的结点数为（）（A）、11（B）、13（C）、48（D）、377．图的DepthFirstSearchDFS遍历思想实际上是二叉树（a）遍历方法的推广。（A）、先序（B）、中序（C）、后序（D）、层序
8．在下列链队列Q中，元素a出队的操作序列为（ab）
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等于（c）
（A）、除根结点之外的所有结点权值之和（B）、所有结点权值之和
（C）、各叶子结点的带权路径长度之和
（D）、根结点的值
更多精品文档
f学习好资料
10．线索二叉链表是利用（c）域存储后继结点的地址。
（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．设散列函数Hkk13r