[TOC]

第一章 绪论

被计算机加工的数据元素不是孤立的，它们彼此之间一般存在某种关系，通常把数据元素之间的这种关系称为 结构

数据结构涉及数据的逻辑结构、存储结构和施加其上的操作3个方面

数据结构操作的实现与存储结构有关

定义逻辑结构时可不考虑存储结构

数据结构的逻辑结构独立于其存储结构

数据逻辑结构可以分为集合结构、线性结构、树结构和图结构

从逻辑上可将数据结构分为线性结构和非线性结构，线性表、栈与队列、字符串、数组、广义表是线性结构，树、图、集合是非线性结构

线性表——一对一

集合——松散

树——一对多

图——多对多

关于抽象数据类型的描述：数据封装、使用与实现分离、信息隐藏

算法的时间复杂度与（问题规模 ）有关。

某算法的时间复杂度是O(n2)，表明该算法的执行时间与n2成正比

算法+数据结构=程序

数据元素是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。

数据项是数据结构讨论问题的最小单元

数据结构在计算机内存中的表示是指数据的存储结构

数据结构是一门研究非数值计算的程序设计问题中计算机的( 操作对象)以及它们之间的关系和操作的学科。

顺序存储结构的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。（逻辑上相邻的两个元素对应的物理地址也是相邻的）

链式存储结构的特点是借助指示元素存储地址的指针来表示数据元素之间的逻辑关系。

一个正确的算法应该具有 5 个特性：确定性、可行性、有穷性，有一个或多个输出，有零个或多个输入

数据结构中评价算法的两个重要指标是空间复杂度和时间复杂度

第二章 线性表

对于顺序存储的长度为N的线性表，访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)。

顺序表是一种随机存取的存储结构。

顺序存储设计时，存储单元的地址一定连续。

若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用顺序表存储最节省时间。

顺序存储结构的主要缺点是不利于插入或删除操作。

一个顺序表所占用的存储空间大小与(元素的存放顺序 )无关，和表的长度、元素的类型、元素中各字段的类型有关。

要将一个顺序表{a0,a1,……,a**n−1}中第i个数据元素a**i(0≤i≤n-1)删除，需要移动（n-i-1 ）个数据元素。

若长度为n的线性表采用顺序存储结构，那么删除它的第i个数据元素之前，需要它一次向前移动（n-i+1）个数据元素。

若长度为n的线性表采用顺序结构，在第i个数据元素之前插入一个元素，需要它依次向后移动（n-i+1）个元素。

线性表L=（a1, a2 ,……，an ）用一维数组表示，假定删除线性表中任一元素的概率相同（都为1/n），则删除一个元素平均需要移动元素的个数是（n-1）/2。

等概率情况下，在表长为n的顺序表中插入一个元素所需移动的元素平均个数为n/2

删除（n-1）/2 ········查找（n+1）/2·········· 插入n/2

非空线性表除终端结点外，每个结点都有唯一的后继结点。

链式存储的优点是插入、删除元素时不会引起后续元素的移动，缺点是只能顺序访问各元素。

在单链表中，增加一个头结点的最终目的是为了方便运算的实现

将线性表La和Lb头尾连接，要求时间复杂度为O(1)，且占用辅助空间尽量小。应该使用哪种结构？带尾指针的单循环链表

可以用带表头附加结点的链表表示线性表，也可以用不带头结点的链表表示线性表，前者最主要的好处是（使空表和非空表的处理统一）。

在单链表中，要删除某一指定结点，必须先找到该结点的直接前驱。

链表的存储密度小于 1

第三章 栈和队列

堆栈和队列都是插入、删除受到约束的线性表

若采用带头、尾指针的单向链表表示一个堆栈，那么该堆栈的栈顶指针top应该如何设置？将链表头设为top

栈st为空的判断条件为st.top == st.base

栈st为满的判断条件为st.top-st.base>= st.stacksize

在一个链栈中,若栈顶指针等于NULL则为栈空

和顺序栈相比，链栈有一个比较明显的优势是通常不会出现栈满的情况

栈和队列的共同点是只允许在端点处插入和删除元素

不论是入队列操作还是入栈操作,在顺序存储结构上都需要考虑”溢出”情况。

在少用一个元素空间的循环队列(m为最大队列长度)是满队列的条件**(rear+1)%m==front**

缓冲区应该是一个(队列 )结构

最不适合用作链队的链表是（）。只带队头指针的非循环双链表

从一个顺序队列中删除元素时，首先要取出队首指针所指位置上的元素

在一个顺序存储的循环队列中，若队尾指针指向队尾元素的后一个位置，则队头指针一般指向队头元素的（ ）。当前位置

在一个顺序循环队列中，若队头指针指向队头元素的当前位置，则队尾指针一般指向队尾元素的（ ）位置。后一个

一个递归算法必须包括终止条件和递归部分

一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看， 通常递归过程比非递归过程较慢

第四章 数组 广义表 串

广义表是一种（递归）数据结构。

若一个问题既可以用迭代方式也可以用递归方式求解，则（迭代 ）的方法具有更髙的时空效率。

递归函数转换为非递归函数时，通常借助（栈 ）数据结构

递归函数占用较多的存储空间

串既可以采用顺序存储，也可以采用链式存储

串的长度是指串中所含字符的个数

设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ 模式匹配）。

串是一种特殊的线性表，其特殊性体现在（ 数据元素是一个字符）。

对特殊矩阵采用压缩存储的主要目的是(减少不必要的存储空间 )

对n阶对称矩阵压缩存储时，需要表长为（n(n+1)/2　）的顺序表。

设主串的长度为n，子串的长度为m，那么BF算法的时间复杂度为（ ）。O(nxm)

BF算法在最好情况下为O（n+m），最坏情况下为O（nxm）

KMP算法的最大特点是指示主串的指针不用回溯

第六章 图

图的BFS生成树的树高比DFS生成树的树高（小或相等）

图的遍历是从给定的源点出发每一个顶点仅被访问一次

遍历的基本算法有两种：深度遍历和广度遍历

图的深度遍历是一个递归过程

图的深度优先遍历类似于二叉树的先序遍历，栈

在用邻接表表示有N个结点E条边的图时，深度优先遍历算法的时间复杂度为：O(N+E)

图的广度优先搜索遍历类似于二叉树的层次遍历

用邻接表表示图进行广度优先遍历时，通常借助（ 队列）来实现算法

如果从无向图的任一顶点出发进行一次深度优先搜索可访问所有顶点，则该图一定是连通图

下面（　Prim算法）算法适合构造一个稠密图G的最小生成树。

任何一个带权无向连通图的最小生成树——有可能不唯一

在求最小生成树时，Kruskal算法更适合于____。稀疏图

数据结构中Dijkstra算法用来解决哪个问题？最短路径

第七章 查找

对二叉搜索树进行什么遍历可以得到从小到大的排序序列？中序遍历

对于一个数据序列，按照输入顺序建立一个二叉排序树，该二叉排序树的形状取决于（数据元素的输入次序 ）

折半查找与二叉排序树的时间性能（ ）。有时不相同

如果要求一个线性表既能较快的查找，又能适应动态变化的要求，最好采用( 分块查找)查找法。

通过设置哨兵从而不需要判断下标是否越界的是（逆向顺序查找 ）

设有一个已排序的线性表（长度>=２），分别用顺序查找法和二分查找法找一个与K相等的元素，比较的次数分别是S和B，在查找不成功的情况下，S和B的关系是（S>=B）。

对线性表进行二分查找时，要求线性表必须( )以顺序方式存储，且结点按关键字有序排序

第八章 排序

对n个不同的关键字由小到大进行冒泡排序,在下列( )情况下比较的次数最多.从大到小排序好的

在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是( 归并排序).

从未排序的序列中依次取出一个元素与已排序序列中的元素进行比较,然后将其放在已排序序列的合适位置上,该排序方法称为插入排序

下列排序算法中，不稳定的是希尔排序快速排序堆排序

下列排序算法中，占用辅助空间最多的是（归并排序 ）

如果原始数据已有序，那么，使用直接插入排序算法最快。

名词解释题

链表和顺序表

顺序表

优点：便于随机存取，存取速度快，便利了查找和修改元素；存储密度大，利用效率高

缺点：占用了连续一大块的存储空间，容易浪费；不方便插入和删除元素

链表

优点：方便插入和删除元素；存储空间分配灵活，逻辑存储，不要求物理地址相邻
缺点：存储密度小，利用效率不高；不方便存取元素

邻接表和邻接矩阵

一个图的邻接矩阵表示是唯一的，而邻接表表示不唯一

邻接表（O(n+e)）

优点：便于增加和删除顶点；便于统计边的数目；空间效率高

缺点：不便于判断两个顶点是否有边；不便于计算各个顶点的度

邻接矩阵（O(n²)）

优点：便于判断两个顶点是否有边；便于计算各个顶点的度

缺点：不便于增加和删除顶点；不便于统计边的数目；空间复杂度高

排序

直接插入排序：和打扑克牌一样，把未排序的部分按序取出一个元素插入到已经排序好的有序序列中，插入位置从前往后找。时间复杂度O(n^2),空间复杂度O(1)

希尔排序：分组直接插入排序，将排序元素按增量序列分为几组，组内直接插入排序，缩减增量，使得元素基本有序，在进行一次直接插入排序。时间复杂度O(nlog2 n)，空间复杂度O(1)

冒泡排序：比较相邻元素的值。时间复杂度O(n^2),空间复杂度O(1)

快速排序：从左到右的元素都能一次性找到自己最终位置。piovt基准，low,high。时间复杂度O(nlog2 n),空间复杂度O(log2 n)

直接选择排序：在给定的一组记录中选择最小的和第一个记录交换，然后从第二个记录到最后记录中找最小的和第二个记录交换，如此下去。方式可选小放前面、选大放后面。时间复杂度O(n^2),空间复杂度O(1)

堆排序：大根堆、小根堆。时间复杂度O(nlon2 n),空间复杂度O(1)

二路归并排序：两两归并，排序成一个个有序序列。时间复杂度O(nlog2 n),空间复杂度O(n)

基数排序：实现方法为最高位优先、最低为优先。利用辅助队列按位收集和分配。时间复杂度O(n),空间复杂度O(r )