时间空间复杂度分析+数据结构
- [CSP 2024 提高级第一轮 第 2 题] 假设一个长度为 n 的整数数组中每个元素值互不相同，且这个数组是无序的。要找到这个数组中最大元素的时间复杂度是多少？ （ {{ select(1) }} ）
- O(n)
- O(logn)
- O(nlogn)
- O(1)
- [CSP 2024 提高级第一轮 第 3 题] 在 C++ 中，以下哪个函数调用会造成栈溢出？ （ {{ select(2) }} ）
int foo() { return 0; }int bar() { int x = 1; return x; }void baz() { int a[1000]; baz(); }void qux() { return; }
- [CSP 2024 提高级第一轮 第 5 题] 下面哪个数据结构最适合实现先进先出（FIFO）的功能？ （ {{ select(3) }} ）
- 栈
- 队列
- 线性表
- 二叉搜索树
- [CSP 2024 提高级第一轮 第 7 题] 假设有一个包含 n 个顶点的无向图，且该图是欧拉图。以下关于该图的描述中哪一项不一定正确？（注：欧拉图是指通过图（无向图或有向图）中所有边且每边仅通过一次通路，相应的回路称为欧拉回路。具有欧拉回路的图称为欧拉图，具有欧拉通路而无欧拉回路的图称为半欧拉图） （ {{ select(4) }} ）
- 所有顶点的度数均为偶数
- 该图连通
- 该图存在一个欧拉回路
- 该图的边数是奇数
- [CSP 2024 提高级第一轮 第 8 题] 对数组进行二分查找的过程中，以下哪个条件必须满足？ （ {{ select(5) }} ）
- 数组必须是有序的
- 数组必须是无序的
- 数组长度必须是 2 的幂
- 数组中的元素必须是整数
- [CSP 2024 提高级第一轮 第 9 题] 考虑一个自然数 n 以及一个模数 m，你需要计算 n 的逆元（即 n 在模 m 意义下的乘法逆元）。下列哪种算法最为适合？ （ {{ select(6) }} ）
- 使用暴力法依次尝试
- 使用扩展欧几里得算法
- 使用快速幂法
- 使用线性筛法
- [CSP 2024 提高级第一轮 第 10 题] 在设计一个哈希表时，为了减少冲突，需要使用适当的哈希函数和冲突解决策略。已知某哈希表中有 n 个键值对，表的装载因子为 α (0 < α ≤ 1)。在使用开放地址法解决冲突的过程中，最坏情况下查找一个元素的时间复杂度为？ （ {{ select(7) }} ）
- O(1)
- O(log n)
- O(1/(1−α))
- O(n)
- [CSP 2024 入门级第一轮 第 4 题] 以下哪个序列对应数组 0 至 8 的 4 位二进制格雷码（Gray code）？ （ {{ select(8) }} ）
- 0000，0001，0011，0010，0110，0111，0101，1000
- 0000，0001，0011，0010，0110，0111，0100，0101
- 0000，0001，0011，0010，0100，0101，0111，0110
- 0000，0001，0011，0010，0110，0111，0101，0100
- [CSP 2024 入门级第一轮 第 9 题] 假设有序表中有 1000 个元素，则用二分法查找元素 X 最多需要比较多少次？ （ {{ select(9) }} ）
- 25
- 10
- 7
- 1