C语言程序设计习题与答案.pdf

习题参考答案第1章1.1 什么是数据对象、数据元素、数据结构？（略）1.2 什么是数据类型？什么是抽象数据类型？（略）1.3 什么是算法？它有哪些特性？它与程序有何区别？（略）1.4 试判定下列计算过程是否为一个算法？1）开始2）n =03）n=n+14）重复3）5）结束答:不是一个算法。不能满足算法特点中有穷性的要求，其3）八=+1将使程序无限循 环下去。1.5 用图形表示下列数据结构：1）S=（D,R）,D=!a,b,c,d,e,f,g,R=,2）S=（D,R）,D=48,25,64,57,82,36,75 ,R=R,R2 1RI=,R2=,答：21.6 将。(1)、。(九)、0(，)、(X I)、0(nlog2n)、。(log2n)、0(2)按增长率递增排列。答：。(1)、0(log2n)、。()、。(nlog2n)、。(/)、。(/)、0(21.7计算下列算法的时间复杂度：1)x=100；y=0；while(x =y*y)y=y+2;答：I/)。2)sum(int n)I int sum=0,x,j,k；f or(j=l；j=n；j+)lx=1;f or(k=1；k =j；k+)p=p*k；sum=sum+p；I return sum；I答：0(/)。第2章2.1 什么是线性结构？其特点是什么？(略)2.2试分析顺序表和链表的各自特点。(略)2.3 试编写一个算法，将一个顺序表逆置，并使用最少的辅助存储空间实现。答：invert_ list(int list,int n)/*将顺序表进行逆置*/I int i,t;f or(i=1;i n/2;i+)!t=list i;list i =list n-i-1;list n-i-1 =t;1/*f or*/*invert_ list*/2.4 试编写一个算法，将两个元素值递减排列的顺序表合并为一个非递增的顺序表。答：Merge_ list(int a,int b,int c,int m,int n)int j=0,k=0,i=0;while(i m&j b j)I c k =a i;i+;k+;Ielse I c k =b j;j+;k+;!Iwhile(im)|ck=a i;i+;k+;!while(j next;while(p!=head)Ip=p-next;length+;!/*while*/printf(the length of the list is：%d n,length);/*length*/2.6 试编写一个算法，在一个递增有序排列的单链表中插入一个新结点%,并保持有序。答：struct Linknod e Iint d ata;struct Linknod e*next；!；typed ef struct Linknod e*Link;Link insert(Link head)Iint i,e,j;Link pointer,s;printf(nplease input the elem of you want insert：);scanf(%d ,&e);pointer=head;while(pointer-next&e =pointer-next-d ata)/*在链表中确定插入的位置*/pointer=pointer-next；if(!pointer-next)s=(Link)malloc(sizeof C struct Linknod e);s-d ata=e；pointer-next=s；s-next=NULL；Ielse Is 二(Link)malloc(sizeof(struct Linknod e);s-d ata=e;/*为插入的结点建立链接关系*/s-next=pointer-next;pointer-next=s;/*if*/return head;!/*LinkList_ insert*/2.7 试编写一个算法，将一个单链表逆置。答：struct Linknod e Iint d ata；struct Linknod e*next;typed ef struct Linknod e*Link；invert(Link head)/将带头结点的单链表进行逆置*/Link p,q,r;4p=head-next;q=p-next;p-next=NULL；while(q)!r=q-next;q-next=p;head-next=q;P=q;q 二 r；l/while*/Print(head)；/*invert*/2.8 试编写一个算法，在一个双向循环链表中将结点%插入到指定结点p之前 答：struct DuLinknod eIint d ata；struct DuLinknod e*prior；/*直接前马区*/struct DuLinknod e*next;/*直接后继*/i；typed ef struct DuLinknod e*DuLink；DuLink insert(DuLink head)/*在第 i 个位置之前插入 x*/int i,e,j;DuLink pointer,new;printf(nplease input the elem of you want insert：);scanf(%d，&e);printf(nplease input the location of you want insert：);scanf(%d ,&i)；pointer=head-next;j=1；while(pointer-d ata&j v i)/*在链表中确定插入的位置*/pointer=pointer-next;+j；/*while*/if(!pointer-d ata I Ij i)printf(error);else Inew=(DuLink)malloc(sizeof(struct DuLinknod e);new-d ata=e;new-prior=pointer-prior；/*为插入的结点建立链接关系*/pointer-prior-next=new;new-next=pointer;pointer-prior=new;/*if*/return head；/*DuLinkList_ insert*/2.9 若有4个元素，入栈顺序为ABCD,请列出所有可能的出栈序列。答：所有可能的出栈序列一共有16种，如下：ABCD ABDC ACBD ACDB ADCB BACD BADCBCDA BCAD BDCA CBDA CBAD CDBA DCBA习题参考答案 5*2.10试编写一个算法，让两个顺序栈共用一个数组SscHN,分别实现人栈、出栈操 作。答：定义共享栈的数据结构：#d ef ine MAX 100int stack MAX ,topi=0,top=MAX-1;(1)共享进栈算法void pushl(int x)Iif(topi top2)printf(overf low);else Istack topi =x；topi+;iIvoid push2(int x)if(topi top2)printf(overf low);else Istack top2 =x;top2；(2)共享出栈算法int popl()!if(topi 二 二 0)Sprintf(und erf low )；return(NULL)；i topi-;return(stack topi);Iint pop2()if(top2=MAX-1)iprintf(und erf low );return(NULL);(top2+;return(stack top2);I2.11试编写一个算法，计算一个循环队列中包含的元素个数。答：struct queuenod e!struct queuenod e*base;int f ront;int rear;1；typed ef struct queuenod e*sqQueue;QueueLength(sqQueue q)Iint x;x=(q-rear-q-f ront+maxsize)%maxsize;printf(the length is%d n,x);I/*QueueLength*/2.12试编写一个算法，实现链栈的人栈、出栈操作。答：struct stacknod e iint d ata；6struct stacknod e*next;1;typed ef struct stacknod e*Nod e;pushstack(Nod e top)/*入栈*/int e;Nod e new；printf(Xnplcaoc input the d ata(No f or 0)：);scanf(%d ,&e);if(e!=0)Inew=(Nod e)malloc(sizeof(struct stacknod e);/*分配结点*/new-d ata=e；/*初始化结点*/new-next=top-next；top-next=new;/*插入结点*/top-d ata+;I/*if*/*pushstack*/popstack(Nod e top)int answer；printf(nAre you want d elete the d ata?);/*用户确认是否删除*/printf(nplease answer 1 f or Y or 0 f or N：);scanf(%d ,&answer)；switch(answer)Icase(1)：d elete(top)；break；case(0)：break；d ef ault：printf(nyour answer is error!n);I/*switch*/1/*pop*/d elete(Nod e top)/*弹栈*/iNod e old;if(top-next=NULL)printf(the stack is empty!);else Iold=top-next;/*old指向待删除的结点*/top-next=old-next;/*删除结点*/printf(nthe d elete d ata is%d n,old-d ata)；f ree(old);/*释放空间*/top-d ata-;/*else*/I/*d elete*/2.13试编写一个算法，实现对个以只带尾指针的循环单链表表示的队列的入队、出队操 作。答：struct queuenod e Iint d ata;struct queuenod e*next；习题参考答案7typed ef struct queuenod e*Nod e;Nod e enqueue(Nod e f ront,Nod e rear)I int e;Nod e new；printf(nplease input the d ata(No f or 0)：);scanf(%d，&e);i f(e!-0)(new=(Nod e)malloc(sizeof(struct queuenod e);/*分配结点*/if(!new)exit(0);/*分配失败*/new-d ata=e;/*初始化结点*/new-next=NULL;rear-next=new；/*插入新结点*/rear二new；/*队尾指针后移*/f ront-d ata+；I/*if*/return rear；I/*enqueue*/Nod e d equeue(Nod e f ront,Nod e rear)I Nod e old;if(f ront 二 二 rear)printf(nthe queue is empty!);else I old二f ront-next;/*old指向待删除的结点*/printf(nthe d elete d ata is%d n,old-d ata);f ront-next=old-next；/*删除结点*/if(rear=old)rear=f ront;f ree(old);/*释放空间*/f ront-d ata-;I/*else*/return rear；/*d equeue*/第3章3.1 设字符串 S=good ,T=I am a stud ent,/?=!,求：答：(1)CONCA7X T,R,S)=I am a stud ent!good(2)SUBSTR(7,8,7)=stud ent(3)Len(D=14(4)index(.T,a)=3(5)insert(T,S,8)=I am a good stud ent(6)replaced T,SUBSTR 7,8,7),teacher)=I am a teacher3.2 设a=*+XyZ,6=(X+Y)*Z,试用连接、求子串和置换等操作，将串。转换 成字符串6,写出其转换过程。答：用求子串与连接操作将串。变换成人因为有：*=SUBST a,1,1)；+=SUBST a,2,1)；X=SUBSTI a,3,l);7=SUB-STR(a,4,1)；Z=SUBSTR(a,5,1)8所以有：d=CONCATi(,X Y)；e=CONCATi ),Z)最后有：b=CONCATX d,e)=(X+丫)*Z3.3 若x和y是两个单链表存储的串，试设计一个算法，找出x中第一个不在y中出现的 字符。答：单链表的存储结构如下定义：设其结点数据域d ata只存储1个字符，若X和y是 两个单链表存储的串，且头指针分别为x和y,则查找x中第一个不在y中出现 的字符的算法描述为：typed ef struct Nod e Ichar d ata；struct Nod e*Next;iLink;Search(Link*X,Link*Y)Ip=X-Next;/*p为X串的查询指针*/while p!=NULL!q=Y-Next;while q!=NULLif p-d ata=q-d ata/*q 为 Y 串的查询指针*/q=q-Nextelse return”该字符不在Y串中p=p-Next;Iif p=NULLreturn 串X中的字符全部在Y中return p-d ata3.4 设结点数据域可存放4个字符，以这样的结点构成单链表来存储。写出将串T插入到 串S某个字符之后的算法，若S中不存在该字符，则将串T连接在S的后面。答：因单链表结点数据域可存放4个字符，链表中最后一个结点不一定全部被串值占满，此时通常应补上或其他非串值来填满最后结点的数据域，在这种块链 结构上实现将串T插入到串S中某个字符之后的算法逻辑描述如下：若设为某个指定的字符，且先在串S中存在，则该字符将串S分解成两个串就 和S2。串片的首字符是串5的首字符，串的尾字符是申5中首次出现的字符%；串S2的首字符是串S中字符的后继字符，串2的尾字符是串S的尾字符。因此，该算法为连接三个串，即。5Vs 7TS1,T,2)。若串S中不存在,则算法 为 CONCATO S,T)03.5计算下列串的7的值:答：(1)序号(j)：模式串T：next(j)：(2)序号(j)：4b348 b381235679a01a12a23c15a16a27a19习题参考答案9模式串T：next(j)：(3)序号(j)：模式串T：next(j)：a01 b0a13 b1a14 b2c36 b3c b2 18 b33.6 对 S=aabcbabcaabcaaba,配过程。若S串长度为，T=abcaaba,画出以T为模式串、S为目标串的快速匹T串长度为小，问该算法的时间复杂度为多少？答：计算模式串T的碇权数组为:序号(j):模式串r：next(j)：借助于加数组，进行快速匹配找到T=SUBSTR(S,10,7),具体过程如下:序号3)：模式串s：匹配过程:1()11b12131415b16b12a11a02 b1341aaa2a bbc1a13b4ccaab25a47a2a45a25baaa6 b26abbb7a(m=7)37baac8ca9aaaacaaabb)acaaab注：字符下有符号的表示用该字符比较产生不等，括号中的字符表示跳过的字 符。该算法的时间复杂度为。(+机)。这是因为在快速匹配过程中，利用了模式 串丁的碇口数组，使得指示目标串的指针不许回溯，对目标串仅需从头至尾扫视 一遍即可。3.7 采用顺序结构存储串，编写一个实现具有通配符？的模式串S与目标串丁进行匹配 的函数一征/改()。通配符？可以和任意字符匹配；若匹配成功则返回串S在 目标串丁中首次出现的下标位置，否则返回-1。例如，pattern _ index(?re,there are)返回结果 2。答：具有通配符的模式串S与目标串7的匹配函数如下：int pattern_ ind ex(char s,char t)/*若匹配成功,则返回首次匹配的下标位置，否则返回*/Iint i,j;int f ound=-1;i=j=0；while(t j!=1 01)I if(s i =1 01)return f ound;if(s i =?I I s i =t j)I i f(f ound=-1)f ound=j;10elseif(s i!=t j&f ound!=-1)/*从模式串S起始位置重新匹配*/I i=0；f ound=-1;(else j+;I return f ound;i第4章4.1已知二维数组瓦加,对采用行序为主方式存储，每个元素占L个存储单元，并且第一 个元素的存储地址是L()a A(),0),则A：i J 的地址是什么？答：i,j 的存储地址是：Loa 5)=(。(40,0)+(i*n+j)k4.2设行列的下三角矩阵4已压缩到一维数组51.*(+1)/2中，若按行序为主 存储,则A ij对应的S中的存储位置是什么？答：A，j在S中的存储位置K是：，(1+1)/2+j,当，刁时 K=n(n+1)/2,当/源时4.3 一个稀疏矩阵如图4-16所示，求对应的三元组表示、十字链表表示。0 0 2 03 0 0 00 0-150 0 0 0图4-16 一个稀疏矩阵答：对应的三元组表示为：(0,2,2)(1,0,3)(2,2,-1)(2,3,5)对应的十字链表表示为：chead习题参考答案4.4求下列广义表操作的结果：(1)GetHead_(p,/i,w)=p(2)GetTa亚(b,k,p,h)=(k,p,h)(3)GetHea_(a,6),(c,3)二(a,b)(4)-iZ(),(c9d)=(c9d)(5)GetHea(l_ GetTail_(a,6),(c,d)=(c,d)(6)GetTaiR GetHead_(a,6),(c,)=(6)注：为函数的符号。4.5利用广义表的GetHead和GetTail操作，将原子stud ent从下列广义表中分离出来。(1)1=(sold er,teacher,stud ent,worker,f armer)答：GetHead(GetTail(GetTaiK LI)o(2)2=(sold er,(teacher,stud ent),worker,f armer)答：GetTaiK GetHead(GetTaUk L2)o4.6 画出下列广义表的头尾表示法和孩子兄弟表示法，并求出其深度。(1)(),a,(6,c),(),d),(e)(2)(。),6),(),d),(e,f)答：广义表(1)的深度是4,其头尾表示法如下：广义表（1）的孩子兄弟表示法如下:12广义表（2）的孩子兄弟表示法如下:4.7 若矩阵A,“内中的某个元素与是第，行中的最小值，同时又是第，列中的最大值，则称 此元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵4,“*“，试编写求出矩阵中 所有马鞍点的算法，并分析你的算法在最坏情况下的时间复杂度。答：求出矩阵中所有马鞍点的算法如下：minMax(int*matrixA)Iint rowMin,colMax,f lag；int i,j,minCol,maxRow;f or(i=0;i M;+i)IrowMin=*(matrixA+i)+0);f or(j=l；j*(matrixA+i)+j)IrowMin=*(matrixA+i)+j);minCol=j;/*if*/f lag=1；f or(maxRow=0;maxRow M;+maxRow)Iif(maxRow 二二 i)continue;if(rowMin 加时10(m2),当 m 时4.8 假设稀疏矩阵A和B均以三元组顺序表作为存储结构，试写出矩阵相加的算法，另设 三元组表。存放结果矩阵。答：MatrixAd d(TSMatrix M,TSMatrix N)习题参考答案13int i=1,j=1；if(M.mu!=N.mu)I l(M.nu!=N.nu)printf(nthe rows or col is error!);else Iwhile(i =M.tu)&(j =N.tu)Iif(M.d ata i.row=N.d ata j.row)Iif(M d ata i.col=N.d ata j.col)ADDToMatrixC(M,i+,N,j+);elseif(M.d ata i.col N.d ata j.col)Append ToMatrixC(M,i+)；else Append ToMatrixC(N,j+);else!if(M.d ata i.row N.d ata j.row)Append ToMatrixC(M,i+);else Append ToMatrixC(N,j+);iIif(i =N.tu)while(i =M.tu)&(j =N.tu)while(j C.d ata C.tu.row)?C.mu：C.d ata C.tu.row;C.nu=(C.nu C.d ata C.tu.col)?C.nu：C.d ata C.tu.col；IADDToMatrixC(TSMatrix A,int i,TSMatrix B,int j)IC.tu+;C.d ata C.tu.row=A.d ata i.row;C.d ata C.tu.col=A.d ata i.col;C.d ata C.tu.d ata=A.d ata i.d ata+B.d ata j.d ata；C.mu=(C.mu C.d ata C.tu.row)?C.mu：C.d ata C.tu.row；C.nu=(C.nu C.d ata C.tu.col)?C.nu：C.d ata C.tu.col;4.9 试编写判别两个广义表是否相等的递归算法。答：判定两个广义表是否相等的功能函数如下：14same(p,q)=same(p-tp yq-tp)若 p-tag=0,q-tag=。且 p-data,atom=data,atomsame(p,q)=same(p-data,hp y q-data,hp)若 p _tag=1,q-tag=1 且 same(p-tpq-ip)same(p,q)=false若 p _tag=0,q-tag=0 且 一 data,atom Wq-data,atom若 p _tag=0 且 q-tag=1 或 p-tag=1 且 q-tag=0same(p,q)=f alse若 p=NULL 且 q W NULL 或 p W NULL 且 q=NULL其相应的算法如下：int same(GList p,GList q)Iint f lag=1;if(p!=NULL&q!=NULL)if(p-tag=0&q-tag=0)if(p-d ata,atom!=q-d ata-d ata,atom)f lag=0;else if(p-tag=1&q-tag=1)f lag=same(p-d ata.hp,q-d ata.hp)；else f lag=0；if(f lag)f lag=same(p-tp,q-tp);Ielseif(p=NULL&q!=NULL)f lag=0;if(p!=NULL&q=NULL)f lag=0;Ireturn(f lag)；I第5章5.1 已知一棵树边的集合为 ,e,i，,画出这棵树,并回答下列问题:(1)哪个是根结点？(2)哪些是叶结点?(3)哪个是结点g的双亲？(4)哪些是结点g的祖先？(5)哪些是结点g的孩子？(6)哪些是结点e的子孙？(7)哪些是结点e的兄弟？哪些是结点了的兄弟？(8)树的深度是多少？(9)树的度数是多少？答：这棵树的形状如下：习题参考答案15（1）q是根结点；（2）加、，、八鼠/、/是叶结点；（3），是结点g的双亲;（4）a、c是结点g的祖先;（5）j、k是结点g的孩子；（6）m、n是结点e的子孙;（7），是结点e的兄弟，g、6是结点了的兄弟；（8）树的深度是5;（9）树的度 数是3。5.2 一棵二叉树的结点数据采用顺序存储结构存储于数组，中，如图5-22所示，画出该二 叉树的二叉链表表示形式。图5-22 一棵二叉树的顺序存储数组c 答：eafdgcJIhib5.3 对图5-23所示的二叉树，回答下列问题：（1）写出先序、中序、后序遍历的序列。（2）画出该二叉树的中序线索二叉树。（3）画出该二叉树对应的森林。答：（1）先序遍历的序列为：abdgcefhi 中序遍历的序列为：dgbaech if 后序遍历的序列为：g db eihfca（2）该二叉树的中序线索二叉树为：16|!|1 I j|1 I l(3)该二叉树对应的森林为:5.4 已知一棵二叉树的中序序列为足加修力，后序序列为cedbhjigfa,画出该二叉树的先序 线索二叉树。答：先序遍历的结果是：a 6 c e/g A订-。习题参考答案175.5 有一份电文中共使用5个字符：a、b、c、d、e,它们的出现频率依次为4、7、5、2、9,试画出对应的哈夫曼树(请按左子树根结点的权小于等于右子树根结点的权的次序 构造)，并求出每个字符的哈夫曼编码。答：哈夫曼树为：哈夫曼编码如下:a(001);b(10);c()1);d(000);e(11)。5.6 设给定权集=!2,3,4,7,8,9 1,试构造关于的一棵哈夫曼树，并求其带权路 径长度WPLC答：哈夫曼树如下图所示。带权路径长度 WPL=7x2+8 x2+4 x3+2 x4+3 x4+9 x2=805.7 假设二叉树采用二叉链表存储方式存储，编写一个中序遍历二叉树的非递归函数。答：Inord erTraverse(Head nod e head)/*利用链表结构中序遍历二叉树*/Iint i,e；int*stack 10;/*设置一个指针数组，用于存放遍历时的结点地址*/18int top=0,base=0;Bitree pointer；printf(n=Inord erTraverse：);f or i=0;i next；while(pointer!=NULL I Ibase!=top)Iif(pointer!=NULL)tstack top+=pointer；/*根结点地址入栈*/pointer=pointer-lef t;/*访问左子树*/I/*if*/else I/*从左子树返回*/pointer=stack top;/*取出根结点地址*/printf(%d=”，pointier-(iata)；/*输出信息*/pointer=stack top;pointer=pointer-right;/*进入右子树*/I/*else*/*while*/*Inord erTraverse*/5.8 试编写一个递归算法，求二叉树中以元素值为的结点为根的子树的深度。答：int Nod eHeight(Bitree p)/*递归法计算结点所在树的深度*/Iint totalHeight,lef tHeight,rightHeight;if(p=NULL)return(0);else：lef tHeight=Nod eHeight(p-lef t);rightHeight=Nod eHeight(p-right);if(lef tHeight rightHeight)totalHeight=lef tHeight+1；else totalHeight=rightHeight+1;return(totalHeight);/*else*/*Nod eHeight*/5.9 假设二叉树采用二叉链表存储结构，设计一个算法求二叉树中指定结点的层数 答：getLevel(Bitree curPoint,int e,int nod eHeight,int currentHeight)Iif(currentpoint=NULL)nod eHeight=0;else if(e=currentPoint-d ata)nod eHeight=currentHeight;elsegetLevel(curPoint-lef t,e,nod elleight,currentHeight+1)；if(nod eHeight=-1)getLevel(curPoint-right,e,nod eHeight,currentHeight+1);I/*else*/*getLevel*/5.10 假设二叉树采用二叉链表存储，编写一个函数复制一棵给定的二叉树。习题参考答案19答：Copy(P)=NULL,若 p=NULL“Cop)(p)一产生一个新结点neivNode,若p片NULL newNod e-d ata=p-d ata实现的功能函数如下：Bitree Copy(Bitree p)Bitree newNod e;if(p!=NULL)inewNod e=(Bitree)malloc(sizeof(struct treenod e)；newNod e-d ata=p-d ata;newNod e-lef t=Copy(p-lef t);newNod e-right=Copy(p-right);return(newNod e);I/*if(p!=NULL)*/else return(NULL);I5.11 试编写一个将二叉树中每个结点的左右孩子交换的算法。答：将二叉树中每个结点的左右孩子交换的递归模型如下：exchanged p)mewNode=NULL,若夕=NULLexchanged p)复制当前根结点p产生newNode,若pW NULLexchange(p-lef t)lef tNod e,exchange(p-right)righlNod enewNod e-lef t=right Nod e,newNod e-right=lef tNod e 实现的功能函数如下：Bitree Exchange(Bitree p)Bitree newNod e,lef tNod e,rightNod e;if(p=NULL)newNod e=NULL;elsenewNod e=(Bitree)malloc(sizeof(struct treenod e)；newNod e-d ata=p-d ata;lef tNod e=Exchange(p-lef t);rightNod e=Exchange(p-right);newNod e lef t=rightNod e;newNod e-right=lef tNod e；I/*else*/return(newNod e);5.12 写出中序线索化二叉树中查找结点*p中序后继的算法20答：可以先将二叉树中序线索化，然后再进行查找，下面给出将二叉树中序线索化的 程序。thread ing(Bithrtree head)/*中序遍历二叉树head,将其中序线索化*/IBithrtree pointer;head-right=head;pointer-head-lef t;if(pointer 二二 NULL)head-lef t=head;/*二叉树为空*/else!head-lef t=pointer；pre=head;inthread ing(pointer);/*递归调用中序线索化*/pre-right二head;/*设置最后一个结点和头结点的关系*/pre-rtag=1;head-right=pre;I/*else*/*thread ing*/inthread ing(Bithrtree pointer)/*中序线索化二叉树*/：if(pointer!=NULL)Iinthread ing(pointer-lef t)；/*左子树线索化*/if(pointer-lef t=NULL)：pointer-Itag=1;/*前马区线索化*/pointer-lef t=pre；I/*if*/if(pre-right=NULL)pre-rtag=1;/*后继线索化*/pre-right=pointer；/*if*/pre=pointer；inthread ing(pointer-right);/*右子树线索化*/I/*if*/!/*inthread ing*/第6章6.1图6-24所示为一有向图：(1)求每个顶点的入度和出度。(2)画出它的邻接矩阵。(3)画出它的邻接表与逆邻接表。(4)写出它的强连通分量。答：(1)见表解64。习题参考答案21表解6-1顶点的入度和出度顶点1234567入度0213121出度3111112(2)邻接矩阵为:0111000000010000000100100000000000100010000001010(3)邻接表见图解6-1。其逆邻接表见图解6-2。(4)有三个强连通分量：2,4,5,6,7 1,!1!,!3 L226.2编写一个实现连通无向图G的深度优先搜索(从顶点V出发)的非递归函数，图G用 邻接表表示。答：实现连通无向图G的深度优先搜索(从顶点V出发)的非递归函数如下：vexnod e ALGraphf N;/*设图 ALGraph 有 N 个顶点*/vexnod e*ptr MAX；int visit MAX;/*遍历标志数组，初始化为0;visit i =1表示顶点i访问过*/int number MAX;/*遍历顶点数组*/int count=0;/*遍历顶点个数数组*/int stack MAX;/*栈数组*/DeepFirst()I int i；f or(i=0;i link;visit i =0;!/*初始化遍历数组标记为 0*/f or(i=0;i ad j vex;if(visit w =0)/*判定搜索标记*/I printf(%D,%D)t,vl,w);number w=+count；visit w =1；/*设置遍历标记为1*/push(w);/*顶点 w 人栈*/Iptr vl =ptr vl -link;；pop();/*一个顶点出栈*/i i注：关于人栈、出栈算法，请同学们自己补充。6.3假设无向图G采用邻接表存储，编写一个函数利用深度优先搜索方法求出该图中通过 给定点V的简单回路。答：参考6.2中的深度优先遍历算法，稍加改造得到下面的算法，该算法可得到在无 向图中通过顶点V的所有简单回路：int path N;/*存储从path 0 开始的路径*/d eepf t(int v)/*从顶点V开始遍历*/I int vl,w,i;int count=0；path 0 =v;/*路径的起点*/+count；visit v =1;push(v);习题参考答案23while(top!=0)I while(ptr vl=stack top !=0)I w=ptr vl-ad jvex;if(visit w =0)/*判定搜索标记*/!path count =w;/*记录经过的顶点，即路径*/+count;visit w J=1;push(w)；/*顶点 w 入栈*/Iif(w=v)/*已找到了一个关于顶点V的回路*/!printf(”已找到了一个关于顶点V的回路！Vi);f or(i=0;i link；tpop();/*一个顶点出栈*/iif(count N)printf(该图不是连通图!);6.4已知如图6-25所示的无向带权图：(1)写出它的邻接表，并在此存储表示基础上用克鲁斯卡尔算