2003 年数据结构期末考题
一. 填空题：(每空 1 分，共 11 分)
1. 设只包含根结点的二叉树的高度为 0，则高度为 k 的二叉树的最大结点数为___________，
最小结点数为_____________。
2. 某二叉树结点的中序遍历序列为 A，B，C，D，E，F，G，后序遍历序列为 B，D，C，
A，F，G，E，则该二叉树结点的前序遍历序列为____________________，该二叉树对应的
树林包括________棵树。
3. 设有关键码序列（Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增
的次序进行排序，若采用初始步长为 4 的 Shell(希尔)排序法，则一趟扫描的结果是
____________________________________________；若采用以第一个元素为分界元素的快速
排序法，则一趟扫描的结果是___________________________________________________。
4. 对于顺序存储的栈，因为栈的空间是有限的，在进行_______操作时，可能发生栈的上溢，
在进行________操作时，可能发生栈的下溢。
5. 用起泡法对n
个关键码排序，在最好情况下，只需做_____________次比较和____________
次移动；在最坏的情况下要做_________________次比较。
二．判断题(下列各题，你认为正确的，请在题干的括号内打
“√”，错的打“×”。)(每题 1 分，共 10 分)
1. 数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个
方面 ( )
2. 线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。( )
3. 栈和队列逻辑上都是线性表。 ( )
4. 单链表从任何一个结点出发，都能访问到所有结点。( )
5. 将一棵树转换成二叉树后，根结点没有左子树。 ( )
6．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。 ( )
7．用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。 ( )
8．在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同。( )
9．线性表采用顺序存储表示时，必须占用一片连续的存储单元。( )
10．快速排序是一种稳定的排序方法。( )
三. 单项选择题，从每小题后给出的答案中选择一个正确的
答案填入括号内。(每题 1 分，共 9 分)
1. 若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间复
杂度为( )。(1≤i≤n+1)
评论0