湖南工业大学硕士研究生课程考试试卷《计算理论与算法设计》--20

湖南工业大学硕士研究生课程考试试卷

考试科目：计算理论与算法设计（A 卷）课程编码： 05003 考试形式： 开卷 （开/闭卷）考试时间： 150 分钟 适用年级： 2013 学年学期： 2014学年 第一学期 考生学号： 考生姓名： 考生专业：

考生注意事项：1、本试卷共 5 页，试卷如有缺页或破损，请立即举手报告以便更换。 2、请将全部答案都写在答卷纸上，否则不记分。(答案请写在密封线内)

2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。

一、 单项选择题（每小题2分，共2×10=20分）

1 2 3 4 5 6 7 8 9 10 1. 常见的两种分支限界法为（ ）。

A、广度优先分支限界法与深度优先分支限界法； B、队列式（FIFO）分支限界法与堆栈式分支限界法； C、排列树法与子集树法；

D、队列式（FIFO）分支限界法与优先队列式分支限界法； 2．衡量一个算法好坏的标准是（ ）。

A、运行速度的快慢 B、占用空间的多少 C、时间复杂度和空间复杂度低 D、代码长短 3. 下推自动机与图灵机的不同之处是（ ）。 A、下推自动机比图灵机识别的语言多； B、下推自动机比图灵机识别的语言少； C、下推自动机识别的语言是不可判定； D、拥有一个无限的存储带；

第1页 共5页

4. 如果一个语言是图灵可判定的，则（ ）。

A、对于一个不属于它串s，图灵机计算s时，一定能够到达拒绝状态； B、对于一个不属于它串s，不一定有一个判定器判定s；

C、对于一个不属于它串s，图灵机计算s时，有可能进入无限循环状态； D、对于一个不属于它串s，图灵机计算s时，一定不会停机； 5. 一个集合在条件（ ）下是不可数的。 A、该集合为无限集合； B、组成该集合的元素是实数；

C、该集合的规模大于自然数集合的规模； D、该集合是一个有限的集合；

6. 动态规划算法的基本要素为（ ）。 A、最优子结构性质与贪心选择性质； B、重叠子问题性质与贪心选择性质； C、最优子结构性质与重叠子问题性质； D、预排序与递归调用；

7. 如果A可归约到B且B是可判定的，则（ ）。 A、A也是可判定的 B、A不一定是可判定 C、A是不可判定的 D、A可判定否与B无关 8. NP类语言在图灵机下的定义为（ ）

A、NP={L|L是一个能在非多项式时间内被一台NDTM所接受的语言}； B、NP={L|L是一个能在多项式时间内被一台NDTM所接受的语言}； C、NP={L|L是一个能在多项式时间内被一台DTM所接受的语言}； D、NP={L|L是一个能在多项式时间内被一台NDTM所接受的语言}； 9. k带图灵机的空间复杂性S(n)是指（ ）

A、k带图灵机处理所有长度为n的输入时，在某条带上所用过最大方格数； B、k带图灵机处理所有长度为n的输入时，在k条带上所用过方格数的总和； C、k带图灵机处理所有长度为n的输入时，在k条带上所用过平均方格数； D、k带图灵机处理所有长度为n的输入时，在某条带上所用过最小方格数；

第2页 共5页

10． 如果B是PSPACE-hard，则（ ）。 A、B?NPSPACE B、B?P

C、B?PSPACE D、B一定是NP完全的

二、证明题(每小题10分 共10×2=20分)

1.利用泵引理证明语言C={aibjck|0?i?j?k}不是上下文无关的。(10分)

2.考虑这样的问题，检查图灵机在输入w上，当其读写头处于带最左方格时，是否曾经试图将读写头向左移。将这个问题形式化为一个语言，并证明它是不可判定的。(10分)

第3页 共5页

三、综合应用题 (每小题10分 共10×6=60分)

1.一台DFA M的状态图如右图所示，请写出该DFA的5元组。 (10分)

2.在下图实例上应用Dijkstra算法求结点a到其它所有结点的最短路径。 1)、请用文字描述其算法的基本思路。(10分) 2)、用表格展示出主要的计算过程。

3.请将下述CFG转换成等价的乔姆斯基范式文法。(10分)

A→CAC｜C｜ε C→01｜ε

第4页 共5页

4.上下文无关文法CFG＝（V，∑，R，E），其中V＝｛E，T，F｝，∑＝｛b，

＋，×，(，)｝，规则为： E→E＋T｜T T→T×F｜F F→(E)｜b

请给出如下字符串的派生序列: (10分) 1）、((b)) 2）、b×（b＋b）

5.语言A＝｛w｜w所包含的0的个数不是1的个数的二倍｝是字母表｛0,1｝上的语言，请以实现水平级描述给出判定该语言的图灵机：(10分)

6.设计一个分治算法来找出n个元素中的第2大元素，要求如下：(10分)

1)、要求用文字描述算法的基本思路。 2)、分析其时间复杂度。

第5页 共5页

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库湖南工业大学硕士研究生课程考试试卷《计算理论与算法设计》--20在线全文阅读。