2025年广度优先搜索是回溯吗（广度优先搜索的特点和使用场合）

大家好，我是讯享网，很高兴认识大家。

 <p> 1.给定二分图G = 中无孤立点，|V|=n，其最大流算法求得最大流f, 则 G的（）=f.<br>A:最大匹配数

讯享网

B:最小顶点覆盖 C:最大独立数 D:最小边覆盖
答案:最大匹配数最小顶点覆盖
2.贪心算法的基本要素是
A:最优子结构性质 B:独立子问题的性质 C:贪心选择的性质 D:无后效性性质
答案:最优子结构
3.贪心算法的常用证明方法有
A:交换论证 B:反证 C:领先 D:界
答案:领先反证交换论证界
4.最短路算法中适用于负权图的是（）
A:Bellman算法 B:SPFA算法 C:Floyd算法 D:Dijkstra算法
答案:Floyd算法SPFA算法Bellman算法
5.动态规划算法的基本要素有（）。
A:无后效性 B:贪心选择性质 C:重叠子问题性质 D:最优子结构性质
答案:最优子结构; 重叠子问题
6.动态规划算法的特点（）
A:子问题独立 B:自顶向下计算 C:子问题重叠 D:自底向上计算
答案:子问题重叠自底向上计算
7.时间复杂度为O(nlogn)的排序算法有
A:堆排序 B:计数排序 C:快速排序 D:合并排序
答案:合并排序堆排序
8.枚举算法的优化方法有
A:优化数学模型 B:优化数据结构 C:减少枚举变量 D:减少枚举变量的值域
答案:减少枚举变量减少枚举变量的值域优化数据结构优化数学模型
9.改进分治算法的方法有（）
A:减少问题的规模 B:减少合并的时间 C:改进分治的均衡度 D:减少子问题的个数
答案:减少合并的时间改进分治的均衡度
10.最好情况下，时间复杂度为O（n）的排序算法有
A:插入排序 B:冒泡排序 C:计数排序 D:直接选择排序
答案:冒泡排序插入排序计数排序
11.从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法，最常见的方式有（）。
A:FIFO分支限界法 B:栈式分支限界法 C:优先队列式分支限界法 D:队列式分支限界法

32.下面说法正确的是（）
A:多源点和多汇点的网络流问题可以通过增加一个“超源点”和“超汇点”转化为单源点和单汇点的网络流问题。
B:剩余网络中从源s到汇t的最小费用路是剩余网络中从s到t的以费用为权的最短路
C:最小费用最大流算法寻找从源点s到汇点t的最小费用路，然后沿最小费用路增流，直至找到最小费用流。
D:无向图的每条边变为方向相反的两条边，容量是原边的容量，这样无向图的最大流问题变换为有向图的最大流问题。

33.

对于n个物品，背包容量为C的0-1背包问题，其动态规划算法的空间效率为（）。

A:
B:
C:O(nC）
D:

34.函数
讯享网的渐进表达式为（）。
A:
B:
C:n
D:logn

35.n!=o(2ⁿ)
A:错
B:对

36.对于n皇后问题，需要满足( )。
A:任意两个皇后不能处在同一右斜线
B:任意两个皇后不能处在同一左斜线
C:任意两个皇后不能处在同一列
D:任意两个皇后不能处在同一行

37.

在《阿里巴巴与四十大盗》的故事中，当阿里巴巴进入到强盗们藏宝的山洞中时，面对洞中堆满的金银财宝，阿里巴巴也想让乡亲们看看眼界，见识下这些宝物。于是他想每样宝物只拿一个，如果太重就用锤子凿开，但他骑来的毛驴运载能力有限，怎样才能用驴子运走最大价值的宝物分给穷人们呢？请根据以上描述回答下列问题：

38.为帮助阿里巴巴解决问题,可以使用贪心算法解决此问题,则采用的贪心策略为:( )
39.现有一批宝物,价值和重量如表1所示,毛驴运载能力为m=30,使用贪心算法,最终阿里巴巴能带走的最大价值的宝物序号依次为:( )表 1 宝物清单宝物序号重量价值15
40.请写出回溯法中遍历排列树的算法框架程序
41.程序块（）是回溯法中遍历排列树的算法框架程序。
42.备忘录法使用的是自底向上的求解方式。（）
A:对
B:错

43.下面说法错误的是
A:设G是n阶无孤立点的图，则V*是G的顶点覆盖，当且仅当V-V*是G的独立集。
B:给定G = , G的匹配中任何两条边都没有公共顶点。
C:设 f 任意流, (A, B) 是任意 s-t 割, 则流值不小于割的容量。
D:给定连通图G, BFS遍历得到层次图，如果同一层中的结点无边相连，则G是二分图。

44.以下是NP完全问题的（）
A:最短路
B:最大公因子
C:部分背包
D:0-1背包

94.代码填空【快速排序的分区函数：以第1个元素为基准元素】int swap(int a[], int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp;}int partition(int a[], int p, int q) { int x = a[p]; int i = p, j; for(j = p + 1;j if(a[j] i++; ___(1)_____; } } ______(2)________; return i;}
A:(1) swap(a,i,j)(2) swap(a,p,i) B:(1) swap(a,q,i)(2) swap(a,p,q) C:(1) swap(a,q,j)(2) swap(a,p,q) D:(1) swap(a,i,j)(2) swap(a,i,q)

115.函数n^²⁄₁₀ + 2^n的渐进表达式为( )。
A:O(n) B:O(n^²⁄₁₀) C:O(2^n) D:O(n^2)

讯享网 </p>

2025年广度优先搜索是回溯吗（广度优先搜索的特点和使用场合）

相关推荐