1.1 综合题讲评：用同与不同解释结构、存储和效率

同学，选择题要求辨认概念，今天综合题的新困难是自己构造例子，说明逻辑结构、存储结构和运算效率之间究竟怎样关联。答案不能只有名称，必须指出“什么相同、什么不同、为什么影响结果”。

陪做第一问：举例说明逻辑结构相同、存储结构不同。顺序表和单链表都表达线性表，元素之间仍是一对一的前驱后继关系；顺序表用连续地址和下标体现关系，单链表用指针连接结点。这说明逻辑模型不因实现改变。

第二问：能否存储方式相似而逻辑结构不同？可以。数组中的顺序表和按层序存放的完全二叉树都使用连续存储单元，但前者的逻辑关系是一条线，后者由父子关系组成树。判断依据是元素间的抽象关系，不是内存外观。

第三问：同一线性表的插入效率为什么会因存储方式不同？必须先把题目条件说全。若已经给出插入位置的结点指针，单链表修改常数个指针，插入本身为 $O(1)$；顺序表平均要移动 $O(n)$ 个元素。若只给出一个待查值，两种结构都可能先花 $O(n)$ 查找，整项操作就不能只报链表 $O(1)$。效率结论取决于输入条件和被计入的步骤。

针对性错解：只写“数组和链表”却不说明它们表达同一线性关系，论证不完整；把“链表插入 $O(1)$”当无条件结论，会漏掉定位前驱的成本；认为逻辑与存储都相同就必然是同一种结构，也忽略了操作集合可能不同。

迁移题：同样表示集合，位图和散列表的逻辑结构是否相同？一次成员查询的成本有什么区别？参考答案：逻辑上都表达无序元素集合；位图适合值域有限的整数，查询按位访问近似 $O(1)$ 且空间依赖值域；散列表平均查询 $O(1)$，空间依赖元素数并受冲突影响。独立验收是能独自给出三组“同/不同”例子，每组明确逻辑、存储、操作条件与复杂度。下一课转入算法性质和复杂度题的限时判断。