级计研算法设计与分析试卷.doc

07级计算机应用研究生《算法设计与分析》期未考试试卷
题号
一
二
三
四
总分
得分

一 、 填空题 （每题4分，共20分）
1。按照渐近阶从低到高的顺序排列以下表达式：＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿。
2．n位二进制整数X分为2段，高位段是A，低位段是B，每段的长为n/2位，假设n是2的幂，用A，B表示X＝＿＿＿＿＿＿＿＿＿＿＿＿＿＿。
3． 若X＝｛A，B，C，B，D，A，B｝，Y＝｛B，D，C，A，B，A｝,则X，Y的一个最长公共子序列是＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿。
4． 设7个独立作业｛1,2，3,4，5,6，7｝由3台机器M1，M2和M3加工处理。各作业所需的处理时间分别为｛2,14,4，16,6，5,3｝。按贪心算法（greedy算法）产生的作业调度所需要的加工时间为＿＿＿＿＿＿＿＿＿＿＿＿。
5． 在进行问题的计算复杂性分析时，其中最重要的3个计算模型是＿＿＿＿＿＿＿＿，＿＿＿＿＿＿＿＿＿＿＿＿＿，＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿。这3　个计算模型在计算能力上是＿＿＿＿＿＿＿＿＿＿＿＿＿。
二、算法与问答（共40分）
1． 什么是P类语　　　1。什么是NP类语言？什么是P类语言？（6分）
2． 考虑如下定义的函数f(n)
请写出计算函数f(n)的算法。（8分）
3． 概率算法可分为哪4类？（3分）怎样设计k级完全跳跃链表？（3分）
4． 用数值概率算法的平均值法计算定积分（8分）
5． 在下图所给的有向图中，每一边都有一个非负边权，要求用优先队列式法求图的从源顶点s到目标顶点t之间的最短路的解空间树的过程，并计算最短路。（12分）
5 3
2 2 2 6
3
s 3 9 3 4 t
4 2 5 3 2
2 1
三 、计算题
1. 批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。每一个作业必须先在机器1加工后再到机器2上加工。下图给出三种作业及在机器1，机器2的作业时间 ，请算出最佳调度方案（10分）
t
机器1
机器2
作业1
3
1
作业2
2
2
作业3
2
3
2. 6个作业要在两台机器M1和M2组成的流水线上完成加工每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为。请写出.最优调度方案使所需的时间最少？（10分）
　　作业i　
机器j
1
2
3
4
5
6
1
3
1
4
6
5
3
2
5
4
3
4
3
4
3. Ackerman函数为如下双递归函数形式

　　　　　　求　A(n,2) (10分)
四 、证明题：设O表示函数的复杂性的上界。证明O（f）+O(g)=O(max(f,g)) (10分)