2014上数据结构期末复习大纲

《2014上数据结构期末复习大纲》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、2014上数据结构期末复习大纲一.期中前以期中考试试卷复习，算法要真正理解二、二叉树、图、排序算法将是考试重点（占60%左右）三、要掌握的算法1.二叉树的链表表示2.建立二叉树的链表存储结构3.先序、中序、后序遍历二叉树（递归算法）4.遍历算法的应用（如求二叉树的结点数）5.建立huffman树和huffman编码6.图的邻接矩阵表示和邻接链表表示7.图的深度优先遍历和广度优先遍历算法8.有向图求最短路径（迪杰斯特拉算法）9.直接插入排序算法10.shell排序(排序过程)12.堆排序（排序过程）练

2、习题1.有8个结点的无向图最多有条边。A．14B.28C.56D.1122.有8个结点的无向连通图最少有条边。A．5B.6C.7D.83.有8个结点的有向完全图有条边。A．14B.28C.56D.1124.用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。A．栈B.队列C.树D.图5.用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。A．栈B.队列C.树D.图A．0243156B.0136542C.0423165D.03615426.已知图的邻接矩阵，根据算法思想，则从顶点0出发按深

3、度优先遍历的结点序列是*（）7.已知图的邻接矩阵同上题，根据算法，则从顶点0出发，按深度优先遍历的结点序列是A．0243156B.0135642C.0423165D.01342568.已知图的邻接矩阵同上题6，根据算法，则从顶点0出发，按广度优先遍历的结点序列是（）A．0243651B.0136425C.0423156D.01342569.已知图的邻接矩阵同上题6，根据算法，则从顶点0出发，按广度优先遍历的结点序列是A．0243165B.0135642C.0123465D.012345610.从未排

4、序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为（）。A．归并排序B．冒泡排序C．插入排序D．选择排序11.从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（）。A．归并排序B．冒泡排序C．插入排序D．选择排序12.对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数最多为（）。A．n+1B．nC．n-1D．n(n-1)/213.若一组记录的排序码为（46,79，56，38，40，84），则利用快速排序的

5、方法，以第一个记录为基准得到的一次划分结果为（）。A．38，40，46，56，79，84B．40，38，46，79，56，84C．40，38，46，56，79，84D．40，38，46，84，56，7914.堆是一种（）排序。A．插入B．选择C．交换D．归并15.若一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为（）。A．79，46，56，38，40，84B．84，79，56，38，40，46C．84，79，56，46，40，38D．84，56，79，40，

6、46，38二、填空题（每空1分，共20分）1.图有、等存储结构，遍历图有、等方法。2.有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的。3.n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为。4.n个顶点e条边的图，若采用邻接表存储，则空间复杂度为。5.设有一稀疏图G，则G采用存储较省空间。6.设有一稠密图G，则G采用存储较省空间。7.图的逆邻接表存储结构只适用于图。8.图的深度优先遍历序列惟一的。（是，不是）9.n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为；若

7、采用邻接表存储时，该算法的时间复杂度为。10.n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为；若采用邻接表存储，该算法的时间复杂度为。11.用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度的次序来得到最短路径的。三、简答题.1.已知如图所示的有向图，请给出该图的:顶点123456入度出度（1）每个顶点的入/出度；（2）邻接矩阵；（3）邻接表；逆邻接表。3.、已知一个无向图的邻接表如图2所示，要求：（1）画出该无向图；（2）根据邻接表，分别写出用DFS(深度优先

8、搜索)和BFS（广度优先搜索）算法从顶点V0开始遍历该图后所得到的遍历序列。图2图的邻接表存储V6V0V1V5V3V4V223056043611∧2∧1∧210250∧6∧3∧4∧4、图3所示为一个有向网图及其带权邻接矩阵，要求对有向图采用Dijkstra算法，求从V0到其余各顶点的最短路径,写出执行算法过程中各步的状态。(a)有向带权图V1V0V5V4V3V251060301005020100∞10∞30100∞05∞∞∞∞∞050∞∞∞∞∞0∞10∞∞∞20060