当前位置:文档之家› 上数据结构期末图习题答案

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

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

A .14 B. 28 C. 56 D. 1122. 有8个结点的无向连通图最少有 C 条边。

A .5 B. 6 C. 7 D. 8 3. 有8个结点的有向完全图最多有 C 条边。

A .14 B. 28 C. 56 D. 1124. 用邻接表表示图进行广度优先遍历时,通常是采用 B 来实现算法的。

A .栈 B. 队列 C. 树 D. 图 5. 用邻接表表示图进行深度优先遍历时,通常是采用 A 来实现算法的。

A .栈 B. 队列 C. 树 D. 图6. 已知图的邻接矩阵,根据算法思想,则从顶点0出发按深度优先遍历的结点序列是*( C )A .0 2 4 3 1 5 6 B. 0 1 3 6 5 4 2 C. 0 4 2 3 1 6 5⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡01000111011000010110101100110010001100100110111107.已知图的邻接矩阵同上题,根据算法,则从顶点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 )。

A.n+1 B.n C.n-1 D.n(n-1)/213.若一组记录的排序码为(46, 79,56,38,40,84),则利用快速排序的方法,以第一个记录为基准得到的一次划分结果为( C )。

A.38,40,46,56,79,84 B.40,38,46,79,56,84C.40,38,46,56,79,84 D.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,84 B.84,79,56,38,40,46C.84,79,56,46,40,38 D.84,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. 图的深度优先遍历序列不是惟一的。

个顶点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开始遍历该图后所得到的遍历序列。

答(1)图2 图的邻接表存储V6V0V1V5V3V4V22356043611∧2∧1∧21250∧6∧3∧4∧v0v1v2v3v6(2)根据该无向图的邻接表表示,从顶点V0开始的深度优先遍历序列为:V0、V2、V3、V1、V4、V6、V5。

广度优先遍历序列为V0、V2、V5、V6、V1、V3、V4。

3.、图3所示为一个有向网图及其带权邻接矩阵,要求对有向图采用Dijkstra 算法,求从V0 到其余各顶点的最短路径, 写出执行算法过程中各步的状态。

3、求解过程如下表所示。

(a) 有向带权图4. 设待排序的关键字序列为{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 3016* 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和四、程序填空题1、根据有向图的邻接矩阵求出序号为numb的顶点的度数(邻接矩阵可参考简答题第三题),请填写算法中下划线的空白处。

int degree2(Graph & ga, int numb){ int i,j,d=0;for(j=0; j<; j++) 已知r[1..n]是n个记录的递增有序表,用折半查找法查找关键字(key)为k的记录。

如果查找失败,,则输出“失败”,函数返回值为0;否则输出“成功”,函数返回值为该记录的序号值。

Int binary_search(struct recordtype r[ ],int n ,keytype k)/* r[1..n] 为N 个记录的递增有序表,k 为关键字 */{ int mid,low=1,hig=n;while( low<=hig){ mid=(low+hig)/2;if(k<r[mid].key) (1) hig=mid-1 ;else if(k==r[mid].key){ printf(“ 成功”);(2) return mid ;}else (3) low=mid+1 ; }if(low>high) printf(“失败”);return(0);}3. 建立huffman 树void HuffmanCoding(HuffmanTree &HT, int *w,int n) 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;ht[s2].parent==I;ht[i].lchild=s1;ht[i].lchild=s2;ht[i].weight=ht[s1].weight+ht[s2].weight;}}六.编程题1.期中考试二个程序题(循环队列入队出队、用栈处理进制转换(P48 算法)2. 以二叉链表作为二叉树的存储结构,编写以下算法: (看实习题)(1)写出先序、中序、后序遍历二叉树的递归算法;(1)统计二叉树的结点个数。

3. 带头结点的单链表的插入和删除算法。

(书上P30 算法,)答.1. 期中循环队列入队出队#define MAX 20typedef struct {int qu[MAX];int rear,length;}Queue;Int EnQueue( Queue &q, int e) { if( ==MAX) return -1;=+1)%max;=+1;[]=e;return 1;}Int DeQueue( Queue &q, int &e) { int front;if( ==0) return -1;front=+1+%max;e=[front];;return 1;}。

相关主题