算法设计与分析试卷.doc

一、 填空题（每空1分，共15分） 1．算法的时间复杂性是算法运行所需要的（ ）的量，这个量应该是只依赖于（ ）、（ ）和（ ）。 2．通常只考虑三种情况下的时间复杂性，实践表明可操作性最好且最有实用价值的是（ ）下的时间复杂性。 3．随机存取机RAM、随机存取存储程序机RASP和图灵机这三个计算模型在计算能力上是（ ）。 4．非确定图灵机与确定图灵机的不同之处是允许（ ）。 5．P类与NP类语言的定义分别为： P =（ ） NP =（ ） 6．设L11* ，L22* 是两个语言。语言L1能在多项式时间内变换为语言L2（简记为L1PL2 ）是指存在映射f：1* 2*，且f满足： ⑴（ ） ⑵（ ） 7．递归程序常见的形式有四种，它们是（ ）、（ ）、（ ）和（ ）。