首页 › 题库 › 信息学奥赛 › 8.1 深度优先搜索

信息学奥赛-入门级 题库

共 10 道题 · 按题型筛选,点「查看答案」核对解析
章节 8.1 深度优先搜索 清除
1 单选题 适中 信息学奥赛 ·信息学奥赛-入门级 · 8.1 深度优先搜索

以 a 为起点,对右边的无向图进行深度优先遍历,则 b、 c、 d、 e 四个点中有可能作为最后一个遍历到的点的个数为( )。

A
1
B
2
C
3
D
4
答案与解析
正确答案:B

从a向b的方向开始搜索的终点是e(a-b-d-c-e),从a向c的方向开始搜索的终点是b(a-c-e-d-b)或c(a-c-d-b-e),则最多有两个终点分为b和c。

题目详情
2 单选题 适中 信息学奥赛 ·信息学奥赛-入门级 · 8.1 深度优先搜索

设有100个数据元素,采用折半搜索时, 最大比较次数为( )。

A
6
B
7
C
8
D
10
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
3 单选题 适中 信息学奥赛 ·信息学奥赛-入门级 · 8.1 深度优先搜索

以 A0 作为起点,对下面的无向图进行深度优先遍历时,遍历顺序不可能是( )。

A
A0, A1, A2, A3
B
A0, A1, A3, A2
C
A0, A2, A1, A3
D
A0, A3, A1, A2
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
4 单选题 适中 信息学奥赛 ·信息学奥赛-入门级 · 8.1 深度优先搜索

通常在搜索引擎中, 对某个关键词加上双引号表示( )。

A
排除关键词,不显示任何包含该关键词的结果
B
将关键词分解,在搜索结果中必须包含其中的一部分
C

精确搜索,只显示包含整个关键词的结果

D

站内搜索,只显示关键词所指向网站的内容

答案与解析
正确答案:C
这道题暂未补解析。
题目详情
5 单选题 适中 信息学奥赛 ·信息学奥赛-入门级 · 8.1 深度优先搜索

广度优先搜索时,需要用到的数据结构是(      )。

A
链表
B
队列
C
栈
D
散列表
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
6 单选题 适中 信息学奥赛 ·信息学奥赛-入门级 · 8.1 深度优先搜索

(       )是一种选优搜索法,按选优条件向前搜索,以达到目标。当搜索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择。

A
回溯法
B
枚举法
C
动态规划
D
贪心
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
7 单选题 适中 信息学奥赛 ·信息学奥赛-入门级 · 8.1 深度优先搜索

以 a 为起点,对右边的无向图进行深度优先遍历,则 b、 c、 d、 e 四个点中有可能作为最后一个遍历到的点的个数为( )。

A
1
B
2
C
3
D
4
答案与解析
正确答案:B

从a向b的方向开始搜索的终点是e(a-b-d-c-e),从a向c的方向开始搜索的终点是b(a-c-e-d-b)或c(a-c-d-b-e),则最多有两个终点分为b和c。

题目详情
8 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 8.1 深度优先搜索

完善程序(2)

(汉诺塔问题)给定三根柱子,分别标记为 A、B 和 C。初始状态下,柱子A上有若干个圆盘,这些圆盘从上到下按从小到大的顺序排列。任务是将这些圆盘全部移到柱子c上,且必须保持原有顺序不变。在移动过程中,需要遵守以不规则:

1.只能从一根柱子的顶部取出圆盘,并将其放入另一根柱子的顶部。

2.每次只能移动一个圆盘

3.小圆盘必须始终在大圆盘之上。

试补全程序

#include <bits/stdc++.h>
using namespace std;
void move(char src, char tgt) {
cout << "从柱子" << src << "挪到柱子上" << tgt << endl;
}
void dfs(int i, char src, char tmp, char tgt) {
if(i == ___(1)___) {
move(___(2)___);
return;
}
dfs(i-1, ___(3)___);
move(src, tgt);
dfs(___(4)___, ___(5)___);
}
int main() {
int n;
cin >> n;
dfs(n, 'A', 'B', 'C');
}


答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
9 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 8.1 深度优先搜索

#include <algorithm>

#include <iostream>

using namespace std;                     

                                         

int n;                                   

int d[50][2];                            

int ans;                                 

                                        

void dfs(int n, int sum) {               

  if (n == 1) {                            

    ans = max(sum, ans);           

    return;                                   

  }                                        

  for (int i = 1; i < n; ++i) {            

    int a = d[i - 1][0], b = d[i - 1][1];  

    int x = d[i][0], y = d[i][1];            

    d[i - 1][0] = a + x;                     

    d[i - 1][1] = b + y;                     

    for (int j = i; j < n - 1; ++j)            

      d[j][0] = d[j + 1][0], d[j][1] = d[j + 1][1];

    int s = a + x + abs(b - y);              

    dfs(n - 1, sum + s);                    

    for (int j = n - 1; j > i; --j)          

      d[j][0] = d[j - 1][0], d[j][1] = d[j - 1][1];

    d[i - 1][0] = a, d[i - 1][1] = b;        

    d[i][0] = x, d[i][1] = y;                

  }                                        

}                                        

                                       

int main() {                             

  cin >> n;                                

  for (int i = 0; i < n; ++i)              

  cin >> d[i][0];

  for (int i = 0; i < n;++i)

     cin >> d[i][1];

  ans = 0;

  dfs(n, 0);

  cout << ans << endl;

  return 0;

}

假设输入的n是不超过5。的正整数,d[i][0], d[i][l]都是不超过 10000的正整数,完成下面的判断题和单选题:

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
10 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 8.1 深度优先搜索

#include <algorithm>

#include <iostream>

using namespace std;                     

                                         

int n;                                   

int d[50][2];                            

int ans;                                 

                                        

void dfs(int n, int sum) {               

  if (n == 1) {                            

    ans = max(sum, ans);           

    return;                                   

  }                                        

  for (int i = 1; i < n; ++i) {            

    int a = d[i - 1][0], b = d[i - 1][1];  

    int x = d[i][0], y = d[i][1];            

    d[i - 1][0] = a + x;                     

    d[i - 1][1] = b + y;                     

    for (int j = i; j < n - 1; ++j)            

      d[j][0] = d[j + 1][0], d[j][1] = d[j + 1][1];

    int s = a + x + abs(b - y);              

    dfs(n - 1, sum + s);                    

    for (int j = n - 1; j > i; --j)          

      d[j][0] = d[j - 1][0], d[j][1] = d[j - 1][1];

    d[i - 1][0] = a, d[i - 1][1] = b;        

    d[i][0] = x, d[i][1] = y;                

  }                                        

}                                        

                                       

int main() {                             

  cin >> n;                                

  for (int i = 0; i < n; ++i)              

  cin >> d[i][0];

  for (int i = 0; i < n;++i)

     cin >> d[i][1];

  ans = 0;

  dfs(n, 0);

  cout << ans << endl;

  return 0;

}

假设输入的n是不超过5。的正整数,d[i][0], d[i][l]都是不超过 10000的正整数,完成下面的判断题和单选题:

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情