爱迪国际C++章节测试-图

*
1.单选题
无向完全图是图中每对顶点之间都恰好有一条边的简单图。已知无向完全图G有7个顶点，则它共有（ ）条边。
A 7
B 21
C 42
D 49
*
2.单选题
对一个有向图而言，如果每个节点都存在到达其他任何节点的路径，那么就称它是强连通的。例如，下图就是一个强连通图。事实上，在删掉边（ ）后，它依然是强连通的。
A. a
B. b
C. c
D. d
*
3.单选题
将（2, 6, 10, 17）分别存储到某个地址区间为0~10 的哈希表中，如果哈希函数h(x) = （ ），将不会产生冲突，其中
a mod b表示 a 除以 b 的余数。
A. x mod 11
B. x 2 mod 11
C. (2x) mod 11
D. ⌊sqrt(x)⌋ mod 11，其中⌊sqrt(x)⌋表示sqrt(x)下取整
*
4.单选题
在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。下图是一个有4个顶点、6条边的连通图。若要使它不再是连通图，至少要删去其中的（ ）条边。
A. 1
B. 2
C. 3
D. 4
*
5.单选题
设简单无向图 G 有 16 条边且每个顶点的度数都是 2，则图 G 有()个顶点。
A 10
B 12
C 8
D 16
*
6.单选题
设 G 是有 n 个结点、m 条边（n≤m）的连通图，必须删去 G 的（ ）条边，才能使得 G 变成一棵树。
A. m−n+1
B. m−n
C. m+n+1
D. n−m+1
*
7.单选题
由四个没有区别的点构成的简单无向连通图的个数是（ ）。
A. 6
B. 7
C. 8
D. 9
*
8.单选题
有 10 个顶点的无向图至少应该有（ ）条边才能确保是一个连通图。
A. 9
B. 10
C. 11
D. 12
*
9.单选题
对于有n个顶点、m条边的无向联通图（m>n），需要删掉（ ）条边才能使其成为一棵树。
A.n−1
B.m−n
C.m−n−1
D.m−n+1
*
10.单选题
考虑由 N 个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在（ ）个非零元素。
A N-1
B N
C N+1
D N的平方
*
11.单选题
以下对数据结构的表述不恰当的一项为:（ ）。
A 图的深度优先遍历算法常使用的数据结构为栈。
B 栈的访问原则为后进先出，队列的访问原则是先进先出。
C 队列常常被用于广度优先搜索算法。
D 栈与队列存在本质不同，无法用栈实现队列。
12.填空题
（洪水填充）现有用字符标记像素颜色的 8x8 图像。颜色填充的操作描述如下：给定起始像素的位置和待填充的颜色，将起始像素和所有可达的像素（可达的定义：经过一次或多次的向上、下、左、右四个方向移动所能到达且终点和路径上所有像素的颜色都与起始像素颜色相同），替换为给定的颜色。*
试补全程序。
01 #include <bits/stdc++.h>
02 using namespace std;
03
04 const int ROWS = 8;
05 const int COLS = 8;
06
07 struct Point {
08 int r, c;
09 Point(int r, int c) : r(r), c(c) {}
10 };
11
12 bool is_valid(char image[ROWS][COLS], Point pt,
13 int prev_color, int new_color) {
14 int r = pt.r;
15 int c = pt.c;
16 return (0 <= r && r < ROWS && 0 <= c && c < COLS &&
17 ① && image[r][c] != new_color);
18 }
19
20 void flood_fill(char image[ROWS][COLS], Point cur, int new_color) {
21 queue<Point> queue;
22 queue.push(cur);
23
24 int prev_color = image[cur.r][cur.c];
25 ②;
26
27 while (!queue.empty()) {
28 Point pt = queue.front();
29 queue.pop();
30
31 Point points[4] = {③, Point(pt.r - 1, pt.c),
32 Point(pt.r, pt.c + 1), Point(pt.r, pt.c - 1)};
33 for (auto p : points) {
34 if (is_valid(image, p, prev_color, new_color)) {
35 ④;
36 ⑤;
37 }
38 }
39 }
40 }
41
42 int main() {
43 char image[ROWS][COLS] = {{'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g'},
44 {'g', 'g', 'g', 'g', 'g', 'g', 'r', 'r'},
45 {'g', 'r', 'r', 'g', 'g', 'r', 'g', 'g'},
46 {'g', 'b', 'b', 'b', 'b', 'r', 'g', 'r'},
47 {'g', 'g', 'g', 'b', 'b', 'r', 'g', 'r'},
48 {'g', 'g', 'g', 'b', 'b', 'b', 'b', 'r'},
49 {'g', 'g', 'g', 'g', 'g', 'b', 'g', 'g'},
50 {'g', 'g', 'g', 'g', 'g', 'b', 'b', 'g'}};
51
52 Point cur(4, 4);
53 char new_color = 'y';
54
55 flood_fill(image, cur, new_color);
56
57 for (int r = 0; r < ROWS; r++) {
58 for (int c = 0; c < COLS; c++) {
59 cout << image[r][c] << " ";
60 }
61 cout << endl;
62 }
63 // 输出：
64 // g g g g g g g g
65 // g g g g g g r r
66 // g r r g g r g g
67 // g y y y y r g r
68 // g g g y y r g r
69 // g g g y y y y r
70 // g g g g g y g g
71 // g g g g g y y g
72
73 return 0;
74 }
40.①处应填（ ）
A. image[r][c] == prev_color
B. image[r][c] != prev_color
C. image[r][c] == new_color
D. image[r][c] != new_color
41.②处应填（ ）
A. image[cur.r+1][cur.c] = new_color
B. image[cur.r][cur.c] = new_color
C. image[cur.r][cur.c+1] = new_color
D. image[cur.r][cur.c] = prev_color
42.③处应填（ ）
A. Point(pt.r, pt.c)
B. Point(pt.r, pt.c+1)
C. Point(pt.r+1, pt.c)
D. Point(pt.r+1, pt.c+1)
43.④处应填（ ）
A. prev_color = image[p.r][p.c]
B. new_color = image[p.r][p.c]
C. image[p.r][p.c] = prev_color
D. image[p.r][p.c] = new_color
44.⑤处应填（ ）
A. queue.push(p)
B. queue.push(pt)
C. queue.push(cur)
D. queue.push(Point(ROWS,COLS))
1.判题时不忽略大小写，如答案为B，而你输入的答案为b，则会被判错！
2.判题时不会忽略你输入答案的前后空格，如答案为B，而你输入的答案为空格B空格，则会被判错！
3.判断题 A代表正确、B代表错误
问题1：问题2：问题3：问题4：问题5：
*
13.单选题
考虑一个有向无环图，该图包含4条有向边:(1 , 2) , (1 , 3) , (2 , 4)和(3 , 4) 。以下哪个选项是这个有向无环图的一个有效的拓扑排序?
A 4,2,3,1
B 1,2,3,4
C 1,2,4,3
D 2,1,3,4
*
14.单选题
有向图中每个顶点的度等于该顶点的( )。
A 入度
B 出度
C 入度和出度之和
D 入度和出度之差
问卷星提供技术支持
举报