第 3 次作业 · 线性表与复杂度

2 个，对应 B。

p->next == h，对应 A。

“线性表的有序性是数据元素按数值由小到大或由大到小排列”错误，对应 C。线性表的“有序”指元素具有前后次序，不等于按关键字排序。

$O(n\log n)$，对应 C。

源答案为 3, 4, 1, 2，对应 B。原 PDF 中四个公式字形没有被文本层保留下来，因此这里只保留可核验的编号顺序。

$(n+1)/2$，对应 C。

顺序、链式、索引和散列存储结构，对应 D。

$O(n)$，对应 C。

“顺序存储便于插入和删除”错误，对应 B。

仅设尾指针的单循环链表，对应 D；尾指针的后继就是首结点。

9 号。

$O(\log n)$。

$O(mn)$。

$n$ 次。

取 p 时依次执行 r->link=p; r=p; p=p->link;；取 q 时同理。循环结束后可写 r->link = (p != NULL) ? p : q;。

$n-i+1$ 个。

顺序存储平均移动近一半元素，为 $O(n)$；已知链表结点位置后，局部插入、删除为 $O(1)$。

$100+(10-1)\times4=136$。

q->link=p->link; p->link=q;。

$(n-1)/2$ 个。

提交代码遍历线段数据并维护连续关系。独立题面没有保留，无法确认“连续”的全部判定约束，故不从实现反推题意。

课程保存的讲解 PDF 明确采用链表法：两输入链表结点保存系数和指数，枚举两表项相乘，再把结果按指数递减插入第三条链；指数相同则合并系数。

源目录保存输入、加密结果和提交代码。实现以环式移动处理文件字符；由于教师题面和完整密钥约定未保存，这里只保留提交边界。

提交维护空闲分区，申请时选择能够容纳请求的最小分区，分配后更新剩余空间。这对应最佳适应策略；关键不变量是空闲表始终准确覆盖尚未分配的区间。

讲解 PDF 与代码均保留：提交把不同单词放入结构数组，已存在则增加计数，否则追加新项，最后用 qsort 按单词字典序输出。线性查找已有单词使最坏代价较高，后续作业会改用树结构。