《软件技术基础_课后答案_周大为_西电》由会员分享，可在线阅读，更多相关《软件技术基础_课后答案_周大为_西电（25页珍藏版）》请在金锄头文库上搜索。
1、1软件技术基础习题答案软件技术基础习题答案习题 3四、四、1int compare(SeqList*La,SeqList*Lb)int i;i=1;while(ilastif(ilast /ABif(iLa-last /ALa-last /A=B四、2（1）顺序表）顺序表int invert(SeqList*L)2int i=1;datatype temp;while(ilast/2)temp=L-datai;L-datai=L-dataL-last-i+1;L-dataL-last-i+1=temp;（2）链表）链表void invert (linklist*head)linklist*p,
2、*q,*r;p=head-next;q=p-next;while(q!=NULL)r=q-next;q-next=p;p=q;q=r;3head-next-next=NULL;head-next=p;四、5void mergelist(Linear_list*La,Linear_list*Lb,Linear_list* /产生 C 表的头结点头插法Lc-next=NULL;while(La-next!=NULLLa-next=La-next-next;insert(Lc,p);elsep=Lb-next;Lb-next=Lb-next-next;insert(Lc,p);4while(La-n
3、ext!=NULL)p=La-next;La-next=La-next-next;insert(Lc,p);while(Lb-next!=NULL)p=Lb-next;Lb-next=Lb-next-next;insert(Lc,p);/O(Length(La)+Length(Lb)void insert(Linear_list*Lc,Linear_list*p)p-next=Lc-next;Lc-next=p;/O(1)四、8void deleteFront(Link*s)5Link*p=s,*q;while(p-next-next!=s)p=p-next;q=p-next;p-next=s
4、;free(q);习题习题 4四、1int symmetry(linklist*head,stack*s)/具有头结点的单链表中存放有一个字符串， 每个结点的数据域存放一个字符。/head 为单链表的头指针，s 为栈的结构体指针int n=length(head)/2;linklist*p=head-next ;datatype x;for(int i=0;idata);p=p-next ;6if(length(head)%2=1)p=p-next;while(p!=NULL)x=pop(s) ;if (x=p-data )p=p-next;else return 0;return 1;四、3
5、void delete(Stack*s)Stack*temp;datatype x;InitS(temp);while(!EmptyS(s)x=Pop(s);if(x!=m) Push(temp,x);while(!Empty(temp)Push(s,Pop(temp);7四、4int correct(char*exp)InitStack(S);int flag=1;i=0;while( expi!=0/遇左括号入栈if( expi=) if( Pop(S)!=( ) flag=0;if( expi=) if( Pop(S)!= ) flag=0;if( expi=) if( Pop(S)!=
6、 ) flag=0;/遇右括号出栈，若栈顶不是左括号，则括号不配对i+;if(!Empty(S) flag=0;/若栈非空，则括号不配对returnflag;四、6循环队列的结构类型定义：循环队列的结构类型定义：const int m=5;8typedef int datatype;typedef structdatatype sequm;intrear, quelen;qu;说明：队满条件：sq-quelen=m队空条件：sq-quelen=0(注意：不需要空出一个位置)入队：void enqueue(qu *sq, datatype x)if(sq-quelen=m)printf(“que
7、ue is full“);else sq-quelen+;sq-rear=(sq-rear+1)%m;/修改队尾指针sq-sequsq-rear=x;出队：intdequeue(qu *sq , datatypereturn 0;else sq-quelen-;x=sq-sequ(sq-rear-sq-quelen+m)%m;return 1;9习题习题 5四、3（1）顺序串intEqual(SeqString*S,SeqString*T)/比较顺序串 S、T 是否相等i=0；while(S-chi=T-chi)if ( i= =S-length ) else return 0;（2）链串in
8、tEqual(LinkString*S,LinkString*T)/比较链串 S、T 是否相等p=S-next；q=T-next;while(S-data=T-data)q=q-next;if(p=NULL)else return 0;四、7void strDelete(char*S,int i,int m)char temp80;int k;k=i-1;if(i=strlen(S) return;elsestrncpy(temp,S,k);if(k+m=strlen(S) strcpy(temp+k,“0“);else strcpy(temp+k,S+k+m);strcpy(S,temp);
9、或者：void strDelete(seqstring*S,int i,int m)11/字符串中字符的序号从 1 开始，数组元素从下标 0 开始使用char tempmaxsize;if(ilen)strncpy(temp,S-str,i-1); /将 S-str 中第 i 个字符之前的 i-1 个字符复制到 temp 中strcpy(temp+i-1,S-str+i+m-1);/将 S-str 中第 i+m 个字符开始的字符连接到 temp之后strcpy(S-str,temp); /将 temp 复制到 S-str 中if(ilen)if(i+m-1len) S-len=S-len-m;
10、/删除了字符串中间的部分字符else S-len= i-1;/删除了字符串中从第 i 个字符开始的全部字符四、9void create(Spmatrix*a)scanf(“%d,%d,%d“,for(ano=0;anot;ano+)12scanf(“%d,%d,%d“,四、11void minmax(array*p)/找马鞍点inti,j,have=0;for(i=0;imini=p-Ai0;for(j=1;jAijmini) p-mini=p-Aij; /分别找出 m 行的最小值for (j=0;jmaxj=p-A0j;for(i=1;iAijp-maxj) p-maxj=p-Aij; /分
11、别找出 n 列的最大值for(i=0;imini=p-maxj) /若相等，则是一个马鞍点coutAijlchild);t2=swap(p-rchild);p-lchild=t2;p-rchild=t1;return p;12、已知结点序列21，18，37，42，65，24，19，26，45，25，画出相应的二叉排序树，并画出删除结点 37 后的二叉排序树。有问题(1)（2）删除结点 37 后14 某密码电文由 8 个字母组成，每个字母在电文中的出现频率分别是 7、19、2、6、32、3、21、10，试为这 8 个字母设计相应的哈夫曼编码。15解：这 8 个字母可用 A、B、C、D、E、F、G
12、、H 表示组成的哈夫曼编码如下所示。A：1001B：101C：0010D：1000E：11F：0011G：01H：000设计的哈夫曼树如下：哈夫曼树第七章四、4、邻接表:126null2136null324null435null547null6127null756null16DFS:1 2 3 4 5 7 6BFS:1 2 6 3 7 4 5(不唯一)或 1 6 2 7 35 45、按顺序输入后的邻接表:126435null216null3145null41635null56413null61245null6、从顶点 4 开始:DFS: 412653(有多种)BFS: 413562(不唯一)7
13、 最小生成树:7615243第八章174、查找 5861 23456789101112 1314 15166 87 155 188 150 465 505 508 511 586 656 670 700 766897 908Low=1 high=16 mid=(1+16)/2=8R8508586Low=9high=12-1=11mid=(9+11)/2=10R10=586586=R10 查找成功5 线性探查 13HT01234567891011125226151204311847099923725H(key)002341162841112比较121118161611拉链052，261215，7
14、0312018443，82568478999101137，111225给定关键字序列为(105，50，30，25，85，40，100，12，10，28，分别写出直接插入排序、希尔排序、起泡排序、直接选择排序、快速排序和归并排序的每一趟运行结果。直接插入排序：初始关键字序列：105，50，30，25，85，40，100，12，10，28第一趟直接插入排序： 【50，105】第二趟直接插入排序： 【30，50，105】第三趟直接插入排序： 【25，30，50，105】第四趟直接插入排序： 【25，30，50，85，105】第五趟直接插入排序： 【25，30，40，50，85，105】第六趟直接插入
15、排序： 【25，30，40，50，85，100，105】第七趟直接插入排序： 【12，25，30，40，50，85，100，105】19第八趟直接插入排序： 【10，12，25，30，40，50，85，100，105】第九趟直接插入排序： 【10，12，25，28，30，40，50，85，100，105】希尔排序(增量为 5，3，1)：初始关键字序列：105，50，30，25，85，40，100，12，10，28第一趟希尔排序：40，50，12，10，28，105，100，30，25，85第二趟希尔排序：10，28，12，40，30，25，85，50，105，100第三趟希尔排序：10，12，25，28，30，40，50，85，100，105起泡排序：初始关键字序列：105，50，30，25，85，40，100，12，10，28第一趟起泡排序：10，105，50，30，25，85，40，100，12，28第二趟起泡排序：10，12，105，50，30，25，85，40，100，28第三趟起泡排序：10，12，25，105，50，30，85，40，100，2
