GESP2026年3月认证C++七级( 第一部分选择题（8-15））精讲

第8题 时间复杂度分析答案A数组 a 的值域范围是 D求程序时间复杂度。本题考什么这一题实际上考的是不要只看 n还要看值域 D。很多同学分析复杂度时只知道for循环就写O(n)这是错误的。因为有很多算法例如桶排序 计数排序 频率统计 前缀和桶真正复杂度都是O(nD)其中n 元素数量D 值域大小例如100000个数字 但是数字只在0~100之间那么D101复杂度就是O(n101) ≈O(n)如果数字范围 0~10^9那么D 巨大桶排序根本不能用了。一张图记住这道题solve() │ ├── sort(a) │ │ │ └── O(nlogn) │ └── while(二分) │ ├── 共 logD 次 │ └── 每次调用 check() │ └── O(n) ↓ 总复杂度 O(nlognnlogD)第9题 二叉树遍历答案A已知先序A B D H I E C F J G中序H D I B E A F J C G要求后序。第一步 找根先序第一个A一定是根。第二步 分左右子树中序H D I B E A F J C G左边H D I B E右边F J C G第三步 继续递归左子树先序B D H I E根B......一直递归下去。最终得到后序 H I D E B J F G C A就是A如何快速做七级考试推荐口诀先序找根中序切树递归恢复。以后所有重建二叉树都一样。第10题 DFS遍历答案B这一题很多同学不会。其实考的是DFS有什么特点DFS特点一路走到底 不能走 回溯 继续例如1 ↓ 5 ↓ 8 ↓ ……因此DFS序列一定具有连续深入 再回退特点。为什么A错因为1 ↓ 5 ↓ 4 ↓ 8如果4还能继续访问就不会立刻跳8。违反DFS。B为什么可以它符合一直深入 直到不能走 再回来所以可能。考试技巧看到DFS BFS 先序 中序 后序最好画图。来逐一排除。第11题 强连通分量答案B4个什么叫强连通有向图里A能够到BB也能够到A就是强连通例如1→2 ↑ ←互相能到。就是一个强连通分量。例如1→2→3→1三个点互相可达。就是一个SCC本题需要把图拆成若干块每块内部互相可达。最后得到4块所以答案B。第12题 Flood Fill答案C很多同学只知道染色其实Flood Fill本质就是图搜索例如迷宫#### #...# ##..#从一个点开始DFS或者BFS不断扩展。就是Flood Fill。为什么C正确因为Flood Fill就是DFS 或者 BFS从起点开始。本质就是图搜索。为什么A错Flood Fill不仅可以二维。还可以三维 图 状态空间都可以。为什么B错既可以DFS递归也可以DFS栈 BFS队列为什么D错Flood Fill还能求面积 周长 岛屿数量 最短距离 颜色扩散用途非常多。第13题 Huffman编码答案D64给出频率2 3 3 4 6 8Huffman口诀每次取最小两个。第一步235总代价5剩余3 4 5 6 8第二步347总代价5712第三步5611总代价23第四步7815总代价38第五步111526总代价64因此答案64为什么总代价就是WPL这是哈夫曼树的重要性质所有合并过程中的权值之和 最终WPL。因此不用真的画树。第14题 链表答案D逐个分析。A错单链表如果只有当前节点不知道前驱。删不了。必须知道前驱才能修改nextB错循环链表可以有NULL例如空链表或者某些实现。不是一定没有。C错循环双链表尾节点next应该指向头节点不是NULL。D正确带头节点空链表就是head-next head这是竞赛最常见写法。因此判断head-nexthead即可。第15题 树遍历答案C逐项分析。A错普通树DFS如果孩子访问顺序不同结果不同。例如1 2 3可以1 2 3也可以1 3 2B错先序后序不能唯一恢复。例如1 / 2和1 \ 2先序后序都一样。C正确重点这是二叉树最重要性质。先序中序 唯一恢复或者后序中序 唯一恢复一定要记住。D错中序递增说明BST二叉搜索树不是AVL平衡树可能退化成链表例如1 \ 2 \ 3 \ 4中序1 2 3 4递增。但是完全不平衡。第一部分8~15题知识总结题号知识点竞赛重要程度8时间复杂度分析、值域复杂度★★★★★9先序中序恢复二叉树、后序遍历★★★★★10DFS遍历特点与回溯★★★★★11强连通分量Tarjan思想★★★★★12Flood Fill 本质是 DFS/BFS 图搜索★★★★★13哈夫曼树、优先队列贪心、WPL计算★★★★★14单链表、双链表、循环链表性质★★★★☆15树遍历唯一性、BST与AVL区别★★★★★整套选择题115题的命题特点这套七级选择题几乎覆盖了七级最重要的知识体系算法分析时间复杂度、递推式、值域复杂度。数据结构哈希表、链表、二叉树、树的性质。图论DFS、Flood Fill、最小生成树、强连通分量。字符串最长公共子序列LCS。经典算法二分答案、哈夫曼树、贪心思想。