人武学院数据结构课后习题答案及期末综合练习.doc

第十章内部排序一、 基本知识题答案1. 排序: 将一组杂乱无序的数据按一定的规律顺次排列起来叫做排序。 内部排序: 数据存储在内存中, 并在内存中加以处理的排序方法叫内部排序。 堆: 堆是一个完全二叉树, 它的每个结点对应于原始数据的一个元素, 且规定如果一个结点有儿子结点, 此结点数据必须大于或等于其儿子结点数据。稳定排序: 一种排序方法, 若排序后具有相同关键字的记录仍维持原来的相对次序, 则称之为稳定的, 否则称为不稳定的。2. 回答下面问题 (1) 5000个无序的数据, 希望用最快速度挑选出其中前10个最大的元素, 在快速排序、 堆排序、 归并排序和基数排序中采用哪种方法最好? 为什么? (2) 大多数排序算法都有哪两个基本操作? 答: (1)采用堆排序最好。 因为以上几种算法中, 快速排序、 归并排序和基数排序都是在排序结束后才能确定数据元素的全部顺序, 而无法知道排序过程中部分元素的有序性。堆排序则每次输出一个最大( 或最小) 的元素, 然后对堆进行调整, 保证堆顶的元素总是余下元素中最大( 或最小) 的。根据题意, 只要选取前10个最大的元素, 故采用堆排序方法是合适的。 (2)两个基本操作: 比较两个关键字的大小、 改变指向记录的指针或移动记录本身。3. 3. 已知序列17, 25, 55, 43, 3, 32, 78, 67, 91, 请给出采用冒泡排序法对该序列作递增排序时每一趟的结果。 答: 采用冒泡排序法排序时的各趟结果如下: 初始: 17, 25, 55, 43, 3, 32, 78, 67, 91第1趟: 17, 25, 43, 3, 32, 55, 67, 78, 91第2趟: 17, 25, 3, 32, 43, 55, 67, 78, 91第3趟: 17, 3, 25, 32, 43, 55, 67, 78, 91第4趟: 3, 17, 25, 32, 43, 55, 67, 78, 91第5趟: 3, 17, 25, 32, 43, 55, 67, 78, 91第5趟无元素交换, 排序结束。 4. 已知序列491, 77, 572, 16, 996, 101, 863, 258, 689, 325, 请分别给出采用快速排序、 堆排序和基数排序法对该序列作递增排序时每一趟的结果。答: 采用快速排序法排序时的各趟结果如下: 初始: 491, 77, 572, 16, 996, 101, 863, 258, 689, 325第1趟: 325, 77, 258, 16, 101 491 863, 996, 689, 572第2趟: 101, 77, 258, 16 325, 491 863, 996, 689, 572第3趟: 16, 77 101 258 325, 491 863, 996, 689, 572第4趟: 16 77 101 258 325, 491 863, 996, 689, 572第5趟: 16, 77, 101 258 325, 491 863, 996, 689, 572第6趟: 16, 77, 101, 258, 325, 491 863, 996, 689, 572第7趟: 16, 77, 101, 258, 325, 491 572, 689 863 996第8趟: 16, 77, 101, 258, 325, 491, 572 689 863 996第9趟: 16, 77, 101, 258, 325, 491, 572, 689, 863 996第10趟: 16, 77, 101, 258, 325, 491, 572, 689, 863, 996采用堆排序法排序时各趟的结果如下图所示: (a) 初始堆 (b) 建堆 (c) 交换996和77, 输出996 (d) 筛选调整采用基数排序法排序时各趟的结果如下: 初始: 491, 77, 572, 16, 996, 101, 863, 258, 689, 325第1趟( 按个位排序) : 491, 101, 572, 863, 352, 16, 996, 77, 258, 689第2趟( 按十位排序) : 101, 16, 352, 258, 863, 572, 77, 689, 491, 996第3趟( 按百位排序) : 16, 77, 101, 258, 352, 491, 572, 689, 863, 9965. 已知序列86, 94, 138, 62, 41, 54, 18, 32, 请给出采用插入排序法对该序列作递增排序时, 每一趟的结果。答: 采用插入排序法排序时各趟的结果如下: 初始: (86), 94, 138, 62, 41, 54, 18, 32第1趟: (86, 94), 138, 62, 41, 54, 18, 32第2趟: (86, 94, 138), 62, 41, 54, 18, 32第3趟: (62, 86, 94, 138), 41, 54, 18, 32第4趟: (41, 62, 86, 94, 138), 54, 18, 32第5趟: (41, 54, 62, 86, 94, 138), 18, 32第6趟: (18, 41, 54, 62, 86, 94, 138), 32第7趟: (18, 32, 41, 54, 62, 86, 94, 138) 6. 已知序列27, 35, 11, 9, 18, 30, 3, 23, 35, 20, 请给出采用归并排序法对该序列作递增排序时的每一趟的结果。答: 采用归并排序法排序时各趟的结果如下: 初始: 27, 35, 11, 9, 18, 30, 3, 23, 35, 20第1趟: 27, 35 9, 11 18, 30 3, 23 20, 35第2趟: 9, 11, 27, 35 3, 18, 23, 30 20, 35第3趟: 9, 11, 27, 35 3, 18, 20, 23, 30, 35第4趟: 3, 9, 11, 18, 20, 23, 27, 30, 35, 35 二、 算法设计题答案1. 二、 算法设计题1. 一个线性表中的元素为全部为正或者负整数, 试设计一算法, 在尽可能少的时间内重排该表, 将正、 负整数分开, 使线性表中所有负整数在正整数前面。解: 本题的算法思想是: 设置两个变量分别指向表的首尾, 它们分别向中间移动, 指向表首的如果遇到正整数, 指向表尾的如果遇到负整数则互相交换, 然后继续移动直至两者相遇。实现本题功能的算法如下: void part(int array,int n) int i,j; i=1; j=n;while(ij) while(ij & arrayi0) i+; while(i=0) j-; if(inext; /*p指向待插入的元素*/ while(p!=NULL) q=head; if(p-keykey) /*插到表首*/ pre-next =p-next; p-next =head; head=p; else while(q-next!=p & q-next -keykey) q=q-next;if(q-next =p) pre=p;p=p-next; else pre-next =p-next; p-next =q-next; q-next =p; p=pre-next; 3. 试设计一个算法实现双向冒泡排序。( 双向冒泡排序就是在排序的过程中交替改变扫描方向。) 解: 实现本题功能的算法如下: void dbubblesort(sqlist r,int n) int i,j,flag; flag=1; i=1; while(flag!=0) flag=0; for(j=i;jrj+1)flag=1;r0=rj;rj=rj+1;rj+1=r0; for(j=n-i;ji;j-) if(rjrj-1) flag=1;r0=rj;rj=rj-1;rj-1=r0; i+; 4.设一个一维数组An中存储了n个互不相同的整数, 且这些整数的值都在0到n-1之间, 即A中存储了从0到n-1这n个整数。试编写一算法将A排序, 结果存放在数组Bn中, 要求算法的时间复杂性为O(n)。 解: 实现本题功能的算法如下: void sort(int An,int Bn) int i; for(i=0;ip-key) p=p-link; else if(x=p-key) return p; else p=NULL; return p; 虽然链表中的结点是按递增顺序排列的, 可是其存储结构为单链表, 查找结点时只能从头指针开始逐步进行搜索, 因此不能用折半查找。2.如果线性表中各结点查找概率不等, 则能够使用下面的策略提高顺序表的查找效率: 如果找到指定的结点, 则将该结点和其前趋( 若存在) 结点交换, 使得经常被查找的结点尽量位于表的前端。试对线性表的顺序存储结构和链式存储结构写出实现上述策略的顺序查找算法( 注意查找时必须从表头开始向后扫描) 。 解: 采用顺序存储结构的算法如下, 设记录存储在线性表的1n单元中。如果查找成功, 返回关键字为k的记录在线性表中的位置, 如果失败则返回0。 int seqsearch(sqlist r,int n,int k) int i,j; i=1; while(ri.key!=k) & (i=n) i+; if(ikey=k) return(head); else node *p,*q; int x;p=head; q=head-link; while(q!=NULL & q-key!=k) p=q; q=q-link; if(q!=NULL) x=p-key; p-key=q-key; q-key=x; q=p; return(q); 3. 试设计一个在用开放地址法解决冲突的散列表上删除一个指定结点的算法。解: 本题的算法思想是: 首先计算要删除的关键字为k的记录所在的位置, 将其置为空( 即删除) , 然后利用线性探测法查找是否有与k发生冲突而存储到下一地址的记录, 如果有则将记录移到原来k所在的位置, 直至表中没有与k冲突的记录为止。实现本题功能的算法如下: void delete(sqlist r,int n,int k) int h,h0,h1; h=k%n; while(rh.key!=k) h=(h+1)%n; rh=NULL;h0=h;h1=(h+1)%n;while(h1!=h) while(rh1.key%n!=h) h1=(h1+1)%n; rh0=rh1; rh1=NULL; h0=h1; h1=(h1+1)%n; 4. 设给定的散列表存储空间为H1m, 每个单元可存放一个记录, Hi(1im)的初始值为零, 选取散列函数为H(R.key), 其中key为记录R的关键字, 解决冲突方法为线性探测法, 编写一个函数将某记录R填入到散列表H中。解: 本题的算法思想: 先计算地址H(R.key), 如果没有冲突, 则直接填入; 否则利用线性探测法求出下一地址, 直到找到一个为零的地址, 然后填入。实现本题功能的函数如下: void insert(record H,int m,record R) int i; i=H(R.key); if(Hi=NULL) Hi=R; else while(Hi!=NULL) i=(i+1)%(m+1); Hi=R; 第七章一、 基本知识题1. 图的逻辑结构特点是什么? 什么是无向图和有向图? 什么是子图? 什么是网络? 答: 图是比树更为复杂的一种非线性数据结构, 在图结构中, 每个结点都能够和其它任何结点相连接。 无向图: 对于一个图G, 若边集合E( G) 为无向边的集合, 则称该图为无向图。 有向图: 对于一个图G, 若边集合E( G) 为有向边的集合, 则称该图为有向图。 子图: 设有两个图G =(V,E)和G=(V,E), 若V(G)是V(G)的子集, 且E(G)是E(G)的子集, 则称G是G的子图(Subgraph)。网络: 有些图, 对应每条边有一相应的数值, 这个数值叫做该边的权。边上带权的图称为带权图, 也称为网络。2. 什么是顶点的度? 什么是路径? 什么是连通图和非连通图? 什么是非连通图的连通分量? 答: 顶点的度: 图中与每个顶点相连的边数, 叫该顶点的度。 在一个图中, 若从某顶点Vp出发, 沿一些边经过顶点V1,V2,Vm到达, Vq, 则称顶点序列(Vp, V1,V2,Vm, Vq)为从Vp到Vq的路径。 在无向图中, 如果从顶点Vi到顶点Vj之间有路径, 则称这两个顶点是连通的。如果图中任意一对顶点都是连通的, 则称此图是连通图。 非连通图的连通分量: 非连通图的每一个连通的部分叫连通分量。3. 给出图6.25所示的无向图G的邻接矩阵和邻接表两种存储结构。答: 图G所对应的邻接矩阵如下: 图G所对应的邻接表如下: 图254. 假设图的顶点是A、 B请根据下面的邻接矩阵画出相应的无向图或有向图。 答: (a)所对应的无向图如下图(a)所示, (b)所对应的有向图如下图(b)所示: 5.5. 分别给出图6.26所示G图的深度优先搜索和广度优先搜索得到的顶点访问序列。图26 答: 深度优先搜索得到的顶点访问序列: 0、 1、 3、 7、 8、 4、 9、 5、 6、 2; 广度优先搜索得到的顶点访问序列: 0、 1、 2、 3、 4、 5、 6、 7、 8、 9。6. 应用prim算法求图6.27所示带权连通图的最小生成树。答: 该图的最小生成树如下: 图277. 写出图6.28所示有向图的拓朴排序序列答: 该有向图的拓朴排序序列为: 3、 1、 4、 5、 2、 6。二、 算法设计题图28二、 算法设计题答案1. 如图6.29所示图G, 试给出其对应的邻接表, 并写出深度优先算法。解: 该图对应的邻接表如下: 深度优先算法: void dfsgraph(adjlist adj, int n) /*深度优先遍历整个图*/ int i; for(i=1;i=n;i+) visitedi=0; for(i=1;i=n;i+) if(!visitedi) dfs(adj,i);void dfs(adjlist adj,int v) /*以v为出发点, 对图进行dfs遍历*/ struct edgenode *p; visitedv=1; printf(%d,v); p=adjvlink; while(p!=NULL) if(visitedpadjvex=0) dfs(adjlist,padjvex); p=pnext; 2. 如图6.29所示图G, 试给出其对应的邻接矩阵, 并写出广度优先算法。解: 该图对应的邻接矩阵如下: 广度优先算法: void bfsgraph(int adjarraynn,int n) /*广度优先遍历整个图*/ int i; for(i=0;in;i+) visitedi=0; for(i=0;in;i+)图29 if(!visitedi)bfs(adjarray,i); void bfs(int adjarray,int v) /*以v为出发点, 对图进行bfs遍历*/ int i,j; queue q; printf(%d,v); visitedv=1; enqueue(&q,v); while(!queueemty(&q) i=dequeue(&q);for(j=0;jn;j+) if(adjarrayij=1 & !visitedj) printf(%d,j); visitedj=1; enqueue(&q,j); 3. 编写一个函数经过与用户交互建立一个有向图的邻接表。解: 实现本题功能的算法如下: void creategraph(adjlist g) int e,i,s,d,n; struct edgenode *p ; printf(请输入结点数(n)和边数(e):n); scanf(%d,%d,&n,&e); for(i=1;i=n;i+) printf(n请输入第%d个顶点信息: ,i); scanf(%c,&gi.data);gi.link=NULL; for(i=1;i=e;i+) printf(n请输入第%d条边起点序号, 终点序号: ,i); scanf(%d,%d,&s,&d); p=(struct edgenode *)malloc(sizeof(edgenode); padjvex=d; pnext=gs.link; gs.link=p;4. 编写一个无向图的邻接矩阵转换成邻接表的算法。解: 本题的算法思想是: 逐个扫描邻接矩阵的各个元素, 如第i行第j列的元素为1, 则相应的邻接表的第i个单链表上增加一个j结点。实现本题功能的算法如下: void transform(int adjarraynn,adjlist adj) int i,j; edgenode *p; for(i=0;in;i+) adji.data=i;adji.link=NULL; for(i=0;in;i+) for(j=0;jnext; return degree; void printout(adjlist adj,int n) int i,degree; printf(The outdegrees are:n); for(i=0;in;i+) degree=outdegree(adj,i); printf(%d,%d),i,degree); (2)本题的算法思想是: 计算出整个邻接表中所具有的结点为i的结点数, 这就是i顶点的入度。求顶点的入度数的算法: int indegree(adjlist adj,int n,int v) int i,j,degree; edgenode *p; for(i=0;iadjvex=v)degree+; p=p-next; return degree; void printin(adjlist adj,int n) int i,degree; printf(The indegrees are:n); for(i=0;in;i+) degree=indegree(adj,n,i); printf(%d,%d),i,degree); (3)求最大出度的算法: void maxoutdegree(adjlist adj,int n)int maxdegree=0,maxv=0, degree, i;for(i=0;imaxdegree) maxdegree=degree; maxv=i; printf(maxoutdegree = %d, maxvertex = %d,maxdegree,maxv);(4)求出度数为0的顶点数的算法: int outzero(adjlist adj,int n)int num=0,i;for(i=0;in;i+) if(outdegree(adj,i)=0) num+;return num;第六章一、 基础知识题1. 就如图5.21所示的树回答下面问题: 1) 哪个是根结点? 2) 哪些是叶子结点? 3) 哪个是E的父结点? 4) 哪些是E的子孙结点? 5) 哪些是E的兄弟结点? 哪些是C的兄弟结点? 6) 结点B和结点I的层数分别是多少? 7) 树的深度是多少? 8) 以结点G为根的子树的深度是多少? 9) 树的度是多少? 答: 1) A是根结点2) D、 H、 I、 J、 F、 G是叶子结点3) B是E的父结点4) H、 I、 J是E的子孙结点5) D是E的兄弟结点, B是C的兄弟结点6) B的层数是2, I的层数是47) 树的深度是48) 以结点G为根的子树的深度是19) 树的度是3 2.分别画出含3个结点的树与二叉树的所有不同形态。答: 3个结点的树: 3个结点的二叉树: 3. 高度为h的完全二叉树至少有多少个结点? 最多有多少个结点? 答: 高度为h的完全二叉树至少有个结点, 最多有个结点。4. 采用顺序存储方法和链式存储方法分别画出图5.22所示二叉树的存储结构。答: 该二叉树的顺序存储: 该二叉树的链式存储: 5. 分别写出图5.22所示二叉树的前序、 中序和后序遍历序列。图22答: 先序遍历序列: 1、 2、 4、 7、 3、 5、 8、 6、 9中序遍历序列: 7、 4、 2、 1、 8、 5、 3、 6、 9后序遍历序列: 7、 4、 2、 8、 5、 9、 6、 3、 1 6.若二叉树中各结点值均不相同。 1)已知一个二叉树的中序和后序遍历序列分别为GDHBAECIF和GHDBEIFCA, 请画出此二叉树。 2)已知一个二叉树的前序和中序分别为ABCDEFGH和BDCEAFHG, 请画出此二叉树。答: 7. 一个二叉树如图5.23所示,分别写出其前序、 中序、 后序的遍历序列。答: 先序遍历序列: A、 B、 D、 E、 F、 C、 G中序遍历序列: D、 F、 E、 B、 A、 G、 C后序遍历序列: F、 E、 D、 B、 G、 C、 A 8.输入一个正整数序列55,34,18,88,119,11,76,9,97,99,46, 试构造一个二叉排序树。9. 有一份电文中共使用5个字符: a、 b、 c、 d、 e, 它们的出现频率依次为5、 2、 1、 6、 4。试画出对应的哈夫曼树, 并求出每个字符的哈夫曼编码。第8题各字符对应的哈夫曼编码如