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

《07级计研算法设计与分析试卷》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、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

2、和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．概率算法

3、可分为哪4类？（3分）怎样设计k级完全跳跃链表？（3分）4．用数值概率算法的平均值法计算定积分（8分）5．在下图所给的有向图中，每一边都有一个非负边权，要求用优先队列式法求图的从源顶点s到目标顶点t之间的最短路的解空间树的过程，并计算最短路。（12分）5322263s3934t4253221三、计算题1.批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。每一个作业必须先在机器1加工后再到机器2上加工。下图给出三种作业及在机器1，机器2的作业时间，请算出最佳调度方案（10分）t机器1机器2作业131

4、作业222作业3232.6个作业要在两台机器M1和M2组成的流水线上完成加工每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为。请写出.最优调度方案使所需的时间最少？（10分）　　作业i　机器j123456131465325434343.Ackerman函数为如下双递归函数形式　　　　　　求　A(n,2)(10分)四、证明题：设O表示函数的复杂性的上界。证明O（f）+O(g)=O(max(f,g))(10分)