1.1知识梳理

1、单选题：
给定男孩和女孩的两张喜欢列表，GS算法的结果对（   ）是最好的选择。‎
选项：
A: 男孩
B: 女孩
C: 男孩或女孩
D: 男孩和女孩
答案: 【 男孩】

2、多选题：
稳定匹配问题的输出是（  ）​
选项：
A: 完美匹配 
B: 没有不稳定配对 
C: 稳定匹配 
D: 不稳定匹配 
答案: 【 完美匹配 ;
没有不稳定配对 ;
稳定匹配 】

3、判断题：
给定一个匹配，如果Z喜欢A甚于匹配的女朋友，A喜欢Z甚于匹配的男朋友，那么A和Z是一个不稳定配对。‎
选项：
A: 正确
B: 错误
答案: 【 正确】

4、判断题：
‎任意给定两张喜欢列表，稳定匹配问题只有一个稳定匹配。‏
选项：
A: 正确
B: 错误
答案: 【 错误】

1.2知识梳理

1、单选题：
‍解决问题的基本步骤是（）。（1）算法设计（2）算法实现（3）数学建模（4）算法分析（5）正确性证明‌
选项：
A: (3)(1)(4)(5)(2)
B: (3)(4)(1)(5)(2) 
C: (3)(1)(5)(4)(2)
D: (1)(2)(3)(4)(5)
答案: 【 (3)(1)(5)(4)(2)】

2、多选题：
‎问题的两个要素是（ ）和（）   ​
选项：
A: 输入
B: 输出
C: 提问
D: 算法
答案: 【 输入;
输出】

3、多选题：
‎算法的性质有（）‍
选项：
A: 确定性
B: 有穷性
C: 输入
D: 输出
答案: 【 确定性;
有穷性;
输入;
输出】

4、判断题：
​程序总是在有穷步的运算后终止。‌
选项：
A: 正确
B: 错误
答案: 【 错误】

5、判断题：
‌算法是一步步正确解决问题的方法或策略。‎
选项：
A: 正确
B: 错误
答案: 【 正确】

6、判断题：
‎程序是算法用某种程序设计语言的具体实现，不能使用自然语言描述。​
选项：
A: 正确
B: 错误
答案: 【 正确】

7、判断题：
‌算法每次求解一个实例，而计算机需要求解该问题的所有实例。‏
选项：
A: 正确
B: 错误
答案: 【 错误】

1.3知识梳理

1、单选题：
从右向左计算p(x) = anxn + an-1xn-1 +… + a1x1 + a0   的数量级为（）   ‍
选项：
A: n
B: n^2
C: nlogn
D: logn
答案: 【 n】

2、多选题：
问题变换的目的（）‌
选项：
A: 复杂变简单
B: 未知变已知
C: 隐式变显式
D: 难解变易解
答案: 【 复杂变简单;
未知变已知;
隐式变显式;
难解变易解】

3、判断题：
‍传教士和野人问题转换的图是状态空间图。‎
选项：
A: 正确
B: 错误
答案: 【 正确】

4、判断题：
‎大学入学问题的核心是稳定匹配问题‎
选项：
A: 正确
B: 错误
答案: 【 正确】

5、判断题：
​ 一个问题的实例可以变换为更简单更便利的实例，变换为不同的表达形式。‍
选项：
A: 正确
B: 错误
答案: 【 正确】

第一章测验

1、单选题：
‍算法与程序的区别是（）  ​‍​
选项：
A: 输入
B: 输出
C: 确定性
D: 有穷性
答案: 【 有穷性】

2、单选题：
‌‌ 解决问题的基本步骤是（）。（1）算法设计（2）算法实现（3）数学建模（4）算法分析（5）正确性证明 ‌‌‌
选项：
A: (3)(1)(4)(5)(2) 
B: (3)(4)(1)(5)(2) 
C: (3)(1)(5)(4)(2) 
D: (1)(2)(3)(4)(5)
答案: 【 (3)(1)(5)(4)(2) 】

3、单选题：
‌下面说法关于算法与问题的说法错误的是（）。‏
选项：
A: 如果一个算法能应用于问题的任意实例，并保证得到正确解答，称这个算法解答了该问题。
B: 算法是一种计算方法，对问题的每个实例计算都能得到正确答案。
C: 同一问题可能有几种不同的算法，解题思路和解题速度也会显著不同。
D: 证明算法不正确，需要证明对任意实例算法都不能正确处理。 
答案: 【 证明算法不正确，需要证明对任意实例算法都不能正确处理。  】

4、单选题：
问题变换的目的有（）。(1)复杂变简单 (2)未知变已知 (3)隐式变显式 (4)难解变易解 （5）以上都是。‍
选项：
A: (1)
B: (2)
C: (3)
D: (4)
E: (5)
答案: 【 (5)】

5、单选题：
‏按照霍纳法则，计算p(x) = anxn + an-1xn-1 +… + a1x1 + a0   的数量级为（）‌
选项：
A: n
B: n^2
C: nlogn
D: logn
答案: 【 n】

6、单选题：
描述算法的基本方法有(  )。(1)自然语言(2)流程图(3)伪代码(4)机器语言‌
选项：
A: A.(2)(3)(4)
B: B.(1)(2)(3) 
C: C.(1)(2)(4) 
D: D.(1)(2)(3)(4)
答案: 【 B.(1)(2)(3) 】

7、多选题：
‎问题变换的方法有（ ）‍‎‍‍
选项：
A: 实例简单化
B: 问题约简
C: 表达变换
D: 分支
答案: 【 实例简单化;
问题约简 ;
表达变换 】

8、多选题：
‏下面关于程序和算法的说法正确的是（）。‏
选项：
A: 算法的每一步骤必须要有确切的含义，必须是清楚的、无二义的。
B: 程序是算法用某种程序设计语言的具体实现。
C: 程序总是在有穷步的运算后终止。
D: 算法是一个过程，计算机每次求解是针对问题的一个实例求解
答案: 【 算法的每一步骤必须要有确切的含义，必须是清楚的、无二义的。;
程序是算法用某种程序设计语言的具体实现。;
算法是一个过程，计算机每次求解是针对问题的一个实例求解】

9、多选题：
最大独立集问题和（）问题等价。‌
选项：
A: 最大团
B: 最小顶点覆盖
C: 区间调度问题
D: 稳定匹配问题
答案: 【 最大团;
最小顶点覆盖】

10、多选题：
​给定两张喜欢列表，稳定匹配问题的输出是（  ） ​
选项：
A: 完美匹配
B: 没有不稳定配对
C: 最大匹配 
D: 稳定匹配
答案: 【 完美匹配;
没有不稳定配对;
最大匹配  ;
稳定匹配】

11、判断题：
‍给定一个实例，如果一个算法能得到正确解答，称这个算法解答了该问题。​‍ ​
选项：
A: 正确
B: 错误
答案: 【 错误】

12、判断题：
‎​计算机每次求解是针对问题的每个实例求解。  ​
选项：
A: 正确
B: 错误
答案: 【 错误】

13、判断题：
‍‌同一数学模型使用不同的数据结构会有不同的算法，有效性有很大差别。‌
选项：
A: 正确
B: 错误
答案: 【 正确】

14、判断题：
‏证明算法不正确，只需给出一个反例，算法不能正确处理即可。  ‎
选项：
A: 正确
B: 错误
答案: 【 正确】

15、判断题：
‍同一算法只有一种形式描述  ‍
选项：
A: 正确
B: 错误
答案: 【 错误】

16、判断题：
‏一个问题的同一实例可以有不同的表示形式。  ‌
选项：
A: 正确
B: 错误
答案: 【 正确】

17、判断题：
​算法必须在有穷时间终止‎
选项：
A: 正确
B: 错误
答案: 【 正确】

18、判断题：
‌一个问题的算法必须在有穷时间终止，并且对一切合法的输入都能得出满足要求的结果。    ‎
选项：
A: 正确
B: 错误
答案: 【 正确】

19、判断题：
‌ 问题的两个要素是输入和实例。​
选项：
A: 正确
B: 错误
答案: 【 错误】

20、判断题：
‏算法是一个语句集合，按照顺序执行语句，处理实例，得到正确答案。‎
选项：
A: 正确
B: 错误
答案: 【 正确】

2.1知识梳理

1、多选题：
计算算法的时间复杂度只要选取()‏
选项：
A: 最复杂部分的运行时间 
B: 关键操作的运行时间 
C: 在最坏情况下运行时间
D: 在平均情况下的运行时间   
答案: 【 最复杂部分的运行时间 ;
关键操作的运行时间 ;
在最坏情况下运行时间】

2、判断题：
‎算法分析的两种方法是事前分析和事后统计。​
选项：
A: 正确
B: 错误
答案: 【 正确】

3、判断题：
‍算法分析的两个阶段是粗粒度比较数量级和细粒度比较各种情况。‎
选项：
A: 正确
B: 错误
答案: 【 正确】

4、判断题：
​求解问题的输入量,称为问题的规模。​
选项：
A: 正确
B: 错误
答案: 【 正确】

5、判断题：
‌时间复杂度就是算法运行的时间的度量，衡量算法的效率。 ‍
选项：
A: 正确
B: 错误
答案: 【 正确】

2.2知识梳理

1、单选题：
‌g(n)为f(n)的下界,记为:f(n)=  (g(n))  ‌
选项：
A: Ο
B: Ω
C: θ 
D: ω
答案: 【 Ω】

2、单选题：
f(n)=3n^3+7n^2+4nlogn =（ ）(n^3）‍
选项：
A: Ο
B: Ω
C: θ
D: ω 
答案: 【 ω 】

3、判断题：
‌O(f(n))+O(g(n)) = O(min{f(n),g(n)}) ‎
选项：
A: 正确
B: 错误
答案: 【 错误】

4、判断题：
‎任何多项式时间算法都是好算法，都是有效的。‏
选项：
A: 正确
B: 错误
答案: 【 错误】

5、判断题：

‎f(n)=(g(n)) 则 f(n)=Ο(g(n))且f(n)=Ω(g(n))

‍选项：
A: 正确
B: 错误
答案: 【 正确】

6、判断题：
​f=o(g)且g = o(h) 则  f=o(h)        ​
选项：
A: 正确
B: 错误
答案: 【 正确】

2.3知识梳理

1、单选题：

‌如果   =0, 则 f(n)=  (g（(n)）

​选项：
A: Ο
B: Ω
C: θ
D: o
答案: 【 o】

2、单选题：
‏logn!=Q(    ) ‎
选项：
A: n
B: nlogn
C: n^2
D: logn
答案: 【 nlogn】

3、多选题：
​n!=()‍
选项：
A:
B:
C:
D:
答案: 【 ;
】

4、判断题：

‏

‎选项：
A: 正确
B: 错误
答案: 【 正确】

5、判断题：
‌对于任意 x > 0,  log n = o(n^x)‏
选项：
A: 正确
B: 错误
答案: 【 正确】

6、判断题：

‍, 常数a, b > 0. 

​选项：
A: 正确
B: 错误
答案: 【 正确】

7、判断题：
‌对任意 r > 1 和  d > 0,  nd = o(r^n).‏
选项：
A: 正确
B: 错误
答案: 【 正确】

8、判断题：

​ , 常数a, b > 0.

‏选项：
A: 正确
B: 错误
答案: 【 正确】

2.4知识梳理

1、单选题：
‎顺序查找的时间复杂度为（） ‎
选项：
A: θ(n)  
B: O（n^2)）
C: O(nlogn)
D: o（n^2）
答案: 【 θ(n)  】

2、单选题：
下面程序的时间复杂度是（）             ‏i=1‏while(i<=n) do‏       i=i*3‏‏
选项：
A: Q(logn) 
B: Q(n)
C: O(n)
D: Ω(n)
答案: 【 Q(logn) 】

3、单选题：
‌快速幂求x^n的时间复杂度为O（）‍
选项：
A: n
B: logn
C: nlogn
D: n^1/2
答案: 【 logn】

4、判断题：
‎T1(n)+T2(n)=O(max(f(n),g(n)))，因此并行语句时间复杂度等于两者中高的复杂度。‌
选项：
A: 正确
B: 错误
答案: 【 正确】

5、判断题：
‎O(f)*O(g)=O(f*g)，因此循环语句的时间复杂度等于循环体的时间复杂度与循环次数的乘积。‏
选项：
A: 正确
B: 错误
答案: 【 正确】

6、判断题：
‌从n个数中查找最大值的时间复杂度为W (n) ‎
选项：
A: 正确
B: 错误
答案: 【 错误】

2.5知识梳理

1、单选题：
给定图G=(V,E), |V|=n, |E|=m, 其邻接矩阵的空间复杂度为(  )     ​‎​
选项：
A: θ(n^2)
B:  O(n)   
C: W(n^3) 
D: o(n^2)   
答案: 【 θ(n^2)】

2、多选题：
下面以空间换时间的方法有（）‏‌‏
选项：
A: 预处理 
B: 预构造 
C: 动态规划
D: 数据压缩
答案: 【 预处理 ;
预构造 ;
动态规划】

3、判断题：
‏空间复杂度S(n)是算法执行所需所有空间的资源量‌
选项：
A: 正确
B: 错误
答案: 【 错误】

4、判断题：
‏时空均衡可通过以时间换空间或以空间换时间实现‏
选项：
A: 正确
B: 错误
答案: 【 正确】

5、判断题：
‏给定n个整数，n个数的取值范围为[1,k], 计数排序的时间复杂度是O （n+k） 。‌
选项：
A: 正确
B: 错误
答案: 【 正确】

6、判断题：
‎使用散列可以降低查找的时间复杂度​
选项：
A: 正确
B: 错误
答案: 【 正确】

第二章测验

1、单选题：
​从资源划分，算法的复杂度分为()和()。​
选项：
A: 时间复杂度  空间复杂度   
B: 空间复杂度   平均复杂度
C: 最好复杂度 最坏复杂度
D: 时间间复杂度   平均复杂度
答案: 【 时间复杂度  空间复杂度   】

2、单选题：
‎算法复杂度分析的两种基本方法为（  ）和（    ）‌
选项：
A: 结构化方法 面向对象方法 
B: 事后统计  事前分析
C: 几何复杂度  平均复杂度  
D:  平摊复杂度 平滑复杂度
答案: 【 事后统计  事前分析】

3、单选题：
​​设f（N）、g（N）是定义在正数集上的正函数，如果存在正的常数C和自然数N0，使得当N≥N0时有f（N）≥Cg（N），则称函数f（N）当N充分大时有下界g（N），记作f（N）=W（g（N）），即f（N）的阶（   ）g（N）的阶。​​​
选项：
A: 不高于
B: 不低于 
C: 等价于
D: 逼近
答案: 【 不低于 】

4、单选题：
 f(n)=   100     当n为奇数‍ f(n)=5n^2+3n.     当n为偶数  ‍f(n)的渐进性态f(n)= W(    )‍
选项：
A:  n  
B: n^2
C: 2^n
D: 1
答案: 【 1】

5、单选题：
‎‍下面程序的时间复杂度为（）  ‍‎‍x=1‍‎‍for i=1 to n  do‍‎‍for j=1 to i do           ‍‎‍for k=1 to j do     ‍‎              
                x++  ‍
选项：
A: n
B: n^3
C: n^2
D: nlogn
答案: 【 n^3】

6、单选题：
对近似递增序列的线性表从小到大排序，使用哪种方法好？​​​
选项：
A: 堆排序 
B: 快速排序
C: 插入排序
D: 归并排序
答案: 【 插入排序】

7、单选题：
给定n个元素的数组A，n=10^3, 使用折半查找比使用顺序查找大约快___倍。‎‍‎
选项：
A: 10
B: 100
C: 1000
D: 141
答案: 【 100】

8、单选题：
‏给定图G=(V,E), |V|=n, |E|=m, 遍历其邻接表的时间复杂度为θ(  )‍
选项：
A: n
B: m
C: n+m
D: n^m
答案: 【 n+m】

9、单选题：
​‌logn!=Q(    ) ‌​‌
选项：
A: n
B: nlogn
C: n^2
D: logn   
答案: 【 nlogn】

10、单选题：
‌‏给定n个元素的数组A，n=10^3, 使用折半查找比使用顺序查找大约快___倍。‏
选项：
A: 10
B: 100
C: 1000
D: 0.1
答案: 【 100】

11、单选题：
‎下面程序的时间复杂度是（）             ‌i=1‌while(i<=n)
do   ‌       i=i*5‌
选项：
A: Q(logn)  
B: Q(n)
C: O(n)  
D:  Ω(n)
答案: 【 Q(logn)  】

12、单选题：
‏给定n个整数，n个数的取值范围为[1,k],计数排序的时间复杂度是O （n+k） 。‍
选项：
A: n+k
B: n
C: k
D: nk
答案: 【 n+k】

13、单选题：
‍给定图G=(V,E), |V|=n, |E|=m, 其邻接矩阵的空间复杂度为(  ) ‏
选项：
A: θ(n^2)  
B: O(n)
C: W(n^2) 
D: o(n^2)
答案: 【 θ(n^2)   】

14、多选题：
‎顺序查找适合的数据结构是（）‍
选项：
A: 散列存储
B: 顺序存储
C: 链式存储
D: 压缩存储
答案: 【 顺序存储;
链式存储 】

15、多选题：
​f(n)=3n^3+7n^2+4nlogn =（）（n^3）‏
选项：
A: Ο
B: Ω
C: θ
D: o 
E: ω
答案: 【 Ο;
Ω;
θ】

16、多选题：
‍‎下面那些算法的时间复杂度为O（n^2）?‎‍‎
选项：
A: 顺序查找
B: 折半查找  
C: 插入排序
D: 冒泡排序
E: 折半插入排序
答案: 【 插入排序;
冒泡排序;
折半插入排序】

17、多选题：
‏​两个n*n的矩阵相加的时间复杂度是（ ）​
选项：
A: θ(n^2)
B: O(n^2)
C: W(n^2)
D: o(n^2)
答案: 【 θ(n^2);
O(n^2);
W(n^2)】

18、多选题：
‌‎以空间换时间的方法有（）‎‌‎
选项：
A: 预处理 
B: 预构造
C: 动态规划
D: 数据压缩
答案: 【 预处理  ;
预构造;
动态规划】

19、判断题：
​时间复杂度是指算法最坏情况下的运行时间。‏
选项：
A: 正确
B: 错误
答案: 【 正确】

20、判断题：
‍f(n)=O(g(n)) 且 g(n)=O(h(n))，则h(n)=O(f(n)) ‌
选项：
A: 正确
B: 错误
答案: 【 错误】

21、判断题：
‏f(n)=O(g(n))  则 f(n)^2=O(g(n)^2)   ‍
选项：
A: 正确
B: 错误
答案: 【 正确】

22、判断题：
‍f(n)=3n^3+7n^2+4nlogn =O（n^2）‌
选项：
A: 正确
B: 错误
答案: 【 错误】

23、判断题：
‍如果一个算法是多项式时间算法，该算法是有效的,是好算法。‍
选项：
A: 正确
B: 错误
答案: 【 正确】

24、判断题：
‌n!=o(2^n) ‍
选项：
A: 正确
B: 错误
答案: 【 错误】

25、判断题：

‍    

‍选项：
A: 正确
B: 错误
答案: 【 正确】

26、判断题：
‍折半查找的时间复杂度为Q(nlogn)‍
选项：
A: 正确
B: 错误
答案: 【 错误】

27、判断题：
‌f(n)=θ(g(n)) 当且仅当 g(n)=θ(f(n))‎
选项：
A: 正确
B: 错误
答案: 【 正确】

28、判断题：
‎f=O(g)当且仅当 g =Ω (f)‎
选项：
A: 正确
B: 错误
答案: 【