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

问答题
输入某年，某月，某日，判断这一天是这一年的第几天。
答案：#include
void main()
{
int y,m,d;
单项选择题
记号Ω的定义正确的是（）。
A.O（g（n））={f（n）∣存在正常数c和n₀使得对所有n≧n₀有：0≦f（n）≦cg（n）}
B.O（g（n））={f（n）∣存在正常数c和n₀使得对所有n≧0有：0≦g（n）≦（n）}
C.O（g（n））={f（n）∣对于任何正常数c>0，存在正数和n₀>0使得对所有n≧n₀有：0≦f（n）<cg（n）}
D.O（g（n））={f（n）∣对于任何正常数c>0，存在正数和n₀>0使得对所有n≧n₀有：0≦cg（n）<f（n）}
问答题
已知非齐次递归方程：其中，b、c是常数，g（n）是n的某一个函数。则f（n）的非递归表达式为：现有Hanoi塔问题的递归方程为：，求h（n）的非递归表达式。
答案：
利用给出的关系式，此时有：b=2,c=1,g(n)=1,从n递推到1，有：
问答题
若n=4，在机器M1和M2上加工作业i所需的时间分别为ai和bi，且（a1，a2，a3，a4）=（4，5，12，10），（b1，b2，b3，b4）=（8，2，15，9）求4个作业的最优调度方案，并计算最优值。
答案：步骤为：
N₁={1，3}，N₂={2，4}；
N
问答题
何谓P、NP、NPC问题？
答案：1.P（Polynomial问题）：也即是多项式复杂程度的问题。
2.NP就是Non-deterministi...
填空题
若序列X={B，C，A，D，B，C，D}，Y={A，C，B，A，B，D，C，D}，请给出序列X和Y的一个最长公共子序列：（）
答案：{B，A，B，C，D}或{C，A，B，C，D}或{C，A，D，C，D｝
单项选择题
在VB设计中，已知x＝-100，则sgn（x）的值为（）。
A.-1
B.0
C.1
D.2
单项选择题
在VB中，如果变量声明语句为Dima，bAsSingle，则变量a、b的数据类型（）。
A.a为变体型，b为单精度型
B.a为单精度型，b为变体型
C.a，b均为变体型
D.a，b均为单精度型
单项选择题
下列四种排序中（）的空间复杂度最大。
A.插入排序
B.冒泡排序
C.堆排序
D.归并排序
填空题
所谓贪心选择性质是指（）。
答案：所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到