数据结构复习提纲

本文最后更新于：June 30, 2018 pm

汕头大学于津老师的数据结构复习题，对应教材是清华的严蔚敏老师的《数据结构》。

以Niklus Wirth的观点，程序等于什么?

程序=数据结构+算法

算法的重要特性；好算法的标准。

算法的重要特性：①有穷性②确定性③可行性④输入⑤输出

好算法的标准：①正确性②可读性③健壮性④高效率和低存储

数据结构主要研究对象：

逻辑结构（线性、非线性）、

存贮结构（顺序、链式、索引、散列hash）；

运算/操作（对数据的最主要的操作：增删改查）；

数据的逻辑结构有几大类？

线性、非线性

数据的存贮结构有几类？

四类：顺序、链式、索引、散列hash

线性结构的特点。

线性结构中的数据元素存在一个对一个的关系，在线性结构中只有一个开始结点和一个终端结点，其他的每一个结点有且仅有一个前驱结点和后继结点。

线性结构与非线性结构的区别。

线性结构中的元素必须是一对一的关系，而非线性结构中的元素可以是一对多或者是多对多。

列出所学过的线性结构与非线性结构。

线性结构：线性表，栈，队列，串，一维数组；

非线性结构：二维数组，多维数组，广义表，树，森林，图；

头指针、头结点、首元结点的区别。

头指针：指向链表中第一个结点（头结点/首元结点）的指针；

头结点：链表的首元结点之前附设的一个结点；

首元结点：链表中存储线性表中第一个数据元素a1的结点；

带头结点和不带头结点的线性链表(单链表)的区别。

在结构上，带头结点的单链表，不管链表是否为空，均含有一个头结点，不带头结点的单链表不含头结点。

在操作上，带头结点的单链表的初始化为申请一个头结点。无论插入或删除的位置是首元结点还是其他结点，算法步骤都相同。不带头结点的单链表，则要考虑插入或删除的位置。

单链表、双链表、循环链表的区别、各自的优缺点及怎样决定选取何种存贮结构。

单链表：每个结点中只包含一个指针域

优点：插入和删除时候不需要移动大量的元素

缺点：指针只能单方向移动

双链表：有两个指针域，其一指向直接后继，其二指向直接前驱

优点：查找直接前驱的时候，则从头指针出发，能够克服单链表这种单向性的缺点

缺点：插入删除操作时需要修改多个指针域

循环链表：最后一个结点的指针域指向头结点

优点：使两个表连接起来就很简单，这个操作仅需两个指针即可，插入、删除时，不会断链等。

缺点：不容易确定退出循环的条件

栈和队列是什么样的线性表?

栈和队列都是操作受限的线性表。

栈是一种后进先出（LIFO）的线性表，限定仅在表尾进行插入或删除操作的线性表。

队列是一种先进先出（FIFO）的线性表，只允许在表的一端进行插入，而在另一端删除元素。

指出顺序线性表、顺序栈、顺序队列的区别。

相同：都是线性表，都是一维数组，

不同：操作不同；（线性表是任意位置操作，栈是栈顶操作，队列是尾进头出）

顺序线性表：用一组地址连续的存储单元依次存储线性表的数据元素。

顺序栈：即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。

顺序队列：除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，尚需附设两个指针front和rear分别指示队列头元素及队列尾元素的位置。

例举栈和队列的实例及用栈和队列所能解决的问题。

栈：后进先出的数据（LIFO），如：数制转换、括号匹配的校验、行编辑程序、迷宫求解、表达式求值、铁路中转站，餐厅的食物盘, 子弹壳。

队列：先进先出的数据 (FIFO)，如：操作系统作业排队，排队买东西

指出通常解决队列和栈溢出时所能用到的方法。

队列：双向队列，链队列，循环队列

栈：双栈共享，多栈共享，链栈

循环队列的循环是怎样实现的?

队头、队尾指针加1，用取模(余数)运算实现循环

给出对称矩阵、三角矩阵、对角矩阵节省内存的存贮结构并写出相应的输入、输出算法。

对称矩阵的存贮结构：

利用 = 来存储(以按行存储为例)

K=I(I-1)/2 +J-1 I>=J;

K=J(J-1)/2 +I-1 I<J;

k 是对称矩阵位于（i，j）位置的元素在一维数组中的存放位置，从0开始

a11 a21 a22 a31 …… ann

三角矩阵的存贮结构：

以下三角为例，当i<j时,aij=0

K=0的位置存储0

0 a11 a21 a22 …… a

对角矩阵的存贮结构：

记住loc( aij )=loc( a11 )+( 2i+j-3 ) L i-1<=j<=i+1

输入输出算法：

给出稀疏矩阵的节省内存的存贮结构并写出相应的输入、输出算法。

为了节省存储单元，可只存储非零元素。由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须存储非零元素所在的行号、列号，才能迅速确定一个非零元素是矩阵中的哪一个元素。其中每一个非零元素所在的行号、列号和值组成一个三元组，并由此三元组惟一确定。

//三元组表

#define MAXSIZE 100 //非零元个数的最大值

typedef struct{

int i,j; // 行下标,列下标

ElemType e; // 非零元素值

}Triple;

typedef struct

{Triple data[MAXSIZE+1]; //非零元三元组表,data[0]未用

int mu,nu, tu; // 矩阵的行数、列数和非零元个数

}TSMatrix;

//十字链表

typedef struct OLNode //结点的定义

{int i,j; // 非零元的行和列下标

ElemType e; // 非零元素值

struct OLNode *right,*down; // 该非零元所在行表和列表的后继链域

}OLNode, *OLink;

typedef struct //链表的定义

{ OLink *rhead,*chead; // 行和列链表头指针向量基址,由CreatSMatrix_OL()分配

int mu,nu,tu; // 稀疏矩阵的行、列数和非零元个数

}CrossList;

输入输出算法

用十字链表存贮稀疏矩阵时, 矩阵的每个元素同时在几条链上, 分别被称为什么链？

两条链：行链和列链

给出树的不同的几种表示（图示）形式。

（一）层次表示法

（二）广义表表示法

（三）嵌套表示法

（四）凹入法表示法

在二叉树的第 i层上至多有多少个结点。深度为 K的二叉树至多有多少个结点。

第i层上至多有2^（i-1）^个结点

深度为 K的二叉树至多有2^k^-1个结点

在一颗二叉树中, 其叶子结点数n0和度为二的结点数n2之间的关系。

n0=n2+1

证明过程如下：

假设二叉树的0度,1度,2度结点为n0,n1,n2,总节点数为T

则有按照结点求和的：T = n0 + n1 + n2 （1）

按照边求和得：T = n1 + 2 * n2 + 1 （2）

所以（2） - （1）可得：n2 + 1 - n0 = 0

所以n0 = n2 + 1

有 n个结点的完全二叉树的深度。

(log2n)+1

在二叉树的顺序存贮结构中如何求结点的双亲、孩子?

双亲：i/2；左孩子：2*i；右孩子：2*i+1；

25. 有 n个结点的二叉树用二叉链表存贮时有多少个空链域，用三叉链表存贮时有多少个空链域。

二叉：n+1个空链域

三叉：n+2个空链域

26. 为什么可在不增加指针域的情况下，对二叉树进行线索化，线索化的目的是什么?

①利用n+1个空链域

②目的：遍历方便

27. 对于已线索化二叉树如何识别指针域是指向孩子还是其后继结点?

增加标志域：LeftThread和RightThread（0指向孩子指针，1指向前驱/后继指针）

28. 树的几种存贮结构(双亲表示法、孩子表示法、孩子兄弟表示法)的优缺点，各自适应的运算。

双亲表示法：便于查找双亲，缺点：找孩子难

孩子表示法：便于涉及到孩子的操作，缺点：找双亲难

孩子兄弟法：操作容易，缺点：破坏了树的层次

29. 哪种存贮结构可将森林转为二叉树。对此种结构的各个域给予注释。说明在这个结构中怎样找到森林的n棵树。

孩子兄弟表示法，左指针是第一个孩子，右指针是第一个兄弟，最右的为第n棵树

30. 树的先根遍历、后根遍历对应其二叉树的哪种遍历，森林的先根遍历、中根遍历对应其二叉树的哪种遍历?

（先根对应先序，剩下的凑合一下）

树的先根遍历 → 二叉树的先序遍历；

树的后根遍历 → 二叉树的中序遍历；

森林的先根遍历 → 二叉树的先序遍历；

森林的中根遍历 → 二叉树的中序遍历。

31. （送命题）写算法求树中结点的度；树的度；树中的叶子结点数；树中的非终端结点数；树中某结点的兄弟、祖先、子孙、层次、堂兄弟；树的高度；森林中树的数目。（默认为树是二叉树）

求树中结点的度：（孩子表示法）求树的度只需要指针移动，度数递增就好

树的度：先把每个结点的度数求出来，再把所有结点的度数总和求出来就好啦

求树的叶子结点的个数：（下面这个只是求二叉树的）

int Leaf_Count(Bitree T)

{*//求二叉树中叶子结点的数目*

if(!T) return 0; //空树没有叶子

else if(!T->lchild&&!T->rchild) return 1; //叶子结点

else return Leaf_Count(T-lchild)+Leaf_Count(T-rchild);

//左子树的叶子数加上右子树的叶子数

}

求森林中树的数目：就是右孩子循环过去，算出右孩子的数目，再加上本身根节点（即右孩子树+1）

32. Huffman树能够解决的问题是什么？图示huffman编码过程。

1）数据通信中的数据压缩编码问题

2）构造Huffman树步骤：

图示：

33. 如何设计Huffman编译码器最有效？

（看不懂就看上面的图）

①根据给定的n个权值{w1,w2,……wn}，构造n棵只有根结点的二叉树，令其权值为wj；

②在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和；

③在森林中删除这两棵树，同时将新得到的二叉树加入森林中重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树。

34. 何为完全图、稀疏图、稠密图。

完全图：即一个图中的任意一个顶点都与其余所有顶点相邻（有连线）。对有向图来说，边数为n(n-1),对无向图来说,边数为n(n-1)/2
稀疏图和稠密图没有明确量化定义

稀疏图：有很少条边的图(e<<n )
稠密图：有很多条边的图

35. 写算法求无向图中结点的度；有向图中结点的入度和出度。（邻接矩阵存图）

** 无向图：邻接矩阵的一行或一列的数值和代表对应定点的度**。

** 有向图：邻接矩阵的对应顶点的行代表出度，列代表入度**。

36. 图的邻接矩阵、邻接表存贮结构各自优缺点，适应运算。

数组表示法（邻接矩阵表示法）：二维数组存储图

优点：容易求各个顶点的度

缺点：当图为稀疏图时浪费空间

邻接表表示法：

优点：容易找到第一个邻接点和下一个邻接点

缺点：不方便找一个结点的入度

37. 最小代价生成树的实际应用背景。

要在n个城市间建立通信联络网，顶点表示城市，权表示城市间建立通信线路所需花费代价，希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小———最小代价生成树

38. 什么图适合用Prim算法求最小代价生成树，什么图适合用 Kruskal算法求最小代价生成树。

Prim算法（稠密图，n>47）Kruskal算法（稀疏图）

39. 图示用 Prim算法及 Kruskal算法求最小代价生成树过程。

（看作业题7.5）

Prim算法——加点法，时间复杂度O(n2)

从某顶点开始，找其相邻边中权值最小的边所连另一个顶点，再找与这两个顶点相邻边中权值最小的边所连第三个顶点，重复，扩展到所有顶点。

Kruskal算法——加边法,时间复杂度与边相关

先将所有顶点都看作无边的非连通图，选择各顶点间最小边做连通分量，直到所有顶点都在同一个连通分量上。

40. 举例简述”拓扑排序”所解决的实际问题。

流程图，施工流程图，课程决定的优先权

41. 请图示”拓扑排序”的过程。

拓扑排序的方法：

①在有向图中选一个没有前驱的顶点且输出之

②从图中删除该顶点和所有以它为尾的弧

③重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止

42. 举例简述”关键路径”所解决的实际问题。

一个工程的并行的进行过程

（1）完成整个工程至少需要多少时间；

（2）哪些活动是影响工程的关键。

43. 最短路径的两个算法是什么？

迪杰斯特拉(Dijkstra)算法和弗洛伊德(Floyd)算法

（看作业7.6和PPT第7章第100-117页）

迪杰斯特拉(Dijkstra)算法

按路径长度递增次序产生最短路径，求从某个源点到其余各顶点的最短路径；

void ShortestPath_DIJ( MGraph G, int v0, PathMatrix &pre, ShortPathTable &D)

{*// 用Dijkstra 算法求有向网G的v0顶点到其余顶点v的最短路径pre[v]及其带权长度D[v]*

// final[v]为TRUE当且仅当v∈S, 即已经求得v0到v的最短路径

for (v=0;v<G.vexnum;++v) { pre[v] = -1;

final[v]=FALSE; D[v]=G.arcs[v0][v];

if (D[v]<INFINITY) pre[v]=V0;

} //for

D[v0]=0; final[v0]=TRUE; //初始化，v0顶点属于S集

//开始主循环，每次求得v0到某个v顶点的最短路径，并加v到S集

for (i=1;i<G.vexnum; ++i){ // 其余G.vexnum-1个顶点

min=INFINITY; // 当前所知离v0顶点的最近距离

for (w=0;w<G.vexnum; ++w)

if(!final[w])

if(D[w]<min) {v=w; min=D[w];} //w顶点离v0顶点更近

final[v]=TRUE; //离v0顶点最近的v加入S集

for (w=0; w<G.vexnum; ++w) // 更新当前最短路径及距离

if(!final[w] &&(min+G.arcs[v][w]<D[w])) { //修改D[w]和pre[w], w∈V-S

D[w]=min+G.arcs[v][w];

pre[w]=v;

} //if

} //for

} //ShortestPath_DIJ

弗洛伊德(Floyd)算法

逐个顶点试探法，求从某个源点到其余各顶点的最短路径；

void shortestPath_FLOYD(MGrgph G, PathMatrix &path ,DistancMatrix &length) {

//用Floyd算法求得有向网G中各对顶点v和w之间的最短路径 Path[v][w]及其带权

//长度length[v][w]。 path[i][j]是相应路径上顶点 j 的前一顶点的顶点号,

for ( int i = 0; i < n; i++ ) //矩阵length与path初始化

for ( int j = 0; j < n; j++ ) {

length[i][j] = G.arcs [i][j];

if ( i <> j && length [i][j] < INFINITY ) path[i][j] = i; // i 到 j 有路径

else path[i][j] = -1; // i 到 j 无路径

}

for ( int k = 0; k < n; k++ ) //产生length(k)及path(k)

for ( i = 0; i < n; i++ )

for ( j = 0; j < n; j++ )

if ( length[i][k] + length[k][j] < length[i][j] ) {

length [i][j] = length [i][k] + length [k][j];

path[i][j] = k;

} //缩短路径长度, 绕过 k 到 j

}