数据结构复习资料第一章

基本概念和术语

  1. 数据：信息的载体，指能够输入计算机并被识别、存储和处理的符号集合。
  2. 数据元素：数据的基本单位，通常作为整体进行处理。
  3. 数据对象：性质相同的数据元素的集合，是数据的一个子集。
  4. 数据类型：一组性质相同的值及其操作的总称。
  5. 数据结构：包括数据的逻辑结构、存储结构和运算。

逻辑结构

  • 线性结构：如线性表、栈、队列，数据元素间为一对一关系。
  • 非线性结构：如树、图，数据元素间为一对多或多对多关系。

存储结构

  • 顺序存储结构：数据元素存放在地址连续的存储单元中，逻辑关系与物理关系一致。
  • 链式存储结构：数据元素存放在任意存储单元，通过指针链接实现逻辑关系。
  • 索引存储结构：建立附加索引表，通过索引快速查找数据元素。
  • 散列存储结构：通过散列函数计算存储地址，实现快速存取。

算法的定义

  1. 有穷性：算法在有限步内结束。
  2. 确定性：每一步有确切定义，无二义性。
  3. 可行性：每一步可通过基本运算在有限时间内完成。
  4. 输入：零个或多个输入。
  5. 输出：一个或多个输出。

算法的设计要求

  • 正确性：能正确反映问题需求。
  • 可读性：易于理解和阅读。
  • 健壮性：能对非法输入做出合理反应。
  • 高效率与低存储量：尽量减少运行时间和存储空间占用。

例题

  1. 数据结构是一门研究非数值计算的程序设计问题中计算机的数据结构以及它们之间的关系和运算等的学科。
  2. 计算机识别、存储和加工处理的对象被统称为数据。
  3. 数据结构通常是研究数据的存储和逻辑结构及它们之间的联系。
  4. 数据的逻辑结构有：线性结构和非线性结构。
  5. 数据的存储结构有：顺序存储结构、链式存储结构、索引存储结构、散列存储结构。
  6. 同一记录结构中的各数据项的类型不必一致。
  7. 组成数据的基本单位是：数据元素。
  8. 算法分析的两个方面是：空间复杂度和时间复杂度。
  9. 下面**O(log₂n)**的时间复杂度最好，即执行时间最短。