2014上数据结构期末图习题答案

-2014 上 数据结构期末复习大纲一. 期中前以期中考试试卷复习，算法要真正理解二、二叉树、图、排序算法将是考试重点（占60%左右）三、要掌握的算法1. 二叉树的链表表示2.建立二叉树的链表存储结构3. 先序、中序、后序遍历二叉树（递归算法）4. 遍历算法的应用（ 如求二叉树的结点数）5.建立huffman树和huffman编码6. 图的邻接矩阵表示和邻接链表表示7.图的深度优先遍历和广度优先遍历算法8. 有向图求最短路径（迪杰斯特拉算法）9. 直接插入排序算法10. shell 排序(排序过程)12. 堆排序 （排序过程）练习题1. 有8个结点的无向图最多有 B 条边。 A14 B. 28 C. 56 D. 112 2. 有8个结点的无向连通图最少有 C 条边。 A5 B. 6 C. 7 D. 8 3. 有8个结点的有向完全图最多有 C 条边。 A14 B. 28 C. 56 D. 112 4. 用邻接表表示图进行广度优先遍历时，通常是采用 B 来实现算法的。A栈 B. 队列 C. 树 D. 图 5. 用邻接表表示图进行深度优先遍历时，通常是采用 A 来实现算法的。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 2建议：0 1 3 4 2 5 66. 已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是*（ C ）7.已知图的邻接矩阵同上题，根据算法，则从顶点0出发，按深度优先遍历的结点序列是( D )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出发，按广度优先遍历的结点序列是（B ）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出发，按广度优先遍历的结点序列是( C )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.从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为（ C ）。A归并排序 B冒泡排序 C插入排序 D选择排序 11. 从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（ D ）。A归并排序 B冒泡排序 C插入排序 D选择排序12. 对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数最多为（ D ）。An+1 Bn Cn-1 Dn(n-1)/213.若一组记录的排序码为（46, 79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ C ）。A38，40，46，56，79，84 B40，38，46，79，56，84C40，38，46，56，79，84 D40，38，46，84，56，7914. 堆是一种（ B ）排序。A插入 B选择 C交换 D归并15. 若一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为（ B ）。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条边的图，若采用邻接矩阵存储，则空间复杂度为 O(n2) 。4. n个顶点e条边的图，若采用邻接表存储，则空间复杂度为 O(n+e) 。5. 设有一稀疏图G，则G采用 邻接表 存储较省空间。6. 设有一稠密图G，则G采用 邻接矩阵 存储较省空间。7. 图的逆邻接表存储结构只适用于 有向 图。8. 图的深度优先遍历序列 不是 惟一的。9.n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为 O(n2) ；若采用邻接表存储时，该算法的时间复杂度为 O(n+e) 。10. n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为 O(n2) ；若采用邻接表存储，该算法的时间复杂度为 O(n+e) 11. 用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度 递增 的次序来得到最短路径的。三 、简答题. 1. 已知如图所示的有向图，请给出该图的:（1） 每个顶点的入/出度；（2） 邻接矩阵；（3） 邻接表；(4)逆邻接表。2. 已知一个无向图的邻接表如图2所示，要求：（1）画出该无向图；（2）根据邻接表，分别写出用DFS(深度优先搜索)和BFS（广度优先搜索）算法从顶点V0开始遍历该图后所得到的遍历序列。图2 图的邻接表存储V6V0V1V5V3V4V22305604361121210250634答（1）v0v1v2v3v4v6v5（2）根据该无向图的邻接表表示，从顶点V0开始的深度优先遍历序列为：V0、V2、V3、V1、V4、V6、V5。广度优先遍历序列为V0、V2、V5、V6、V1、V3、V4。3.、图3所示为一个有向网图及其带权邻接矩阵，要求对有向图采用Dijkstra算法，求从V0 到其余各顶点的最短路径, 写出执行算法过程中各步的状态。(a) 有向带权图 V1V0V5V4V3V251060301005020100 10 30 100 0 5 0 50 0 10 20 0 60 0(b) 带权邻接矩阵3、求解过程如下表所示。终点 从v0到各终点的D值和最短路径的求解过程 i=1 i=2 i=3 i=4 i=5 V1 无 V2 10 (v0,v2) V3 60 (v0,v2,v3) 50 (v0,v4,v3) V4 30 (v0,v4) 30 (v0,v4) V5 100 (v0,v5) 100 (v0,v5) 90 (v0,v4,v5) 60 (v0,v4,v3,v5) Vj V2 V4 V3 V5 S v0,v2 v0,v2,v4v0,v2,v3,v4v0,v2,v3,v4,v54. 设待排序的关键字序列为12，2，16，30，28，10，16*，20，6，18，试分别写出使用以下排序方法，每趟排序结束后关键字序列的状态。（1）.直接插入排序（2）希尔排序（增量选取5，3，1）（3）快速排序（1）直接插入排序2 12 16 30 28 10 16* 20 6 18 2 12 16 30 28 10 16* 20 6 18 2 12 16 30 28 10 16* 20 6 18 2 12 16 28 30 10 16* 20 6 18 2 10 12 16 28 30 16* 20 6 18 2 10 12 16 16* 28 30 20 6 18 2 10 12 16 16* 20 28 30 6 18 2 6 10 12 16 16* 20 28 30 18 2 6 10 12 16 16* 18 20 28 30（2） 希尔排序（增量选取5，3，1）10 2 16 6 18 12 16* 20 30 28 （增量选取5）6 2 12 10 18 16 16* 20 30 28 （增量选取3）2 6 10 12 16 16* 18 20 28 30 （增量选取1）（3）快速排序枢轴 12 6 2 10 12 28 30 16* 20 16 18 6 2 6 10 12 28 30 16* 20 16 18 28 2 6 10 12 18 16 16* 20 28 30 18 2 6 10 12 16* 16 18 20 28 30 16* 2 6 10 12 16* 16 18 20 28 305. 设待排序的关键字序列为30，60,8,40,70,12,10，试使用堆排序，（1）画出将无序数据建成初始堆的图，（2）画出将第二个数排定顺序时的堆的图。 答（1）初始堆序列 为 70 60 12 40 30 8 10 （2） 交换60和8 四、程序填空题 1、 根据有向图的邻接矩阵求出序号为numb的顶点的度数(邻接矩阵可参考简答题第三题), 请填写算法中下划线的空白处。 int degree2(Graph & ga, int numb) int i,j,d=0; for(j=0; jga.vexnum; j+) /求出顶点numb的出度 if(ga.arcs numb j!=0 & ga.arcs numb j!=MAXINT) d+ ; for(i=0; iga.vexnum; i+) /求出顶点numb的入度 if(ga.arcs I numb !=0 & ga.arcs I numb !=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(khigh) printf(“失败”);return(0);3. 建立huffman 树 void HuffmanCoding(HuffmanTree &HT, 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;+i,+p) (*p).parent=0; for(i=n+1;i=m;+i) / 建赫夫曼树 / 在HT1i-1中选择parent为0且weight最小的两个结点，其序号分别为s1和s2 select(HT,i-1,s1,s2); hts1.parent=I; hts2.parent=I; hti.lchild=s1; hti.lchild=s2; hti.weight=hts1.weight+hts2.weight; 六编程题 1.期中考试 二个程序题（循环队列入队出队、用栈处理进制转换（P48 算法3.1） 2. 以二叉链表作为二叉树的存储结构，编写以下算法： (看实习题)（1）写出先序、中序、后序遍历二叉树的递归算法；（1）统计二叉树的结点个数。3. 带头结点的单链表的插入和删除算法。（书上P30 算法2.9，2.10）答.1. 期中循环队列入队出队 #define MAX 20 typedef struct int quMAX; int rear，length; Queue; Int EnQue