普及组和提高组难度之间

1. 在有向无环图（DAG）中，求解顶点的一种线性序列，使得所有边均从序列中较前的顶点指向较后的顶点，这个过程称为？ {{ select(1) }}

• 最小生成树
• 拓扑排序
• 强连通分量
• 欧拉路径

2. 一个包含n个顶点和n-1条边的连通图是？ {{ select(2) }}

• 完全图
• 树
• 稀疏图
• 平面图

3. 以下哪种算法利用了"贪心选择性质"和"最优子结构"？ {{ select(3) }}

• Floyd-Warshall算法
• Bellman-Ford算法
• Prim算法
• 深度优先搜索

4. 在C++中，std::vector的capacity()和size()的关系是？ {{ select(4) }}

• capacity()恒等于size()
• capacity()恒小于size()
• capacity()总是size()的两倍
• capacity()大于或等于size()

5. 一个采用邻接矩阵存储的无向图，该矩阵必然是？ {{ select(5) }}

• 单位矩阵
• 对称矩阵
• 对角矩阵
• 稀疏矩阵

6. 求解最长不下降子序列（LIS）问题，通常使用哪种算法思想？ {{ select(6) }}

• 贪心算法
• 分治算法
• 动态规划
• 回溯搜索

7. 在8位二进制补码表示中，整数-1的值是？ {{ select(7) }}

• 10000001
• 11111111
• 10000000
• 01111111

8. 欧拉函数的定义φ(n)是？ {{ select(8) }}

• 小于n的质数个数
• n的约数之和
• 小于等于n且与n互质的正整数个数
• n的质因数分解中所有质数的和

9. 在C++的STL中，哪种容器的内部元素默认是有序的？ {{ select(9) }}

• std::vector
• std::list
• std::set
• std::unordered_map

10. 卡特兰数（Catalan number）不适用于下列哪个问题的计数？ {{ select(10) }}

• n对括号的合法匹配方案数
• n个节点的二叉搜索树种类数
• n个元素的入栈、出栈序列总数
• n个不同元素的全排列数

11. 在C++中，static关键字用于函数内部的局部变量时，会使该变量？ {{ select(11) }}

• 只能被函数内部访问，且函数调用结束后销毁
• 只能被函数内部访问，但其生命周期为整个程序运行期
• 可以被文件内其他函数访问
• 变为只读的常量

12. 一个函数的定义域是实数，且该函数图像是一个单峰（或单谷）曲线，求其极值点最高效的算法是？ {{ select(12) }}

• 二分查找
• 广度优先搜索
• 爬山算法
• 三分查找

13. 关于P类问题和NP类问题的描述，正确的是？ {{ select(13) }}

• P类问题是NP类问题的子集
• NP类问题是指非多项式时间复杂度的难题
• P=NP问题已经被证明是正确的
• 任何P类问题都比NP类问题更难

14. Prim算法和Kruskal算法都是用来解决什么问题的？ {{ select(14) }}

• 单源最短路径
• 字符串匹配
• 网络最大流
• 最小生成树

15. 在计算机中，浮点数的表示通常遵循哪种标准？ {{ select(15) }}

• ASCII
• Unicode
• IEEE 754
• EBCDIC

16. 逻辑运算A XOR B(异或)等价于？ {{ select(16) }}

• (A AND B) OR (NOT A)
• (A AND NOT B) OR (NOT A AND B)
• NOT (A OR B)
• A AND B

17. 在解决动态区间和查询、单点修改的问题时，哪种数据结构的综合效率通常最高？ {{ select(17) }}

• 前缀和数组
• 树状数组（Fenwick Tree）
• 链表
• 哈希表

18. 从n个不同元素中取出m个元素组成一个排列，其排列数为？ {{ select(18) }}

• n!
• C(n, m)
• n! / (n-m)!
• n^m

19. 在平衡二叉搜索树（如AVL树）中，插入或删除一个节点后，维持其平衡性的操作主要是？ {{ select(19) }}

• 节点染色
• 旋转操作
• 堆调整
• 路径压缩

20. Tarjan算法主要用于高效求解图的哪种问题？ {{ select(20) }}

• 寻找哈密顿回路
• 强连通分量
• 二分图匹配
• 拓扑排序

21. 在C++中，虚函数（virtual function）主要用于实现？ {{ select(21) }}

• 模板元编程
• 编译时多态
• 运行时多态
• 运算符重载

22. 下列哪个排序算法是基于"分配"和"收集"的思想，而不是比较？ {{ select(22) }}

• 希尔排序
• 堆排序
• 基数排序
• 快速排序

23. Sieve of Eratosthenes（埃拉托斯特尼筛法）是一种高效的算法，用于？ {{ select(23) }}

• 求解最大公约数
• 查找某一范围内的所有质数
• 计算大数的阶乘
• 排序整数数组

24. 在程序内存管理中，由程序员手动申请和释放的内存区域是？ {{ select(24) }}

• 栈（Stack）
• 堆（Heap）
• 静态存储区
• 代码段

25. "鸽巢原理"（Pigeonhole Principle）最基本的描述是？ {{ select(25) }}

• 任务可以分解为独立的子任务
• 如果n个物品放入m个容器，且n > m，则至少有一个容器包含多于一个物品
• 局部最优解能导出全局最优解
• 两个随机事件同时发生的概率是它们各自概率的乘积

26. KMP算法中的next数组（或称fail数组）存储的信息是？ {{ select(26) }}

• 模式串中每个前缀的最长公共前后缀长度
• 模式串中每个字符在主串中出现的位置
• 模式串的反转形式
• 模式串中每个字符的出现频率

27. 一个无向图存在欧拉路径的充要条件是？ {{ select(27) }}

• 图是连通的，且所有顶点的度数均为偶数
• 图是连通的，且度数为奇数的顶点数量为0或2
• 图是一个完全二分图
• 图中没有环

28. 在C++中，std::priority_queue默认实现的数据结构是？ {{ select(28) }}

• 红黑树
• 排序数组
• 最大堆
• B+树

29. 求解斐波那契数列第n项，若使用矩阵快速幂，时间复杂度可以优化到？ {{ select(29) }}

• O(n)
• O(n²)
• O(log n)
• O(1)

30. 在C++中，const关键字修饰成员函数时，其作用是？ {{ select(30) }}

• 该函数不能被重载
• 该函数不能修改类的任何成员变量
• 该函数只能返回const类型的值
• 该函数不能修改类的非静态数据成员（this指针变为const）

31. 下列哪个问题是经典的NP完全问题？ {{ select(31) }}

• 在排序数组中查找一个元素
• 计算两个n位整数的乘积
• 旅行商问题（TSP）
• 求解图的最小生成树

32. 求解点集凸包的经典算法是？ {{ select(32) }}

• Dijkstra算法
• Graham扫描法
• A*搜索算法
• Edmonds-Karp算法

33. 在计算机网络的分层模型中，TCP协议工作在哪一层？ {{ select(33) }}

• 物理层
• 数据链路层
• 网络层
• 传输层

34. 若一个递归的深度为d，每个节点的分支数量为b，则该递归算法的时间复杂度大致为？ {{ select(34) }}

• O(d * b)
• O(d + b)
• O(b^d)
• O(d^b)

35. 在C++中，#define和const都可以用来定义常量，它们的主要区别是？ {{ select(35) }}

• const定义的常量有类型检查，#define没有
• const只能定义整数，#define可以定义任何类型
• #define效率更高
• 没有区别，可以互换使用

36. 霍夫曼编码（Huffman Coding）是一种用于无损数据压缩的算法，其基本原理是？ {{ select(36) }}

• 对出现频率高的字符使用较短的编码
• 将重复的数据序列用指针代替
• 使用定长编码表示所有字符
• 对数据进行加密

37. 一个程序从高级语言代码到可执行文件的过程，通常不包括下列哪个阶段？ {{ select(37) }}

• 预处理
• 编译
• 链接
• 解释

38. 若离散随机变量X的取值为1, 2, 3，对应的概率分别为0.5, 0.3, 0.2，则X的期望值是？ {{ select(38) }}

• 1.5
• 1.7
• 2.0
• 2.2

39. 在操作系统中，负责管理和分配CPU资源的模块是？ {{ select(39) }}

• 内存管理器
• 文件系统
• 进程调度程序
• I/O控制系统

40. 解决汉诺塔（Tower of Hanoi）问题，将n个盘子从A移动到C，最少需要多少步？ {{ select(40) }}

• n - 1
• n² - 1
• 2^n - 1
• n