• / 153
  • 下载费用:10 金币  

第十章 习题解答.ppt

关 键 词:
第十章 习题解答.ppt
资源描述:
数据结构,第十章 习题解答,第十章 习题解答,第十章 习题解答,10.1 第1章习题解答 10.2 第2章习题解答 10.3 第3章习题解答 10.4 第4章习题解答 10.5 第5章习题解答 10.6 第6章习题解答 10.7 第7章习题解答 10.8 第8章习题解答,第十章 习题解答,第一章习题解答,一、名词解释答案 数据:就是一切能够由计算机接受和处理的对象。 数据项:是数据的不可分割的最小单位,在有些场合下,数据项又称为字段或域。 数据元素:是数据的基本单位,在程序中作为一个整体加以考虑和处理,也称为元素、顶点或记录。它可以由若干个数据项组成。 数据结构:指的是数据之间的相互关系,即数据的组织形式,它包括数据的逻辑结构、数据的存储结构和数据的运算三个方面的内容。 数据逻辑结构:是指数据元素之间的逻辑关系,是从逻辑上描述数据,与数据的存储无关,独立于计算机。,第十章 习题解答,数据物理结构:是指数据元素及其关系在计算机存储器内的表示,是数据的逻辑结构用计算机语言的实现,是依赖于计算机语言的。 算法:是对特定问题求解步骤的一种描述。它是一个有穷的规则序列,这些规则决定了解决某一特定问题的一系列运算。由此问题相关的一定输入,计算机依照这些规则进行计算和处理,经过有限的计算步骤后能得到一定的输出。 算法的时间复杂性:是该算法的时间耗费,它是该算法所求解问题规模n的函数。当n趋向无穷大时,我们把时间复杂性T(n)的数量级称为算法的渐进时间复杂性。,第十章 习题解答,二、简答题答案 1. 答:对算法进行分析的目的有两个:第一个目的是可以从解决同一问题的不同算法中区分相对优劣,选出较为适用的一种;第二个目的是有助于设计人员考虑对现有算法进行改进或设计出新的算法。 2. 答:算法的最坏时间复杂性是研究各种输入中运算最慢的一种情况下的运算时间;平均时间复杂性是研究同样的n值时各种可能的输入,取它们运算时间的平均值。,第十章 习题解答,三、答案 1.答:该程序段的时间复杂性为T(n)=O(n)。 2.答:该程序段的时间复杂性T(n)=O(log10n)。 3.答:该程序段的时间复杂性T(n)=O(n2)。,返回,第十章 习题解答,第二章习题解答,一、基本知识题答案 1. 答:数组是由一些单元组成的,每个单元对应着一组下标值和一个数据元素。数组的主要特点有:(1)同一数组中各个元素必须是同一数据类型;(2)可以用下标值随机的访问数组的任意一个元素。 2. 答:线性表是由有限数目的相同类型元素组成的序列。表中的数据元素,除了第一个和最后一个以外,都有一个且只有一个前驱元素,同时也都有一个且只有一个后继元素;第一个元素只有一个后继元素而无前驱元素;最后一个元素只有一个前驱元素而无后继元素。线性表的元素个数n称为这个表的长度,当n=0时,这个表叫做空表。,第十章 习题解答,线性表的主要运算包括: (1) 求线性表的长度n; (2) 在第i个数据元素前面插入一个新的数据元素; (3) 删除第i个数据元素; (4) 存取或更新线性表第i个元素; (5) 将两个或两个以上的线性表合并成一个线性表; (6) 将一个线性表拆成多个线性表; (7) 将线性表中个数据元素按某个域值(如关键字)递增或递减的顺序重新排列; (8) 在线性表中查找满足某种条件的数据元素;,第十章 习题解答,3. 答:栈是限定在表的一端进行插入或删除操作的线性表;队列是元素的添加在表的一端进行,而元素的删除在表的另一端进行的线性表;栈的特点是后进先出,队列的特点是先进先出。 4. 答:栈和队列都是线性表,但是是受限的线性表,对插入、删除运算加以限制。栈是只允许在一端进行插入、删除运算,因而是后进先出表;而队列是只允许在一端进行插入、另一端进行删除运算,因而是先进先出表。 5. 答:栈的入栈、出栈操作均在栈顶进行,栈顶指针指向栈顶元素处。入栈操作先将栈顶指针加1,然后将入栈元素放到栈顶指针所指示的位置上。出栈操作先从栈顶指针指向位置取值,然后将栈顶指针减1。,第十章 习题解答,6. 答:在循环队列中,设队首指针指向队首元素,队尾指针指向队尾元素后的一个空闲元素。在队列不满时,可执行入队操作,此时先送值到队尾指针指向的空闲元素,队尾指针再加1(要取模)。在队列不空时,可执行出队操作,此时先从队首指针指向处取值,队首指针再减1(要取模)。 7. 答:栈结构主要应用在下列三个方面:①算术表达式的求值;②子程序的调用与返回;③递归函数的求值。队列结构主要应用在需要“排队”的事件中,例如操作系统中的作业调度等。 8. 答:数组A有8个元素,数组B有4*7=28个元素,数组C有5*8*6=240个元素。,第十章 习题解答,二 、算法设计题答案 1. 解:将该线性表逆序可以通过将A[0]与A[n-1]、A[1]与A[n-2]…两两交换来完成。注意互相交换的A[i]与A[j]的数组下标的关系i+j=n-1,i从0到n/2-1变化。实现本题功能的函数如下:,第十章 习题解答,void reverse(){int i,j,temp;for(i=0;i=n/2-1;i++){j=n-1-i;temp=A[i];A[i]=A[j];A[j]=temp;}},第十章 习题解答,2. 解:用一整型变量top表示栈顶指针,top为0时表示栈为空。如果栈不空,则从stack[1]开始存放元素。实现本题功能的函数如下:入栈算法:void Push(EleType x){ if((top+length)n)printf(“上溢出\n“);else {if(top==0) /*为空栈*/,第十章 习题解答,{top++;stack[top]=x;}else{top=top+length;stack[top]=x;}} },第十章 习题解答,出栈算法:void Pop(EleType x){if(top==0)printf(“为空栈\n“);else{if(top==1){x=stack[top];,第十章 习题解答,top--;}else{x=stack[top];top=top-length;}} },第十章 习题解答,3. 解:设表达式在字符数组a[ ]中,使用一堆栈S来帮助判断。实现本题功能的函数如下:int correct(char a[]){Stack S;InitStack(S);for(i=0;istrlen(a);i++)if(a[i]=='(')Push(S,'(');else if (a[i]==')'),第十章 习题解答,{if(StackEmpty(S))return 0;elsePop(S);}if(StackEmpty(S))return 1; /*配对正确*/else return 0; /*配对错误*/},第十章 习题解答,4. 解:实现本题功能的函数如下:void travel(Queue, int front,rear){int i;for(i=front;i=rear;i++){printf(“%4d“,Queue[i]);} },第十章 习题解答,5. 解:用一个循环数组Queue[0,n-1]表示该循环队列,头指针为front,计数器count用来记录队列中结点的个数。入队算法如下:void enqueue(int x){int temp;if(count==n)printf(“队列上溢出\n“);else,第十章 习题解答,{count++;temp = (front+count)%n;Queue[temp]=x;} } 出队算法如下: int dequeue() {int temp;,第十章 习题解答,if(count==0)printf(“队列下溢出\n“);else{temp=Queue[front];front=(front+1)%n;count--;return temp;} },返回,第十章 习题解答,第三章习题解答,一、基本知识题答案1. 答:顺序表用结点物理位置的相邻性来反映结点间的逻辑关系,其优点是:节省存储、随机存取,当表长变化较小,主要操作是进行查找时,宜采用顺序表。链表用附加的指针来反映结点间的逻辑关系,插入和删除操作相对比较方便,当表长变化较大,主要操作是进行插入和删除时,宜采用链表。,第十章 习题解答,2. 答:双链表比单链表多增加了一个指针域以指向结点的直接前趋,它是一种对称结构,因此在已知某个结点之前或之后插入一个新结点、删除该结点或其直接后继都同样方便,操作的时间复杂度为O(1);而单链表是单向结构,对于找一个结点的直接前趋的操作要从开始结点找起,其时间复杂度为O(n)。 3. 答:由于对表的操作常常在表的两端进行,所以对单循环链表,当知道尾指针rear后,其另一端的头指针是rear-next-next(表中带头结点)。这会使操作变的更加容易。,第十章 习题解答,4. 答:s-prior=p;s-next=p-next;p-next-prior=s;p-next=s; 5. 答:s-next=p-next;p-next=s;temp=p-data;p-data=s-data;s-data=temp;,第十章 习题解答,6. 答:多项式A(x)用链表表示如下:,第十章 习题解答,二、算法设计题答案 1. 解:本题的算法思想是:要使结点互换而指针不变,只要将两个结点的数据进行交换即可。实现本题功能的函数如下:void exchange(node *head,int i,n){node *p,*q;int data;if(in)printf(“error!\n“);,第十章 习题解答,else{p=head;for(int j=1;jnext;q=p-next;data=q-data;q-data=p-data;p-data=data;} },第十章 习题解答,2. 解:实现本题功能的函数如下:void search(node *head,int x){node *p;p=head;while(p-data!=x },第十章 习题解答,3. 解:本题的算法思想是:先找到值为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) },第十章 习题解答,if(p==NULL)printf(“未找到x!\n“);else if(q==head)printf(“x为第一个结点,无前趋!\n“);else{q-data=x;q-next=p-next;free(p);}},第十章 习题解答,4. 解:实现本题功能的函数如下:void deletelength(node *head,int i,int length){ node *p,*q;int j;if(i==1)for(j=1;jnext;free(p);}else,第十章 习题解答,{ p=head;for(j=1;jnext;/*p指向要删除的结点的前一个结点*/for(j=1;jnext; /*q指向要删除的结点*/p-next=q-next;free(q);} } },第十章 习题解答,5. 解:本题算法的思想是:先建立一个待插入的结点,然后依次与链表中的各结点的数据域比较大小,找到插入该结点的位置,然后插入该结点。实现本题功能的函数如下:void insert(node *head,int x){node *s,*p,*q;s=(node *)malloc(sizeof(node)); /*建立一个待插入的结点*/s-data=x;s-next=NULL;,第十章 习题解答,if(head==NULL||xdata) /*若单链表为空或x小于第一个结点data域*/ { s-next=head; /*插入到表头后面*/head=s;}else{q=head;p=q-next;while(p!=NULL && xp-data),第十章 习题解答,{q=p;p=p-next;}s-next=p; /*插入结点*/q-next=s;} },第十章 习题解答,6. 解:本题算法的思想是依次查找原单链表(其头指针为head1)中的每个结点,对每个结点复制一个新结点并链接到新的单链表(其头指针为head2)中。实现本题功能的函数如下:void copy(node *head1,node *head2){node *p,*q,*s;head2=(node *)malloc(sizeof(node));q=head2;q-data=head1-data;,第十章 习题解答,p=head1-next;while(p!=NULL){s=(node *)malloc(sizeof(node));s-data=p-data;q-next=s;q=s;p=p-next;}q-next=NULL; },第十章 习题解答,7. 解:本题的算法思想是:在原单链表一半处将其分开,第5个结点的next域置为空,为第一个单链表的表尾。第二个单链表的表头指针指向原单链表的第6个结点。实现本题功能的函数如下,函数返回生成的第二个单链表的表头指针,第一个单链表仍然使用原单链表的表头指针。node* divide(node *head1){node *head2,*prior;head2=head1;,第十章 习题解答,for(int i=1;inext;}prior-next=NULL;return head2; },第十章 习题解答,8. 解:本题算法的思想是将第一个链表中的所有偶数序号的结点删除,同时把这些结点链接起来构成第二个单链表。实现本题功能的函数如下:void split(node* head1,node * head2){node *temp,*odd,*even;odd=head1;head2=head1-next;temp=head2;,第十章 习题解答,while(odd!=NULL },第十章 习题解答,9. 解:本题的算法思想是:因为是单循环链表,所以只要另设一指针q指向p用来帮助判断是否已经遍历一遍即可。实现本题功能的函数如下:void travel(node *p){ node *q=p;while(q-next!=p){printf(“%4d“,q-data);q=q-next;}printf(“%4d“,q-data);},第十章 习题解答,10. 解:本题算法的思想是:从头到尾扫描该循环链表,将第一个结点的next域置为NULL,将第二个结点的next域指向第一个结点,如此直到最后一个结点,便用head指向它。由于是循环链表,所以判定最后一个结点时不能用p-next=NULL作为条件,而是用q指向第一个结点,以p!=q作为条件。实现本题功能的函数如下:void invert(node *head){node *p,*q,*r;p=head;,第十章 习题解答,q=p-next;while(p!=q){r=head;while(r-next!=p)r=r-next;p-next=r;p=p-next;}q-next=head; },第十章 习题解答,11. 解:能。本题的算法思想是:分别从p开始沿着next以及prior向右、向左扫描直至各自的链为空即可遍历整个链表。实现本题功能的函数如下:void travellist(node *p){ node *q;q=p;while(q!=NULL){printf(“%4d“,q-data);q=q-next;},第十章 习题解答,q=p-prior;while(q!=NULL){printf(“%4d“,q-data);q=q-prior;} },第十章 习题解答,12. 解:实现本题功能的算法如下:void deleteprior(node *p){node *pri,q;pri=p-prior;q=pri-prior;if(pri==p)printf(“p结点无前趋!\n“);,第十章 习题解答,else {q-next=pri-next;p-prior=pri-prior;free(prior);} },返回,第十章 习题解答,第四章习题解答,一、基本知识题答案 1. 答:空串是指长度为零的串;空格串是指包含一个或多个空白字符“ ”(空格键)的字符串。 2. 答:B串是A串的子串,其起始点是A串的第9个字符。 3. 答:串是一种特殊的线性表,其特殊性体现在串的数据元素是一个字符。 4. 答:串的两种最基本的存储方式为顺序存储方式和链式存储方式。 5. 答:两个串相等的充分必要条件是两个串的长度相等且对应位置的字符相同。,第十章 习题解答,二、算法设计题答案 1. 解:本题的算法思想是:从头到尾扫描串,对于值为ch的元素采用移动的方式进行删除。其函数如下:void delelech(orderstring *r,char ch){int i,j;for(i=0;ilen;i++),第十章 习题解答,if(r-vec[i]==ch){for(j=i;jlen;j++)r-vec[j]=r-vec[j+1];r-len=r-len-1;} },第十章 习题解答,2. 解:本题的算法思想是:先判定串中要删除的内容是否存在,若存在则将i+j-1之后的字符前移j个位置。其函数如下:void deletesub(orderstring *r,int i,int j){int k;if(i+j-1r-len)printf(“出界\n“);,第十章 习题解答,else{for(k=i+j;klen;k++)r-vec[k-j]=r-vec[k]; r-len=r-len-j;} },第十章 习题解答,3. 解:本题的算法思想是:设两个变量分别指向串首及串尾,将它们所指的数据互换,然后将它们逐渐向中间移动直至相遇即可。实现本题功能的函数如下:void inverse(orderstring *r){int i,j;char temp,i=0;j=r-len-1;,第十章 习题解答,{temp=r-vec[i];r-vec[i]=r-vec[j];r-vec[j]=temp;i++;j--;} },第十章 习题解答,4. 解:本题采用的算法是:逐一扫描r的每个结点,对于每个数据域为c的结点修改其元素值为s。其对应的函数如下:void replace(linkstring *r,char c,char s);{linkstring *p;p=r;,第十章 习题解答,while(p!=NULL){if(p-data=='c')p-data='s';p=p-link;} },第十章 习题解答,5. 解:实现本题功能的函数如下:void insert(linkstring *A,linkstring *B,int k){int i=1;linkstring *p,*q;p=A;while(ilink;i++;},第十章 习题解答,if(p==NULL)printf(“k值错!\n“);else{q=B;while(q!=NULL)q=q-link;q-link=p-link;p-link=B;} },返回,第十章 习题解答,第五章习题解答,一、基本知识题答案 1. 答: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的层数是4 7)树的深度是4 8)以结点G为根的子树的深度是1 9)树的度是3,第十章 习题解答,2. 答:3个结点的树:,第十章 习题解答,3个结点的二叉树:,第十章 习题解答,3. 答:高度为h的完全二叉树至少有个结点,最多有个结点。 4. 答:该二叉树的顺序存储:,第十章 习题解答,该二叉树的链式存储:,第十章 习题解答,5. 答:先序遍历序列: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),(2),第十章 习题解答,7.答:先序遍历序列:A、B、D、E、F、C、G 中序遍历序列:D、F、E、B、A、G、C 后序遍历序列:F、E、D、B、G、C、A,第十章 习题解答,8.答:二叉排序树如下:,第十章 习题解答,9. 答:本题对应的对应的哈夫曼树如下:,各字符对应的哈夫曼编码如下:a: 10, b: 001, c: 000, d: 11, e: 01。,第十章 习题解答,二、算法设计题答案 1. 解:求二叉树结点总数的算法如下:int CountNode(btree *t,int num) /*num初值为0*/ { if(t!=NULL){ num++;num=CountNode(t-left,num);num=CountNode(t-right,num);}return num; },第十章 习题解答,求二叉树叶子结点总数的算法如下: int CountLeaf(btree *t,int num) /*num初值为0*/ { if(t!=NULL){ if(t-left==NULL },第十章 习题解答,2. 解:本题可以用先序、中序和后序遍历中的任意一种遍历,只要将遍历算法中的访问根结点改为判断其值是否等于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; /*找到x的地址放在p中*/p=search(t-right,x,p);}return p; },第十章 习题解答,3. 解:这是一个递归算法,如下:void create(btree *t,int tree[],int i){if(t!=NULL){tree[i]=t-data;create(t-left,tree,2*i);create(t-right,tree,2*i+1);} },第十章 习题解答,4. 解:按中序序列遍历二叉排序树即按递增次序遍历,所以递增打印二叉排序树各元素值的函数如下:void 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);} },第十章 习题解答,由此得到中序遍历线索二叉树的非递归算法如下: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);} },返回,第十章 习题解答,第六章习题解答,一、基本知识题答案 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. 答:图G所对应的邻接矩阵如下:,第十章 习题解答,图G所对应的邻接表如下:,第十章 习题解答,4. 答:(a)所对应的无向图如下图(a)所示,(b)所对应的有向图如下图(b)所示:,(a),(b),第十章 习题解答,5. 答:深度优先搜索得到的顶点访问序列:0、1、3、7、8、4、9、5、6、2;广度优先搜索得到的顶点访问序列:0、1、2、3、4、5、6、7、8、9。 6. 答:该图的最小生成树如下:,第十章 习题解答,7. 答:该有向图的拓朴排序序列为:3、1、4、5、2、6。,第十章 习题解答,二、算法设计题答案 1. 解:该图对应的邻接表如下:,第十章 习题解答,深度优先算法: void dfsgraph(adjlist adj, int n) /*深度优先遍历整个图*/ {int i;for(i=1;i=n;i++) visited[i]=0;for(i=1;i=n;i++)if(!visited[i])dfs(adj,i); },第十章 习题解答,void dfs(adjlist adj,int v) /*以v为出发点,对图进行dfs遍历*/{ struct edgenode *p;visited[v]=1;printf(“%d“,v);p=adj[v]→link;while(p!=NULL){ if(visited[p→adjvex]==0)dfs(adjlist,p→adjvex);p=p→next;}},第十章 习题解答,2. 解:该图对应的邻接矩阵如下:,第十章 习题解答,广度优先算法: void bfsgraph(int adjarray[n][n],int n) /*广度优先遍历整个图*/ {int i;for(i=0;in;i++)visited[i]=0;for(i=0;in;i++)if(!visited[i])bfs(adjarray,i); },第十章 习题解答,void bfs(int adjarray[][],int v) /*以v为出发点,对图进行bfs遍历*/ {int i,j;queue q;printf(“%d“,v);visited[v]=1;enqueue(,第十章 习题解答,for(j=0;jn;j++)if(adjarray[i][j]==1 }} },第十章 习题解答,3. 解:实现本题功能的算法如下:void creategraph(adjlist g){int e,i,s,d,n;struct edgenode *p ;printf(“请输入结点数(n)和边数(e):\n“);scanf(“%d,%d“,,第十章 习题解答,g[i].link=NULL;}for(i=1;i=e;i++){ printf(“\n请输入第%d条边起点序号,终点序号:“,i);scanf(“%d,%d“,} },第十章 习题解答,4. 解:本题的算法思想是:逐个扫描邻接矩阵的各个元素,如第i行第j列的元素为1,则相应的邻接表的第i个单链表上增加一个j结点。实现本题功能的算法如下:void transform(int adjarray[n][n],adjlist adj){int i,j;edgenode *p;for(i=0;in;i++){adj[i].data=i;,第十章 习题解答,adj[i].link=NULL;}for(i=0;in;i++)for(j=0;jn;j++){ if(adjarray[i][j]==1){ p=(edgenode *)malloc(sizeof(edgenode));p→adjvex=j;p→next=adj[i].link;adj[i].link=p;}} },第十章 习题解答,5.解:(1) 本题的算法思想是:计算出邻接表中第i个单链表的结点数,即为i顶点的出度。求顶点的出度数的算法如下:int outdegree(adjlist adj,int v){ int degree=0;edgenode *p;p=adj[v].link;while(p!=NULL){ degree++;p=p-next;},第十章 习题解答,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;in;i++){p=adj[i].link;while(p!=NULL),第十章 习题解答,{if(p-adjvex==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;in;i++){degree=outdegree(adj,i);,第十章 习题解答,if(degreemaxdegree){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. 答:(1) 排序:将一组杂乱无序的数据按一定的规律顺次排列起来叫做排序。 (2) 内部排序:数据存储在内存中,并在内存中加以处理的排序方法叫内部排序。 (3) 堆:堆是一个完全二叉树,它的每个结点对应于原始数据的一个元素,且规定如果一个结点有儿子结点,此结点数据必须大于或等于其儿子结点数据。 (4) 稳定排序:一种排序方法,若排序后具有相同关键字的记录仍维持原来的相对次序,则称之为稳定的,否则称为不稳定的。,第十章 习题解答,2. 答:(1)采用堆排序最好。因为以上几种算法中,快速排序、归并排序和基数排序都是在排序结束后才能确定数据元素的全部顺序,而无法知道排序过程中部分元素的有序性。堆排序则每次输出一个最大(或最小)的元素,然后对堆进行调整,保证堆顶的元素总是余下元素中最大(或最小)的。根据题意,只要选取前10个最大的元素,故采用堆排序方法是合适的。(2)两个基本操作:比较两个关键字的大小、改变指向记录的指针或移动记录本身。,第十章 习题解答,3. 答:采用冒泡排序法排序时的各趟结果如下: 初始: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 第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) 筛选调整,第十章 习题解答,(e) 交换863和16,输出863,(f) 筛选调整,第十章 习题解答,(g) 交换689和16,输出689,(h) 筛选调整,第十章 习题解答,(i) 交换572和77,输出572,(j) 筛选调整,第十章 习题解答,(k) 交换491和16,输出491,(l) 筛选调整,第十章 习题解答,(m) 交换325和77,输出325,(n) 筛选调整,第十章 习题解答,(o) 交换258和16,输出258,(p) 筛选调整,第十章 习题解答,(q) 交换101和16,输出101,(r) 筛选调整,(s) 交换77和16,输出77,(t) 输出16,第十章 习题解答,采用基数排序法排序时各趟的结果如下: 初始: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,996,第十章 习题解答,5. 答:采用插入排序法排序时各趟的结果如下: 初始:(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),
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:第十章 习题解答.ppt
链接地址:https://www.weizhuannet.com/p-8138572.html
微传网是一个办公文档、学习资料下载的在线文档分享平台!

网站资源均来自网络,如有侵权,请联系客服删除!

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开