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

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