写出要求结果[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.
一,简答问题:(15分)
1.结构化程序设计.
2.简述面向对象开发方法的特点.
3.何谓程序中的千年虫问题,简述一种解决问题的方法.
4. 给出抽象数据类型的特征,并举例说明.
5. 简述广义表属于线性结构的理由.
第 1 页
四.编写程序,统计在输入宇符串中各个不同字符出现的频度并将结果存入文
件(字符串中的合法字符为A-Z这26个字母和0-9这10个数字). [10分]
五.己知两个线性表A ,B均以带头结点的单链表作存储结构,且表中元索按值递增有序排列.设计算法求出A与B的交集C,要求C另开辟存储空间,要求C同样以元素值的递增序的单链表形式存贮[8分]
六,要求二叉树按二叉链表形式存储,
(1)写一个建立二叉树的算法.
(2)写一个判别给定的二叉树是否是完全二叉树的算法.
完全二又树定义力:深度为K.具有N个结点的二又树的每--个结点都与深
度为K的满二叉树中编号从1至N的结点一一对应.此题以此定义为准.[l2分]
七.给定一公园的导游图,自给适当的数据结构,编写算法实现下列要求:
游客从大门进入,选择以一条最佳路线,使游客可以不重复的游览各景点,最后
回到大门. [l0分] "