一、简答问题:（15分）
1．结构化程序设计。
2．简述面向对象开发方法的特点。
3．何谓程序中的千年虫问题，简述一种解决问题的方法。
4. 给出抽象数据类型的特征，并举例说明。
5. 简述广义表属于线性结构的理由。
二、写出要求结果[45分]
1． 有函数定义如下，
FUNCTIONGC(M ,N:INTEGERG)：INTEGER；
BEGIN
IF N:=0 THEN GC:=M
ELSE GC：=GC(N,M MOD N)
END
写出此函数功能，并改写它，使其执行速度仅可能的短。
2.设T. M为全程量，有函数定义如下，
FUNTIONA(N:INTEGER)INTEGER
BEGIN
M:=N+M;FA=M;
END
在上程序段中，有如下语句:
M:=10;T:=(M+2)*FA(10); WRILELN(T)
M:=10;T:=FA(10)*(M+2); WRILELN(T)
写出程序输出结果，说明为什么T的输出结果不同的原因。
3.。对以下关键宇序列建立哈希表;(SUN,MON,TUE,WED,THE,FRI,SAT)，哈希函数为H（K）=（关键宇中第一个字母在字母表中的序号）MOD7线性探测法处理冲突，耍求构造一个装填因子为0。7的哈希表;并分别计算出在等概率情况下查找成功与不成功的平均查找长度。
4.。在数轴上有N个彼此相临不交的区间，每个区间下界上界都是整数。N个区间顺序为1一N。要查找给定的X落入的区间号，您认为应怎样组织数据结构，选择什么方法最快，简述原因。
5.。对N个元素组成的线性表进行快速排序时，所需进行的比较次数依赖于这N
个元素的初始排列。对N=7，给出快速排序的一个最好椿情况的初始排列实
例(7个元素可取自集合{l，2，3，4，5，6，7})。
6．在前序线索树上，要找出结点p的直接后继结点，请写出相关浯句
ltag lc data rtag rc
7。给出循环队列中元素个数的计算式(设队最大长度为N,队首指针FROUNT，队尾指针REAR)
8。有向图的拓扑排序能否用图的深度搜索模式来查找?
若能，请简述方法，若不能，请简述原因。
9．写三个形如A=B的语句，完成将单链表LA整表释放的功能。可利用堆栈指针AV。
四．编写程序，统计在输入宇符串中各个不同字符出现的频度并将结果存入文
件（字符串中的合法字符为A-Z这26个字母和0-9这10个数字）. [10分]
五。己知两个线性表A ，B均以带头结点的单链表作存储结构，且表中元索按值递增有序排列。设计算法求出A与B的交集C，要求C另开辟存储空间，要求C同样以元素值的递增序的单链表形式存贮[8分]
六、要求二*树按二*链表形式存储，
（1）写一个建立二*树的算法。
（2）写一个判别给定的二*树是否是完全二*树的算法。
完全二又树定义力:深度为K。具有N个结点的二又树的每--个结点都与深
度为K的满二*树中编号从1至N的结点一一对应。此题以此定义为准。[l2分]
七．给定一公园的导游图，自给适当的数据结构，编写算法实现下列要求:
游客从大门进入，选择以一条最佳路线，使游客可以不重复的游览各景点，最后
回到大门。 [l0分] "
