《第二章 算法初步》试卷及答案_高中数学必修3_北师大版_2024-2025学年.docx

《第二章算法初步》试卷(答案在后面)

一、单选题（本大题有8小题，每小题5分，共40分）

1、下面哪个选项不属于算法的基本特征？

A、可行性

B、确定性

C、无限性

D、拥有足够的情报

2、下列四个选项中，表示算法特征的是（）

A、可重复性，关联性，规则性

B、简洁性，关联性，有效性

C、简洁性，有效性，有穷性

D、可重复性，简洁性，有效性

3、已知算法A的运行时间T(n)满足以下递推关系：T(1)=1，T(n)=T(n-1)+n，其中n≥2。求T(5)的值。

A.15

B.25

C.30

D.35

4、下列关于算法的描述中，正确的是：

A、算法可包含不确定的步骤

B、算法可以有零个输入

C、算法必须具有确定性、可行性、有穷性和拥有足够的信息

D、算法的每一步骤可以不清晰、不唯一

4、下列关于算法的描述中，正确的是：

A、算法可以包含不确定的步骤

B、算法可以有零个输入

C、算法必须具有确定性、可行性、有穷性和拥有足够的信息

D、算法的每一步骤可以模糊和不唯一

5、一个算法包括的步骤最少可以有几个？

A.1个

B.2个

C.3个

D.4个

6、下列算法中，属于排序算法的是（）

A、冒泡排序

B、快速排序

C、线性搜索

D、二分搜索

7、阅读下面的程序框图，输出的结果是（）

开始i=1S=0_whilei=5_S=S+ii=i+1_endwhile_输出S结束

A、10B、15C、20D、25

8、已知一个算法产生的文档按照以下规则创建，规则如下：

1.第一个文档包含数字1；

2.若前一个文档中包含偶数，下一个文档是前一个文档两倍的奇数，若前一个文档中包含奇数，下一个文档是前一个文档两倍的偶数；

3.文档仅包含一个数字。

按照上述规则，创建第三个文档可能会出现的情况是：（）

A.3

B.6

C.2

D.9

二、多选题（本大题有3小题，每小题6分，共18分）

1、下列关于算法的描述中，正确的是（）

A.算法是一种解决问题的清晰指令序列，它必须保证在有限的步骤内完成

B.算法可以包含无限循环，只要能够达到解决问题的目的即可

C.算法的设计应遵循一定的原则，如可行性、确定性、有穷性、输入输出等

D.算法执行过程中，每一步操作都是独立的，不受前一步操作的影响

2、下列选项中，是算法特征的有（）。

A、有穷性

B、精确性

C、确定性

D、可行性

3、（15分）下列选项中，哪些是算法的特征？（）

A、确定性

B、简洁性

C、有穷性

D、机器性

三、填空题（本大题有3小题，每小题5分，共15分）

1、一个算法的复杂度包括时间复杂度和______。

2、已知一个算法的执行时间复杂度为O(n^2)，则当输入数据规模为n时，其最坏情况下的执行时间大约为______。

3、若算法的执行时间为On2，当输入数据量n增加到原来的2倍时，算法执行时间将增加到原来的

四、解答题（第1题13分，第2、3题15，第4、5题17分，总分：77）

第一题

题目：

已知算法A的流程图如下，请根据流程图填写下列空格，并完成算法的步骤分析。

开始|V输入：n（一个大于1的自然数）|V判断n是否等于2|是----否||VV输出：1输出：n-1|V结束

步骤分析：

1.输入一个大于1的自然数n；

2.判断n是否等于2；

如果是，则输出1；

如果不是，则输出n-1。

空格填写：

1.当n=2时，算法输出______；

2.当n大于2时，算法输出______。

第二题

题目：

一种新的排序算法“跳跃排序”如下：首先将数组分成若干子数组，每个子数组包含相邻的2n-1个元素，然后对每个子数组进行插入排序。现在有一个数组A={3,1

解答与解析：

步骤一：

首先，根据题目要求，将数组A={3,1,5,7

步骤二：

对A1和A

对A1

初始数组：3

第一步：将1插入到正确位置：1

最终数组：1

对A2

初始数组：7

第一步：将2插入到正确位置：2

第二步：将4插入到正确位置：2

最终数组：2

步骤三：

合并A1与A

我们暂时用这两个已排序的子数组对其进行重新排序。

合并过程：

我们只需考虑每个子数组的第一个元素来决定如何合并，跳过中间部分，因为插入排序已经保证了每个是v位置的最佳元素。

将A1和A

首先添加1（来自A1）：1

首先添加2