图与哈希表
当前没有测试数据。
- 无向完全图是图中每对顶点之间都恰好有一条边的简单图。已知无向完全图G有7个顶点，则它共有（ ）条边？ {{ select(1) }}
- 7
- 21
- 42
- 49
- 对一个有向图而言，如果每个节点都存在到达其他任何节点的路径，那么就称它是强连通的。例如，下图就是一个强连通图。事实上，在删掉边（ ）后，它依然是强连通的？
{{ select(2) }}
- a
- b
- c
- d
- 将（2, 6, 10, 17）分别存储到某个地址区间为0~10 的哈希表中，如果哈希函数h(x) = （ ），将不会产生冲突，其中a mod b表示 𝑎a 除以 𝑏b 的余数？ {{ select(2) }}
- 在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。下图是一个有4个顶点、6条边的连通图。若要使它不再是连通图，至少要删去其中的（ ）条边？
{{ select(4) }}
- 1
- 2
- 3
- 4
- 一棵具有5层的满二叉树中结点数为？ {{ select(5) }}
- 31
- 32
- 33
- 16
- 设简单无向图 G 有 16 条边且每个顶点的度数都是 2，则图 G 有()个顶点？ {{ select(6) }}
- 10
- 12
- 8
- 16
- 设 G 是有 n 个结点、m 条边（n≤m）的连通图，必须删去 G 的（ ）条边，才能使得 G 变成一棵树？ {{ select(7) }}
- m - n + 1
- m - n
- m + n + 1
- n - m + 1
- 由四个没有区别的点构成的简单无向连通图的个数是? {{ select(8) }}
- 6
- 7
- 8
- 9
- 有 10 个顶点的无向图至少应该有（ ）条边才能确保是一个连通图？ {{ select(9) }}
- 9
- 10
- 11
- 12
- 对于有n个顶点、m条边的无向联通图（m>n），需要删掉（ ）条边才能使其成为一棵树？ {{ select(10) }}
- n - 1
- m - n
- m - n - 1
- m - n + 1
- 考虑由 N 个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在（ ）个非零元素？ {{ select(11) }}
- N-1
- N
- N+1
- N的平方
- 以下对数据结构的表述不恰当的一项为? {{ input(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 }
①处应填{{ select(13) }}
- image[r][c] == prev_color
- image[r][c] != prev_color
- image[r][c] == new_color
- image[r][c] != new_color
②处应填{{ select(14) }}
- image[cur.r+1][cur.c] = new_color
- image[cur.r][cur.c] = new_color
- image[cur.r][cur.c+1] = new_color
- image[cur.r][cur.c] = prev_color
③处应填{{ select(15) }}
- Point(pt.r, pt.c)
- Point(pt.r, pt.c+1)
- Point(pt.r+1, pt.c)
- Point(pt.r+1, pt.c+1)
④处应填{{ select(16) }}
- prev_color = image[p.r][p.c]
- new_color = image[p.r][p.c]
- image[p.r][p.c] = prev_color
- image[p.r][p.c] = new_color
⑤处应填{{ select(17) }}
- queue.push(p)
- queue.push(pt)
- queue.push(cur)
- queue.push(Point(ROWS,COLS))
- 考虑一个有向无环图，该图包含4条有向边：(1 , 2) , (1 , 3) , (2 , 4)和(3 , 4) 。以下哪个选项是这个有向无环图的一个有效的拓扑排序？ {{ input(18) }}
- 4,2,3,1
- 1,2,3,4
- 1,2,4,3
- 2,1,3,4