非线性结构、查找与排序

文件夹有层级，为什么用一条链描述不自然？

树连接父子关系，无环；根没有父节点，叶子无子节点。二叉树每节点最多两个有区别的孩子，左和右不能随便交换。完全二叉树除最后层外满，最后层向左连续；不是所有二叉树都适合紧凑数组存储。遍历：先序根左右，中序左根右，后序左右根；层序使用队列。二叉搜索树BST要求每个节点左子树键较小、右子树较大，重复键策略须约定；中序结果有序。

递归遍历先处理空树：直接返回；其余按所选顺序访问根和两个子树。搜索按比较选择一个分支，复杂度O(h)，h是树高；平衡时O(log n)，退化成链时O(n)。不是出现“树”就自动对数复杂度。

先独立作答；卡住时看提示，完成后再对照解析。

先按图示和正文用纸笔追踪，再阅读以下伪代码。箭头←为赋值，“若”为条件，“当”为循环；不是可直接编译的C。

preorder(node):
  若 node 为空：返回
  访问 node
  preorder(node.left)
  preorder(node.right)
将访问根移到两次递归之间是中序；移到之后是后序。

四个字母频率不同，用一样长的编码会浪费什么？

叶子权重代表频率，路径长度是根到叶的边数。带权路径长度WPL=Σ权重×长度。哈夫曼算法反复选择当前最小的两棵树合并，新根权重为两者之和，直到只剩一棵。左边0右边1可得前缀码：没有一个符号编码是另一个的前缀，因此可即时逐段解码。同权时合并次序可能不唯一，但最优WPL相同。

频率越高，短路径节省越多；贪心选择把最低频符号放到最深相邻叶，再将其视为一个合并符号递归处理。WPL也等于每次合并产生的新权重之和，可用于独立核算。

先独立作答；卡住时看提示，完成后再对照解析。

先按图示和正文用纸笔追踪，再阅读以下伪代码。箭头←为赋值，“若”为条件，“当”为循环；不是可直接编译的C。

把所有正频率叶放入最小优先队列Q
当 Q 至少有2项：
  a ← 取最小项；b ← 再取最小项
  新根权重 ← a.weight+b.weight
  新根左右孩子 ← a,b
  新根放回Q
仅一个符号时，实际码流需约定长度/码字以支持解码。

校园道路与课程先修关系都能画成点和线，但方向意味着什么？

图G=(V,E)，V是顶点，E是边。有向边有起止，无向边表示双向关系；权重表示长度或成本。邻接矩阵用V×V空间，查边快；邻接表只记录实际邻居，适合稀疏图。DFS深度优先沿一条路深入，使用递归或栈；BFS广度优先逐层扩张，使用队列，能求无权图最少边数路径。

遍历必须记visited防止环导致重复；非连通图要从每个尚未访问的点再开始。拓扑序只适用于有向无环图DAG，将入度0节点反复输出并删其出边；存在多个可选点时次序不唯一。

先声明邻居访问顺序（本课按字母）。BFS节点入队时即标记可避免重复入队。DFS递归进入时标记。拓扑排序若输出数少于顶点数，则剩余部分有环，不能强行补成一个合法顺序。

先独立作答；卡住时看提示，完成后再对照解析。

先按图示和正文用纸笔追踪，再阅读以下伪代码。箭头←为赋值，“若”为条件，“当”为循环；不是可直接编译的C。

BFS(start):
  start 标为已发现并入队
  当队列非空：
    u ← 出队；访问u
    对u的邻居v（按题目约定次序）：
      若v未发现：标记v并入队
非连通图外层还须遍历所有未发现顶点。

导航找A到D最短路，与铺网线连接全部楼，为什么不是同一题？

单源最短路最小化起点到各点的路径总权；Dijkstra每次确定未确定点中暂定距离最小者，再松弛其出边，要求边权非负。松弛是检查d[v]>d[u]+w(u,v)并更新。Floyd依次允许每个点作中转，更新d[i][j]=min(d[i][j],d[i][k]+d[k][j])；可处理负边但不能存在相关负环，时间O(V³)。

无向连通图的最小生成树MST连通全部点、无环、边数V−1，总权最小。Prim从已有点集选最小跨界边，Kruskal按边权递增选不成环的边。非连通图只能得到生成森林。

最短路径保持的是“到固定起点的距离”；MST选择的是连接割两侧的边。前者得到的树未必总边权最小。Dijkstra若存在负边，已确定距离可能被后来路径改小，贪心证明失效。

先独立作答；卡住时看提示，完成后再对照解析。

先按图示和正文用纸笔追踪，再阅读以下伪代码。箭头←为赋值，“若”为条件，“当”为循环；不是可直接编译的C。

Dijkstra(start):
  d[start] ← 0；其他d ← ∞；已确定集合S ← 空
  重复：
    选S外有限d最小的u；若不存在则停止
    u加入S
    对u的出边(u,v,w)：
      若d[u]+w<d[v]：更新d[v]与前驱
前提：所有边权非负；未可达点保持∞。

有序书架可不断对半，杂乱书堆为什么不行？

顺序查找逐项比，最坏O(n)。二分需按同一键有序且支持高效随机访问，维护闭区间[l,r]，mid=l+floor((r−l)/2)；相等返回，否则排除至少一半，最坏O(log n)。空区间l>r即失败。重复值若要求最左位置，需要相等时继续向左缩，不可直接任意返回。

散列函数将键映到槽。冲突是不同键映到同槽，不能完全避免。链地址把冲突放链中；开放定址按探测序列找空槽，删除需墓碑等处理，不能随便清空破坏查找链。装填因子α=元素数/槽数，越满通常冲突越多，平均O(1)有散列质量与负载假设。

二分每次保持：若目标存在，则仍在候选区间内。散列先算槽，再按同样探测规则查找，直至找到或遇真正未使用位置；满表必须有探测次数上限，避免无限循环。

先独立作答；卡住时看提示，完成后再对照解析。

先按图示和正文用纸笔追踪，再阅读以下伪代码。箭头←为赋值，“若”为条件，“当”为循环；不是可直接编译的C。

binary(a,n,key):
  l ← 0；r ← n−1
  当 l≤r：
    mid ← l+floor((r−l)/2)
    若a[mid]=key：返回mid
    若a[mid]<key：l ← mid+1
    否则：r ← mid−1
  返回未找到
前提：a非降序且可随机访问；返回任一匹配位置。

成绩相同的人要保留报名先后，选排序方法时要多看哪个指标？

稳定排序保持相同键元素原先的相对顺序。直接插入把当前元素插到已排好前缀；冒泡比较邻项并交换；简单选择每轮找最小换到前面。三者通常O(n²)，插入在近乎有序时可高效。快速排序按枢轴分区再递归，平均O(n log n)、最坏O(n²)；归并把有序段合并，O(n log n)、数组实现常用O(n)额外空间；堆排维护大根堆，每轮根换到末端再调整，O(n log n)。

希尔排序以递减间隔作插入，复杂度依间隔序列，通常不稳定。基数排序按位或字符分配，要求每趟稳定，适合可分解的键，时间常写O(d(n+r))，d为位数、r为基数。常见稳定实现：插入、冒泡、归并、基数；选择、快排、堆排、希尔一般不稳定。

先写算法版本再追踪。插入若只移动严格大于当前键的项，可保留同键顺序；归并相等时先取左侧才稳定。快排最坏常来自极端不平衡分区，随机化降低遇到这种输入的风险，但不是取消最坏界。

先独立作答；卡住时看提示，完成后再对照解析。

先按图示和正文用纸笔追踪，再阅读以下伪代码。箭头←为赋值，“若”为条件，“当”为循环；不是可直接编译的C。

insertion(a,n):
  对i=1到n−1：
    value ← a[i]；j ← i
    当j>0且a[j−1]>value：
      a[j] ← a[j−1]；j ← j−1
    a[j] ← value
严格大于才右移，可保持同键顺序。

两种算法都分而治之，为什么一个主要忙于分区，一个主要忙于合并？

快速排序选枢轴，把较小值放一侧、较大值放另一侧，再递归两段。不同分区法中枢轴位置与递归边界不同，题目必须声明版本。本节用末元素为枢轴的Lomuto分区，扫描时把≤枢轴的元素交换到前段，最后放置枢轴；长度0或1不再分。

归并排序先按位置分两半，分别有序后用双指针合并。比较两边首个尚未输出项，相等先左保证稳定；一边耗尽就复制另一边剩余。它与“只把两个数组拼接”不同。典型数组归并O(n log n)时间、O(n)辅助空间；快排递归空间依分区平衡，最坏可O(n)。

伪代码（闭区间）：partition(a,l,r)：p←a[r]；i←l；对j=l到r−1，若a[j]≤p则交换a[i],a[j]并i加1；交换a[i],a[r]；返回i。quick先判断l<r，再递归[l,i−1]与[i+1,r]。合并时每输出一项，仅移动它来源侧指针。

先独立作答；卡住时看提示，完成后再对照解析。

每轮找最大值都重扫全部元素，有没有结构帮忙？

大根堆是满足父键不小于孩子的完全二叉树；0起始数组中i的孩子为2i+1与2i+2（若下标<n）。堆序只约束父子，不保证数组整体有序。自底向上对最后一个非叶节点到根下沉，可O(n)建堆；排序每次根换到有效区末尾，缩小有效区，再向下调整，整体O(n log n)。

希尔先以大间隔把跨距元素做插入，逐步缩小间隔，最后gap=1，表现依间隔序列。LSD基数排序从最低位向高位稳定分桶，各趟必须保持同桶原顺序，最后才整体有序；适合这里示范的非负整数，负数处理需另定规则。

下沉时选择更大孩子与父比较，若孩子更大则交换并继续，否则停止。LSD每趟按0—9桶顺序收集。不能将“桶内随便排”与稳定分配混用；高位相同时，低位已得到的次序必须保存。

先独立作答；卡住时看提示，完成后再对照解析。

最短路为什么可能被一个新允许的中转点缩短？

Floyd以k为外层，把允许的中转点从空集逐步扩成{0,…,k}。每对i,j比较原距离与i→k→j，更新较小者。无边记∞，自身距离0；∞加数仍视作∞。如果计算后d[i][i]<0，说明存在负环的迹象，相关路径不能当作有限最短路。

Prim维护已连入树的顶点集S，从一端在S、另一端不在S的边中选最小者，加入新顶点。它选的是跨界边权，不是起点到新点的累计路径长。连通性不足时会无法继续，应报告森林/非连通，不凭空加边。

Floyd伪代码：对k，再对i，再对j：若两段可达且d[i][k]+d[k][j]<d[i][j]则更新，并同步记录路径信息。Prim伪代码：从起点S开始；重复选最小跨界边，记录边并扩S；找不到而仍有外点则停止报告不连通。

先独立作答；卡住时看提示，完成后再对照解析。