数据结构笔试

按知识点

1、算法的五个特性

一个算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。一个标准的算法必须具备以下五个基本特性：

  1. 有穷性 (Finiteness)：一个算法必须总是在执行有穷步之后结束，且每一步都可在有穷时间内完成。算法不能陷入死循环。
  2. 确定性 (Definiteness)：算法中每一条指令必须有确切的含义。对于相同的输入只能得出相同的输出，执行时不能产生二义性（歧义）。
  3. 可行性 (Feasibility / Effectiveness)：算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。（即理论上可以在纸笔上通过有限步骤推导出来）。
  4. 输入 (Input)：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。
  5. 输出 (Output)：一个算法有一个或多个输出，这些输出是同输入有着某种特定关系的量。没有输出的算法是毫无意义的。

【例题 1】 算法的五个特性中，不包括（ ）

A. 有穷性 B. 确定性 C. 可行性 D. 随机性

【正确答案】 D. 随机性

【详细解析】 根据算法的经典定义，算法的五个基本特性分别是：有穷性、确定性、可行性、输入和输出。

  • 选项 A（有穷性）、选项 B（确定性）、选项 C（可行性）均属于这五个必备特性。
  • 选项 D（随机性）不是算法的必备特性。虽然在算法设计中确实存在“随机化算法”（如随机化快速排序），但它不属于普遍意义上衡量一个过程是否为“算法”的标准特性。

2、算法分析

设计出一个满足“五个基本特性”的算法只是第一步，现实中解决同一个问题往往有多种不同的算法。为了评判算法的优劣，我们需要进行算法分析。

算法分析的核心目的在于评估算法消耗的资源，主要围绕两个维度展开：

  1. 时间复杂度 (Time Complexity)：评估执行算法所需要的计算工作量（运行时间）。我们希望算法跑得越快越好。
  2. 空间复杂度 (Space Complexity)：评估执行算法所需要的内存空间。我们希望算法占用的内存越少越好。

核心目标： 通过分析时间复杂度和空间复杂度，我们可以发现算法的性能瓶颈，从而优化算法的时间和空间效率，选出或者设计出最高效的解决方案。

【例题 2】 算法分析的核心目标是（ ）

A. 验证算法的正确性 B. 优化算法的时间和空间效率 C. 提高算法的可读性 D. 减少算法的输入规模

【正确答案】 B. 优化算法的时间和空间效率

【详细解析】

  • 选项 B 正确：算法分析的主要任务是分析算法的时间复杂度和空间复杂度，以此来评估算法的运行效率，并为优化时间和空间资源提供理论依据。
  • 选项 A 错误：验证正确性属于“算法验证”或“程序证明”的范畴，是算法可用的基础，而非狭义上“算法分析（复杂度分析）”的核心目标。
  • 选项 C 错误：提高可读性属于编码规范和软件工程的要求，与算法本身的理论性能分析无关。
  • 选项 D 错误：输入规模是由实际问题决定的客观条件，算法分析是为了了解算法在处理大规模输入时的表现，而不是去减少输入规模。

3、线性表

线性表是一种逻辑结构（元素之间是一对一的线性关系）。当我们要把这种逻辑关系保存在计算机内存中时，就涉及到了物理存储结构。最主要的两大流派就是顺序存储和链式存储：

  1. 顺序存储结构 (Sequential Storage Structure)
    • 核心特点：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中。
    • 实现方式：通常借助高级语言中的数组来实现。
    • 优点：支持随机访问（可以通过下标直接在 O(1) 时间内找到特定位置的元素）；存储密度高（不需要额外的空间存指针）。
    • 缺点：插入和删除操作效率低（需要移动大量元素以保持连续性）；需要预先分配一整块连续的内存空间，容易造成空间浪费或溢出。
  2. 链式存储结构 (Linked Storage Structure)
    • 核心特点：数据元素的物理存储位置不要求连续。逻辑上相邻的元素在物理内存中可以分散在任何地方。
    • 实现方式：每个数据元素除了存储自身数据（数据域）外，还需要额外开辟空间存储指向下一个元素的内存地址（指针域/链域）。这就构成了节点 (Node)。
    • 优点：插入和删除操作效率高（只需修改指针，不需要移动元素）；动态分配内存，不需要预先知道总数据量，不会产生空间浪费。
    • 缺点：不支持随机访问（找第 n 个元素必须从头节点顺着指针逐个找，O(n) 时间）；存储密度较低（指针占用额外空间）。

总结对比：它们最本质的区别就在于底层内存地址是否连续。

【例题 3】 线性表的顺序存储结构和链式存储结构的主要区别在于（ ）

A. 数据元素的存储顺序不同 B. 数据元素的存储位置是否连续

C. 数据元素的类型不同 D. 数据元素的数量不同

【正确答案】 B. 数据元素的存储位置是否连续

【详细解析】

  • 选项 B 正确：这是定义两种存储结构最根本的标准。顺序表要求内存必须是整块连续的，而链表利用指针将零散不连续的内存块串联起来。
  • 选项 A 错误：无论是顺序存储还是链式存储，它们在逻辑上都严格保持着数据元素的线性排列顺序（即谁在前面、谁在后面是确定的），只是实现这种顺序的物理手段不同。
  • 选项 C 错误：存储结构的划分与具体存储的数据类型（如存整数、存字符串还是存复杂对象）无关。
  • 选项 D 错误：元素的数量（表长）只是线性表当前的一个状态属性，这两种结构都能存储不同数量的元素。

4、链表

在单链表中，每个节点只有一个指向下一个节点的指针（next）。为了克服单链表“只能单向查找”的缺点，我们引入了双向链表。

双向链表的节点结构包含三个部分：

  1. prior (前驱指针)：指向前一个节点。
  2. data (数据域)：存储实际数据。
  3. next (后继指针)：指向后一个节点。

插入节点的核心逻辑： 假设我们要在节点 p 的后面插入一个新节点 s。因为双向链表的节点之间是靠两根线（prior 和 next）互相拉着的，所以要加入一个新节点，需要建立两对（共4个）新的指针关系：

  1. 新节点 s 的 next 指向 p 原来的下一个节点。
  2. p 原来的下一个节点的 prior 重新指向新节点 s。
  3. 新节点 s 的 prior 指向节点 p。
  4. 节点 p 的 next 重新指向新节点 s。

代码实现（非常经典的 4 步）：

s->next = p->next;       // 第1步：修改 s 的 next
p->next->prior = s;      // 第2步：修改 p 后继节点的 prior
s->prior = p;            // 第3步：修改 s 的 prior
p->next = s;             // 第4步：修改 p 的 next

【例题 4】 在双链表中，插入一个结点需要修改的指针数量为（ ） A. 1 B. 2 C. 3 D. 4

【正确答案】 D. 4

【详细解析】

  • 选项 D 正确：正如知识点中分析的那样，在双向链表中插入一个新节点，需要处理该节点与其前驱节点和后继节点之间的双向关系。
    • 前驱节点的 next 指针（1个）
    • 后继节点的 prior 指针（1个）
    • 新节点自身的 prior 指针和 next 指针（2个）
    • 总共必须修改 4 个指针的指向。
  • 选项 B 错误（易错点）：如果是单链表，插入一个节点只需要修改 2 个指针（新节点的 next 和前驱节点的 next）。很多人会把单双链表搞混。
  • 选项 A 和 C 均为干扰项。