算法设计与分析转贴算法试卷收集3.doc资源-CSDN文库

版权申诉

152 浏览量 2022-05-06 22:12:13 上传评论收藏 28KB DOC 举报

资源推荐

资源详情

资源评论

算法设计与分析转贴算法试卷收集 3

一、填空题(每空 1 分，共 15 分)

1.算法的时间复杂性是算法运行所需要的()的量，这个量应该是只依赖于()、()和

()。

2.通常只考虑三种情况下的时间复杂性，实践表明可操作性最好且最有实用价值

的是()下的时间复杂性。

3.随机存取机 RAM、随机存取存储程序机 RASP 和图灵机这三个计算模型在计算

能力上是()。

4.非确定图灵机与确定图灵机的不同之处是允许()。

5.P 类与 NP 类语言的定义分别为：

P=()NP=()

6.设 L1&Iacute；S1*，L2&Iacute；S2*是两个语言。语言 L1 能在多项式时间

内变换为语言 L2(简记为 L1&micro；PL2)是指存在映射 f：S1*&reg；S2*，且

f 满足：

⑴() ()⑵

7.递归程序常见的形式有四种，它们是()、()、()和()。

二、1.什么是最优子结构性质 2.什么是拟阵，拟阵 M 中极大独立子集有哪些特点

3.什么是 NP 完全语言和 NP 完全语言类 4.解释记号 O、W、q 和 o 的意义 5.回溯

法和分支界限法在本质上分别是什么方法，请说明这两种算法的不同之处。

三、假设某算法 A 的计算时间为 T(n)=3&acute；2n，在某台计算机上实现并完

成该算法的时间为 t 秒。⑴现有另一台计算机，其运行速度为第一台的 256 倍，

那么算法 A 在这台新机器上求解同等规模的问题需要多少时间?⑵ 如果算法 A 的

计算时间改进为 T(n)=n2，其余条件不变，则在新机器上用 t 秒时间能解输入规

模为多大的问题?

四、设 a[0.n– 1]为一个数组，请用分治法设计一个合并排序算法将数组 a 中的元

素递增排序

五、码头上有 n 艘船舶同时等待装卸，而码头每次只能装卸一艘船舶。船舶 i 需要

装卸的时间为 ti，1≤i≤n。应如何安排这 n 艘船舶的装卸次序才能使得总的等待

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余1页未读，立即下载

内容反馈

版权申诉

老帽爬新坡

粉丝: 79
资源: 2万+

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip