Exam 版 (精华区)

发信人: fenggao (kk), 信区: Exam
标  题: t1
发信站: 哈工大紫丁香 (Sat Dec  6 08:50:04 2003), 站内信件


一、 判断题(8分,每小题1分)
1. 线性表的长度是指线性表中元素的个数。
2. 栈是限制只能在一端插入,而在另一端删除的线性表。
3. 二叉树是一种特殊形状的树。
4. 由二叉树的前序、后序遍历序列可以唯一确定这棵二叉树。
5. 所谓带权无向图G的最小生成树T就是将G中各节点间的最短路径作为边所构造出来的G
的子图。
6. 快速排序的记录移动次数小于等于比较次数,其总执行时间为Ο(nlog2n)。
7. 冒泡排序的平均时间复杂度为Ο(n2)。
8.堆排序在平均情况及最坏情况下的时间复杂度均为Ο(nlog2n)。
二、 填空题(24分)
1.(2分)队列是      线性表。
2.(4分)已知二叉树按前序遍历所得到的结点序列为ABDFCEGH,按中序遍历所得到的结
点序列为FDBACGEH,按后序遍历所得到的结点序列为      。
3.(4分)设哈希表长度为13,哈希函数H(k)=k MOD 13, 若输入顺序为(8,10,21,9,6,3
,16,20,7),处理冲突方法为线性探测再散列,请构造哈希表。
          0     1    2    3    4    5    6    7     8    9   10   11   12


4.(9分)给出一组关键字 T=(12,2,16,30,8,28,4,10,20,6,18),执行下列算法从小到大
进行排序,并给出:
1) 冒泡排序第一趟排序结果                          。
2) 快速排序(选第一个记录为枢轴)第一趟排序结果      。
3) 极小化堆排序的初始化堆为                       。
5.(2分)画出具有3个结点的树的所有不同形状        。
    6.(3分)数据1,2,3,4按顺序依次进栈,在各种出栈的序列中,以3先出栈的序列
有      。
三、简答题(24分)
1.(8分)试求按关键字序列(95,89,76,50,32,80,100,130)插入生成二叉排序树的生成过
程和生成结果。
2.(12分)考虑下图:
     1) 从顶点 A 出发,求它的深度优先生成树。
     2) 从顶点 E 出发,求它的广度优先生成树。
     3) 根据普里姆 (Prim) 算法,从顶点D出发,求它的最小生成树。
3.(4分)找出前序序列和后序序列相同的所有二叉树。
四、 程序设计题(24分)
1.(12分)若已知两棵二叉树B1和B2皆为空,或者皆不空且B1的左右子树和B2的左右子树
分别相似,则称二叉树B1和B2相似。试编写算法,判别给定的两棵二叉树是否相似。
2.(12分)假设一个算术表达式中可含有三种括号: 圆括号“(”和“)”,方括号“[”
和“]”,花括号“{”和“}”,且这三种括号可按任意的次序嵌套使用。试利用栈的运算
,编写判别给定表达式中所含括号是否正确配对出现的算法(可设表达式已存入字符型的数
组中)。

--

※ 来源:.哈工大紫丁香 bbs.hit.edu.cn [FROM: 210.46.77.132]
[百宝箱] [返回首页] [上级目录] [根目录] [返回顶部] [刷新] [返回]
Powered by KBS BBS 2.0 (http://dev.kcn.cn)
页面执行时间:5.635毫秒