数据结构期末考试7.doc

班级： 专业： 姓名： 考号： 密 封 装 订 线信息技术学院2006-2007学年第二学期期末考试一、判断题（10分，每题1分）1、进行折半搜索的表必须是顺序存储的有序表。（ ）2、已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。（ ）3、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。（ ）4、带权连通图中某一顶点到图中另一顶点的最短路径不一定唯一。（ ）5、邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。（ ）6、无向图的邻接矩阵是对称的，有向图的邻接矩阵是不对称的。（ ）7、删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。（ ）8、一个好的哈希函数应使函数值均匀的分布在存储空间的有效地址范围内，以尽可能减少冲突。（ ）9、直接选择排序是一种不稳定的排序方法。（ ）10、在平均情况下，快速排序法最快，堆积排序法最节省空间。（ ）二、填空题（20分，每题2分）1. 假定一棵树的广义表表示为A(B(C, D(E, F,G), H(I, J)，则结点D的孩子结点为_。2. 对于一颗具有n个结点的二叉树，对应二叉链表中指针域总数为_个。3. 在一棵二叉树的第5层上，最多具有_个结点。4. 下图所示二叉树存储在一维数组中，则元素F的下标位置为_。ABCDEF5. 对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小为_。6. 若要对某二叉排序树进行遍历，保证输出元素的值序列按增序排列，应对该二叉排序树采用_遍历法。7. 元素关键字转换为该元素存储位置的函数f称为_。8. 每次从无序表中挑选出一个最大或最小元素，把它交换到有序表的一端，此种排序方法叫做_排序。9. 假定一组数据的关键字为46,79,56,38,40,84，则以第一个记录为枢轴，对其进行第一趟快速排序的结果为_。10. 对20个记录进行归并排序时，在第二趟归并时是把长度为_的有序表两两归并为长度为_的有序表。三、选择题（20分，每题2分）1. 一棵具有32个结点的完全二叉树的深度为_。A. 6 B. 7 C. 5 D. 82. 在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加_。A. 2 B. 1 C. 0 D. -13. 在一棵具有n个结点的二叉树中，所有结点的空子树个数等于_。A. n B. n-1 C. n+1 D. 2*n4. 顶点个数为n的无向图最多有_条边。A. n-1 B. n(n-1)/2 C. n(n+1)/2 D. n(n-1)5. 具有e条边的无向图，它的邻接表中有_个边结点。A. e-1 B. e C. 2(e-1) D. 2e6. 有向图的一个顶点的度为该顶点的_。A. 入度 B. 出度 C. 入度与出度之和 D. (入度出度)/27. 长度为m的哈希表，采用线性探测再散列处理冲突，假定对一个元素第一次计算的存储地址为d，则下一次的存储地址为_。A. d B. d+1 C. (d+1)/m D. (d+1)%m8. 对线性表进行折半查找时，要求线性表必须_。A. 以顺序方式存储B. 以链接方式存储C. 以顺序方式存储，且元素按关键字有序排序D. 以链接方式存储，且元素按关键字有序排序9. 用某种排序方法对关键字序列（23，72，21，47，15，27，59，35，20）进行排序时，前三趟的结果情况如下： 23，21，47，15，27，59，35，20，72 21，23，15，27，47，35，20，59，72 21，15，23，27，35，20，47，59，72则所采用的排序方法是_。A.选择排序 B.起泡排序 C.归并排序 D.快速排序10. 若对n个元素进行直接插入排序，在进行i趟(2in)排序时，为寻找插入位置最多需要进行_次元素的比较。A. i+1 B. i-1 C. i D. 1四、应用题（30分，每题6分）1. 已知一棵二叉树的先根和中根序列，求其后根序列。（6分）先根序列：A, B, C, D, E, F, G, H, I, J中根序列：C, B, A, E, F, D, I, H, J,G后根序列：2. 对于下面两个图，求出：（1） 无向图中每个顶点的度，有向图中每个顶点的入度，出度和度。（2） 是否是连通图/强连通图，如果不是，画出连通分量/强连通分量。（6分）01243403123. 分别画出在线性表(a, b, c, d, e, f, g)中进行折半查找，以查关键字等于e、f和g的过程。（6分）4. 已知一组元素的关键字46,74,16,53,14,26,40,38,86,65,27,34，利用堆排序法，画出建立小顶堆和利用堆排序的过程。（6分）5用序列（46，88，45，39，70，58，101，10，66，34）建立一个平衡的二叉排序树，画出该树。（6分）五、程序题（20分）1. 将下面算法填完整。（10分，每空2分）int Search_Bin(SSTable ST, KeyType key) /在有序表ST中折半查找其关键字等于key的数据元素，若找到，则返回该元素/在表中的位置，否则返回0 low=1;high=ST.length; while(low=high) mid=_; if(EQ(key, ST.elemmid.key) return _; else if(LT(key, ST.elemmid.key) high=_; else low=_; return _;2. 将下面算法填完整。（10分，每空2分）void InsertSort(SqList &L)/对顺序表L作直接插入排序for(i=2;i=L