高级中学信息技术算法与程序设计章节练习(2019.05.07)

填空题
算法的复杂性有（）和（）之分，衡量一个算法好坏的标准是（）。
答案：时间复杂性；空间复杂性；时间复杂度高低
单项选择题
下列选项中，能正确地将x和y两个变量中的数据进行交换的表达式是（）。
A.x＝x+y y＝y+x x＝x+y
B.x＝x+y y＝x-y x＝x-y
C.x＝x+y y＝y-x x＝x-y
D.x＝x-y y＝x-y x＝y-x
填空题
用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h（n），则回溯法所需的计算空间通常为（）
答案：O(h(n))
问答题
举反例证明0/1背包问题若使用的算法是按照pi/wi的非递减次序考虑选择的物品，即只要正在被考虑的物品装得进就装入背包，则此方法不一定能得到最优解（此题说明0/1背包问题与背包问题的不同）。
答案：举例如：
p{7，4，4}，w={3，2，2}，c=4时，
由于7/3最大，
若按题目要求...
单项选择题
Hanoi塔问题如下图所示。现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解Hanoi塔问题的递归算法正确的为：（）
A.
B.
C.
D.
填空题
一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性：（）、（）、（）、（）、（）。
答案：确定性；有穷性；可行性；0个或多个输入；一个或多个输出
填空题
算法的复杂性是（）的度量，是评价算法优劣的重要依据。
答案：算法效率
单项选择题
在Visual Basic中，若a＝3，b＝3，c＝1，语句Ifa＞bThenc＝a+1Elsec＝b-1执行后，变量c的值是（）。
A.3
B.2
C.4
D.1
单项选择题
NP类语言在图灵机下的定义为（）
A.NP={L∣L是一个能在非多项式时间内被一台NDTM所接受的语言}
B.NP={L∣L是一个能在非多项式时间内被一台DTM所接受的语言}
C.NP={L∣L是一个能在多项式时间内被一台DTM所接受的语言}
D.NP={L∣L是一个能在多项式时间内被一台NDTM所接受的语言}
单项选择题
算法分析中，记号O表示（）。
A.渐进下界
B.渐进上界
C.非紧上界
D.紧渐进界
E.非紧下界