《数据结构》期末考试试题及答案
20032004学年第2学期
单项选择题1、C2、D3、A4、D5、C6、D7、A8、B9、C10、C
、
1对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为c。
A、正确性
但可行性C健壮性
2设S为C语言的语句计算机执行下面算法时，
fori
1i0iforj0jvijS；
A、
2
BO
lg

CO
D
3折半查找法适用于aA、有序顺序表
。B、有序单链表
C、有序顺序表和有序单链表都可以
D输入性算法的时间复杂度为d
O
2
D、无限制
4顺序存储结构的优势是d。
A、利于插入操作B、利于删除操作
C、利于顺序访问D、利于随机访问5深度为k的完全二叉树，其叶子结点必在第
c层上。
A、k1
B、k
C、k1和k
D、1至
6具有60个结点的二叉树，其叶子结点有
12个，则度过1
A、11
B、13
7图的DepthFirstSearchDFS
C、48
D、37
遍历思想实际上是二叉树
k
的结点数为
a遍历方
法的推广。
A、先序B、中序
C、后序
D、层序
8在下列链队列Q中，元素a出队的操作序列为
fro
t
■b
A、pQfro
t
extp
extQfro
t
extB、pQfro
t
extQfro
t
extp
extC、pQrear
extp
extQrear
extD、pQ
extQ
extp
ext9Huffma
树的带权路径长度WPL等于
A、除根结点之外的所有结点权值之和
C、各叶子结点的带权路径长度之和

B所有结点权值之和、根结点的值D、
f10线索二叉链表是利用c域存储后继结点的地址。
A、Ichild
B、data
C、rchild
D、root
二、填空题
1
计现_______。
2
逻辑结构决定了算法的______________________设，而存储结构决定了算法的__________________实
栈和队列都是一种的线性表，栈的插入和删除只能在
特殊栈顶
进行。
3
aia2…a
的顺序存储结构中，设每个单元的长度为
线性表L元素a
的存储地址LOCa为____________________________4已知一双向链表如下指针域名为
ext和prior
现将p所指的结点插入到x和y结点之间，其操作步骤
___________________________________________________________5
个结点无向完全图的的边数为___________________
个结点的生成树的边数为________________________。6已知一有向无环图如下：
任意写出二种拓扑排序序列：__________________、_______________________。7已知二叉树的中序遍历序列为BCA后序遍历序列为CBA则该二叉树的先序遍历序列为__________________，层序遍历序列为___________________。
三、应用题
1设散列函数Hkk13设关键字系列为221224645781321要求用r