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

填空题
贪心算法总是做出在当前看来（）的选择。也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的（）。
答案：最好；局部最优选择
问答题
通过键盘输入一个高精度的正整数n（n的有效位数≤240），去掉其中任意s个数字后，剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n和s，寻找一种方案，使得剩下的数字组成的新数最小。【样例输入】 178543 S=4 【样例输出】 13
答案：为了尽可能地逼近目标，我们选取的贪心策略为：每一步总是选择一个使剩下的数最小的数字删去，即按高位到低位的顺序搜索，若各位...
单项选择题
能采用贪心算法求最优解的问题，一般具有的重要性质为：（）
A.最优子结构性质与贪心选择性质
B.重叠子问题性质与贪心选择性质
C.最优子结构性质与重叠子问题性质
D.预排序与递归调用
填空题
回溯法的算法框架按照问题的解空间一般分为（）算法框架与（）算法框架。
答案：子集树；排列树
单项选择题
以下选项中，（）不是面向对象程序设计的基本特征。
A.封装性
B.继承性
C.可移植性
D.多态性
单项选择题
已知一个线性储存的线性表设每个结点需要占n个存储单元，若第一个结点地址为xul，则第i个结点的地址为（）。
A.xul+（i-1）*n
B.xul+i*n
C.xul-i*n
D.xul+（i+1）*n
填空题
算法的复杂性有（）和（）之分，衡量一个算法好坏的标准是（）。
答案：时间复杂性；空间复杂性；时间复杂度高低
单项选择题
下列常量说明的书写格式，正确的是（）。
A.ConstPIassingle＝3.14
B.ConstPIassingle
C.ConstPI＝3.14assingle
D.ConstPI＝3.14asinteger
单项选择题
首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为（）。
A.中序遍历
B.先序遍历
C.后序遍历
D.层次遍历
填空题
0-1背包问题的回溯算法所需的计算时间为（），用动态规划算法所需的计算时间为（）。
答案：
O(n*2ⁿ)；O(min{nc,2ⁿ})