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

1、数据结构专科复习资料计算机网络管理专业（专科） 数据结构期末复习指导广州市广播电视大学理工部夏静清2008年6月第一部分 各章复习要求和重点习题 3第一章 绪论 3第二章 线性表 6第三章 稀疏矩阵和广义表 9第四章 栈和队列 10第五章 树和二叉树 12第六章 二叉树的应用 14第七章 图 15第八章 查找 17第九章 排序 18第二部分 需要重点掌握的运算题类型 19第三部分 考核要求 31第四部分 期末复习题示例 35第五部分 期末复习题示例解答 54数据结构（专科）期末复习提要数据结构是计算机应用专业一门省开选修课和专业基础课，它主要研究数据的各种逻辑结构及其在计算机中的存储结构和操作

2、实现。为了更好地掌握该课程的主要内容，特编辑此复习提要。第一部分 各章复习要求和重点习题下面按照主教材中各章次序给出每章的具体复习要求和重点习题，以便指导同学们更好地、更有目的地进行期末复习。第一章 绪论一、本章重点掌握的内容：1. 数据结构的定义及其二元组表示方法。数据结构是指数据及其相互之间的联系。为了确切地描述一种数据结构，通常采用二元组表示：B=（K , R）B是一种数据结构，它由数据元素的集合K和K上二元关系R所组成。其中：K=Ki |1in ,n0 R= | Ku,KvK Ki 表示集合K中的一个数据元素，n为K中数据元素个数。R是序偶 （ Ku,KvK）的集合。其中，Ku 为Kv

3、的前驱元素，Kv为Ku的后继元素。2. 数据的逻辑结构数据之间的相互联系称为数据的逻辑结构。数据的逻辑结构分为：集合结构、线性结构、树结构和图结构四种。四种逻辑结构的特点：集合结构：数据元素之间没有联系；线性结构：数据元素之间为1对1（1:1）的联系;树型结构：数据元素之间为1对N（1:N）的联系;图型结构：数据元素之间为M对N（M:N）的联系。3数据的物理结构或存储结构一种数据结构在存储器中的存储方式称为数据的物理结构或存储结构。四种主要的存储结构：顺序，链接，索引与散列。从理论上讲，一种数据的逻辑结构都可以用任一种存储结构实现。4 抽象数据类型（ADT）的定义和表示方法抽象数据类型由一组数

4、据结构和在该组数据结构上的一组操作所组成；抽象数据类型在C+语言中是通过类描述的；抽象数据类型的表示方法：ADT isDATA :OPERATIONS:END 5.一维和二维数组中元素的按下标和按地址的访问方式以及相互转 换，元素地址和数组地址的计算。对于一维数组an，每个元素ai的存储位置的首字节地址为：Address(ai)=a + i * L (0in-1)a：该数组首地址；L：数组a中元素类型的大小。对于二维数组bmn，每个元素bij的存储位置的首字节地址为：Address(bij)=b + i * n * L + j * L (0im-1, 0jn-1)b：该数组首地址；L：数组b中

5、元素类型的大小，n为数组b中每行元素个数。6. 函数定义中值参数和引用参数的说明格式及作用，函数被调用执行时对传送来的实际参数的影响。当在说明一个形参类型说明符后带有引用说明符&时，该形参被说明为引用参数，不带有引用说明符&时，则被说明为值参数。在函数体内对引用参数的改变将反映给对应的实参变量。7. 算法的时间复杂度和空间复杂度的概念，典型算法的时间复杂度的数量级表示。算法的时间复杂度是对一个算法运行时间的相对量度；算法的空间复杂度是对一个算法在运行时过程中临时占用存储空间的大小量度；后续各章典型算法的时间复杂度的数量级表示。二、本章重点习题主教材 P36 习题一 一、单选题 1、3、4、5二

6、、填空题 1、2、3、4、6、11、15、16、17、18三、普通题 4 （1）、（2）、（3）、（4）第二章 线性表一、本章重点掌握的内容：1.线性表的定义和线性表中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。2.线性表的顺序存储结构的类型定义，即List类型的定义和每个域的定义及作用。 List类型的定义：struct List ElemType listMaxSize；int size ； ； 3. 顺序存储下的线性表主要操作实现：从线性表中查找具有给定值的元素，其时间复杂度为：O(n)bool Find(List & L , ElemType & item)向线

7、性表的末尾添加一个元素，时间复杂度为：O(1)void InsertRear(List& L, const ElemType & item)向线性表的表头插入一个元素，时间复杂度为：O(n)void InsertFront(List & L, const ElemType & item)向有序顺序表中插入一个元素，时间复杂度为：O(n)void Insert(List & L, const ElemType & item)从线性表中删除表头元素，其时间复杂度为：O(n)ElemType DeleteFront(List & L)从线性表中删除等于给定值的元素，其时间复杂度为O(n)bool D

8、elete(List & L, const ElemType & item)线性表的插入排序算法，时间复杂度为：O(n2)void Sort(List & L)4. 单链表中结点的结构，每个域的定义及作用，即LNode和ALNode类型的定义及结构。 struct LNode /定义单链表结点类型ElemType data；LNode * next； ； struct ALNode /作为单链表结点的数组元素类型ElemType data ；int next ； ；5. 带表头附加结点的链表、循环链表、双向链表的结构特点。在线性表的链接存储中，为了便于在表头插入和删除结点，使得与在其它地方所做

9、的操作相同，需要在表头结点前增加一个结点，把它称之为表头附加结点。在单链表中，若让表尾结点的指针域指向表头结点或附加表头结点，就构成了循环链表。在双向链表中，每个结点中除包含有数值域外，还设置两个指针域，分别指向其前趋结点和后继结点，其结点类型定义为：struct DNodeElemType data ；DNode * left ；DNode * right；6. 线性表的主要操作在单链表上实现的算法及相应的时间复杂度。得到单链表的长度，时间复杂度为O(n)int ListSize(LNode * HL )从单链表中查找具有给定值的元素，其时间复杂度为：O(n)bool Find(LNode

10、* HL , ElemType & item)得到单链表中第pos个结点中的元素，其时间复杂度为： O(n)ElemType GetElem(LNode * HL, int pos)向单链表的末尾添加一个元素，时间复杂度为：O(n)void InsertRear(LNode *& HL, const ElemType & item)向单链表的表头插入一个元素，时间复杂度为：O(1)void InsertFront(LNode *& HL,const ElemType & item)向有序单链表中插入一个元素，时间复杂度为：O(n)void Insert(LNode *& HL, const E

11、lemType & item)从单链表中删除表头元素，其时间复杂度为：O(1)ElemType DeleteFront(LNode *& HL)从单链表中删除等于给定值的元素，其时间复杂度为O(n)bool Delete(LNode * & HL, const ElemType & item)二、本章重点习题主教材 P88 习题二 一、 单选题 1、2、3、4、5、6二、 填空题 1、2、3、4、5、6、7、8、9、10三、 普通题 1 ；3 、；4 、第三章 稀疏矩阵和广义表一、重点掌握的内容：1. 稀疏矩阵的定义和三元组线性表表示。稀疏矩阵是矩阵中的一种特殊情况，它的非零元素的个数远远小于

12、零元素的个数。对于稀疏矩阵中的每个非零元素，用它所在的行号、列号以及元素值这个三元组（i，j，aij）来表示，若把所有的三元组按照行号为主序、列号为辅序进行排列，就构成了一个表示稀疏矩阵的三元组线性表。2. 广义表的定义和表示，给定一个广义表求其长度和深度。广义表中的元素可以是单元素，也可以是表元素；广义表的图形表示和链接存储表示方法；给定一个广义表求其长度和深度。二、本章重点习题主教材 P116 习题 一、 单选题 1、2、3二、 填空题 1、2、5、6、7、8、9、10三、 普通题 1 、3第四章 栈和队列一、重点掌握的内容：1. 栈的定义和抽象数据类型的描述，栈中每一种操作的功能，对应的

13、函数名、返回值类型和参数表中每个参数的作用。2. 栈的顺序存储结构的类型定义，即Stack类型的定义和每个域的定义及作用。struct Stack ElemType stackStackMaxSize；int top ；3. 栈的主要运算在顺序存储结构上实现的算法，及相应的时间复杂度。读栈顶元素，时间复杂度为：O(1)ElemType Peek(Stack & S)向栈中插入元素，时间复杂度为：O(1)void Push(Stack & S, const ElemType & item)从栈中删除元素，时间复杂度为：O(1)ElemType Pop(Stack & S)4. 栈的链接存储结构的

14、结点类型为第二章定义的LNode，栈的主要操作在链接存储结构上实现的算法及相应的时间复杂度。读栈顶元素，时间复杂度为：O(1)ElemType Peek(LNode * HS)向链栈中插入元素，时间复杂度为：O(1)void Push(LNode * & HS , const ElemType & item)从链栈中删除元素，时间复杂度为：O(1)ElemType Pop(LNode * & HS )5. 算术表达式的中缀表示和后缀表示，以及相互转换的规则，后缀表达式求值的方法。6. 队列的定义和抽象数据类型的描述，队列中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。7.

15、 队列的顺序存储结构的类型定义，即Queue类型的定义和每个域的定义及作用。struct Queue ElemType queueQueueMaxSize；int front, rear ；8. 队列的主要运算在顺序存储结构上实现的算法及相应的时间复杂度。9. 队列的链接存储结构，其结点类型为LNode，其类型定义为：struct LinkQueue LNode * front；LNode * rear；10. 利用栈和队列解决简单问题的算法分析和设计。二、本章重点习题主教材 P160 习题四 一、 单选题 1、2、3、4、5、6、7、8二、 填空题 1、2、3、4、5、6、7、8、9、10、

16、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个结点；

17、具有n个结点的完全二叉树的最小深度为log2(n+1)。4.二叉树中结点的编号规则和对应的顺序存储结构。二叉树结点的编号按完全二叉树结点编号的规则编号，再以各结点的编号为下标，把结点的值对应存储在一个一维数组中。5.二叉树的链接存储结构及存储结点的类型定义，即BTreeNode类型的定义和每个域的定义及作用。BTreeNode类型的定义：struct BTreeNode ElemType data;BTreeNode * left;BTreeNode * right;6.二叉树的先序、中序、后序遍历的递归过程和递归算法，按层遍历的过程和算法，每种算法的时间复杂度。每种遍历算法的时间复杂度均为：

18、 O(n) ；给定一棵二叉树能把其四种遍历结果写出来；7.普通树的先根、后根和按层遍历的过程。给定一棵普通树，能把其先根、后根和按层遍历结果写出来；8.在链接存储的二叉树上实现指定功能的算法分析求二叉树的深度算法分析二、本章重点习题主教材 P194 习题五 一、 填空题 124二、 普通题 3 、6、7、8、12第六章 二叉树的应用一、重点掌握的内容：1. 二叉搜索树的定义和性质。2. 二叉搜索树查找的递归算法和非递归算法，相应的时间复杂度（最好为O（log2n），最差为O（n）,平均大致为O（log2n），查找一个元素的查找长度，即从树根结点到该结点的路径上的结点数（小于树的深度）。3. 二

19、叉搜索树插入的递归算法和非递归算法，相应的时间复杂度（与查找元素一样的时间复杂度，平均大致为O（log2n） ）。 4. 堆的定义和顺序存储结构，小根堆和大根堆的异同。5. 向堆中插入元素的过程、算法描述及时间复杂度（时间复杂度为：O（log2n） ）。6. 从堆中删除元素的过程 。7. 哈夫曼树的定义，树的带权路径长度的计算，根据若干个叶子结点的权值构造哈夫曼树的过程。二、本章重点习题主教材 P219 习题六 一、 单选题 16二、 填空题 17三、 普通题 1、2、7、8、9第七章 图一、重点掌握的内容：1. 图的顶点集和边集的表示。2. 图的一些概念的含义，如顶点、边、度、完全图、子图、

20、路径、路径长度、连通图、权、网等。3. 图的邻接矩阵、邻接表和边集数组三种存储结构表示及相应的空间复杂度。图的邻接矩阵的存储需要占用nn个整数存储位置，所以其空间复杂度为O(n2)。图的邻接表的存储表示，需要占用n+e（e为边的数目）个结点的空间，所以其空间复杂度为O(n+e )。图的边集数组的存储表示，需要占用e个结点的空间， 所以其空间复杂度为O(e)。4. 存储图使用的vexlist，adjmatrix，adjlist，edgenode，edgeset，edge等类型的定义及用途。Const int MaxVertexNum=图的最大顶点数，它要大于等于具体图的顶点数n；Const in

21、t MaxEdgeNum=图的最大边数，它要大于等于具体图的顶点数e；Typedef VertexType vexlistMaxVertexNum；Typedef int adjmatrixMaxVertexNumMaxVertexNum；struct edgenode int adjvex；int weight；edgenode * next；typedef edgenode * adjlistMaxVertexNum；struct edge int fromvex；int endvex；int weight；typedef edge edgesetMaxEdgeNum5. 图的深度优先和广

22、度优先搜索遍历的过程。6. 对用邻接矩阵和用邻接表表示的图进行深度优先搜索遍历的过程、算法描述以及相应的时间复杂度。对用邻接矩阵表示的图进行深度优先搜索遍历的时间复杂度为O(n2)。 对用邻接表表示的图进行深度优先搜索遍历的时间复杂度为O(e)。7. 对分别用邻接矩阵和用邻接表表示的图进行广度优先搜索遍历的过程、算法描述以及相应的时间复杂度。对用邻接矩阵表示的图进行深度优先搜索遍历的时间复杂度为O(n2)。 对用邻接表表示的图进行深度优先搜索遍历的时间复杂度为O(e)。8. 图的生成树、生成树的权、最小生成树等的定义。9. 根据普里姆算法求图的最小生成树的过程。10. 根据克鲁斯卡尔算法求图的

23、最小生成树的过程。11. 图的拓扑序列和拓扑排序的概念，求图的拓扑序列的方法，对用邻接表表示的图进行拓扑排序的过程和算法。二、本章重点习题主教材 P254 习题七 一、 填空题 118二、 普通题 2、3、6、7 第八章 查找一、重点掌握的内容：1. 在一维数组上进行顺序查找的过程、算法、平均查找长度和时间复杂度。2. 在一维数组上进行二分查找的过程、递归和非递归算法、平均查找长度和时间复杂度，二分查找一个给定值元素的查找长度（即查找路径上的元素数），二分查找对应的判定树及其查找成功与不成功的平均查找长度ASL的计算。3. 索引存储的概念，索引表的存储结构和索引项的存储结构，索引查找一个元素的

24、过程、平均查找长度和时间复杂度。4. 散列存储的概念，散列函数、散列表、冲突、同义词、装填因子等术语的含义。5. 利用除留余数法建立散列函数求元素散列地址的方法。6. 利用开放定址法中的线性探查法处理冲突进行散列存储和查找的过程，利用链接法处理冲突进行散列存储和查找的过程。7. 根据除留余数法构造散列函数，采用线性探查法或链接法处理冲突，把一组数据散列存储到散列表中，计算出一个给定值元素的查找长度和查找所有元素的平均查找长度。8. B_树中每个结点的结构，树根结点或非树根结点中关键字的个数范围和子树的个数范围，B_的结构特性，从B_树上查找一个给定值元素的过程。二、本章重点习题主教材 P296

25、 习题八 一、 填空题 126二、 普通题 1、3、4第九章 排序一、重点掌握的内容：1. 直接插入、直接选择和冒泡排序的方法，排序过程及时间复杂度（均为O(n2)）。2. 在堆排序中建立初始堆的过程和利用堆排序的过程，对一个分支结点进行筛运算的过程、算法及时间复杂度（为O（log2n），整个堆排序的算法描述及时间复杂度（为O（nlog2n）。3. 快速排序的方法，对一组数据的排序过程，对应的二叉搜索树，快速排序过程中划分的层数和递归排序区间的个数。4. 快速排序的递归算法，它在平均情况下的时间和空间复杂度(分别为O（nlog2n）和O（log2n）)，在最坏情况下的时间和空间复杂度(分别为：

26、O（n2）和O（n）)。5. 二路归并排序的方法和对数据的排序过程，每趟排序前、后的有序表长度，二路归并排序的趟数、时间复杂度和空间复杂度(分别为：O（nlog2n）和O（n）)。二、本章重点习题主教材 P319 习题九 一、 填空题 115二、 普通题 1、2、3第二部分 需要重点掌握的运算题类型1、 对于已初始化的线性表，对其在不同位置插入一些数据，最后给出线性表中的元素序列；例1：对于以下算法： void ListOP(List& L) InitList(L); Insert(L,67); int a =42,68,38,56; for (int i=0; i4; i+) InsertF

27、ront ( L, ai); InsertRear ( L,DeleteFront(L); int x= GetElem(L,2)+GetElem(L,i); InsertFront(L,x); for(i=0;iL.size;i+) coutL.listi ; 该算法被调用后得到的输出结果应为： 135 38 68 42 67 562、 对于已初始化的堆栈，对其插入及删除一些数据，最后给出堆栈中的元素序列；例2：对于以下算法：void AS(Stack& S) InitStack(S); Push(S,67); int a =42,68,39,50; for(int i=0;i4;i+) P

28、ush(S,a i ); int x=2*Pop(S)+Pop(S)/3; Push(S,x); while (top != -1) coutPop(S)=0;i- -) QInsert(Q,a i ); int x=2*QDelete(Q)+QDelete(Q)/3; QInsert(Q,x); while (!QueueEmpty(Q) coutQDelete(Q) ; 该算法被调用后得到的输出结果应为：39 68 42 1524、 已知一棵二叉树或树、二叉树的广义表表示，给出对其进行各种遍历的结果。例4：已知一棵二叉树的广义表表示为：A（B（, C （ D， E），写出对其进行前序、中序

29、、后序和层次遍历的结果。解：根据其广义表表示，则其对应的二叉树为：所以对其进行前序遍历的结果为：A，B，C，D，E对其进行中序遍历的结果为：B，D，C，E，A对其进行后序遍历的结果为：D，E，C，B，A对其进行层次遍历的结果为：A，B，C，D，E5、 给定一组权值集合，构造相应的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=1316、 从空堆开始依次向堆中插入线性表中的每一个元素，要求以线性表的形式给出每插入一个元素后堆的状态。再从堆中删除一些元素后堆的状态。例11：从空堆开始依