哈尔滨工程大学 2002年数据结构试题
一 填空题 (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 将二叉树的结点按层编号(从根还是往下，同层自左至右)。请设计一算法，将该二叉树的结点按编号从小到大顺序输出。设二叉树用二叉链表表示。 | 
