数据结构专科复习资料.docx

数据结构专科复习资料.docx

《数据结构专科复习资料.docx》由会员分享，可在线阅读，更多相关《数据结构专科复习资料.docx（52页珍藏版）》请在冰点文库上搜索。

数据结构专科复习资料

计算机网络管理专业（专科）

《数据结构》期末复习指导

广州市广播电视大学理工部

夏静清

2008年6月

第一部分各章复习要求和重点习题3

第一章绪论3

第二章线性表6

第三章稀疏矩阵和广义表9

第四章栈和队列10

第五章树和二叉树12

第六章二叉树的应用14

第七章图15

第八章查找17

第九章排序18

第二部分需要重点掌握的运算题类型19

第三部分考核要求31

第四部分期末复习题示例35

第五部分期末复习题示例解答54

《数据结构》（专科）期末复习提要

《数据结构》是计算机应用专业一门省开选修课和专业基础课，它主要研究数据的各种逻辑结构及其在计算机中的存储结构和操作实现。

为了更好地掌握该课程的主要内容，特编辑此复习提要。

第一部分各章复习要求和重点习题

下面按照主教材中各章次序给出每章的具体复习要求和重点习题，以便指导同学们更好地、更有目的地进行期末复习。

第一章绪论

一、本章重点掌握的内容：

1.数据结构的定义及其二元组表示方法。

·数据结构是指数据及其相互之间的联系。

·为了确切地描述一种数据结构，通常采用二元组表示：

B=（K,R）

B是一种数据结构，它由数据元素的集合K和K上二元关系R所组成。

其中：

K={Ki|　1≤i≤n,n≥0}R={|Ku,Kv∈K}

Ki表示集合K中的一个数据元素，n为K中数据元素个数。

R是序偶（Ku,Kv∈K）的集合。

其中，Ku为Kv的前驱元素，Kv为Ku的后继元素。

2.数据的逻辑结构

·数据之间的相互联系称为数据的逻辑结构。

·数据的逻辑结构分为：

集合结构、线性结构、树结构和图结构四种。

·四种逻辑结构的特点：

集合结构：

数据元素之间没有联系；

线性结构：

数据元素之间为1对1（1:

1）的联系;

树型结构：

数据元素之间为1对N（1:

N）的联系;

图型结构：

数据元素之间为M对N（M:

N）的联系。

3．数据的物理结构或存储结构

·一种数据结构在存储器中的存储方式称为数据的物理结构或存储结构。

·四种主要的存储结构：

顺序，链接，索引与散列。

·从理论上讲，一种数据的逻辑结构都可以用任一种存储结构实现。

4．抽象数据类型（ADT）的定义和表示方法

·抽象数据类型由一组数据结构和在该组数据结构上的一组操作所组成；

·抽象数据类型在C++语言中是通过类描述的；

·抽象数据类型的表示方法：

ADT<抽象数据类型名>is

DATA:

<数据描述>

OPERATIONS:

<操作声明>

END<抽象数据类型名>

5.一维和二维数组中元素的按下标和按地址的访问方式以及相互转换，元素地址和数组地址的计算。

·对于一维数组a[n]，每个元素a[i]的存储位置的首字节地址为：

Address（a[i]）=a+i*L（0≤i≤n-1）

a：

该数组首地址；L：

数组a中元素类型的大小。

·对于二维数组b[m][n]，每个元素b[i][j]的存储位置的首字节地址为：

Address（b[i][j]）=b+i*n*L+j*L（0≤i≤m-1,0≤j≤n-1）

b：

该数组首地址；L：

数组b中元素类型的大小，n为数组b中每行元素个数。

6.函数定义中值参数和引用参数的说明格式及作用，函数被调用执行时对传送来的实际参数的影响。

·当在说明一个形参类型说明符后带有引用说明符&时，该形参被说明为引用参数，不带有引用说明符&时，则被说明为值参数。

·在函数体内对引用参数的改变将反映给对应的实参变量。

7.算法的时间复杂度和空间复杂度的概念，典型算法的时间复杂度的数量级表示。

·算法的时间复杂度是对一个算法运行时间的相对量度；

·算法的空间复杂度是对一个算法在运行时过程中临时占用存储空间的大小量度；

·后续各章典型算法的时间复杂度的数量级表示。

二、本章重点习题

主教材P36习题一

一、单选题1、3、4、5

二、填空题1、2、3、4、6、11、15、16、17、18

三、普通题4

（1）、

（2）、（3）、（4）

第二章线性表

一、本章重点掌握的内容：

1.线性表的定义和线性表中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。

2.线性表的顺序存储结构的类型定义，即List类型的定义和每个域的定义及作用。

·List类型的定义：

structList{

ElemTypelist[MaxSize]；

intsize；

}；

3.顺序存储下的线性表主要操作实现：

⑴从线性表中查找具有给定值的元素，其时间复杂度为：

O（n）

boolFind（List&L,ElemType&item）

⑵向线性表的末尾添加一个元素，时间复杂度为：

O

（1）

voidInsertRear（List&L,constElemType&item）

⑶向线性表的表头插入一个元素，时间复杂度为：

O（n）

voidInsertFront（List&L,constElemType&item）

⑷向有序顺序表中插入一个元素，时间复杂度为：

O（n）

voidInsert（List&L,constElemType&item）

⑸从线性表中删除表头元素，其时间复杂度为：

O（n）

ElemTypeDeleteFront（List&L）

⑹从线性表中删除等于给定值的元素，其时间复杂度为O（n）

boolDelete（List&L,constElemType&item）

⑺线性表的插入排序算法，时间复杂度为：

O（n2）

voidSort（List&L）

4.单链表中结点的结构，每个域的定义及作用，即LNode和ALNode类型的定义及结构。

·structLNode{//定义单链表结点类型

ElemTypedata；

LNode*next；

}；

·structALNode{//作为单链表结点的数组元素类型

ElemTypedata；

intnext；

}；

5.带表头附加结点的链表、循环链表、双向链表的结构特点。

·在线性表的链接存储中，为了便于在表头插入和删除结点，使得与在其它地方所做的操作相同，需要在表头结点前增加一个结点，把它称之为表头附加结点。

·在单链表中，若让表尾结点的指针域指向表头结点或附加表头结点，就构成了循环链表。

·在双向链表中，每个结点中除包含有数值域外，还设置两个指针域，分别指向其前趋结点和后继结点，其结点类型定义为：

structDNode{

ElemTypedata；

DNode*left；

DNode*right；

}；

6.线性表的主要操作在单链表上实现的算法及相应的时间复杂度。

⑴得到单链表的长度，时间复杂度为O（n）

intListSize（LNode*HL）

⑵从单链表中查找具有给定值的元素，其时间复杂度为：

O（n）

boolFind（LNode*HL,ElemType&item）

⑶得到单链表中第pos个结点中的元素，其时间复杂度为：

O（n）

ElemTypeGetElem（LNode*HL,intpos）

⑷向单链表的末尾添加一个元素，时间复杂度为：

O（n）

voidInsertRear（LNode*&HL,constElemType&item）

⑸向单链表的表头插入一个元素，时间复杂度为：

O

（1）

voidInsertFront（LNode*&HL,constElemType&item）

⑹向有序单链表中插入一个元素，时间复杂度为：

O（n）

voidInsert（LNode*&HL,constElemType&item）

⑺从单链表中删除表头元素，其时间复杂度为：

O

（1）

ElemTypeDeleteFront（LNode*&HL）

⑻从单链表中删除等于给定值的元素，其时间复杂度为O（n）

boolDelete（LNode*&HL,constElemType&item）

二、本章重点习题

主教材P88习题二

一、单选题1、2、3、4、5、6

二、填空题1、2、3、4、5、6、7、8、9、10

三、普通题1；3⑴、⑵、⑶、⑷；4⑴、⑵、⑶、⑷

第三章稀疏矩阵和广义表

一、重点掌握的内容：

1.稀疏矩阵的定义和三元组线性表表示。

·稀疏矩阵是矩阵中的一种特殊情况，它的非零元素的个数远远小于零元素的个数。

·对于稀疏矩阵中的每个非零元素，用它所在的行号、列号以及元素值这个三元组（i，j，aij）来表示，若把所有的三元组按照行号为主序、列号为辅序进行排列，就构成了一个表示稀疏矩阵的三元组线性表。

2.广义表的定义和表示，给定一个广义表求其长度和深度。

·广义表中的元素可以是单元素，也可以是表元素；

·广义表的图形表示和链接存储表示方法；

·给定一个广义表求其长度和深度。

二、本章重点习题

主教材P116习题

一、单选题1、2、3

二、填空题1、2、5、6、7、8、9、10

三、普通题1、3

第四章栈和队列

一、重点掌握的内容：

1.栈的定义和抽象数据类型的描述，栈中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。

2.栈的顺序存储结构的类型定义，即Stack类型的定义和每个域的定义及作用。

structStack{

ElemTypestack[StackMaxSize]；

inttop；

}；

3.栈的主要运算在顺序存储结构上实现的算法，及相应的时间复杂度。

·读栈顶元素，时间复杂度为：

O

（1）

ElemTypePeek（Stack&S）

·向栈中插入元素，时间复杂度为：

O

（1）

voidPush（Stack&S,constElemType&item）

·从栈中删除元素，时间复杂度为：

O

（1）

ElemTypePop（Stack&S）

4.栈的链接存储结构的结点类型为第二章定义的LNode，栈的主要操作在链接存储结构上实现的算法及相应的时间复杂度。

·读栈顶元素，时间复杂度为：

O

（1）

ElemTypePeek（LNode*HS）

·向链栈中插入元素，时间复杂度为：

O

（1）

voidPush（LNode*&HS,constElemType&item）

·从链栈中删除元素，时间复杂度为：

O

（1）

ElemTypePop（LNode*&HS）

5.算术表达式的中缀表示和后缀表示，以及相互转换的规则，后缀表达式求值的方法。

6.队列的定义和抽象数据类型的描述，队列中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。

7.队列的顺序存储结构的类型定义，即Queue类型的定义和每个域的定义及作用。

structQueue{

ElemTypequeue[QueueMaxSize]；

intfront,rear；

}

8.队列的主要运算在顺序存储结构上实现的算法及相应的时间复杂度。

9.队列的链接存储结构，其结点类型为LNode，其类型定义为：

structLinkQueue{

LNode*front；

LNode*rear；

}；

10.利用栈和队列解决简单问题的算法分析和设计。

二、本章重点习题

主教材P160习题四

一、单选题1、2、3、4、5、6、7、8

二、填空题1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16

三、普通题1、5、6、8、15、16

第五章树和二叉树

一、重点掌握的内容：

1.树和二叉树的定义，对于一棵具体树和二叉树的二元组表示及广义表表示。

2.树和二叉树的概念，如结点的度、树的度、树的层数、树的深度等。

3.树和二叉树的性质，如已知树或二叉树的深度h可求出相应的最多结点数，已知结点数n可求出对应树或二叉树的最大和最小高度。

·树中的结点数等于所有结点的度数加1；

·深度为h的K叉树至多有（Kh-1）/（k-1）个结点；

·具有n个结点的K叉树的最小深度为└logk（n（k-1）+1）┘

·二叉树上终端结点数等于双分支结点数加1；

·深度为h的二叉树至多有2h-1个结点；

·具有n个结点的完全二叉树的最小深度为┌log2（n+1）┐。

4.二叉树中结点的编号规则和对应的顺序存储结构。

·二叉树结点的编号按完全二叉树结点编号的规则编号，再以各结点的编号为下标，把结点的值对应存储在一个一维数组中。

5.二叉树的链接存储结构及存储结点的类型定义，即BTreeNode类型的定义和每个域的定义及作用。

·BTreeNode类型的定义：

structBTreeNode{

ElemTypedata;

BTreeNode*left;

BTreeNode*right;

};

6.二叉树的先序、中序、后序遍历的递归过程和递归算法，按层遍历的过程和算法，每种算法的时间复杂度。

·每种遍历算法的时间复杂度均为：

O（n）；

·给定一棵二叉树能把其四种遍历结果写出来；

7.普通树的先根、后根和按层遍历的过程。

·给定一棵普通树，能把其先根、后根和按层遍历结果写出来；

8.在链接存储的二叉树上实现指定功能的算法分析

·求二叉树的深度算法分析

二、本章重点习题

主教材P194习题五

一、填空题1～24

二、普通题3、6、7、8、12

第六章二叉树的应用

一、重点掌握的内容：

1.二叉搜索树的定义和性质。

2.二叉搜索树查找的递归算法和非递归算法，相应的时间复杂度（最好为O（log2n），最差为O（n）,平均大致为O（log2n）），查找一个元素的查找长度，即从树根结点到该结点的路径上的结点数（小于树的深度）。

3.二叉搜索树插入的递归算法和非递归算法，相应的时间复杂度（与查找元素一样的时间复杂度，平均大致为O（log2n））。

4.堆的定义和顺序存储结构，小根堆和大根堆的异同。

5.向堆中插入元素的过程、算法描述及时间复杂度（时间复杂度为：

O（log2n））。

6.从堆中删除元素的过程。

7.哈夫曼树的定义，树的带权路径长度的计算，根据若干个叶子结点的权值构造哈夫曼树的过程。

二、本章重点习题

主教材P219习题六

一、单选题1～6

二、填空题1～7

三、普通题1、2、7、8、9

第七章图

一、重点掌握的内容：

1.图的顶点集和边集的表示。

2.图的一些概念的含义，如顶点、边、度、完全图、子图、路径、路径长度、连通图、权、网等。

3.图的邻接矩阵、邻接表和边集数组三种存储结构表示及相应的空间复杂度。

·图的邻接矩阵的存储需要占用n×n个整数存储位置，所以其空间复杂度为O（n2）。

·图的邻接表的存储表示，需要占用n+e（e为边的数目）个结点的空间，所以其空间复杂度为O（n+e）。

·图的边集数组的存储表示，需要占用e个结点的空间，所以其空间复杂度为O（e）。

4.存储图使用的vexlist，adjmatrix，adjlist，edgenode，edgeset，edge等类型的定义及用途。

ConstintMaxVertexNum={图的最大顶点数，它要大于等于具体图的顶点数n}；

ConstintMaxEdgeNum={图的最大边数，它要大于等于具体图的顶点数e}；

TypedefVertexTypevexlist[MaxVertexNum]；

Typedefintadjmatrix[MaxVertexNum][MaxVertexNum]；

structedgenode{

intadjvex；

intweight；

edgenode*next；

}；

typedefedgenode*adjlist[MaxVertexNum]；

structedge{

intfromvex；

intendvex；

intweight；

}；

typedefedgeedgeset[MaxEdgeNum]

5.图的深度优先和广度优先搜索遍历的过程。

6.对用邻接矩阵和用邻接表表示的图进行深度优先搜索遍历的过程、算法描述以及相应的时间复杂度。

·对用邻接矩阵表示的图进行深度优先搜索遍历的时间复杂度为O（n2）。

·对用邻接表表示的图进行深度优先搜索遍历的时间复杂度为O（e）。

7.对分别用邻接矩阵和用邻接表表示的图进行广度优先搜索遍历的过程、算法描述以及相应的时间复杂度。

·对用邻接矩阵表示的图进行深度优先搜索遍历的时间复杂度为O（n2）。

·对用邻接表表示的图进行深度优先搜索遍历的时间复杂度为O（e）。

8.图的生成树、生成树的权、最小生成树等的定义。

9.根据普里姆算法求图的最小生成树的过程。

10.根据克鲁斯卡尔算法求图的最小生成树的过程。

11.图的拓扑序列和拓扑排序的概念，求图的拓扑序列的方法，对用邻接表表示的图进行拓扑排序的过程和算法。

二、本章重点习题

主教材P254习题七

一、填空题1～18

二、普通题2、3、6、7

第八章查找

一、重点掌握的内容：

1.在一维数组上进行顺序查找的过程、算法、平均查找长度和时间复杂度。

2.在一维数组上进行二分查找的过程、递归和非递归算法、平均查找长度和时间复杂度，二分查找一个给定值元素的查找长度（即查找路径上的元素数），二分查找对应的判定树及其查找成功与不成功的平均查找长度ASL的计算。

3.索引存储的概念，索引表的存储结构和索引项的存储结构，索引查找一个元素的过程、平均查找长度和时间复杂度。

4.散列存储的概念，散列函数、散列表、冲突、同义词、装填因子等术语的含义。

5.利用除留余数法建立散列函数求元素散列地址的方法。

6.利用开放定址法中的线性探查法处理冲突进行散列存储和查找的过程，利用链接法处理冲突进行散列存储和查找的过程。

7.根据除留余数法构造散列函数，采用线性探查法或链接法处理冲突，把一组数据散列存储到散列表中，计算出一个给定值元素的查找长度和查找所有元素的平均查找长度。

8.B_树中每个结点的结构，树根结点或非树根结点中关键字的个数范围和子树的个数范围，B_的结构特性，从B_树上查找一个给定值元素的过程。

二、本章重点习题

主教材P296习题八

一、填空题1～26

二、普通题1、3、4

第九章排序

一、重点掌握的内容：

1.直接插入、直接选择和冒泡排序的方法，排序过程及时间复杂度（均为O（n2））。

2.在堆排序中建立初始堆的过程和利用堆排序的过程，对一个分支结点进行筛运算的过程、算法及时间复杂度（为O（log2n）），整个堆排序的算法描述及时间复杂度（为O（nlog2n））。

3.快速排序的方法，对一组数据的排序过程，对应的二叉搜索树，快速排序过程中划分的层数和递归排序区间的个数。

4.快速排序的递归算法，它在平均情况下的时间和空间复杂度（分别为O（nlog2n）和O（log2n）），在最坏情况下的时间和空间复杂度（分别为：

O（n2）和O（n））。

5.二路归并排序的方法和对数据的排序过程，每趟排序前、后的有序表长度，二路归并排序的趟数、时间复杂度和空间复杂度（分别为：

O（nlog2n）和O（n））。

二、本章重点习题

主教材P319习题九

一、填空题1～15

二、普通题1、2、3

第二部分需要重点掌握的运算题类型

1、对于已初始化的线性表，对其在不同位置插入一些数据，最后给出线性表中的元素序列；

例1：

对于以下算法：

voidListOP（List&L）

{

InitList（L）;

Insert（L,67）;

inta[]={42,68,38,56};

for（inti=0;i<4;i++）

InsertFront（L,a[i]）;

InsertRear（L,DeleteFront（L））;

intx=GetElem（L,2）+GetElem（L,i）;

InsertFront（L,x）;

for（i=0;i

cout<

}

该算法被调用后得到的输出结果应为：

1353868426756

2、对于已初始化的堆栈，对其插入及删除一些数据，最后给出堆栈中的元素序列；

例2：

对于以下算法：

voidAS（Stack&S）

{

InitStack（S）;

Push（S,67）;

inta[]={42,68,39,50};

for（inti=0;i<4;i++）

Push（S,a[i]）;

intx=2*Pop（S）+Pop（S）/3;

Push（S,x）;

while（top!

=-1）

cout<

}

该算法被调用后得到的输出结果应为：

113684267

3、对于已初始化的队列，对其插入及删除一些数据，最后给出队列中的元素序列；

例3：

对于以下算法：

voidAQ（Queue&Q）

{

InitQueue（Q）;

QInsert（Q,67）;

inta[]={42,68,39,54};

for（inti=3;i>=0;i--）

QInsert（Q,a[i]）;

intx=2*QDelete（Q）+QDelete（Q）/3;

QInsert（Q,x）;

while（!

QueueEmpty（Q））

cout<

}

该算法被调用后得到的输出结果应为：

396842152

4、已知一棵二叉树或树、二叉树的广义表表示，给出对其进行各种遍历的结果。

例4：

已知一棵二叉树的广义表表示为：

A（B（,C（D，E））），写出对其进行前序、中序、后序和层次遍历的结果。

解：

根据其广义表表示，则其对应的二叉树为：

所以对其进行前序遍历的结果为：

A，B，C，D，E

对其进行中序遍历的结果为：

B，D，C，E，A

对其进行后序遍历的结果为：

D，E，C，B，A

对其进行层次遍历的结果为：

A，B，C，D，E

5、给定一组权值集合，构造相应的Huffman树，并计算带权外部路径长度WPL；

例8：

给定权值集合{3，7，8，2，6，10，14},构造相应的Huffman树，并计算它的带权外部路径长度。

解：

根据Huffman树的构造规则构造的树为：

WPL=（2+3）*4+（6+7+8）*3+（10+14）*2=20+63+48=131

6、从空堆开始依次向堆中插入线性表中的每一个元素，要求以线性表的形式给出每插入一个元素后堆的状态。

再从堆中删除一些元素后堆的状态。

例11：

从空堆开始依