该系列属于计算机基础系列中的《数据结构基础》子系列，参考书《数据结构考研复习指导》(王道论坛 组编)，完整内容请阅读原书。

1.绪论部分

1.1 数据结构基本概念

1.1.1 数据结构基本概念和术语

1. 数据

   数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合，且数据是计算机程序加工的原料；

2. 数据元素

   数据元素是数据的基本单位，一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位；如：学生记录是一个数据元素，由学号、姓名、性别等数据项组成；

3. 数据对象

   数据对象是具有相同性质数据元素的集合，是数据的一个子集；如：整数数据对象是集合N={0,±1,⋯}N=\{0,±1,\cdots\}N={0,±1,⋯}；

4. 数据类型

   数据类型是一个值的集合和定义在此集合上的一组操作的总称；

   • 原子类型：其值不可再分的数据类型；
   • 结构类型：其值可以再分解为若干分量的数据类型；
   • 抽象数据类型：抽象数据组织及与之相关的操作；

5. 数据结构

   • 数据结构是相互间存在一种或多种特定关系的数据元素的集合；
   • 在任何问题中，数据元素间存在某种关系，这种数据元素间的关系称为结构(Structure)({\rm Structure})(Structure)；
   • 数据结构包括：逻辑结构、存储结构、数据的运算；
   • 一个算法的设计取决于所选定的逻辑结构，算法的实现依赖于所采用的存储结构；

1.1.2 数据结构三要素

1. 数据的逻辑结构

   • 逻辑结构：指数据元素间的逻辑关系，即从逻辑关系上描述数据，逻辑结构与数据的存储无关，独立于计算机；

   • 数据的逻辑结构分为：线性结构和非线性结构，线性表是典型的线性结构，集合、树、图是典型的非线性结构；

   • 数据的逻辑结构分类：

     

     • 线性结构：结构中的数据元素间只存在一对一的关系；
     • 集合：结构中的数据元素间除"同属一个集合"，别无其他关系；
     • 树形结构：结构中的数据元素间存在一对多的关系；
     • 图状结构：结构中的数据元素间存在多对多的关系；

2. 数据的存储结构

   • 存储结构：指数据结构在计算机中的表示，亦称物理结构，包括数据元素的表示和关系的表示；

   • 数据存储结构用计算机语言实现的逻辑结构，依赖于计算机语言；

   • 数据的存储结构主要有：顺序存储、链式存储、索引存储、散列存储；

     • 顺序存储

       把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素间的关系由存储单元的邻接关系体现；

       顺序存储优点：可以实现随机存取，每个元素占用最少的存储空间；

       顺序存储缺点：只能使用相邻的一整块存储单元，可能会产生较多的外部碎片；

     • 链式存储

       借助指示元素存储地址的指针来表示元素间的逻辑关系；

       链式存储优点：不会出现碎片现象，能充分利用所有存储单元；

       链式存储缺点：每个元素因存储指针而占用额外的存储空间，且只能实现顺序存取；

     • 索引存储

       在存储元素信息的同时，还建立附加的索引表；索引表中的每项称为索引项，索引项的一般形式是：(关键字，地址)；

       索引存储优点：检索速度快；

       索引存储缺点：附加的索引表额外占用存储空间，增加和删除数据时需要修改索引表，会花费较多时间；

     • 散列存储

       根据元素的关键字直接计算出该元素的存储地址，亦称哈希(Hash)({\rm Hash})(Hash)存储；

       散列存储优点：检索、增加和删除结点的操作速度快；

       散列存储缺点：若散列函数不好，则可能出现元素存储单元冲突，解决冲突会增加时间和空间开销；

3. 数据运算

   • 施加在数据上的运算包括：运算的定义和实现；
   • 运算的定义是针对逻辑结构的，指出运算的功能；
   • 运算的实现是针对存储结构的，指出运算的具体操作步骤；

1.2 数据结构概念习题

1.2.1 单项选择题

1. 可以用( )定义一个完整的数据结构。
   • 数据元素；
   • 数据对象；
   • 数据关系；
   • 抽象数据类型；
2. 以下数据结构中，( )是非线性数据结构。
   • 树；
   • 字符串；
   • 队列；
   • 栈；
3. 以下属于逻辑结构的是( )。
   • 顺序表；
   • 哈希表；
   • 有序表；
   • 单链表；
4. 以下与数据的存储结构无关的术语是( )。
   • 循环队列；
   • 链表；
   • 哈希表；
   • 栈；
5. 以下关于数据结构的说法中，正确的是( )。
   • 数据的逻辑结构独立于其存储结构；
   • 数据的存储结构独立于其逻辑结构；
   • 数据的逻辑结构唯一决定其存储结构；
   • 数据结构仅由其逻辑结构和存储结构决定；
6. 在存储数据时，通常不仅要存储各数据元素的值，而且要存储( )。
   • 数据的操作方法；
   • 数据元素的类型；
   • 数据元素之间的关系；
   • 数据的存取方法；
7. 链式存储设计时，结点内的存储单元地址( )。
   • 一定连续；
   • 一定不连续；
   • 不一定连续；
   • 部分连续，部分不连续；

1.2.2 综合应用题

1. 对于两种不同的数据结构，逻辑结构或物理结构一定不相同吗？

   答：

   对于两种不同的数据结构，它们的逻辑结构和物理结构完全有可能相同。

   如二叉树和二叉排序树，二叉排序树可以采用二叉树的逻辑表示和存储方式，前者通常用于表示层次关系，后者通常用于排序和查找；虽然它们的运算都有建立树、插入结点、删除结点和查找结点等功能，但对于二叉树和二叉排序树，这些运算的定义是不同的，以查找结点为例，二叉树的时间复杂度为O(n)O(n)O(n)，二叉排序树的时间复杂度为O(log⁡2n)O(\log_2n)O(log2​n)。

2. 试举一例，说明对相同的逻辑结构，同一种运算在不同的存储方式下实现时，其运算效率不同。

   答：

   线性表可以用顺序存储方式实现，亦可以用链式存储方式实现。

   在顺序存储方式下，在线性表中插入和删除元素，平均要移动近一半的元素，时间复杂度为O(n)O(n)O(n)；

   在链式存储方式下，插入和删除的时间复杂度都是O(1)O(1)O(1)。

1.3 算法和算法评价

1.3.1 算法的基本概念

• 算法(Algorithm)({\rm Algorithm})(Algorithm)是对特定问题求解步骤的一种描述，是指令的有限序列，其中的每条指令表示一个或多个操作；

• 算法的555个重要特性：

  • 有穷性。

    一个算法必须总在执行有穷步后结束，且每一步都可在有穷时间内完成；

  • 确定性。

    算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出；

  • 可行性。

    算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现；

  • 输入。

    一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合；

  • 输出。

    一个算法有一个或多个输出，这些输出与输入有着某种特定关系的量；

• 一个好的算法应该考虑的问题：

  • 正确性。

    算法应能够正确地解决求解问题。

  • 可读性。

    算法应具有良好的可读性，以帮助人们理解；

  • 健壮性。

    输入非法数据时，算法能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果；

  • 效率与低存储量需求。

    效率：指算法执行的时间；

    存储量需求：指算法执行过程中所需要的最大存储空间；

1.3.2 算法效率的度量

算法效率的度量通过时间复杂度和空间复杂度描述。

1. 时间复杂度。

   • 一个语句的频度：指该语句在算法中被重复执行的次数；

   • 算法中所有语句的频度之和记为T(n)T(n)T(n)，是该算法问题规模nnn的函数，时间复杂度主要分析T(n)T(n)T(n)的数量级；

   • 算法中基本运算(最深层循环内的语句)的频度与T(n)T(n)T(n)同数量级，因此，通常采用算法中基本运算的频度f(n)f(n)f(n)来分析算法的时间复杂度；如：f(n)=an3+bn2+cnf(n)=an^3+bn^2+cnf(n)=an3+bn2+cn的时间复杂度为O(n3)O(n^3)O(n3)；

   • 算法的时间复杂度记作：T(n)=O(f(n))T(n)=O(f(n))T(n)=O(f(n))；其中，OOO的含义是T(n)T(n)T(n)的数量级，严格的数学定义为：若T(n)T(n)T(n)和f(n)f(n)f(n)是定义在正整数集合上的两个函数，则存在正常数CCC和n0n_0n0​，使得n≥n0n≥n_0n≥n0​时，都满足0≤T(n)≤Cf(n)0≤T(n)≤Cf(n)0≤T(n)≤Cf(n)；

   • 最坏时间复杂度：指在最坏情况下，算法的时间复杂度；

   • 平均时间复杂度：指所有可能输入实例在等概率出现的情况下，算法的期望运行时间；

   • 最好时间复杂度：指在最好情况下，算法的时间复杂度；

   • 分析时间复杂度的加法规则：
     T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max⁡(f(n),g(n)))T(n)=T_1(n)+T_2(n)=O(f(n))+O(g(n))=O(\max(f(n),g(n))) T(n)=T1​(n)+T2​(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))

   • 分析时间复杂度的乘法规则：
     T(n)=T1(n)×T2(n)=O(f(n))×O(g(n))=O(f(n)×g(n))T(n)=T_1(n)\times{T_2(n)}=O(f(n))\times{O}(g(n))=O(f(n)\times{g(n)}) T(n)=T1​(n)×T2​(n)=O(f(n))×O(g(n))=O(f(n)×g(n))

   • 常见的渐近时间复杂度：
     O(1)

2. 空间复杂度

   • 算法的空间复杂度S(n)S(n)S(n)定义为算法所耗费的存储空间，是问题规模nnn的函数，记为：S(n)=O(g(n))S(n)=O(g(n))S(n)=O(g(n))；
   • 一个程序在执行时除需要存储空间来存放本身所用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间；
   • 若输入数据所占空间只取决于问题本身，和算法无关，则只需分析除输入和程序外的额外空间；
   • 算法原地工作：指算法所需的辅助空间为常量，即O(1)O(1)O(1)；

1.4 算法和算法评价习题

1.4.1 单项选择题

1. 一个算法应该是( )。

   • 程序；
   • 问题求解步骤的描述；
   • 要满足五个基本特性；
   • A{\rm A}A和C{\rm C}C；

2. 某算法的时间复杂度为O(n2)O(n^2)O(n2)，表明该算法的( )。

   • 问题规模是n2n^2n2；
   • 执行时间等于n2n^2n2；
   • 执行时间与n2n^2n2成正比；
   • 问题规模与n2n^2n2成正比；

3. 以下算法的时间复杂度为( )

   void fun(int n){int i=1;while(i<=n){i=i*2;}
   }
   

   • O(n)O(n)O(n)；
   • O(n2)O(n^2)O(n2)；
   • O(nlog⁡2n)O(n\log_2n)O(nlog2​n)；
   • O(log⁡2n)O(\log_2n)O(log2​n)；

   解析：

   程序段的基本运算为：i=i∗2i=i*2i=i∗2，设执行次数为ttt，则有：2t≤n2^t≤n2t≤n，即t≤log⁡2nt≤\log_2nt≤log2​n，因此时间复杂度为：T(n)=O(log⁡2n)T(n)=O(\log_2n)T(n)=O(log2​n)。

4. 设nnn是描述问题规模的非负整数，下面程序片段的时间复杂度是( )。

   x=2;
   while(x

   • O(log⁡2n)O(\log_2n)O(log2​n)；
   • O(n)O(n)O(n)；
   • O(nlog⁡2n)O(n\log_2n)O(nlog2​n)；
   • O(n2)O(n^2)O(n2)；

   解析：

   程序段的基本运算为：x=2∗xx=2*xx=2∗x，每执行一次xxx乘222，设执行次数为ttt，则有：2t+1

5. 求整数n(n≥0)n(n≥0)n(n≥0)的阶乘的算法如下，其时间复杂度是( )。

   int fact(int n){if (n<=1) return 1;return n*fact(n-1);
   }
   

   • O(log⁡2n)O(\log_2n)O(log2​n)；
   • O(n)O(n)O(n)；
   • O(nlog⁡2n)O(n\log_2n)O(nlog2​n)；
   • O(n2)O(n^2)O(n2)；

6. 已知两个长度分别为mmm和nnn的升序链表，若将它们合并为长度为m+nm+nm+n的一个降序链表，则最坏情况下的时间复杂度是( )。

   • O(n)O(n)O(n)；
   • O(mn)O(mn)O(mn)；
   • O(min⁡(m,n))O(\min(m,n))O(min(m,n))；
   • O(max⁡(m,n))O(\max(m,n))O(max(m,n))；

7. 下列程序段的时间复杂度是( )。

   count=0;
   for(k=1;k<=n;k*=2)for(j=1;j<=n;j++)count++;
   

   • O(log⁡2n)O(\log_2n)O(log2​n)；
   • O(n)O(n)O(n)；
   • O(nlog⁡2n)O(n\log_2n)O(nlog2​n)；
   • O(n2)O(n^2)O(n2)；

   解析：

   内层循环条件j≤nj≤nj≤n与外层循环的变量无关，各自独立，每执行一次jjj自增111，每次内层循环都执行nnn次；

   外层循环条件k≤nk≤nk≤n，增量定义为：k∗=2k*=2k∗=2，可知循环次数ttt满足k=2t≤nk=2^t≤nk=2t≤n，即：t≤log⁡2nt≤\log_2nt≤log2​n；

   即内层循环时间复杂度为O(n)O(n)O(n)，外层循环时间复杂度为O(log⁡2n)O(\log_2n)O(log2​n)；

   对于嵌套循环，根据乘法规则可知，该段程序时间复杂度：T(n)=O(n)×O(log⁡2n)=O(nlog⁡2n)T(n)=O(n)\times{O(\log_2n)}=O(n\log_2n)T(n)=O(n)×O(log2​n)=O(nlog2​n)；

8. 下列函数的时间复杂度是( )。

   int func(int n){int i=0,sum=0;while(sum

   • O(log⁡n)O(\log{n})O(logn)；
   • O(n1/2)O(n^{1/2})O(n1/2)；
   • O(n)O(n)O(n)；
   • O(nlog⁡n)O(n\log{n})O(nlogn)；

   解析：

   程序段的基本运算为：sum+=++i{\rm sum+=++i}sum+=++i，等价于++i;sum=sum+i++i;{\rm sum=sum+i}++i;sum=sum+i；每执行一次iii自增111；

   i=1i=1i=1时，sum=0+1{\rm sum=0+1}sum=0+1；i=2i=2i=2时，sum=0+1+2{\rm sum=0+1+2}sum=0+1+2；i=3i=3i=3时，sum=0+1+2+3{\rm sum=0+1+2+3}sum=0+1+2+3，以此类推可得：sum=0+1+2+3+⋯+i=(1+i)∗i/2{\rm sum=0+1+2+3+\cdots+i=(1+i)*i/2}sum=0+1+2+3+⋯+i=(1+i)∗i/2，可知循环次数ttt满足(1+t)∗t/2

9. 算法如下，其时间复杂度为( )。

   void fun(int n){int i=0;while(i*i*i<=n)i++;
   }
   

   • O(n)O(n)O(n)；
   • O(nlog⁡n)O(n\log{n})O(nlogn)；
   • O(n3)O(\displaystyle\sqrt [3]{n})O(3n​)；
   • O(n)O(\sqrt{n})O(n​)；

   解析：

   程序段基本运算为：i++i++i++，设执行次数为ttt，有t×t×t≤nt\times{t}\times{t}≤nt×t×t≤n，即t3≤nt^3≤nt3≤n，则有：t≤n3t≤\sqrt[3]{n}t≤3n​，因此时间复杂度为：T(n)=O(n3)T(n)=O(\sqrt[3]{n})T(n)=O(3n​)；

10. 程序段如下：

    for(i=n-1;i>1;i--)for(j=1;jA[j+1])A[j]与A[j+1]对换;
    

    其中nnn为正整数，则最后一行语句的频度在最坏情况下是( )。

    • O(n)O(n)O(n)；
    • O(nlog⁡n)O(n\log{n})O(nlogn)；
    • O(n3)O(n^3)O(n3)；
    • O(n2)O(n^2)O(n2)；

    解析：

    当所有相邻元素都为逆序时，则最后一行的语句每次都会执行，此时，
    T(n)=∑i=2n−1∑j=1i−11=∑i=2n−1i−1=(n−2)(n−1)/2=O(n2)T(n)=\sum_{i=2}^{n-1}\sum_{j=1}^{i-1}1=\sum_{i=2}^{n-1}i-1=(n-2)(n-1)/2=O(n^2) T(n)=i=2∑n−1​j=1∑i−1​1=i=2∑n−1​i−1=(n−2)(n−1)/2=O(n2)

11. 以下算法中最后一行的语句的执行次数为( )

    int m=0,i,j;
    for(i=1;i<=n;i++)for(j=1;j<=2*i;j++)m++;
    

    • n(n+1)n(n+1)n(n+1)；
    • nnn；
    • n+1n+1n+1；
    • n2n^2n2；

12. 下面说法中，错误的是( )

    Ⅰ.算法原地工作的含义是指不需要任何额外的辅助空间；

    Ⅱ.在相同规模nnn下，复杂度为O(n)O(n)O(n)的算法在时间上总是由于复杂度为O(2n)O(2^n)O(2n)的算法；

    Ⅲ.所谓时间复杂度，是指最坏情况下估算算法运行时间的一个上界；

    Ⅳ.同一个算法，实现语言的级别越高，执行效率越低；

    • Ⅰ；
    • Ⅰ，Ⅱ；
    • Ⅰ，Ⅳ；
    • Ⅲ；

13. 设nnn是描述问题规模的非负整数，下列程序段的时间复杂度是( )。

    x=0;
    while(n>=(x+1)*(x+1))x=x+1;

    • O(log⁡n)O(\log{n})O(logn)；
    • O(n1/2)O(n^{1/2})O(n1/2)；
    • O(n)O(n)O(n)；
    • O(n2)O(n^2)O(n2)；

    解析：

    假设第kkk次循环终止，则第kkk次执行时，(x+1)2>n，x(x+1)^2>n，x(x+1)2>n，x的初始值为000，第kkk次判断时，x=k−1x=k-1x=k−1，即k2>n，k>nk^2>n，k>\sqrt{n}k2>n，k>n​，因此，该程序段的时间复杂度为：O(n)O(\sqrt{n})O(n​)。