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

《人武学院《数据结构》课后习题答案及期末综合练习》由会员分享，可在线阅读，更多相关《人武学院《数据结构》课后习题答案及期末综合练习（35页珍藏版）》请在装配图网上搜索。

1、第十章内部排序一、基本知识题答案1. 排序：将一组杂乱无序的数据按一定的规律顺次排列起来叫做排序。 内部排序：数据存储在内存中，并在内存中加以处理的排序方法叫内部排序。 堆：堆是一个完全二叉树，它的每个结点对应于原始数据的一个元素，且规定如果一个结点有儿子结点，此结点数据必须大于或等于其儿子结点数据。稳定排序：一种排序方法，若排序后具有相同关键字的记录仍维持原来的相对次序，则称之为稳定的，否则称为不稳定的。2. 回答下面问题 (1) 5000个无序的数据，希望用最快速度挑选出其中前10个最大的元素，在快速排序、堆排序、归并排序和基数排序中采用哪种方法最好？为什么？ (2) 大多数排序算法都有哪

2、两个基本操作？ 答：(1)采用堆排序最好。 因为以上几种算法中，快速排序、归并排序和基数排序都是在排序结束后才能确定数据元素的全部顺序，而无法知道排序过程中部分元素的有序性。堆排序则每次输出一个最大（或最小）的元素，然后对堆进行调整，保证堆顶的元素总是余下元素中最大（或最小）的。根据题意，只要选取前10个最大的元素，故采用堆排序方法是合适的。 (2)两个基本操作：比较两个关键字的大小、改变指向记录的指针或移动记录本身。3. 3. 已知序列17，25，55，43，3，32，78，67，91，请给出采用冒泡排序法对该序列作递增排序时每一趟的结果。 答：采用冒泡排序法排序时的各趟结果如下：初始：17

3、，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，

4、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 57

5、2，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，25

6、8，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

7、第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趟：

8、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) whil

9、e(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. 试设计一个算法实现双向冒泡

10、排序。（双向冒泡排序就是在排序的过程中交替改变扫描方向。）解：实现本题功能的算法如下： 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个整数。试编写一算法将

11、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.如果线性表中各结点查找概率不等，则可以使用下面的策略提高顺序表的查找效率：如果找到指定的结点，则将该结点和其前趋（若存在）结点交换，使得经常被查找的结点尽量位于表的前端

12、。试对线性表的顺序存储结构和链式存储结构写出实现上述策略的顺序查找算法（注意查找时必须从表头开始向后扫描）。 解：采用顺序存储结构的算法如下，设记录存储在线性表的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

13、; 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)

14、 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)，如果没有冲突，则直接填入；否则利用线性探测法求出下一地址，直到找到一个为零的地址，然后填入。实

15、现本题功能的函数如下： 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）为有向边的集合，则称该图为有向图。 子图：

16、设有两个图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之间有路径，则称这两个顶点是连通的。如果

17、图中任意一对顶点都是连通的，则称此图是连通图。 非连通图的连通分量：非连通图的每一个连通的部分叫连通分量。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、

18、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) d

19、fs(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; fo

20、r(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)

21、; 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=(

22、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+)

23、 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

24、=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=

25、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;ileft,num); num=CountNode(t-right,num); return num;求二叉树叶子结点总数的算法如下：int CountLeaf(btree *t,int num) /*num初值为0*/ if(t!=NULL) if(t-left=NULL & t-right=NULL) num+;

26、 num=CountLeaf(t-left,num); num=CountLeaf(t-right,num); return num;2. 2. 一个二叉树以链式结构存储，写出在二叉树中查找值为x的结点的算法。解：本题可以用先序、中序和后序遍历中的任意一种遍历，只要将遍历算法中的访问根结点改为判断其值是否等于x。下面是用中序遍历求解的算法，函数返回值为x的结点的地址，若没有找到则返回空。 btree *search(btree *t,int x,btree p) /*p的初值为NULL*/ if(t!=NULL) p=search(t-left,x,p); if(t-data=x)p=t; /

27、*找到x的地址放在p中*/ p=search(t-right,x,p); return p;3. 设计一个算法将一个以链式存储结构的二叉树，按顺序方式存储到一维数组中。解：这是一个递归算法，如下： void create(btree *t,int tree,int i) if(t!=NULL) treei=t-data; create(t-left,tree,2*i); create(t-right,tree,2*i+1); 4. 假设二叉排序树t的各元素值均不相同，设计一个算法按递增次序打印各元素值。解：按中序序列遍历二叉排序树即按递增次序遍历，所以递增打印二叉排序树各元素值的函数如下： v

28、oid inorder(btree *t) if(t!=NULL) inorder(t-left); printf(%d,t-data); inorder(t-right); 5. 已知一个中序线索二叉树，试编写中序遍历的非递归算法。解：在中序线索二叉树中进行非递归中序遍历，只要从头结点出发，反复找到结点的后继，直至结束即可。在中序线索二叉树中求结点后继的算法如下： tbtree *succ(tbtree *p) btree *q; if(p-rtag=1) return (p-right);else q=p-right; while(q-ltag=0) q=q-left; return(q)

29、;由此得到中序遍历线索二叉树的非递归算法如下： void thinorder(tbtree *p) if(p!=NULL) while(p-ltag=0) p=p-left; do printf(%d,p-data); p=succ(p); while(p!=NULL);第五章A1020采用列为主序存储,每个元素占1个单元,A00的地址为200,则A612的地址是多少? 3262. 稀疏矩阵mn采用三元组顺序表存储结构,非零元个数tu满足什么条件时,该存储结构才有意义?tum*n/33. 二维数组A10.205.10采用行为主序存储,每个元素占4个单元,A105的地址为1000,则A189的地

30、址是多少?(1208)4. 稀疏矩阵的三元组顺序表存储结构是随机存储结构吗?为什么?(不是)5. 广义表(a,b,c,d)的表头和表尾分别是什么?（(a,b,c,d);空表）6. 广义表(a),(b),c),(d)的长度和深度分别是多少? （3，4）第一章数据物理结构 算法 二、简答 一、名词解释数据：就是一切能够由计算机接受和处理的对象。数据项：是数据的不可分割的最小单位，在有些场合下，数据项又称为字段或域。数据元素：是数据的基本单位，在程序中作为一个整体加以考虑和处理，也称为元素、顶点或记录。它可以由若干个数据项组成。数据结构：指的是数据之间的相互关系，即数据的组织形式，它包括数据的逻辑结

31、构、数据的存储结构和数据的运算三个方面的内容。数据逻辑结构：是指数据元素之间的逻辑关系，是从逻辑上描述数据，与数据的存储无关，独立于计算机。数据物理结构：是指数据元素及其关系在计算机存储器内的表示，是数据的逻辑结构用计算机语言的实现，是依赖于计算机语言的。算法：是对特定问题求解步骤的一种描述。它是一个有穷的规则序列，这些规则决定了解决某一特定问题的一系列运算。由此问题相关的一定输入，计算机依照这些规则进行计算和处理，经过有限的计算步骤后能得到一定的输出。算法的时间复杂性：是该算法的时间耗费，它是该算法所求解问题规模n的函数。当n趋向无穷大时，我们把时间复杂性T(n)的数量级称为算法的渐进时间复

32、杂性。二、简答题1. 算法分析的目的是什么？ 答：对算法进行分析的目的有两个：第一个目的是可以从解决同一问题的不同算法中区分相对优劣，选出较为适用的一种；第二个目的是有助于设计人员考虑对现有算法进行改进或设计出新的算法。2. 什么是算法的最坏和平均时间复杂性？ 答：算法的最坏时间复杂性是研究各种输入中运算最慢的一种情况下的运算时间；平均时间复杂性是研究同样的n值时各种可能的输入，取它们运算时间的平均值。三、答案1三、分析下列算法的时间复杂性: 1sum=0; for (i=1;i=n;i+) sum=sum+i; 答：该程序段的时间复杂性为T(n)=O(n)。22i=1; while(i=n)

33、 i=i*10; 1*10 for(j=0;jn;j+) 答：该程序段的时间复杂性T(n)=O(log10n)。33sum=0; for(i=0;inext-next（表中带头结点）。这会使操作变的更加容易。 4. 4. 写出在循环双链表中的p所指结点之后插入一个s所指结点答： s-prior=p; s-next=p-next; p-next-prior=s; p-next=s; 5.5. 写出在单链表中的p所指结点之前插入一个s所指结点的操作。 答： s-next=p-next; p-next=s; temp=p-data; p-data=s-data; s-data=temp; 6. 6.

34、 请利用链表来表示下面一元多项式 A(x)=4*x11+9*x8+11*x3+8*x+7答：多项式A(x)用链表表示如下：head_A-4,11-9,8-.11,3-8,1-7,0二、算法设计题答案1. 1. 有一个有n个结点的单链表，设计一个函数将第i-1个结点与第i个结点互换，但指针不变。解：本题的算法思想是：要使结点互换而指针不变，只要将两个结点的数据进行交换即可。实现本题功能的函数如下： void exchange(node *head,int i,n) node *p,*q; int data; if(in) printf(error!n); else p=head; for(int

35、 j=1;jnext; q=p-next; data=q-data; q-data=p-data; p-data=data; 2. 2. 设计一个函数，查找单链表中数值为x的结点。 解：实现本题功能的函数如下： void search(node *head,int x) node *p; p=head; while(p-data!=x & p!=NULL) p=p-next; if(p!=NULL) printf(结点找到了！n); else printf(结点未找到！n); 3. . 已知一个单链表，编写一个删除其值为x的结点的前趋结点的算法。解：本题的算法思想是：先找到值为x的结点*p和它的前趋结点*q，要删除*q，只需把*p的值x放到*q的值域中，再删除结点*p即可。实现本题功能的函数如下： void delete(node *head,int x) node *p,*q; q=head; p=head-next; while(p!=NULL) & (p-data!=x) q=p; p=p-next; if(p=NULL) printf(未找到x！n); else if(q=head) printf(x为第一个结点，无前趋！n); else q-data=x; q-next=p-