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

2014 上 数据结构期末复习大纲一. 期中前以期中考试试卷复习，算法要真正理解二、二叉树、图、排序算法将是考试重点（占60%左右）三、要掌握的算法1. 二叉树的链表表示2.建立二叉树的链表存储结构3. 先序、中序、后序遍历二叉树（递归算法）4. 遍历算法的应用（ 如求二叉树的结点数）5.建立huffman树和huffman编码6. 图的邻接矩阵表示和邻接链表表示7.图的深度优先遍历和广度优先遍历算法8. 有向图求最短路径（迪杰斯特拉算法）9. 直接插入排序算法10. shell 排序(排序过程)12. 堆排序 （排序过程）练习题1. 有8个结点的无向图最多有 条边。 A14 B. 28 C. 56 D. 112 2. 有8个结点的无向连通图最少有 条边。 A5 B. 6 C. 7 D. 8 3. 有8个结点的有向完全图有 条边。 A14 B. 28 C. 56 D. 112 4. 用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。A栈 B. 队列 C. 树 D. 图 5. 用邻接表表示图进行深度优先遍历时，通常是采用 来实现算法的。A栈 B. 队列 C. 树 D. 图 A0 2 4 3 1 5 6B. 0 1 3 6 5 4 2C. 0 4 2 3 1 6 5D. 0 3 6 1 5 4 26. 已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是*（ ）7.已知图的邻接矩阵同上题，根据算法，则从顶点0出发，按深度优先遍历的结点序列是A 0 2 4 3 1 5 6 B. 0 1 3 5 6 4 2 C. 0 4 2 3 1 6 5 D. 0 1 3 4 2 5 68. 已知图的邻接矩阵同上题6，根据算法，则从顶点0出发，按广度优先遍历的结点序列是（ ）A 0 2 4 3 6 5 1 B. 0 1 3 6 4 2 5 C. 0 4 2 3 1 5 6 D. 0 1 3 4 2 5 69. 已知图的邻接矩阵同上题6，根据算法，则从顶点0出发，按广度优先遍历的结点序列是A 0 2 4 3 1 6 5 B. 0 1 3 5 6 4 2 C. 0 1 2 3 4 6 5 D. 0 1 2 3 4 5 610.从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为（ ）。A归并排序 B冒泡排序 C插入排序 D选择排序 11. 从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（ ）。A归并排序 B冒泡排序 C插入排序 D选择排序12. 对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数最多为（ ）。An+1 Bn Cn-1 Dn(n-1)/213.若一组记录的排序码为（46, 79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。A38，40，46，56，79，84 B40，38，46，79，56，84C40，38，46，56，79，84 D40，38，46，84，56，7914. 堆是一种（ ）排序。A插入 B选择 C交换 D归并15. 若一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为（ ）。A79，46，56，38，40，84 B84，79，56，38，40，46 C84，79，56，46，40，38 D84，56，79，40，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条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为 ；若采用邻接表存储时，该算法的时间复杂度为 。10. n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为 ；若采用邻接表存储，该算法的时间复杂度为 。11. 用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度 的次序来得到最短路径的。三 、简答题. 1. 已知如图所示的有向图，请给出该图的:顶点123456入度出度（1） 每个顶点的入/出度；（2） 邻接矩阵；（3） 邻接表；逆邻接表。3. 、已知一个无向图的邻接表如图2所示，要求：（1）画出该无向图；（2）根据邻接表，分别写出用DFS(深度优先搜索)和BFS（广度优先搜索）算法从顶点V0开始遍历该图后所得到的遍历序列。图2 图的邻接表存储V6V0V1V5V3V4V223056043611212102506344、图3所示为一个有向网图及其带权邻接矩阵，要求对有向图采用Dijkstra算法，求从V0 到其余各顶点的最短路径, 写出执行算法过程中各步的状态。(a) 有向带权图 V1V0V5V4V3V251060301005020100 10 30 100 0 5 0 50 0 10 20 0 60 0(b) 带权邻接矩阵5. 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。 试为这8个字母设计赫夫曼编码。 试设计另一种由二进制表示的等长编码方案。 对于上述实例，比较两种方案的优缺点。 6. 设待排序的关键字序列为12，2，16，30，28，10，16*，20，6，18，试分别写出使用以下排序方法，每趟排序结束后关键字序列的状态。（1）.直接插入排序（2）希尔排序（增量选取5，3，1）（3）快速排序7. 设待排序的关键字序列为30，60,8,40,70,12,10，试使用堆排序，（1）画出将无序数据建成初始堆的图，（2）画出将第二个数排定顺序时的堆的图。四、程序填空题 1、 根据有向图的邻接矩阵求出序号为numb的顶点的度数(邻接矩阵可参考简答题第六题), 请填写算法中下划线的空白处。 int degree2(Graph & ga, int numb) int i,j,d=0; for(j=0; j<ga.vexnum; j+) /求出顶点numb的出度 if(ga.arcs (4 ) j!=0 && ga.arcs (4) j!=MAXINT) (5) ; for(i=0; i<ga.vexnum; i+) /求出顶点numb的入度 if(ga.arcs I (6) !=0 && ga.arcs I (6) !=MAXINT) d+; return (d);2. 已知r1.n是n个记录的递增有序表，用折半查找法查找关键字（key）为k的记录。如果查找失败，则输出“ 失败”，函数返回值为0；否则输出“成功”，函数返回值为该记录的序号值。 Int binary_search(struct recordtype r ,int n ,keytype k) /* r1.n 为N 个记录的递增有序表，k 为关键字 */ int mid,low=1,hig=n; while( low<=hig) mid=(low+hig)/2;if(k<rmid.key) (1) ;else if(k=rmid.key) printf(“ 成功”)； (2) ;else (3) ; printf(“失败”);return(0);3. 建立huffman 树 void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) / 算法6.12 / w存放n个字符的权值(均>0)，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC int m,i,s1,s2,start; unsigned c,f; HuffmanTree p; char *cd; if(n<=1) return; m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); / 0号单元未用 for(p=HT+1,i=1;i<=n;+i,+p,+w) (*p).weight=*w; (*p).parent=0; (*p).lchild=0; (*p).rchild=0; for(;i<=m;+