数据结构+算法+第二版+课后+答案+部分

1、算法与数据结构课后习题答案第一章一、选择题CCADB二、判断题FFFFT三、简答题5.(1) n-1 (2)1 (3)n(n+1)/2 (4)if(a<b) n , a+ n/2(5)if(x>100) 11*100-1, x-=10;y- 100226.(1)O(log3n)(2) O(n2) (3) O(n2)第二章一、选择题15: AADCD 610:BCBAD 1112:BD二、判断题15:FTFTF 610:TFTTF 1112:FF三、算法设计题1.#define arrsize 100int Inserseqx(datatype A , int *elenum, da

2、tatype x ) int i=*elenum-1;if(*elenum=arrsize) return 0; while(i>=0&&Ai>=x ) Ai+1=Ai; i-; Ai+1=x; *elenum +;return 1;typedef struct node dataype data;struct node *next;LNode, *LinkList;int Inserlinkx(LinkList L,datatype x ) LNode *p=L,*s;s=(LNode *)malloc(sizeof(LNode);if(!s) return 0;

3、s->data=x;while(p->next&&p->next->data<=x) p=p->next; s->next=p->next; p->next=s;return 1;第三章一、选择题15:CBDBB 610: CBDCC二、判断题15:TTTFF三、简答题4. 共 14 种顺序：4321 3214 3241 3421 2134 2143 23142341 2431 1234 1243 1324 1342 1432四、简答题1.#define MAXSIZE 1000typedef structdatatype

4、dataMAXSIZE;int top;SeqStack;SeqStack *Init_SeqStack(); /*栈初始化 */int Empty_SeqStack(SeqStack *s；) /* 判栈空*/int Push_SeqStack(SeqStack *s,datatype x); /*x 入栈 */ int Pop_SeqStack(SeqStack *s,datatype *x); /* 出栈*/ - 3 -int judgehuiwe n( char *str)/*返回1表示是回文，否则不是*/ SeqStack *s=I nit_SeqStack();char *ch=s

5、tr,ch1;while(*ch!= ' ) Push_SeqStack(s, *ch);ch+; ch=str;while(!Empty_SeqStack(s) Pop_SeqStack(s,&ch1);if(*ch!=ch1) return 0;ch+;return 1;5.#defi ne MAXSIZE 1000typedef structdatatype dataMAXSIZE;int top;SeqStack;SeqStack *lnit_SeqStack(); /*栈初始化 */int Empty_SeqStack(SeqStack *s)/* 判栈空 */int

6、 Push_SeqStack(SeqStack *s,datatype x); /*x 入栈 */ int Pop_SeqStack(SeqStack *s,datatype *x); /* 出栈 */ int judge(char *str)/*返回1表示是匹配，否则不是*/ SeqStack *s=l nit _SeqStack();char *ch=str,ch1;while(*ch!= 'O') if ( *ch= ' ( ') PuBeqStack(s, *ch);else if(*ch=') ) if(!Pop_SeqStack(s,&

7、;ch1) return 0; ch+;if(Empty_SeqStack(s) return 1;else return 0;4.typedef struct node dataype data;struct node *n ext;Lqno de, *LqList;置空：LqListIni t_lq() LqList rear=(LqList *)malloc(sizeof(LqList);rear- >n ext=rear;return rear;入队：int in _lq(LqList *rear, datatype x) Lqnode *p=(LqList *)malloc(s

8、izeof(LqList);if(!p) return 0;p->data=x;p->n ext=*rear- >n ext; *rear- >n ext=p; *rear=p; return 1;出队：int out_lq(LqList *rear, datatype x) Lqnode *p;- 9 -if(*rear- >n ext=*rear) retur n 0;p=*rear- >n ext- >n ext;if(p=*rear)*rear=*rear- >n ext;*rear- >n ext=*rear;else *rear

9、- >n ext- >n ext=p->n ext;free(p);return 1;第四章一、选择题1-3: CBA 4: DAB 5:CCC 6:C二、判断题FTFFFFF三、简答题2.(1)aabaabaabaacn ext012123456789aabaacn ext0121234.k=i+j-2+(i+1)%2 或 k=i+j-1+i%26.ijv11422216-15322134233534-66519176328第五章一、选择题：15: CCBBB 610:CBDAD 1115:DCBDB610:FFFTF二、判断题：1115:TFTFF 1620:FTFFT1

10、5: FTFFT三、简答题：4、条件：森林中既没有孩子也没有右边的兄弟的结点5.2h-116.n n 伯 n m n npn 们 nn cian 4?nn aaw . w 1w . 1 v/ w . i j w . w ww . 11 jU U Ixy 1 Uxy j Txy jDU r I0.59a b c d e f g015901122a010c1g:0001a:01b:001c:110d:0000e:111f:10四、算法设计题：typedef struct bitnode datatype data;struct bitnode *lchild, *rchild;BiTNode, *

11、BiTree;1.计算结点数目int counttotal(BiTree bt) if(bt=NULL) return 0;return counttotal(bt->lchild)+counttotal(bt->rchild)+1;计算度为 1 的结点数目：int countdegree1(BiTree bt) if(bt=NULL) return 0;if( bt->lchild=NULL&& bt->rchild=NULL)return 0;if( bt->lchild=NULL| bt->rchild=NULL)return coun

12、tdegree1(bt->lchild)+ countdegree1(bt->rchild)+1;return countdegree1(bt->lchild)+ countdegree1(bt->rchild); 3.求深度 ;int depth(BiTree bt) int ld,rd; if(bt=NULL) return 0;ld= depth(bt->lchild); rd=depth(bt->rchild);if( ld>=rd) return ld+1; return rd+1;第 6 章作业讲评一、选择题1-4：BABC 5:BD 6-

13、10:DBACB二、判断题1-5：FTTFF 6-10:TTFFT 11-15:FTFFF三、简答题1.1)ID(1)=2OD(1)=1ID(2)=2OD(2)=2ID(3)=1OD(3)=3ID(4)=3OD(4)=0ID(5)=2OD(5)=3ID(6)=1OD(6)=2- 11 -(4)0 0 0 1 0 0 '1 0 1 0 0 00 0 0 1 1 10 0 0 0 0 01 1 0 1 0 00 1 0 0 1 0 /012345- 17 -(5)52.厂=0 1 1 0 0 0 01 0 0 1 0 0 01 0 0 1 0 0 00 1 1 0 1 1 00 0 0 1

14、 0 0 10 0 0 1 0 0 1<_0 0 0 0 1 1 0/(4)(5)v1 v2 v3 v4 v5 v6 v73.邻接矩阵表示图时，与顶点个数有关，与边的条数无关5.(1)事件最早发生时间最迟发生时间A00B36C55D1212E2124F2626G2020H2929活动最早发生时间最迟发生时间a103a200a336a455a51215a61216a7M212a82020a92124a10”626a112027(3)关键路径：ACDGFH完成该工 程需要的最短 时间是29第7章作业讲评一、选择题1-5: BCCCD 6-10:BCDDD 11-13:CDB二、判断题ASL=

15、(1*1+2*2+3*4+4*8+5*3)/18=64/18=32/9查找失败时最多的关键字比较次数为6。janfebmaraprmayjunejulyaugsepoctnovdec5360655097726.各关键码对应的散列地址apraugdecfebjanmarmayjunejulysepoctnov01234 5678910111213 14 15 160AugAprjanSep101112查找成功：ASL=(7*1+4*2+3*1)/12=18/12=1.5查找失败：ASL=(6*1+3*2+3*3+4*1)/12=25/12(1)四、1、int Bisearch(datatype

16、r , int low, int high, keytype kx) int mid;if(low>high) return 0; mid=(low+high)/2;if(rmid=kx) return mid;if(rmid>kx) return Bisearch(r,low,mid-1,kx);return Bisearch(r,mid+1,high,kx);第 8 章作业讲评一、选择题1-5： ACCDD 6-10:CBCDC二、判断题1-5： TFFFF 6-10:TFTTT三、简答题1、 已知关键字序列为 (24,69,12,30,106,8,26,76,87,170,4

17、26,100，) 试分别用下列排序方法进行排序，并给出每一趟排序后的结果。(1) 简单插入排序(24),69,12,30,106,8,26,76,87,170,426,100第 1 趟：( 24,69) ,12,30,106,8,26,76,87,170,426,100第 2 趟：( 12,24,69) , 30,106,8,26,76,87,170,426,100第 3 趟：( 12,24, 30,69) , 106,8,26,76,87,170,426,100第 4 趟：( 12,24, 30,69, 106) ,8,26,76,87,170,426,100第 5趟：(8,12,24, 3

18、0,69, 106), 26,76,87,170,426,100第 6 趟：( 8,12,24, 26,30,69, 106) , 76,87,170,426,100第 7 趟：( 8,12,24, 26,30,69, 76,106) , 87,170,426,100第 8趟：(8,12,24, 26,30,69, 76, 87,106), 170,426,100 第 9 趟：(8,12,24, 26,30,69, 76, 87,106, 170) ,426,100 第 10趟：(8,12,24, 26,30,69, 76, 87,106, 170,42)6 ,100 第 11趟：( 8,12

19、,24, 26,30,69, 76, 87, 100 ,106, 170,42)6(2) 直接选择排序24,69,12,30,106,8,26,76,87,170,426,100第 1 趟：( 8) ,12,30,106,24,26,76,87,170,426,100第 2 趟：( 8,12) ,30,106,24,26,76,87,170,426,100第 3 趟：(8,12，24) ,106,30,26,76,87,170,426,100第 4 趟：( 8,12， 24,26) , 30, 106,76,87,170,426,100第 5 趟：( 8,12， 24,26, 30) 第 6

20、趟：( 8,12， 24,26, 30， 第 7 趟：( 8,12， 24,26, 30， 第 8 趟：( 8,12， 24,26, 30， 第 9 趟：( 8,12， 24,26, 30，, 106,76,87,170,426,10076), 106, 87,170,426,10076, 87) , 106,170,426,10076, 87,100),170,426, 10676, 87,100, 106) ,426,170第 10 趟：( 8,12，24,26, 30，76, 87,100, 106,170),426 第 11趟：( 8,12，24,26, 30，76, 87,100, 106,170,426)(3) 冒泡排序24,69,12,30,106,8,26,76,87,170,426,100第 1趟： 24,12,30,69, 8,26,76,87, 106,170,100,(426)第 2 趟： 12, 24,30, 8,26, 69,76,87, 106, 100, (170,426)第 3 趟：12, 24, 8,26, 30,69,76,87, 100, (106,170,426)第 4 趟：12, 8, 24, 26, 30,69,76,87, (100,106