【算法不挂科】算法期末考试【选择题专项练习】＜多单元汇总＞

前言

大家好吖，欢迎来到 YY 滴算法不挂科系列 ，热烈欢迎！ 本章主要内容面向接触过C++的老铁
主要内容含：

一.选择题

【1】算法绪论

1.算法与程序的区别是( )

A.输出
B.输入
C.确定性
D.有穷性

• D

2.算法复杂度分析的两种基本方法为()和()

A.结构化方法 面向对象方法
B.事后统计事前分析
C.几何复杂度平均复杂度
D.平摊复杂度 平滑复杂度

• B

3.设f(N)、g(N)是定义在正数集上的正函数，如果存在正的常数C和自然数N0，使得当N≥N0时有f(N)>Cg(N)，则称函数f(N)当N充分大时有下界g(N)，记作f(N)=Q(g(N))，即f(N)的阶( )g(N)的阶。

A.不高于
B.逼近
C.等价于
D.不低于

• D

4.对近似递增序列的线性表从小到大排序，使用哪种方法好?

A.归并排序
B.堆排序
C.插入排序
D.快速排序

• C

5.当输入规模为n时,下列算法渐进复杂性中最低的是（）

A.n！
B.2n的平方
C.5n
D.n的平方

• C

6.下面( )不是算法所必须具备的特性

A.高效性
B.确定性
C.输出
D.有限性

• A

7.算法分析的目的是()

A.找出数据结构的合理性
B.研究算法中输入和输出的关系
C.分析算法的效率以求改进
D.分析算法的易读性和文档性

• C

8.已知f(n)=nlogn+n, g(n)=logn, 那么 f(n)=___(g(n)),下划线处应该填的是( )。

A.

B.

C.

D.

• C

9.已知f(n)=2的n次方, g(n)=3的n次方, 那么 f(n)=__(g(n)),下划线处应该填的是( )。

A.

B.

C.

D.

• B

10.下面哪个性质是程序不一定具备的?

A.确定性
B.有限性
C.输入
D.输出

• B

11.下面关于程序和算法的说法错误的是()

A.算法的每一步骤必须要有确切的含义，必须是清楚的、无二义的。
B.程序总是在有穷步的运算后终止。
C.算法是一个过程，计算机每次求解是针对问题的一个实例求解
D.程序是算法用某种程序设计语言的具体实现

• B

12.下面那些算法的时间复杂度不为0(n的2次方)?

A.冒泡排序
B.插入排序
C.折半插入排序
D.顺序查找

• D

【2】分支递归

1.设有5000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用()法。

A.合并排序
B.基数排序
C.冒泡排序
D.快速排序

• C

2.使用分治法求解不需要满足的条件是()。

A.原问题和子问题使用相同的方法求解
B.子问题不能够重复
C.子问题必须是一样的
D.子问题的解可以合并

• C

3.分治法的时间复杂性分析,通常是通过分析得到一个关于时间复杂性T(n)的一个递归方程,然后解此方程可得T(n)的结果。T(n)的递归定义如下:关于该定义中k,n/m,f(n)的解释准确的是()

A.k是常系数,n/m是规模为n的问题分为m个子问题,f(n)是分解为子问题的时间复杂性与合并子问题的解的时间复杂性之和。
B.k是子问题个数,n/m是子问题的规模,f(n)是分解为子问题的时间复杂性与合并子问题的解的时间复杂性之和
C.k是子问题个数,n/m是子问题的规模,f(n)是规模为n的问题分解为子问题的时间复杂性
D.k是常系数,n/m是规模为n的问题分为m个子问题,f(n)是将子问题的解合并为问题的解的时间复杂性。

• B

4.二分搜索算法是利用()实现的算法。

A.贪心法
B.动态规划法
C.回溯法
D.分治策略

• D

5.实现合并排序利用的算法是()

A.贪心法
B.动态规划法
C.回溯法
D.分治策略

• D

6.将一个递归算法改造为非递归算法,常用的数据结构是?

A.链表
B.顺序表
C.队列
D.栈

• D
• 递归算法通常涉及函数调用自身，每次调用都会形成一个新的函数执行环境（或称为“函数调用帧”或“活动记录”）。这些执行环境按照后进先出（LIFO, Last In First Out）的顺序被管理，即最后进入的函数调用帧会最先退出。

7.对n个元素进行合并排序,在最坏情况下所需的计算时间T(n)=（）

A.O(n)
B.O(n^2)
C.O(n^3)
D.O(nlogn)

• D

8.对n个元素进行快速排序,在最坏情况下所需的计算时间T(n)=（）

A.O(n)
B.O(n^2)
C.O(n^3)
D.O(nlogn)

• B

9.分治法在每一层递归上没有哪个步骤()

A.选择
B.解决
C.合并
D.分解

• A

【3】动态规划

1.动态规划算法的基本要素有()和最优子结构性质

A.贪心选择性质
B.重叠子问题性质
C.分解合并性质
D.独立子问题性质

• B

2.int n=5; //5个矩阵连乘int pl={10,5,4,2,2,4}; //第1个矩阵105,第5个矩阵24最优值数组中,m[2][4]的值为( )

A.56
B.60
C.48
D.40

• A

3.5个矩阵连乘,最优断开位置数组如下,短阵最优计算次序为( )

A.(A1((A2A3)(A4A5)))
B.(((A1A2)(A3A4))A5)
C.(((A1A2) A3) (A4A5))
D.((A1(A2A3))(A4A5))

• C

4.图像的灰度序列为:695 24012最优分段所需的存储位数数组中,s[4]的值为()

A.43
B.42
C.40
D.38

• B

5.矩阵连乘问题:下图是动态规划算法计算6个矩阵A1A2A3A4A5A6连乘所生成的信息表.

A.15125,(A2A3)((A4A5)A6)
B.10500,(A2A3)((A4A5)A6)
C.15125,(A2(A3A4))(A5A6)
D.10500,(A2(A3A4))(A5A6)

• B

6.动志规划解题的步骤分为四步(1)分析最优解的结构(2)建立递归关系(3)计算最优值(4)构造最优解。关于这四个步骤的内容描述 不正确 的是哪个?

A.构造最优解:根据计算最优值时得到的信息构造出问题的最优解，通常是用递归算法完成最优解的构造
B.分析最优解的结构:将一个一般化问题可以分解为几个性质相同的子问题，并且问题的最优解可以通过子问题的最优解合并得到，也就是要满足最优子结构性质
C.计算最优值:以自顶往下的方法计算问题的最优值，也就是先求解规模较大的问题的最优值。
D.建立递归关系:建立关于问题最优值的递归定义，即问题的最优值通过子问题的最优值合并得到。

• C

7.0-1背包问题中，背包容量是9，5种物品的重量分别是:324355种物品的价值分别是:45857m[][j]表示:背包容量为j,可选物品为i,i+1…,n时0-1背包问题最优值如下。最优解向量为()

A.1010 1
B.0110 1
C.10110
D.01110

• D

【4】贪心算法

1.下列算法中不能解决0/1背包问题的是()。

A.贪心法
B.动态规划
C.回溯法
D.分支限界法

• A

2.活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。用贪心算法解决时,贪心策略是( )。

A.持续时间短的活动先安排
B.持续时间长的活动先安排
C.最早开始的活动先安排
D.最早结束的活动先安排

• D

3.背包问题n=3,c=6,w={3,5,2},v={3,10,6},最大价值为

A.9
B.14
C.16
D.13

• B

4.最优装载问题,载重量为400,有8个集装箱,重量数组为w={100,200,50,90,150,50,20,80};用贪心算法求解,最

优解为()
A.(10110111)
B.(10011111)
C.(11110107)
D.(10110101)

• A

【5】回溯法

1.回溯法求解电路板排列问题，电路板个数n=4,连接块m=2,链接块N1={1,3,4),N2={2，4)，请写出正确的B[][👿)

A.

B.

C.

D.

• C

2.下面关于回溯法的描述中，不正确的是哪个?

A.回溯法解决的问题，其解通常可以表达为n元组的形式
B.回溯法，从解空间树的根结点开始，当搜索至叶子结点时，就找到了问题的解，算法结束。
C.回溯法可使用递归算法实现
D.回溯法是以深度优先的状态生成树法去搜索问题的解，并且能够避免不必要搜索

• B

3.n皇后问题是可用回溯法解决的问题。下面描述不正确的是?

A.当其解空间树是n叉树时，剪枝函数是任一列或任一(正反)对角线只能安排一个皇后
B.两种不同解空间树的算法效率比较，排列树的时间耗费高于n叉树
C.当其解空间树是排列树时，剪枝函数是任一(正反)对角线只能安排一个皇后。
D.算法搜索至叶子结点时，就找到了一种新的皇后安排方案，算法可找到所有可行的方案

• B

4.0-1背包问题的回溯算法，下面的解释不正确的是()

A.当搜索至叶子结点时，可以确定到目前为止最好的解。
B.右(0)分支的剪枝:已装入背包内的物品价值和+剩余物品装剩余背包容量所能获得的最大价值(物品可分割，即用背包问题的贪心算法求得的最大价值)>当前最优值bestp,就剪枝:
C.左(1)分支的剪枝:当选择装入背包的物品重量之和超过背包容量时就剪枝。
D.解空间树是子集树

• B

5.根据A,B描述的正确与否， 从如下选项中找到正确答案

A.A对，B错
B.A对，B对
C.A错，B对
D.A错、B错

• A

6.旅行商问题的回溯算法所需的计算时间为O（）

A.n^2
B.nlogn
C.n!
D.2^n

• C

【6】分支限界法

1.从上述选项中找出答案。

A.(1)(2)(4)
B.(2)(3)(4)
C.(1)(3)(4)
D.(1)(2)(3)

• A

2.分支限界法中，扩展出的孩子结点在入队时，存储该孩子结点的父结点的地址和左孩子标志。其目的是什么

A.为了方便判定是否已搜索到达叶子层
B.为了构造最优解
C.为了计算最优值
D.为了确定其孩子结点在队列中的位置

• B

3.根据其正确与否，给出答案

A.(1)正确，(2)错误
B.(1)错误，(2)错误
C.(1)正确，(2)正确
D.(1)错误，(2)正确

• C

4.下面是优先队列式分支限界算法解0-1背包问题的部分主代码，分析代码将【】内的代码补齐。

A.【1]i!=n+1,【2】cw=cw+w[]
B.【1】i<n,【2】besp=cp+p[i]
C.【1]i<n+1,【2】besp=cp+p[i]
D.【1】i!=n,【2】cw=cw+w[i]

• D

5.下列算法中不能解决0/1背包问题的是()

A.动态规划
B.回溯法
C.分支限界法
D.贪心法

• D

【7】随机化算法

1.一致的p正确的偏y0的蒙特卡洛算法，下面解释不正确的是?

A.当正确解是y0,而蒙特卡洛算法得到的解不是y0
B.一致是指蒙特卡洛算法对于一个实例，其正确解是唯一的。
C.猜硬币的正反面问题，因为猜一次正确的概率是50%，所以不能使用蒙特卡洛算法解决。
D.运行蒙特卡洛算法p次，至少有一次是正确的。

• D

2.有这样一种算法，运行一次一定能找到问题的解，有时不知其是否正确，可以确定的是该解高概率(大于50%)是正确的。这种算法是?

A.拉斯维加斯算法
B.数值概率算法
C.蒙特卡洛算法
D.舍伍德算法

• C

3.n=12皇后问题的三种不同的解决方案:回溯法、拉斯维加斯算法、拉斯维加斯算法+回溯法。对于给定的一个实例，(1)平均耗费时间最少的是那种方案?，(2)平均耗费时间最多的是那种方案?

A.(1)拉斯维加斯+回湖(2)回溯法
B.(1)回溯法(2)拉斯维加斯
C.(1)拉斯维加斯(2)回溯法
D.(1)回溯法(2)拉斯维加斯+回溯法

• A

4.n后问颖，假设n=8,用拉斯维加斯算法求解n后问颖时，若x[1]=5(即第一个皇后放在了第5列)，则 第2个皇后的y[]是和count分别是()。(x数组下标都从1开始,y数组下标从0开始)

A.

B.

C.

D.

• B

5.下面说法正确的是()

A.线性同余法是产生伪随机数的最常用的方法
B.随机算法是一种使用概率和统计方法在其执行过程中对于下一计算步骤作出随机选择的算法
C.当最坏和平均情况差别较大时，舍伍德算法可以消除好坏实例的差别，达到平均实例的性能
D.增加蒙特卡罗算法的求解次数，可使求解错误的概率任意小

• ABCD