一填空题（13分）
1数据结构从逻辑上分（线性）结构和（非线性）结构。
2若广义表中的每个元素都是（原子），则广义表变成为线性表。
3连通图的极小连通子图称为改图的（生成树）。
4哈希（hash）法存储的基本思想是根据（关键字）来决定（存储地址）。
5迪杰斯特拉算法是按（路径长度递增）次序产生最短路径。
6两个字符串相等的充要条件是：两个串的（长度）相等，且（对应位置）的字符相等。
7哈夫曼树是叶子节点（带权路径长度）最短的二叉树。
8稀疏矩阵一般的压缩方法有两种（三元组表）和（十字链表）。
9N个结点的线索树有（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将二叉树的结点按层编号（从根还是往下，同层自左至右）。请设计一算法，将该二叉树的结点按编号从小到大顺序输出。设二叉树用二叉链表表示。