数据结构导论串讲笔记

1、数据结构导论串讲笔记1）已知出栈序列，写出可能的入栈序列并分析操作过程。2）已知入栈序列，写出可能的出栈序列并分析操作过程。2004/1 如下图所示，输入元素为（ A，B，C），在栈的输出端得到一个输出序列 ABC ，求出在栈的输入端所有可能的输入序列。AB输输栈【分析】 A，B，C 三个字符排成的序列可以有：ABC 、ACB 、BAC 、BCA 、CAB 、CBA六种，按堆栈操作的先进后出（或后进先出）的原则，只有输入序列为 BCA 时，输出无法得到 ABC 。因为输入序列为 BCA 时，要想先输出 A，必须 BCA 均入栈，但这样只能得到序列 ACB 。其余五种输入序列都可在输出端得到序列

2、 ABC 。【解答】 ABC 、ACB 、BAC 、CAB 、CBA2队列的操作分析顺序队中元素入队出队操作及队列的状态。（考过）2003/10 设有一顺序队列 sq，容量为 5，初始状态时 sqfront=sq rear=0 ，画出做完下列操作后队列及其头尾指针的状态变化情况， 若不能入队，请简述其理。1） d，e，b 入队2） d，e 出队3） i，j 入队4） b 出队5） n，o，p 入队【解答】队列及其头尾指针的状态变化情况如下图所示jSq.r jSq.rbiiSq.fSq. b Sq.r bSq.feSq.fdSq.rSq.fSq.f（ a）初态（ b） d，e， b 入队（ c）

3、d， e 出队（ d） i， j 入队（ e）b 出队第 5 步操作无法进行，因队列已满。3二叉树的存储结构1） 给出一棵二叉树，画出二叉链表示意图及顺序存储示意图。 （ 2000/10 2003/10 2004/10考过）2003/10画出下列二叉树的二叉链表表示图。ACBD E FG H【解答】二叉树的二叉链表表示ABCDEGH2） 给出二叉树的顺序存储示意图，画出二叉树。（2005/1考过）2005/1 已知某二叉树的顺序存储结构如下所示，试画出该二叉树。A B C D E F G 【分析】按照给出的顺序存储结构， 先绘制出一棵包括空结点的完全二叉树， 然后去掉空结点就是所求的二叉树。【

4、解答】所求二叉树如下图ABCDEFG4二叉树的遍历1）给出一棵二叉树，写出对该二叉树进行先根遍历、中根遍历及后根遍历的序列。 （2001/10 2004/1 2005/10考过）2005/10对于如下图所示二叉树， 分别写出其先根遍历、中根遍历和后根遍历的结点访问序列。ABCBDEF【分析】根据二叉树三种遍历方法的原理，很容易写出该二叉树的先根遍历、 中根遍历和后根遍历的结点访问序【解答】先根遍历的结点访问序： A，B，D，E，F，C中根遍历的结点访问序：B，F，E，D，A ，C后根遍历的结点访问序：F，E，D，B，C， A2）给出一棵二叉树的先根遍历和中根遍历序列，恢复二叉树，写出后根遍历的

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

6、第四章的考核知识点的讲解）5树的存储结构1）给出一棵树，画出该树的双亲表示法、孩子链表表示法、带双亲的孩子链表表示法及孩子兄弟链表表示法的示意图。 （2000/4 考过）2）给出一棵树的某一种存储结构的示意图，画出对应的树。（未考过）6树的遍历给出一棵树， 写出对该树进行先根遍历、 后根遍历及层次遍历的序列。（未考过）7二叉树与树、林的相互转换1）将一棵二叉树转换为树。 （未考过）2）将一棵树转换为二叉树。 （未考过）3）将林转换为一棵二叉树。 （未考过）4）将二叉树转换为林。（未考过）8够造哈夫曼树给出一组权值，构造一棵哈夫曼树并求带权路径长度。（未考过）9图的存储结构1）给出一个图，画出该

7、图的邻接矩阵或邻接表存储示意图。（考过）2005/10试给出下图的邻接矩阵和邻接表表示。【分析】邻接矩阵存储方法是用一个二维数组存放顶点之间关系的信息。对于不带权的有向图，如果一个顶点到另一个顶点有边， 用 1 表示；否则，用 0 表示；对于带权的有图，如果一个顶点到另一个顶点有边，用边的权值表示；否则，用表示。 邻接表存储方法的核心思想是对于具有 n 个顶点的图建立 n 个线性链表。每一个链表最前面都分别设置一个称之为表头结点的结点， n 个结点构成一个数组结构。第 i 个链表中的每一个链结点称之为表结点。 对带权的图， 其邻接表中的每个表结点都要增加一个权值域。【解答】题中图的邻接矩阵为：

8、v 0246V8v1v 21v 3711v 4V13v0 v1v2 v3v123VVV题中图的邻接表为：V223 44 6 V38V273 1 V21 2）给出一个图的邻接表，画出该图的所有连通分量。（考过）2002/10已知无向图 G 的邻接表如下图所示，请画出其所有的连通分量。V35V4V51V2V13【分析】根据邻接表， 很容易画出其所有的连通分量。【解答】画出的连通分量如下图所示VVVVV3）给出一个图的邻接矩阵，画出该图的所有连通分量。（考过）2003/1 已知无向图G 的邻接矩阵如下图。假v000010Vv100101v0201000v 310000vV4010000 v1 v2

9、v3 vV0V1V2设对其访问时每行元素必须从右到左， 请画出其所有的连通分量， 并且写出按深度优先搜索时各连通分量的访问序列。【分析】根据邻接表， 很容易画出其所有的连通分量。【解答】画出的连通分量如下图所示VVVVV深度优先搜索时各连通分量的访问序列：V1V2V4V0V310图的遍历1）给出一个图的邻接表，写出从某一点出发进行广度优先搜索和深度优先搜索的遍历序列。（ 2000/10 2001/10 2004/1 2004/10考过）2004/1已知无向图 G 的邻接表如下图所示，请写出其从顶点 V 2 开始的深度优先搜索的序列。V321V543V2145V235V234【分析】根据深度优先搜索的算法思想和题中给定的存储结构，所得到的遍历序列是惟一的。【解答】深度优先搜索序列：V 2V 5V3V1V 42）给出一个图的邻接矩阵，写出从某一点出发进行广度优先搜索和深度优先搜索的遍历序列。2003/10 考过）2003/10 已知无向图G的邻接矩阵如下图所示，假设对其每行元素访问时必须从右到左，请v001100V10111v 1v0211011v 301101vV401110v0v1v2v3v写出从 V 0 开始的深度优先搜索的序列。【分析】根据深度优先搜索的算法思想和题中给定的存储结构，所得到的遍历序列是惟一的。【解答】深度优先搜索序列：V0V2V4V