算法与线性结构：让步骤可执行

找出一摞书中编号最大的书，为什么“多试几次”不算完整算法？

算法是解决一类问题的有限、明确、可执行步骤，须说明输入、输出和适用条件。伪代码表达逻辑，不依赖具体编译器。本课程过程示例除明确列出的C文件外均为伪代码。O(n)描述规模增长时工作量的上界阶，不是精确秒数。常见阶为常数、对数、线性、n log n、平方。额外空间只计辅助存储还是含输入，应先说明。

递归是函数调用自身，必须有基本情形和趋近它的度量。每层调用保留局部状态，深度会占栈空间，递归不会天然更快。

求最大值：若数组空则返回“无最大值”；否则max←a[0]，从i=1到n−1比较并更新。循环不变式：处理完下标i后，max是前i+1项最大值。递归阶乘：fact(0)=1；n>0时fact(n)=n×fact(n−1)，n必须非负且结果未溢出。

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

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

max(a,n):
  若 n=0：返回“无最大值”
  best ← a[0]
  对 i=1 到 n−1：
    若 a[i]>best：best ← a[i]
  返回 best

队伍中间插一个人，数组和链表为什么付出的工作不同？

线性表是有序元素序列的逻辑结构；顺序表连续存储，按下标O(1)访问，中间插删需移动；链表通过指针连接，查第i个一般O(n)。已知前驱节点时，单链表插删可O(1)，但寻找位置的时间不能漏算。链表额外保存指针，缓存局部性通常不如数组。带头节点可统一首元素操作，头节点不必存业务数据。

数组位置i插入v：检查容量→从尾向右搬移→a[i]←v→长度加1。链表在p后插入s：先s.next←p.next，再p.next←s，顺序反了会丢原后继。删除p后q：保存q←p.next→p.next←q.next→释放q。需检查q存在。

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

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

insert_after(p,s):
  要求 p,s 有效且 s 不在链中
  s.next ← p.next
  p.next ← s
remove_after(p):
  q ← p.next
  若 q 为空：返回失败
  p.next ← q.next
  保存结果，再释放由本表拥有的 q

撤销最后一次操作与按到达顺序叫号，能用同一种出队规则吗？

栈后进先出LIFO，常用于递归、括号匹配、撤销；队列先进先出FIFO，用于排队和广度优先。栈只有栈顶可直接进出。循环队列用取模让下标绕回：next=(index+1)%capacity。若预留一格区分空满，空条件front=rear，满条件(rear+1)%capacity=front，实际容量比数组长度少1；也可另设计数，但条件应随实现改变。

括号匹配：遇左括号压栈；遇右括号先检查栈非空且顶类型匹配，再弹出；结束时栈必须空。队列入队写rear后前移，出队读front后前移。每步先判断满/空。

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

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

match(text):
  栈 S ← 空
  逐字符 c：
    若 c 为左括号：push(S,c)
    若 c 为右括号：
      若 S 为空或栈顶类型不匹配：返回假
      pop(S)
  返回 S 为空

一个百万行矩阵只有千个非零数，仍要把所有零存下来吗？

串是字符序列，子串连续，子序列可跳过。朴素模式匹配在每个起点逐字符比较，最坏O(nm)。KMP利用模式自身前后缀信息，失配时保留已知匹配关系，时间O(n+m)，不必把主串指针退回。不同next或前缀函数定义有不同下标约定，必须先写定义。

二维数组按行优先时，a[i][j]偏移为(i×列数+j)×元素大小。稀疏矩阵可按(行,列,值)三元组存非零项，另存尺寸与数量；适合零很多但索引元数据也有成本。

定义前缀函数π[i]为模式0…i的最长相等真前缀/后缀长度，“真”表示不能用整个串。模式ABAB的π=[0,0,1,2]。若已匹配ABAB后失配，可保留长度2的AB，从较短候选继续，不重查主串前两位。

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

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

prefix(pattern):
  若模式空：返回空表
  pi[0] ← 0
  对 i=1 到 m−1：
    j ← pi[i−1]
    当 j>0 且 pattern[i]≠pattern[j]：j ← pi[j−1]
    若 pattern[i]=pattern[j]：j ← j+1
    pi[i] ← j
  返回 pi
空模式在查找中的结果须另定，本课约定匹配位置0。