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

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

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

3、的结点序列是100100110001001100110101101000011011100010(C)7 .已知图的邻接矩阵同上题，根据算法，则从顶点(D)A.0243156B.0135642C.0423165D.8 .已知图的邻接矩阵同上题6,根据算法，则从顶点0出发，按广度优先遍历的结点序列是（B）A.0243651B.0136425C.0423156D.01342569 .已知图的邻接矩阵同上题6,根据算法，则从顶点0出发，按广度优先遍历的结点序列是（C）A.0243165B.0135642C.0123465D.012345610 .从未排序序列中依次取出元素与已排序序列中的元素进行比较

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

5、40,38,46,56,79,84D,40,38,46,84,56,7914 .堆是一种(B)排序。A.插入B.选择C.交换D.归并15 .若一组记录的排序码为(46,79,56,38,40,84),则利用堆排序的方法建立的初始堆为(B)。A.79,46,56,38,40,84B,84,79,56,38,40,46C.84,79,56,46,40,38D,84,56,79,40,46,38二、填空题(每空1分，共20分)1 .图有邻接矩阵、邻接表等存储结构,遍历图有深度优先遍历、广度优先遍历等方法。2 .有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的出度。3 .n个顶点e条边的图

6、，若采用邻接矩阵存储，则空间复杂度为O(n2)。4 .n个顶点e条边的图，若采用邻接表存储，则空间复杂度为O(n+e)。5 .设有一稀疏图G则G采用邻接表存储较省空间。1.1. 有一稠密图G则G采用邻接矩阵存储较省空间。7 .图的逆邻接表存储结构只适用于有向图。8 .图的深度优先遍历序列不是惟一的。个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为O(n2);若采用邻接表存储时，该算法的时间复杂度为O(n+e)。10 .n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为O(n2);若采用邻接表存储，该算法的时间复杂度为O(n+e)11 .用Dijkstra算法求某

7、一顶点到其余各顶点间的最短路径是按路径长度递增的次序来得到最短路径的。三、简答题.1 .已知如图所示的有向图，请给出该图的(1)(2)(3)每个顶点的入/出度;邻接矩阵；(4)逆邻接表。邻接表；邻接瘪阵(1)逆郛接盘ea) 邹揍寰'000000'1001000J000I001011100000j1oo1fl2 .已知一个无向图的邻接表如图2所示，要求：(1)画出该无向图；(2)根据邻接表，分别写出用DFS(深度优先搜索)和BFS(广度优先搜索)算法从顶点V0开始遍历该图后所得到的遍历序列。答(1)图2图的邻接表存储(2)根据该无向图的邻接表表示，从顶点VI、V4、V6、V5。广

8、度优先遍历序列为V0开始的深度优先遍历序列为:V0、 V2、 V3、V0、V2、V5、V6、VI、V3、V4。3 .、图3所示为一个有向网图及其带权邻接矩阵，要求对有向图采用Dijkstra算法，求从V0到其余各顶点的最短路径，写出执行算法过程中各步的状态。(a)有向带权图0OO 10 OO30100OO058OOOOOO8 050OOOOOO88 0OO10OOOO OO 20060OO OOOOOO0(b)带权邻接矩阵3、求解过程如下表所示。然占S八、从v0到各终点的D值和最短路径的求解过程i=1i=2i=3i=4i=5V1OOOOOOOOOO无V210(v0,v2)V3OO60(v0,v

9、2,v3)50(v0,v4,v3)V430(v0,v4)30(v0,v4)V5100(v0,v5)100(v0,v5)90(v0,v4,v5)60(v0,v4,v3,v5)VjV2V4V3V5Sv0,v2v0,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)直接插入排序2121630281016*206182121630281016*206182121630281

10、016*206182121628301016*206182101216283016*20618210121616*283020618210121616*202830618261012161618202830102166181216*621210181616*2610121616*18(2)希尔排序(增量选取 5, 3, 1)(3)快速排序203028(增量选取5)203028(增量选取3)202830(增量选取1)枢轴12621012283016*2016186261012283016*20161828261012181616*2028301826101

11、216*161820283016*26101216*16182028305.设待排序的关键字序列为30,60,8,40,70,12,10,试使用堆排序,(1)画出将无序数据建成初始堆的图，(2)画出将第二个数排定顺序时的堆的图。交换60和8答(1)初始堆序列为7060124030810四、程序填空题1、根据有向图的邻接矩阵求出序号为numb的顶点的度数(邻接矩阵可参考简答题第三题),请填写算法中下划线的空白处。intdegree2(Graph&ga,intnumb)inti,j,d=0;for(j=0;j<j+)已知r1.n是n个记录的递增有序表，用折半查找法查找关键字(key)

12、为k的记录。如果查找失败，则输出“失败”，函数返回值为0;否则输出“成功”，函数返回值为该记录的序号值。Intbinary_search(structrecordtyper,intn,keytypek)/*r1.n为N个记录的递增有序表，k为关键字*/intmid,low=1,hig=n;while(low<=hig)mid=(low+hig)/2;if(k<rmid.key)(1)hig=mid-1;elseif(k=rmid.key)printf(成功”)(2)returnmid;else(3)low=mid+1;if(low>high)printf(失败”);retur

13、n(0);3.建立huffman树voidHuffmanCoding(HuffmanTree&HT,int*w,intn)eight=*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)arent=I;hts2.parent=I;hti.lchild=s1;hti.lchild=s2;hti.weight=hts1.weight+hts2.weight;六.编程题1 .期中考试二个程序题(循环队列入队出队、用栈处理进制转换(P48算法)2 .以二叉链表作为二叉树的存储结构，编写以下算法：(看实习题)(1)写出先序、中序、后序遍历二叉树的递归算法；(1)统计二叉树的结点个数。3 .带头结点的单链表的插入和删除算法。(书上P30算法，)答.1.期中循环队列入队出队