一、填空题（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＋24A4,7
5.设循环队列最大空间为m（0，…，m－1），头，尾指针为front，rear。加入判别队列空的条件是（front＋1）MODm＝rear，那么判别队列满的条件是什么？front，rear的初值应是多少？
答front＝rear初值front＝0rear＝1

四、应用题（25分）
1.对一组记录的关键字（49，38，66，80，75，19，22）进行快速排序，请写出各趟排序后的状态，并说明总共比较了多少次？
2.设哈希表的地址空间为0－6，哈希函数H(K)=KMOD7。请对关键字序列（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.将二叉树的结点按层编号（从根还是往下，同层自左至右）。请设计一算法，将该二叉树的结点按编号从小到大顺序输出。设二叉树用二叉链表表示。