数据结构导论串讲笔记

1、1、选择题和填空题：这两部分共56分，这56分中大部分分数是很好得的，做好下面两条，相信你一定能拿到不少分。理解和掌握串讲中“考核知识点的内容” 做相关的练习题，尤其是历年的真题，可参照机械工业出版社出版的数据结构导论学习辅导与真题解析。2、应用题：共6小题，每小题5分，全书可以以应用题的方式出考题的17类知识点（已经考过的有12类），我后面会结合历年考同学题给大家讲解可以以应用题的方式出考题的17类知识点，同学应该很好的理解和掌握已经考过的12类知识点，对没有考过的四类知识点，要看懂教材上的相关例题。3、算法设计：考核点主要集中在第2章的有关单链表的算法、第4章的二叉树遍历的有关算法和第8章

2、的排序的相关算法，我后面会结合历年考题给大家讲解相关算法，同学在理解的基础上要多搜集一些相关算法.11类可能出应用题的知识点1 栈的操作2000/4 2001/10 2002/10 2004/1 考过1）已知出栈序列，写出可能的入栈序列并分析操作过程。2）已知入栈序列，写出可能的出栈序列并分析操作过程。2004/1如下图所示，输入元素为（A，B，C），在栈的输出端得到一个输出序列ABC，求出在栈的输入端所有可能的输入序列。 输出端输入端栈ABC【分析】A，B，C三个字符排成的序列可以有：ABC、ACB、BAC、BCA、CAB、CBA六种，按堆栈操作的先进后出（或后进先出）的原则，只有输入序列为

3、BCA时，输出无法得到ABC。因为输入序列为BCA时，要想先输出A，必须BCA均入栈，但这样只能得到序列ACB。其余五种输入序列都可在输出端得到序列ABC。【解答】ABC、ACB、BAC、CAB、CBA2队列的操作分析顺序队中元素入队出队操作及队列的状态。（考过）2003/10设有一顺序队列sq，容量为5，初始状态时sqfront=sqrear=0，画出做完下列操作后队列及其头尾指针的状态变化情况，若不能入队，请简述其理。 （1） d，e，b入队（2） d，e出队（3） i，j入队（4） b出队（5） n，o，p入队【解答】队列及其头尾指针的状态变化情况如下图所示Sq.frontSq.rear

4、bedSq.frontSq.rearbSq.frontSq.rearjbiSq.frontSq.rearjiSq.frontSq.rear（a）初态 （b）d，e，b入队 （c） d，e出队 （d） i，j入队 （e）b出队第5步操作无法进行，因队列已满。3二叉树的存储结构1） 给出一棵二叉树，画出二叉链表示意图及顺序存储示意图。（2000/10 2003/10 2004/10考过） 2003/10画出下列二叉树的二叉链表表示图。 BEDFHGACB【解答】二叉树的二叉链表表示BADCGFHE2） 给出二叉树的顺序存储示意图，画出二叉树。（2005/1考过）2005/1已知某二叉树的顺序存储结

5、构如下所示，试画出该二叉树。ABCDEFG【分析】按照给出的顺序存储结构，先绘制出一棵包括空结点的完全二叉树，然后去掉空结点就是所求的二叉树。【解答】所求二叉树如下图ACBDEGF4二叉树的遍历1）给出一棵二叉树，写出对该二叉树进行先根遍历、中根遍历及后根遍历的序列。（2001/10 2004/1 2005/10考过）2005/10对于如下图所示二叉树，分别写出其先根遍历、中根遍历和后根遍历的结点访问序列。BEDFACB【分析】根据二叉树三种遍历方法的原理，很容易写出该二叉树的先根遍历、中根遍历和后根遍历的结点访问序【解答】先根遍历的结点访问序：A，B，D，E，F，C中根遍历的结点访问序：B，

6、F，E，D，A，C后根遍历的结点访问序：F，E，D，B，C，A2）给出一棵二叉树的先根遍历和中根遍历序列，恢复二叉树，写出后根遍历的序列。（2002/10考过）2002/10现有某二叉树，按先根遍历的序列为ABDEFCGH，按中根遍历的序列为DEFBGHCA，试画出此二叉树。 【分析】由先根遍历和中根遍历恢复二叉树的方法：在先根序列中确定根结点（最前面那个结点一定是根结点），然后根据根结点在中根序列中的位置分出根结点的左、右子树（根结点前面的那些结点为根结点的左子树上的结点，根结点后面的那些结点为根结点的右子树上的结点）。恢复该二叉树的任何一棵子树的过程仍然遵循这个原则。【解答】二叉树如下图所

7、示BCDAKGHFE3）给出一棵二叉树的后根遍历和中根遍历序列，恢复二叉树，写出先根遍历的序列。（未考过，但可能考注意第四章的考核知识点的讲解）5树的存储结构1）给出一棵树，画出该树的双亲表示法、孩子链表表示法、带双亲的孩子链表表示法及孩子兄弟链表表示法的示意图。（2000/4考过）2）给出一棵树的某一种存储结构的示意图，画出对应的树。（未考过）6树的遍历给出一棵树，写出对该树进行先根遍历、后根遍历及层次遍历的序列。（未考过）7二叉树与树、林的相互转换1）将一棵二叉树转换为树。（未考过）2）将一棵树转换为二叉树。（未考过）3）将林转换为一棵二叉树。（未考过）4）将二叉树转换为林。（未考过）8够

8、造哈夫曼树给出一组权值，构造一棵哈夫曼树并求带权路径长度。（未考过）9图的存储结构1）给出一个图，画出该图的邻接矩阵或邻接表存储示意图。（考过）2005/10试给出下图的邻接矩阵和邻接表表示。【分析】邻接矩阵存储方法是用一个二维数组存放顶点之间关系的信息。对于不带权的有向图，如果一个顶点到另一个顶点有边，用1表示；否则，用0表示；对于带权的有图，如果一个顶点到另一个顶点有边，用边的权值表示；否则，用表示。 邻接表存储方法的核心思想是对于具有n个顶点的图建立n个线性链表。每一个链表最前面都分别设置一个称之为表头结点的结点，n个结点构成一个数组结构。第i个链表中的每一个链结点称之为表结点。对带权的

9、图，其邻接表中的每个表结点都要增加一个权值域。【解答】题中图的邻接矩阵为：V1V2V3V4V5V1 V2 V3 V4 V5题中图的邻接表为：V1V3V4V5V222344627311213382）给出一个图的邻接表，画出该图的所有连通分量。（考过） 2002/10已知无向图G的邻接表如下图所示，请画出其所有的连通分量。 V1V3V4V5V242355113【分析】根据邻接表，很容易画出其所有的连通分量。【解答】画出的连通分量如下图所示V1V3V5V2V4V2V23）给出一个图的邻接矩阵，画出该图的所有连通分量。（考过）2003/1V0V1V2V3V4V0 V1 V2 V3 V4已知无向图G的邻

10、接矩阵如下图。假设对其访问时每行元素必须从右到左，请画出其所有的连通分量，并且写出按深度优先搜索时各连通分量的访问序列。 【分析】根据邻接表，很容易画出其所有的连通分量。【解答】画出的连通分量如下图所示V1V4V2V2V3V0V2 深度优先搜索时各连通分量的访问序列：V1V2V4 V0V310图的遍历1）给出一个图的邻接表，写出从某一点出发进行广度优先搜索和深度优先搜索的遍历序列。（2000/10 2001/10 2004/1 2004/10考过） 2004/1已知无向图G的邻接表如下图所示，请写出其从顶点V2开始的深度优先搜索的序列。 V1V3V4V5V23252141543234235【分

11、析】根据深度优先搜索的算法思想和题中给定的存储结构，所得到的遍历序列是惟一的。 【解答】深度优先搜索序列：V2V5V3V1V42）给出一个图的邻接矩阵，写出从某一点出发进行广度优先搜索和深度优先搜索的遍历序列。（2003/10考过）V0V1V2V3V4V0 V1 V2 V3 V42003/10已知无向图G的邻接矩阵如下图所示，假设对其每行元素访问时必须从右到左，请写出从V0开始的深度优先搜索的序列。 【分析】根据深度优先搜索的算法思想和题中给定的存储结构，所得到的遍历序列是惟一的。 【解答】深度优先搜索序列：V0V2V4V3V111最小生成树给出一个带权图，画出所有可能的最小生成树。（2005/1 2006/1考过） 2006/1试用Prim算法构造下图的最小生成树，要求分步给出构造过程。V2V2