![]()
嵌套循环的时间复 杂度计算（外层循 环为√n，内层循环 累加次数）
1.外层循环：i从1到√n，共√n次；
2.内层循环：对每个i执行i次，总次数= 0+1+2+…+(√n-1)=√n (√n-1)/2≈n/2；
3.忽略常数因子，时间复杂度为O (n)，选B
外层循环执行√n次，内层循环累计执行次数约为𝑛 2次，因此总体复杂度为线性O(n)
![]()
栈在括号匹配中的应用（嵌套深度限制）
1.栈容量3，需判断各选项括号嵌套最大深度；
2. D选项括号序列为[ ( [ ( ) ] )，遍历到[a- (b+[c*(d+e)时，栈内有[ ( [ (，深度4，超出容量；
3.其他选项最大深度均为3，选D。
![]()
二叉树顺序存储的节点存在规则（不存在节点的子节点必为 - 1）
1.顺序存储规则：若节点为- 1（不存在），其左 （2i）、右（2i+1）子节点必为- 1；
2. D选项中，索引4为- 1，但索引9（4的右子节点）为 19，违反规则；
3.其他选项符合规则，选D
![]()
二叉树与森林的性质（森林转二叉树、完全二叉树、表达式树
1.选项分析：
- A错（完全二叉树可能有度1节点，如倒数第二层仅左孩子的节点）；
- B对（任意森林可通过“左孩子-右兄弟”表示法转为二叉树）；
- C错（单链二叉树分支节点数＞叶节点数）；
- D错（表达式树根节点保存最后计算的运算符）；
2.选B。
![]()
哈夫曼树构造与编码长度计算
1. 7个字符频次：2,3,4,6,8,10,11，构造哈夫曼树 （每次合并最小两节点）；
2.编码长度：10、11（2位），4、6、8（3位）， 2、3（4位）；
3.编码长度≥3的字符共5个，选D。
![]()
图的性质（回路判定、拓扑排序、最短路径算法适用场景）
1.选项分析：
- A错（有向环中所有节点入度≥1，无入度0节点）；
- B错（DAG拓扑序列存在但不唯一，如并列节点可换序）；
- C对（反证：无回路则为森林，必有叶节点（度1），与“度≥2”矛盾）；
- D错（BFS仅适用于无权/等权图，带权图需Dijkstra 等算法）；
2.选C。
![]()
分块查找的平均查 找长度最优化（最优块大小计算）
1.分块查找平均查找长度ASL=(m+1)/2+(k+1)/2，其中 m =块数，k =每块元素数，n=mk；
2.最优化条件：m=k=√n，n=400→√400=20；
3.每块最优元素数为20，选C。
![]()
4阶B树的结构约束与不同高度的数量计算（关键字数 1~3，叶节点同层）
1. 4阶B树规则：每个节点关键字1~3个，叶节点同层；
2. 7个关键字：
-高度2：8种（根1个关键字+叶2块6 个 /根2个+叶3块5个/根3个+叶4 块 4个）；
-高度3：1种（根1 +中层2个+叶4个， 共 1+2+4=7）；
3.总计9种，选C。
![]()
散列冲突处理（线 性探查与二次探查 的特性对比）
1.选项分析：
- A对（线性探查步长1，可遍历全表，表不满必找空位）；
- B错（二次探查步长为平方数，无法遍历全表，表不满也可能找不到空位）；
- C错（线性探查会处理非同义词冲突，如探查时碰撞已占用非同义词位置）；
- D错（二次探查也会处理同义词冲突，如两关键字散列地址相同）；
2.选A。
![]()
各排序算法最坏情况下的元素移动次数对比
1.移动次数分析：
-冒泡排序：3n (n-1)/2（O (n²)）；
-直接插入排序：n (n-1)/2（O (n²)）；
-快速排序：O (n²)；
-简单选择排序：3 (n-1)（O (n)，仅交换n-1 次，每次 3次移动）；
2.最坏移动最少的是简单选择排序，选D。
![]()
排序算法识别（希尔排序的分组插入特征）
1.希尔排序按增量分组插入，第1趟增量gap=3，分组为(0,3,6)、(1,4,7)、(2,5,8)，排序后
重组为第1趟序列；第2趟增量gap=2，分组后排序得第 2趟序列，与题目一致；
2.基数排序（按数位）、归并排序（分段有序）、折半插入排序（前缀有序）均不匹配，选 A。
