《07级计研算法设计与分析试卷》由会员分享，可在线阅读，更多相关《07级计研算法设计与分析试卷（2页珍藏版）》请在金锄头文库上搜索。
1、07 级计算机应用研究生算法设计与分析期未考试试卷题号题号一二三四总分总分得分得分一一 、 填空题填空题 （每题（每题 4 分，共分，共 20 分）分）1。按照渐近阶从低到高的顺序排列以下表达式：。按照渐近阶从低到高的顺序排列以下表达式：., 2 ,20,3 ,log,43/22nnnnn。 2n 位二进制整数位二进制整数 X 分为分为 2 段，高位段是段，高位段是 A，低位段是，低位段是 B，每段的长为，每段的长为 n/2 位，假位，假 设设 n 是是 2 的幂，用的幂，用 A，B 表示表示 X。 3 若若 XA，B，C，B，D，A，B ，YB，D，C，A，B，A,则则 X，Y 的的 一个最
2、长公共子序列是。一个最长公共子序列是。 4 设设 7 个独立作业个独立作业1,2，3,4，5,6，7由由 3 台机器台机器 M1，M2 和和 M3 加工处理。各加工处理。各 作业所需的处理时间分别为作业所需的处理时间分别为2,14,4，16,6，5,3 。按贪心算法（。按贪心算法（greedy 算法）产算法）产 生的作业调度所需要的加工时间为。生的作业调度所需要的加工时间为。 5 在进行问题的计算复杂性分析时，其中最重要的在进行问题的计算复杂性分析时，其中最重要的 3 个计算模型是个计算模型是 ， 。这。这 3 个计算模型在计算能力上是。个计算模型在计算能力上是。二、算法与问答（共算法与问答（
3、共 40 分）分） 1 什么是什么是 P 类语类语 1。什么是。什么是 NP 类语言？什么是类语言？什么是 P 类语言？（类语言？（6 分）分） 2 考虑如下定义的函数考虑如下定义的函数 f(n)请写出计算函数请写出计算函数 f(n)的算法。的算法。 （8 分）分） 0)(nnnf00 nn3 概率算法可分为哪概率算法可分为哪 4 类？（类？（3 分）怎样设计分）怎样设计 k 级完全跳跃链表？（级完全跳跃链表？（3 分）分）4 用数值概率算法的平均值法计算定积分用数值概率算法的平均值法计算定积分（8 分）分）badxxgI)(5 在下图所给的有向图中，每一边都有一个非负边权，要求用优先队列式法
4、求在下图所给的有向图中，每一边都有一个非负边权，要求用优先队列式法求 图的从源顶点图的从源顶点 s 到目标顶点到目标顶点 t 之间的最短路的解空间树的过程，并计算最短路。之间的最短路的解空间树的过程，并计算最短路。 （12 分）分）5 3 2 2 2 63 s 3 9 3 4 t4 2 5 3 22 1 三三 、计算题、计算题1.批处理作业调度问题要求对于给定的 n 个作业，制定最佳作业调度方案，使其完成时 间和达到最小。每一个作业必须先在机器 1 加工后再到机器 2 上加工。下图给出三种作 业及在机器 1，机器 2 的作业时间 ，请算出最佳调度方案（10 分） tji机器 1机器 2作业 1
5、31作业 222作业 3232.6 个作业要在两台机器 M1 和 M2 组成的流水线上完成加工每个作业加工的顺序都是先在 M1 上加工，然后在 M2 上加工。M1 和 M2 加工作业 i 所需的时间分别为。请iiba ,写出.最优调度方案使所需的时间最少？（10 分） 作业 i 机器 j123456131465325434343.Ackerman 函数为如下双递归函数形式 ) 1), 1(),(1)0 ,(1), 0(2)0 , 1 (mmnAAmnAnnAmAA求 A(n,2) (10 分) 四四 、证明题：设、证明题：设 O 表示函数的复杂性的上界。证明 O（f）+O(g)=O(max(f,g) (10 分)
