一 填空题 （13分）

1 数据结构从逻辑上分（线性）结构和（非线性）结构。
2 若广义表中的每个元素都是（原子），则广义表变成为线性表。
3 连通图的极小连通子图称为改图的（生成树）。
4 哈希（hash）法存储的基本思想是根据（关键字）来决定（存储地址）。
5 迪杰斯特拉算法是按（路径长度递增）次序产生最短路径。
6 两个字符串相等的充要条件是：两个串的（长度）相等，且（对应位置）的字符相等。
7 哈夫曼树是叶子节点（带权路径长度）最短的二叉树。
8 稀疏矩阵一般的压缩方法有两种（三元组表）和（十字链表）。
9 N个结点的线索树有（n+1）根线索。

二 选择题 （12分）

1 一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输入序列是dceab
2 深度为h的4阶B-树（根在第一层，叶子在第h层），叶子结点的数目最少为 2^h-1
3 广义表(a,b,(c,(d,e))) 的尾是 （b,(c,(d,e))）。
4 具有5层结点的平衡二叉树至少有12个结点。
5 设二叉树是由森林变换得来的，若森林中有n个非终端结点，则二叉树中无右孩子的结点有n＋1个。
6 下列不属于内部排序的算法是B
A 归并排序 B 拓扑排序 C 树型排序 D 折半插入排序

三 回答问题（20分）

1 对n个结点的二叉树进行中序遍历，算法中所设的栈，栈中元素最少时可能是多少个？最多时可能是多少个？
答：2个 ，n+1个

2 对n个记录进行简单的插入排序，最少共需要比较多少次？最多共需要比较多少次？
答 最少n－1次 最多1＋2＋3…………＋（n－1）次

3 对13个有序记录进行折半查找，查找成功和不成功的平均查找长度各为多少？
4 采用上三角压缩存储10阶对称矩阵A，若以行序为主存储，且起始地址为d则A3，8的存储地址为多少？它与以列序为主序存储时的哪一个元素的起始位置一致？
答：d＋24 A4,7

5 设循环队列最大空间为m（0，…，m－1），头，尾指针为front，rear。加入判别队列空的条件是（front＋1）MODm＝rear，那么判别队列满的条件是什么？front，rear的初值应是多少？
答 front＝rear 初值front＝0 rear＝1

四 应用题（25分）
1 对一组记录的关键字（49，38，66，80，75，19，22）进行快速排序，请写出各趟排序后的状态，并说明总共比较了多少次？

2 设哈希表的地址空间为0－6，哈希函数H(K)=K MOD 7。请对关键字序列（32，13，49，18，22，38，21）按链地址法解决冲突的办法构造哈希表。并求出查找成功的平均查找长度。

3 已知二叉树的左，右子树各含3个结点。试分别构造满足如下要求的二叉树：（1）左子树的先序序列与中序序列相同，右子树的先序序列与中序序列相同。（2）左子树的中序序列与后序序列相同，右子树的先序序列与中序序列相同。

4 对关键字（67，49，80，14，22，31，95，38，43，56，73）构造平衡二叉树。

5 请写出表达式a+b*(c-d)-e/f的二叉树表示，并使其成为后序线索树。

五 算法题（30分）

1 设计一算法，在单链表中删除数据元素的值相同的多余结点。

2 设计一算法，在中序线索树上求指针P所指结点的前驱结点。

3 将二叉树的结点按层编号（从根还是往下，同层自左至右）。请设计一算法，将该二叉树的结点按编号从小到大顺序输出。设二叉树用二叉链表表示。