有关算法分析的选择题

本博文源于《数据结构与算法解析》，俗话说的好，麻雀虽小，五脏俱全。博文将一些算法分析的题目进行收集并给出解答和解析，值得浏览收看，收藏！

文章目录

• • 1. 以下关于算法的说法，正确的是( )
  • 2. 若一个问题既可以用迭代方式也可以用递归方式求解，则采用( )方法具有更高的时空效率
  • 3. 一个递归算法必须包括（ ）
  • 4. 算法分析的目的是_____,算法分析的两个主要方面是____
  • 5. 算法分析的前提是( ).
  • 6. 计算算法的时间复杂度属于（ ）
  • 7. 算法的时间复杂度与( )有关
  • 8. 算法的计算量的大小称为计算的( )
  • 9. 某算法的时间复杂度为O(n^2),表名该算法的( ).
  • 10. 以下关于算法分析的说法中,错误的是( )
  • 11. 设f(n) = n s i n ( n ) n^{sin(n)} nsin(n)，若用大O表示法，f(n)的渐进时间复杂度为( )
  • 12.设有程序段
  • 13.在下列程序中：
  • 14.设有以下三个函数
  • 15.以下程序段中循环语句的条件表达式的执行次数是( ).
  • 16. 设有一个递归算法如下：

1. 以下关于算法的说法，正确的是( )

• A. 算法的时间效率取决于算法执行所花费的CPU时间
• B. 在算法设计中不允许用牺牲空间的方式来换取好的时间效率
• C 算法必须具备有穷性、确定性等五个特性
• D. 通常用时间效率和空间效率来衡量算法的优劣

答案：C
解析：D选项还要考虑算法的运行环境 使用者的需求 A 选项时间效率取决于不止时间 B 不允许太绝对。

2. 若一个问题既可以用迭代方式也可以用递归方式求解，则采用( )方法具有更高的时空效率

• A 迭代
• B 递归
• C 先递归后迭代
• D. 先迭代后递归

答案：A
解析：递归害怕栈溢出，时空效率综合一下还是迭代

3. 一个递归算法必须包括（ ）

• A. 递归部分
• B. 终止条件和递归部分
• C. 迭代部分
• D. 终止条件和迭代部分

答案: B
解析: 没有终止条件就是死循环，没有递归部分那就不是递归！

4. 算法分析的目的是_____,算法分析的两个主要方面是____

• A. 找出数据结构的合理性
• B. 研究算法中输入与输出的关系
• C. 分析算法的效率以求改进
• D. 分析算法的可读性和文档性
• E 时间复杂度和空间复杂度
• F 正确性和简单性
• G 数据复杂度和程序复杂度
• H 可读性和文档性

答案：第一空 选C 第二空 选E
解析：概念性，记住即可.

5. 算法分析的前提是( ).

• A.算法必须简单
• B. 算法必须正确
• C.算法结构性强
• D.算法必须通用

答案: B
解析: 算法就是拿来解决问题的，如果不正确，算法就显得没有必要。

6. 计算算法的时间复杂度属于（ ）

• A. 事前统计的方法
• B.事前分析估算的方法
• C. 事后统计的方法
• D. 事后分析估算的方法

答案:A
解析:算法时间复杂度度量是一种事前统计的方法，统计的对象是语句的执行频度，并估计当问题规模增大时这个执行频度服从什么样的规律.

7. 算法的时间复杂度与( )有关

• A 问题规模
• B. 计算机硬件的运行速度
• C. 源程序的程度
• D 编译后执行程序的质量

答案：A
解析：问题规模越大，比如百万级别，千万就非常重视程序的时间空间了。

8. 算法的计算量的大小称为计算的( )

• A. 问题规模
• B. 时间复杂度
• C.空间复杂度
• D. 程序难度

答案:B
解析：问题规模是一个考虑因素，但计算量大小表名时间复杂度的大小，空间复杂度与计算量有关，但它不是计算量的度量，程序难度与计算量无关。

9. 某算法的时间复杂度为O(n^2),表名该算法的( ).

• A. 问题规模是n^2
• B.执行时间等于n^2
• C.执行时间与n^2 成正比
• D.问题规模与n^2成正比

答案:C
解析:例如n^2前系数，那我们四舍五入还是 n^2

10. 以下关于算法分析的说法中,错误的是( )

• A 空间效率为O(1)的算法不需要任何额外的辅助空间
• B 若规模n相同，时间复杂度为O(n)的算法在时间上总是优于时间复杂度为O(2^n)的算法
• C. 所谓时间复杂度是指在最坏情况下,估算算法执行时间的一个上界
• D. 同一个算法，实现语言的级别越高，执行的效率不一定越低

11. 设f(n) = n s i n ( n ) n^{sin(n)} nsin(n)，若用大O表示法，f(n)的渐进时间复杂度为( )

• A.O（1）
• B.O(n^-1)
• C.O(n)
• D.O(n^2)

答案：C
解析： s i n ( n ) sin(n) sin(n)的值域[-1,1]，因此直接就是C

12.设有程序段

int k = 10;
while(k==0) k--;

则以下关于此循环的说法中，正确的是( ).

• A. 循环执行10次
• B. 循环是无限循环
• 循环体一次都不执行
• D 循环体只执行一次

答案:C
解析：k不等于0，所以不执行

13.在下列程序中：

void calc(int p1,int p2) {
	p2 = p2*p2;
	p1 = p1 - p2;
	p2 = p2 - p1;
}
void main(void) {
	int i = 2,j = 3;
	calc(i,j);
	printf("%dn",j)
}

当参数传递改用引用方式时，所得结果j=___

• A.2
• B.16
• C.20
• D.28

当参数传递采用赋值方式时，所得结果j=____

• A.0
• B.3
• C.5
• D.6

答案：(1)选B (2)选B
解析：传引用改变主函数变量，形参不传址是无法改变。

14.设有以下三个函数

• f(n) = 100n^3 + n^2 + 1000
• g(n) = 25n^3 + 4000 n^2
• h(n) = n 2.01 + 1000 n l o g 2 n n^{2.01}+1000nlog_2n n2.01+1000nlog2​n

A.f(n) = O(g(n))
B. g(n) = O(f(n))
C.h(n) = O( n 2.01 n^{2.01} n2.01)
D.h(n) = O(nlog_2n)

答案：选D，因为时间复杂度取最高次，ABC选项都是满足正解。f(n)=O(n^3), g(n)=O(n^3),h(n)=n(2.01)

15.以下程序段中循环语句的条件表达式的执行次数是( ).

i = 0;
s = 0;
n = 100;
do {
	i = i + 1;
	s = s + 10*i;
}while(i < n && s < n);

• A 3
• B 4
• C 5
• D 6

答案：B
解析：
他是do循环，所以至少先执行一次

• i = 1 s = 0 + 10*1 1 < 100 && 10 < 100
• i = 2 s = 10 + 10*2 2<100 && 30 < 100
• i = 3 s = 30 + 10 *3 3<100 && 60<100
• i = 4 s = 60 + 10 *4 4<100 && 100<100 跳出

四次完毕

16. 设有一个递归算法如下：

int X(int n) {
	if (n <= 3)
		return 1;
	else return X(n-2) + X(n-4) + 1;	
}

计算X(X(5))时需要调用X函数( )次

• A. 4
• B.5
• C. 8
• D 16

答案：A.4
解析：X(5) = X(3) + X(1) + 1= 3,X(X(5)) = X(3) = 1，调用了4次X函数.