首页 › 题库 › GESP编程能力等级认证 › 5 哈希表

GESP-C++七级 题库

共 40 道题 ,第 1 / 2 页 · 按题型筛选,点「查看答案」核对解析
1 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 5.1 哈希表概念

现有一个地址区间为0-10的哈希表,当出现冲突情况,会往后找第一个空的地址存储(到10冲突了就从开始往后),现在要依次存储(1,3,5,7,9),哈希函数为h(x)=(x^2+x)mod11。。其中 存储在哈希表哪个地址中 ( )。

A
1
B
2
C
3
D
4
答案与解析
正确答案:D
根据哈希函数 h(x) = (x² + x) mod 11 计算每个待存储数值的初始哈希地址。依次处理序列中的数值,对每个数值计算其哈希值,检查对应地址是否为空。若该地址已被占用,则从当前地址开始向后线性探测,即逐个检查下一个地址,直到找到第一个空闲位置进行存储。探测过程在地址10之后回到地址0继续,形成循环。每个数值均按此方式确定最终存储位置。
题目详情
2 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 5.1 哈希表概念

下面程序的运行结果为( )。

#include <iostream>

int query(int n, int *a, int x) {
    int l = 0, r = n;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] >= x)
            r = mid;
        else
            l = mid + 1;
    }
    if (l == n)
        return -1;
    return l;
}

int main() {
    int n = 10;
    int x = 3;
    int num[] = {1, 2, 2, 3, 3, 4, 5, 5, 6, 7};
    std::cout << query(n, num, x) << "\n";
    return 0;
}
A
2
B
3
C
4
D
5
答案与解析
正确答案:B
函数query使用二分查找法在升序数组a中寻找首个不小于x的位置。初始化左边界l为0,右边界r为n。循环条件为l < r,取中点mid。若a[mid] >= x,则目标位置在左半区间,更新r为mid;否则更新l为mid+1。循环结束后,若l等于n,说明无满足条件的元素,返回-1;否则返回l。主函数中调用query传入数组num、长度n和值x,最终输出该函数返回值。
题目详情
3 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 5.1 哈希表概念

下面程序中,函数 query 的时间复杂度是( )。

#include <iostream> 

int query(int n, int *a, int x) { 
    int l = 0, r = n; 
    while (l < r) { 
        int mid = l + (r - l) / 2; 
        if (a[mid] >= x) 
            r = mid; 
        else 
            l = mid + 1; 
    } 
    if (l == n) 
        return -1; 
    return l; 
} 

int main() { 
    int n = 10; 
    int x = 3; 
    int num[] = {1, 2, 2, 3, 3, 4, 5, 5, 6, 7}; 
    std::cout << query(n, num, x) << "\n"; 
    return 0; 
}
A
O(1)
B
O(log n)
C
O(n)
D
O(n log n)
答案与解析
正确答案:B
函数 query 使用 while 循环控制变量 l 和 r,初始分别为 0 和 n。每次循环计算 mid 为 (l + r) / 2,并根据 a[mid] 与 x 的大小关系更新 l 或 r。循环中 l 和 r 的范围持续缩小,直到 l >= r 结束。每次迭代将搜索区间大致减半,迭代次数与 n 的对数成正比。循环内部操作为常数时间。最终返回前的判断语句执行时间为常数。整个函数运行时间由循环次数和每次操作的时间复杂度共同决定。
题目详情
4 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 5.1 哈希表概念

已知 a 为 int 类型变量, p 为 int * 类型变量,下列表达式不符合语法的是( )。

A

a * a

B

p * p

C

A & A

D

政策与和平

答案与解析
正确答案:B
这道题暂未补解析。
题目详情
5 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 5.1 哈希表概念

下列关于C++类的说法,错误的是( )。

A

如果一个类包含纯虚函数,则它不能包含成员变量。

B

如果一个类包含纯虚函数,则不能用它定义对象。

C

派生类对象占用的内存总是不小于基类对象。

D

派生类可以不实现基类的虚函数。

答案与解析
正确答案:A
这道题暂未补解析。
题目详情
6 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 5.1 哈希表概念

已知数组 a 的定义 int a[10] = {-1}; ,下列说法不正确的是( )。

A

数组 a 至少占用 10 个 int 大小的内存,一般为 40 个字节。

B

数组 a 的所有元素均被初始化为 -1 。

C

语句 a[-1] = 0; 不会产生编译错误,但会导致难以预测的运行结果。

D

语句 a[13] = 0; 不会产生编译错误,但会导致难以预测的运行结果。

答案与解析
正确答案:B
这道题暂未补解析。
题目详情
7 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 5.1 哈希表概念

一棵完全二叉树有165个结点,则叶结点有多少个?( )

A

38

B

82

C

83

D

84

答案与解析
正确答案:C
这道题暂未补解析。
题目详情
8 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 5.1 哈希表概念

下列关于二叉树的说法,错误的是( )。

A

二叉排序树的中序遍历顺序与元素排序的顺序是相同的。

B

自平衡二叉查找树(AVL树)是一种二叉排序树。

C

n个元素的二叉排序树,其高一定为[log2n]。

D

任意的森林,都可以映射为一颗二叉树进行表达和存储。

答案与解析
正确答案:C
这道题暂未补解析。
题目详情
9 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 5.1 哈希表概念

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

A

保留树的所有节点,并把树的每个节点指向其父节点,则可以将树转换为一个有向弱连通图。

B

保留树的所有节点,并把树的每个节点指向其子节点,则可以将树转换为一个有向无环图。

C

每个连通图都存在生成树。

D

每个存在生成树的有向图,都一定是强连通的。

答案与解析
正确答案:D
这道题暂未补解析。
题目详情
10 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 5.1 哈希表概念

对一个包含 个顶点、 条边的图,执行广度优先搜索,其最优时间复杂度是( )。

A

O(V+E)

B

O(V)

C

O(E)

D

O(V^2)

答案与解析
正确答案:A
这道题暂未补解析。
题目详情
11 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 5.1 哈希表概念

以下哪个方案不能合理解决或缓解哈希表冲突( )。

A

用新元素覆盖发生冲突的哈希表项。

B

在每个哈希表项处,使用单链表管理该表项的冲突元素。

C

建立额外的单链表,用来管理所有发生冲突的元素。

D

使用不同的哈希函数再建立一个哈希表,用来管理所有发生冲突的元素。

答案与解析
正确答案:A
这道题暂未补解析。
题目详情
12 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 5.1 哈希表概念

以下关于贪心法和动态规划的说法中,错误的是( )。

A

对特定的问题,贪心法不一定适用。

B

当特定的问题适用贪心法时,通常比动态规划的时间复杂度更低。

C

对很多问题,递推实现和递归实现动态规划方法的时间复杂度相当。

D

采用动态规划的算法一定具有多项式时间复杂度。

答案与解析
正确答案:D
这道题暂未补解析。
题目详情
13 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 5.1 哈希表概念

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

int rec_fib[MAX_N]; 
int fib(int n) { 
        if (n <= 1) 
                return n; 
        if (rec_fib[n] != 0) 
                return rec_fib[n]; 
        return fib(n - 1) + fib(n - 2); 
}


A

B

O(2^n)

C

o(n^2)

D

O(n)

答案与解析
正确答案:A
这道题暂未补解析。
题目详情
14 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 5.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(nloglogn)

C

O(nlogn)

D

O(n^2)

答案与解析
正确答案:C
这道题暂未补解析。
题目详情
15 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 5.1 哈希表概念

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

int gcd(int m, int n) { 
        if (m == 0) return n; 
        return gcd(n % m, m); 
} 
int count_triple(int n) {
  int cnt = 0; 
  for (int v = 1; v * v * 4 <= n; v++) 
        for (int u = v + 1; u * (u + v) * 2 <= n; u += 2) 
                if (gcd(u, v) == 1) { 
int a = u * u - v * v; 
int b = u * v * 2; 
int c = u * u + v * v; 
cnt += n / (a + b + c); 
} 
        return cnt; 
}


A

O(n^2)

B

O(n^2logn)

C

O(nlogn)

D

O(n)

答案与解析
正确答案:C
这道题暂未补解析。
题目详情
16 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 5.1 哈希表概念

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

A

2, 3, 5, 7, 8, 9, 6, 4, 1

B

5, 7, 8, 9, 1, 2, 4, 3, 6

C

6, 8, 9, 5, 7, 1, 2, 3, 4

D

8, 5, 7, 9, 1, 2, 3, 6, 4

答案与解析
正确答案:B
这道题暂未补解析。
题目详情
17 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 5.1 哈希表概念

以下哪个方案不能合理解决或缓解哈希表冲突?( )

A
在每个哈希表项处,使用不同的哈希函数再建立一个哈希表,管理该表项的冲突元素。
B
在每个哈希表项处,建立二叉排序树,管理该表项的冲突元素。
C
使用不同的哈希函数建立额外的哈希表,用来管理所有发生冲突的元素。
D
覆盖发生冲突的旧元素。
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
18 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 5.1 哈希表概念

2025 是个神奇的数字,因为它是由两个数 20 和 25 拼接而成,而且 2025 =(20+25)2 。

小杨决定写个程序找找小于 N 的正整数中共有多少这样神奇的数字。下面程序横线处应填入的是?( )

#include <string>
int count_miracle(int N) {
    int cnt = 0;
    for (int n = 1; n * n < N; n++) {
        int n2 = n * n;
        std::string s = std::to_string(n2);
        for (int i = 1; i < s.length(); i++)
            if (s[i] != '0') {
                std::string sl = s.substr(0, i);
                std::string sr = s.substr(i);
                int nl = std::stoi(sl);
                int nr = std::stoi(sr);
                if (_________) // 在此处填入选项
                    cnt++;
            }
    }
    return cnt;
}
A
nl + nr == n
B
nl + nr == n2
C
(nl + nr) * (nl + nr) == n
D
(nl + nr) ^ 2 == n2
答案与解析
正确答案:A

此时应该判断两半的和的平方是否等于原数,而原数是 n2 ,n 是其平方根,所以选择 A。(阅读模拟程序、 字符串函数)

题目详情
19 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 5.1 哈希表概念

在哈希表的实现中,冲突解决是一个重要的问题。以下哪种方法 不是 常见的哈希表冲突解决策略?( )

A
链地址法(Chaining)
B
开放地址法(Open Addressing)
C
二次哈希法(Double Hashing)
D
二分查找法(Binary Search)
答案与解析
正确答案:D

二分查找法用于有序数组中的查找,和哈希表冲突无关。(哈希表)

题目详情
20 单选题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 5.1 哈希表概念

一个哈希表,包括n个位置(分别编号0~(n-1)),每个位置最多仅能存储一个元素。该哈希表只有插入元素和查询两种操作,没有删除或修改元素的操作。以下说法错误的是( )。

A
如果哈希函数取值范围为0 ~ (n-1),且当发生哈希函数碰撞时循环向后寻找空位,则查询操作的最差时间复杂度为 O(n)。(“循环向后”指:0向后一位为1,1向后一位为2,……,(n-2)向后一位为(n-1),(n-1)向后一位为0)
B
如果哈希函数取值范围为0 ~ (n-1),且当发生哈希函数碰撞时仅循环向后一个位置寻找空位,则查询操作的最差时间复杂度为 O(1)。
C
如果哈希函数取值范围为0 ~ (m-1)(m < n),且当发生哈希函数碰撞时仅在m ~ (n-1)的范围内寻找空位,则查询操作的最差时间复杂度为 O(n−m)。
D
查询操作时,如果发现查询元素经哈希函数对应的位置为空位,该查询元素仍可能出现在哈希表内。
答案与解析
正确答案:D
这道题暂未补解析。
题目详情