[管理]数据结构导论串讲笔记

《[管理]数据结构导论串讲笔记》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、链表的算法、笫4章的二义树遍历的有关算法和第8章的排序的相关算法，我示而会结合历年考题给人家讲解相关算法，同学在理解的基础上要多搜集一些相关算法.11类可能出应用题的知识点1.栈的操作[2000/4][2001/10][2002/10][2004/1]考过1）已知出栈序列，写出可能的入栈序列并分析操作过程。2）已知入栈序列，写出可能的出栈序列并分析操作过程。[2004/1]如下图所示,输入元素为（A,B,C）,在栈的输出端得到一个输出序列ABC,求出在栈的输入端所有可能的输入序列。ABC输出端输入端【分析】A,B,C三个字符排成的序歹I」可以有：ABC

3、、ACB、BAC>BCA、CAB、CBA六种，按堆栈操作的先进后出（或后进先出）的原则，只冇输入序列为BCA时，输出无法得到ABCo因为输入序列为BCA吋，要想先输岀A,必须BCA均入栈，但这样只能得到序列ACB。其余五种输入序列都可在输出端得到序列ABCo【解答】ABC、ACB、BAC、CAB、CBA2.队列的操作分析顺序队中元素入队出队操作及队列的状态。（考过）[2003/10]设有一顺序队列sq,容量为5,初始状态时sq.front=sq.rear=0,画出做完下列操作后队列及其头尾指针的状态变化情况，若不能入队，请简述其理。(1)cl,e,b入

4、队(2)d,e出队(3)i,j入队(4)b出队(5)n,o,p入队【解答】队列及具头尾指针的状态变化情况如卜•图所示Sq.rear—Sq.front•J4—Sq.rear•J■1•1b4—Sq.frontSq.rearSq.frontSq.rearSq.front笫5步操作无法进行，因队列已满。3・二叉树的存储结构1）给出一棵二叉树，画出二叉链表示意图及顺序存储示意图。（[2000/10][2003/10][2004/101考过）[2003/10]画出下列二叉树的二叉链表表示图。【解答】二义树的二义链表表示2）给出二叉树的顺序存储示意图，画出二叉树。（

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

6、遍历、中根遍历和后根遍历的结点访问序【解答】先根遍历的结点访问序:中根遍历的结点访问序:后根遍历的结点访问序:A,B,D,E,F,CB,F,E,D,A,CF,E,D,B,C,A2）给出一棵二叉树的先根遍历和中根遍历序列,恢复二叉树，写出后根遍历的序列。（L2002/I0J考过）ABDEFCGH,按屮根遍历的序列为[2002/10]现有某二叉树，按先根遍历的序列为DEFBGHCA,试画出此二叉树。【分析】由先根遍历和中根遍历恢复二叉树的方法：在先根序列中确定根结点（最前面那个结点一定是根结点），然后根据根结点在中根序列屮的位査分出根结点的左、右子树（根结

7、点前面的那些结点为根结点的左子树上的结点，根结点后面的那些结点为根结点的右子树匕的结点）。恢复该二叉树的任何一棵了树的过程仍然遵循这个原则。【解答】二义树如下图所示3）给出一棵二叉树的后根遍历和中根遍历序列，恢复二叉树，写出先根遍历的序列。（未考过，但可能考注意第四章的考核知识点的讲解）5.树的存储结构1）给出一棵树，画出该树的双亲表示法、孩子链表表示法、带双亲的孩子链表表示法及孩子兄弟链表表示法的示意图。（［2000/4］考过）2）给出一棵树的某一种存储结构的示意图，画出对应的树。（未考过）6.树的遍历给出一棵树，写出对该树进行先根遍历、后根遍历及层

8、次遍历的序列。（未考过）4.二叉树与树、林的相互转换1）将一棵二叉树转换为树。（未考过）2）将