一、 回答下述问题（25分）

1、 已知10万个无序的，且互不相等的正整数，现要求找出前10个最大的正整数。采用以下五种分类法：快速分类法，合并分类法，选择分类法，堆分类法，SHELL分类法。试问，那一种方法将能最快地找出这前十个最大的正整数？为什么？

2、 在外部分类时，常采用多阶段合并分类法。假定采用二路多阶段合并分类法。合并开始时，磁带T1分布有Fs-1个合并段，磁带T2分布有Fs-2个合并段，磁带T3为空白带，假定每个合并段都有M个记录。注意，Fs-1,Fs-2分别为fibonacci数列的第S－1及S－2项。试推导出在合并分类结束时，记录读写的总次数9（推导出和式即可）

3、 求下列样品的失效函数：

(1) P1=aaaaaa

(2) P2=abcabdaaabc

(3) P3=abcabdabeabc

4、 已知字母a,b,c,d,e,f,g,h的使用频率分别为40%,20%,10%,8%,8%,5%,5%,4%；给出这8个字符的HUFFUMAN编码，要求给出求解步骤。

5、 可否使用拓扑分类算法，确定所给有向图是否有回路？如何实现，为什么？

6、 求出下图的关键路径，结点的最早完成时间，结点的最晚完成时间及关键活动。

二、（15分）

设计一个程序，以一序列正整数，如：78，45，2，14，23，…作为输入，生成一棵中序穿线二叉树。

三、（10分）

已知一棵以标准形式存贮的三次有序树。设计一个程序，将该有序树转化成相应的二叉树（同样以标准形式存贮）。

四、（10分）

假定在平衡分类二叉树中，进行结点删除操作之后，出现了不平衡。试作图说明，如何针对各种不平衡的情况进行调整，使该数恢复为平衡分类二叉树。

五、（10分）

研制一程序，将十进制数N转换为R（2<=R>=16）进制数的数字串。

六、（15分）

回答问题

1、 你认为评价程序质量的标准是什么？

2、 什么是函数的副作用？

七、（15分）

研制一个求K个数的最大公约数的程序。