首页 › 题库 › GESP编程能力等级认证 › 3 图的定义及遍历

GESP-C++七级 题库

共 80 道题 ,第 1 / 4 页 · 按题型筛选,点「查看答案」核对解析
章节 3 图的定义及遍历 清除
1 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

一棵深度为6(根节点深度为1)的完全二叉树,节点总数最少有( )。

A
31
B
32
C
63
D
64
答案与解析
正确答案:B
完全二叉树的深度由根节点开始计算,深度为1。深度为h的完全二叉树,其节点数最少的情况出现在第h层只有一个节点时。前h-1层构成一棵满二叉树,节点总数为2^(h-1) - 1。第h层至少有一个节点。将前h-1层节点数与第h层最小节点数相加,得到整棵树的最小节点总数。根据深度值代入计算即可得出结果。
题目详情
2 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

一个简单无向图G有36条边,且每个顶点的度数都为4,则图 的顶点个数为( )。

A
9
B
12
C
18
D
36
答案与解析
正确答案:C
利用图论中边数与顶点度数之和的关系,所有顶点的度数之和等于边数的两倍。设顶点个数为n,每个顶点的度数为4,则总度数为4n。根据关系式,4n等于边数36的两倍。建立等式并求解n。
题目详情
3 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

假设一个算法时间复杂度的递推式是 ,和T(0) = 1 ,那么这个算法的时间复杂度是(  )。

A
B
C
O(n2)
D
O(n2 log n)
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
4 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

下面这个有向图的强连通分量的个数是( )。

A
3
B
4
C
5
D
6
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
5 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

有5个字符,它们出现的次数分别为2次、2次、3次、3次、5次。现在要用哈夫曼编码的方式来为这些字符进行编码,最小加权路径长度WPL(每个字符的出现次数 它的编码长度,再把每个字符结果加起来)的值为( )。2025.12-7

A
30
B
34
C
43
D
47
答案与解析
正确答案:B
将字符的出现次数作为叶子节点的权值,构建哈夫曼树。每次选择当前权值最小的两个节点合并为一个新节点,新节点的权值为两者之和,直至所有节点合并为根节点。每个字符的编码长度等于其对应叶子节点在树中的深度。计算每个字符的权值与其编码长度的乘积,再求总和,即得WPL。
题目详情
6 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

下面哪一个可能是下图的深度优先遍历序列( )。2025.12-7

A
1, 5, 6, 3, 2, 8, 9, 4, 7
B
1, 5, 8, 9, 7, 4, 6, 3, 2
C
3, 2, 1, 4, 7, 6, 9, 5, 8
D
2, 5, 6, 3, 8, 7, 9, 4, 1
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
7 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

假定只有一个根节点的树的深度为 ,则一棵有 个节点的完全二叉树,则树的深度为?( )

A
B
C
D
不能确定。
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
8 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

对于如下图的二叉树,说法正确的是?( )

A
先序遍历是 ABDEC 。
B
中序遍历是 BDACE 。
C
后序遍历是 DBCEA 。
D
广度优先遍历是 ABCDE 。
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
9 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

图的存储和遍历算法,下面说法【错误】的是?( )

A
图的深度优先遍历须要借助队列来完成。
B
图的深度优先遍历和广度优先遍历对有向图和无向图都适用。
C
使用邻接矩阵存储一个包含 个顶点的有向图,统计其边数的时间复杂度为 。
D
同一个图分别使用出边邻接表和入边邻接表存储,其边结点个数相同。
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
10 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

一个连通的简单有向图,共有28条边,则该图至少有( )个顶点?

A
5
B
6
C
7
D
8
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
11 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

下面程序的时间复杂度为?( )

int rec_fib[MAX_N];
int fib(int n) {
    if (n <= 1)
        return n;
    if (rec_fib[n] == 0)
        rec_fib[n] = fib(n - 1) + fib(n - 2);
    return rec_fib[n];
}
A
B
C
D
O(n)
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
12 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

下面 search 函数的平均时间复杂度为?( )

int search(int n, int * p, int target) {
    int low = 0, high = n;
    while (low < high) {
        int middle = (low + high) / 2;
        if (target == p[middle]) {
            return middle;
        } else if (target > p[middle]) {
            low = middle + 1;
        } else {
            high = middle;
        }
    }
    return -1;
}
A
O(n log(n))
B
O(n)
C
O(long(n))
D
O(1)
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
13 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

下面程序的时间复杂度为?( )

int primes[MAXP], num = 0;
bool isPrime[MAXN] = {false};
void sieve() {
    for (int n = 2; n <= MAXN; n++) {
        if (!isPrime[n])
            primes[num++] = n;
        for (int i = 0; i < num && n * primes[i] <= MAXN; i++) {
            isPrime[n * primes[i]] = true;
            if (n % primes[i] == 0)
                break;
        }
    }
}
A
O(n)
B
O(n×log n)
C
O(n×log log n)
D
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
14 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

下列选项中,哪个【不可能】是下图的广度优先遍历序列?( )

A
1, 2, 4, 5, 3, 7, 6, 8, 9
B
1, 2, 5, 4, 3, 7, 8, 6, 9
C
1, 4, 5, 2, 7, 3, 8, 6, 9
D
1, 5, 4, 2, 7, 3, 8, 6, 9
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
15 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

下列关于树和图的说法,【错误】的是?( )

A
树是一种有向无环图,但有向无环图不都是一棵树。
B
如果把树看做有向图,每个节点指向其子节点,则该图是强连通图。
C
N 个顶点且连通的无向图,其最小生成树一定包含 N - 1 个条边。
D
N + 1个顶点、N 条边的有向图,一定不是强连通的。
答案与解析
正确答案:B

B 应该是—个有向无环图。(树和图结构)

题目详情
16 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

下列关于有向图的说法,错误的是( )。

A
n 个顶点的弱连通有向图,最少有 n−1 条边。
B
n 个顶点的强连通有向图,最少有 n 条边。
C
n 个顶点的有向图,最多有 n×(n−1) 条边。
D
n 个顶点的有向完全图,有 n×(n−1) 条边。
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
17 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

一个简单无向图有10个结点、6条边。在最差情况,至少增加多少条边可以使其连通?( )

A
3
B
4
C
6
D
9
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
18 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

上题中程序的时间复杂度为( )。

A
O(N)
B
O(NlogN)
C
O(N3/2)
D
O(N2)
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
19 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

下面 init_sieve 函数的时间复杂度为( )。

int sieve[MAX_N];
void init_sieve(int n) {
	for (int i = 1; i <= n; i++)
		sieve[i] = i;
	for (int i = 2; i <= n; i++)
		for (int j = i; j <= n; j += i)
			sieve[j]--;
}
A
O(n)
B
O(nlogn)
C
O(n2)
D
无法正常结束。
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
20 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

下列选项中,哪个不可能是下图的深度优先遍历序列( )。

A
1, 2, 3, 5, 7, 8, 6, 9, 4
B
1, 4, 7, 8, 9, 5, 2, 3, 6
C
1, 5, 7, 8, 9, 4, 2, 3, 6
D
1, 2, 3, 6, 9, 8, 5, 7, 4
答案与解析
正确答案:A
这道题暂未补解析。
题目详情