数据结构期末考试试题及答案
期末样卷参考答案
一．是非题（每题1分共10分）
1线性表的链式存储结构优于顺序存储结构。F
2栈和队列也是线性表。如果需要，可对它们中的任一
元素进行操作。F
3．字符串是数据对象特定的线性表。T
4．在单链表P指针所指结点之后插入S结点的操作是：
P
extSS
extP
extF
5．一个无向图的连通分量是其极大的连通子图。T
6．邻接表可以表示有向图，也可以表示无向图。T
7．假设B是一棵树，B′是对应的二叉树。则B的后
根遍历相当于B′的中序遍历。T
8．通常，二叉树的第i层上有2i1个结点。F
9．对于一棵m阶的B树树中每个结点至多有m个关
键字。除根之外的所有非终端结点至少有ém2ù个关键
字。F
10．对于任何待排序序列来说，快速排序均快于起泡排
序。F
二．选择题（每题2分共28分）
1．在下列排序方法中，（c）方法平均时间复杂度为
0
log
，最坏情况下时间复杂度为0
2；（d）方法
所有情况下时间复杂度均为0
log
。
a插入排序b希尔排序c快速排序d堆排
序
2在有
个结点的二叉树的二叉链表表示中，空指针数
为（b）。
a不定
b
1
c

d
1
3下列二叉树中，（a）可用于实现符号不等长高效编
码。
a最优二叉树
b次优查找树
c二叉平衡树
d二叉排序树
4下列查找方法中，（a）适用于查找有序单链表。
a顺序查找
b二分查找
c分块查找
d哈希查找
5在顺序表查找中，为避免查找过程中每一步都检测整
个表是否查找完毕，可采用（a）方法。
a设置监视哨
b链表存贮
c二分查找
d快速查找
6在下列数据结构中，（c）具有先进先出特性，（b）
具有先进后出特性。
a．线性表
b．栈
c．队列
d．广
义表
7．具有m个结点的二叉排序树，其最大深度为（f），
最小深度为（b）。
alog2m
b└log2m┘1cm2
d┌m2┐1
e┌m2┐
fm
8．已知一组待排序的记录关键字初始排列如下：5634582679526437288457。下列选择中（c）是快速排序一趟排序的结果。（b）是希尔排序（初始步长为4）一趟排序的结果。（d）是基数排序一趟排序的结果。（a）是初始堆（大堆顶）。a84，79，64，37，57，52，58，26，28，34，56。b28，34，57，26，56，52，58，37，79，84，64。c28，34，37，26，52，56，64，79，58，84，57。d52，34，64，84，56，26，37，57，58，28，79。e34，56，26，58，52，64，37，28，79，57，84。f34，56，26，58，52，79，37，64，28，84，57。三．填空题（每题2分共20分）1．有向图的存r