一、问答题
1、不限制GOTO，会带来什么问题。说明GOTO与结构化程序设计的关系。
2、面向对象的程序设计方法的特点是什么？说明封装的含义。
3、什么是函数的副作用？
4、简述数组与字符串属于线性表的理由。
二、选择题
1、在下列算法中，（ ）算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终位置上。
A、堆排序 B、冒泡排序 C、插入排序 D、快速排序
2、堆排序是（ ）类的排序，堆排序平均执行的时间复杂度和需要附加的存储空间复杂度分别是（）
A、插入 B、交换 C、归并 D、基数 E、选择
F、O（n2）和O（1） G、O（nlog2n）和O（1）
H、O（nlog2n）和O（n） I、O（n2）和O（n）
三、写出结果
1、已知二*树有50个叶子结点，则该二*树的总结点数至少应为多少个？
2、在后序线索树中，要找出X结点的前驱结点，请写出相关语句。
Ltag
Lc
Data
Rtag
Rc
3、带权结点为{5，6，7，8，9}，构造Huffman树，计算带权路径长度。
4、对一个堆，按二*树层次进行遍历，是否可以得到一个有序序列，为什么？
5．在快速排序算法中否队列代替栈，说明原因。
6．已知二*树采用二*链表方式存放，要求返回二*树T的后序序列中的第一个结点的指针，是否可不用递归且不用栈来完成？请简述原因。
7．对下面过程写出调用P（3）的运行结果。
PROCEDURE p（w：integer）;
BEGIN
IF w>0 THEN BEGIN
P(w-1);
Writeln(w);{输出W}
P（w-1）
END；
END；
8．已知长度这12 的表（JAN，FEB，MAR，APR，MAY，JUN，JUL，AUG，SEP，OCT，NOV，DEC），按表中顺序依次插入初始为空的二*排序树中。画出整个插入后的二*排序树，并算出在等概率情况下的查找成功的平均查找长度。
四，二*树采用二*链表存储：
1， 编写计算整个二*树高度的算法（二*树的高度也叫二*树的深度）。
2， 编写计算二*树最大宽度的算法（二*树最大宽度是指二*树所有层中结点个数的最大值）。
五，已知某哈希表HT的装填因子小于1，哈希函数H（KEY）为关键字的第一个字母在字母表中的序号。
1． 处理冲突的方法为线性探测开放地址法。编写一个按第一个字母的顺序输出哈希表中所有关键字的程序。
2． 处理冲突的方法为链地址法。编写一个计算在等概率情况下查找不成功的平均查找长度的算法。注意，此算法中规定不能用公式直接求解计算。
六，二*树采用二*链表方式存放，对二*树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其孩子的编号小于其右孩子的编号，请回答采用什么次序的遍历方式实现编号？并给出在二*树中结点的数据部填写实现如上要求编号的非递归算法。
七，设计算法，求出无向连通图中距离顶点V0的最短路径长度（最短路径长度以边数为单位计算）为K的所有的结点，要求尽可能地节省时间。
