中南大学2000年数据结构
填空题(30分)
1.数据结构课程主要研究数据的 结构、 结构，并给出一组 及其相应算法，并评价算法的优劣。
2.输入序列为ABCDE，通过一个堆栈，不可能得到的输出序列有 、 、 、
等。
3.A、B、C三结点为线性链表中的相邻结点，p指针指向A结点，写出将B、C结果交换位置的操作序列 、 、 、 、 、 。
4.已知双枝树的高度为H，求该树最多结点个数为 ，第H层最多有 个结点。该树用具有左、右两个Link的结点的链式结构存储时，共有 个Link域为空。
5.字符串的快速匹配算法(KMP算法)中，匹配的模式串右移位数依赖于模式本身，若K为模式串字符序号，f(k)为失败函数，当模式串p=abcab时，求:f(2)= ，
f(4)= ，f(5)= 。
6.某二维数组M(1…m，1…n)，以列为主行用向量方式存储，写出求元素M(i，j)的地址公式 。
7.用结点表示事件，有向边表示活动，权表示活动持续时间的AOE网表示工程，从起点到终点路径长度 的路径称为关键路径，关键活动、关键事件必然处在某条 路径上。某活动的最早、最迟发生时间 称为关键活动。
8.在快速排序算法中，元素的个数为n，问平均比较次数的时间复杂度为 ，最坏情况下为 。堆排序的最坏情况下的时间复杂度为 。
9.在hash查找中，关键字为k1，k2值 ，而两个hash函数值H(k1)，H(k2) ,这种现象称为 。
10.环形队列中，起始地址为100，存放元素最多100个，每个元素占3个单元，指向当前第1元素的头指针H=370，问该队列最后一个单元地址号为 ，删除15个元素后H= 。
下图为数据流图，弧表示数据流，圆圈表示加工，请用结点表示数据流和加工的链式结构，描述该数据流图。(15分)
在双枝树中，将数据为x的结点，插入数据为A的叶结点，作为其右孩子，写出完成该项操作的非递归算法?在该算法中同时求出该树插入后的高度?(12分)
四、已知有序表共有10个元素，采用折半查找，问找到每个元素的比较次数各为多少?
(10分)
给定一组关键字序列：12，8，9，15，7，16，13，4，10，20，11，14。请给出用快速排序、堆排序、希尔排序(渐减增量序列q=6，3，2，1)各自的第一趟、第二趟排序结果(18分)。
六、阅读下列关于求无向连通图生成树(支撑树)的说明和流程图，填充流程图中a—e框，使之成为完整的流程图。(15分) | 
