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

前言

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

一.选择题

【1】算法绪论

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)=Q(g(N))，即f(N)的阶( )g(N)的阶。

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

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

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

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

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

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

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

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

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

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

A. 在这里插入图片描述

B. 在这里插入图片描述

C. 在这里插入图片描述

D. 在这里插入图片描述

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

A. 在这里插入图片描述

B. 在这里插入图片描述

C. 在这里插入图片描述

D. 在这里插入图片描述

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

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

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

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

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

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

【2】分支递归

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

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

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

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

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)是将子问题的解合并为问题的解的时间复杂性。

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

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

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

A.贪心法
B.动态规划法
C.回溯法
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)

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

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

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

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

【3】动态规划

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

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

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

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

在这里插入图片描述
A.(A1((A2A3)(A4A5)))
B.(((A1A2)(A3A4))A5)
C.(((A1A2) A3) (A4A5))
D.((A1(A2A3))(A4A5))

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

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

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

在这里插入图片描述
A.15125,(A2A3)((A4A5)A6)
B.10500,(A2A3)((A4A5)A6)
C.15125,(A2(A3A4))(A5A6)
D.10500,(A2(A3A4))(A5A6)

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

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

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

【4】贪心算法

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

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

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

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

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

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

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

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

【5】回溯法

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

A. 在这里插入图片描述

B. 在这里插入图片描述

C. 在这里插入图片描述

D. 在这里插入图片描述

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

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

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

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

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

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