計算機軟件基礎課后習題答案

第一章

一、簡答題

1.參考書上第五頁圖1—7

2.因為C語言是強類型語言，語法規(guī)定必須先定義后使用，只有先定義，系統(tǒng)才

能為其分配存儲空間。

3.參考書上第二頁

二、填空題

1.算法

2..C,.obj,.exe

3.提出問題，構造模型，選擇方法，編寫程序，上機調試

4.1

5.sin(35.0)+x*cos(60.0)

6.6

7.0

三、改錯題

1.參考書上第二頁，算法與程序的區(qū)別

2.只能定義為一種類型

3.必須先定義，后使用

4.可以隨時修改

5.只有char型變量才只存儲一個字節(jié)

6.a還是實型變量

7.b中的值不丟失

8.i的類型不變

四、單選

1-5BDCDC6-10DCBBD11-15CBADC16-18AAA

一、簡答

1.參考書上23頁

2.while先判斷，后執(zhí)行，dowhile先執(zhí)行，后判斷，循環(huán)體至少執(zhí)行一次

3.參考書上29頁

4.continue,結束本次循環(huán)

break,結束循環(huán)

區(qū)別在于，continue只結束本次循環(huán)重新進行下次循環(huán)，而break結束整個循環(huán)

二、填空題

1.順序結構，選擇結構，循環(huán)結構

2.ifelse和switch

3.語句1,語句2

4.零

5.break,continue

6.7,0

7.>:,雙目

三、單選

1-5CBDBC6-10DBBDA11-15CBCDA16-20ACAAD

21-25ADCCB26-29BCCA

四、程序分析題

1.end1end

2.num%10max=t

3.j%3

4.99

五、編程題

1.

#include<stdio.h>

intmain(){

charstr[100J;

gets(str);

intnl,n2,n3,n4,i;

nl=n2=n3=n4=0;

for(i=0;str[i]!=f\0';++i){

if(str[i]>=W&&str[i]<=rZ*)

++nl;

elseif(str[i]>='a'&&str[ij<='z')

++n2;

elseif(str[i]>='O'&&str[i]v=9)

++n3;

else

++n4;

)

printf("大寫字母:％d\n",nl);

printf("小寫字母:％d\n",n2);

printf("數字字符:％d\n“，n3);

printf("其他字符:％d\n"，n4);

return0;

2.

#include<stdio.h>

#include<stdlib.h>

intmain(){

intarray[4],min,max,i;

for(i=0;i<4;++i)

scanf("%dn,&array[i]);

min=max=array[0];

for(i=1;i<4;++i){

if(arrayfi]<min)

min=arrayfi];

elseif(array[i]>max)

max=array[i];

)

printf("min=%d,max=%d\n",min,max);

return0;

#include<stdio.h>

intmain(){

floatmoney,lixi;

intyear;

scanf(n%f%d",&money,&year);

switch(year){

case1:

lixi=money*0.63/100;

break;

case2:

lixi=money*0.66/100;

break;

case3:

lixi=money*0.69/100;

break;

case5:

lixi=money*0.75/100;

break;

case8:

lixi=money*0.84/100;

break;

default:

printf("輸入錯誤\n“);

return-1;

printf(H%f\n",money+lixi);

return0;

#include<stdio.h>

intmain(){

intx,y;

scanf(n%d",&x);

if(x>100)

y=x+8;

elseif(x<-10)

y=-x+8;

else

y=0;

printf(,,%d\nn,y);

return0;

#include<stdio.h>

intmain(){

inti,j,k,m=3;

for(k=5;k<12;k+=2,—m){

for(i=0;i<m;++i)

printf(nn);

for(j=0;j<k;++j)

printf(n*");

printfCAn'1);

)

return0;

#include<stdio.h>

intmain(){

printf("*****\nM);

printf(H**\n");

printf(H**\n");

return0;

第三章

一、簡答

1.a：數組名，a[0]：數組第。號元素，&a[l]數組第1號元素的地

址

2.不同，"a”是字符串，末尾有一個'0'

3.2*3*2=12個字節(jié)

二、填空題

1.0

2.按行存放

3.1014

4.str[14]

5.\0'

三、改錯

1.是。

2.只能是常量

3.一定相同

4.不會給錯誤信息

5.沒有提供字符串類型

6.不等價，“ok”末尾有一個、0'

四、單選

1-5DBCAC6-10CDDCB11-13CDC

五、程序分析題

1.AzyD

2.123

3.45

4.4somestring*test

5.統(tǒng)計輸入字符串中空格的個數3,1

6.max<a[row][col]min>maxmin==max

7.aasum/nx[i]<ave

8.a[i]U]!=a[j][i]1

9.j+=2a[i]>a[j]

10.1245600000

1234560000

六、編程題

1.

#include<stdio.h>

intmain(intargc,char*argv[]){

inta[ll],i,n;

printf(”請輸入十個遞增排列的數列:");

for(i=0;i<10;++i)

scanf("%d",&a[i]);

printf("請輸入要插入的數:");

scanf("%d",&n);

for(i=9;i>=0&&a[i]>n;-i){

a[i+l]=a[i];

)

a[i+l]=n;

printf("插入后數列為:");

for(i=0;i<11;++i)

printf("%d",a[i]);

printf("\n");

return0;

)

2.

#include<stdio.h>

#include<string.h>

intmain(intargc,char*argv[]){

chara[100],b[100],min,i;

scanf("%s%s",a,b);

min=0;

for(i=1;a[i]!=\0';++i){

if(a[min]>a[i])

min=i;

)

strcat(b,a+min+1);

a[min+1]=\0';

strcat(a,b);

printf("%s\n",a);

return0;

)

3.

#include<stdio.h>

intmain(intargc,char*argv[]){

charsl[100J,chars2[100];

inti;

gets(sl);

gets(s2);

char.string1=si,*string2=s2;

do{

i=(int)*stringl-(int)*string2;

}while(*stringl++&&*string2++&&(!i));

for(i=O;sl[iJ!='\0'&&s2[i]!=\0'&&sl[i]==s2[i];++i);

printf("%d\n",i);

return0;

)

4.

#include<stdio.h>

intmain(intargc,char*argv[]){

chars[100];

inti;

gets(s);

for(i=0;s[i]!=\0';++i){

if(i==0ll(s[i-l]=="&&s[i]>='a'&&s[i]<='z'))

s[i]-=32;

puts(s);

return0;

)

5.

#include<stdio.h>

intmain(intargc,char*argv[]){

charsl[100],s2[100];

intend,i;

gets(sl);

gets(s2);

for(end=0;si[end]!='O';++end);

for(i=0;s2[i]!='\O';++i)

sl[end++]=s2[i];

sl[end]=W';

puts(sl);

return0;

第四章

一、簡答題

1.參考書上68頁，69頁，72頁

2.函數的返回值，函數的形參

3.實參與形參之間是值傳遞的關系

二、填空題

1.庫用戶自定義

2.3

3.gets()

4.strlen()

5.strcpyO

6.全局局部

7.有返回值無返回值

8.return

9.void

10.前

11.調用

三、改錯

1.表示不同的變量

2.按照調用的先后順序執(zhí)行

3.各自有自己的存儲單元

4.可以沒有形參

5.分配在動態(tài)存儲區(qū)

6.以該函數定義的返回值為準

7.嵌套調用指函數調用函數

四、單選

1-5BDACC6-10DAACC11-13BCC

五、程序分析題

1.jstrU-1]

2.本題程序是錯的，第五行，for(I=m+l;i++)這里少東西，所以跳過

3.i<nx=fun(4)

4.1:a=1,b=1

2:a=2,b=2

3:a=3,b=3

六、編程題

1.

intfun(intyear){

if(year%400==Oil(year%4==0&&year%100))

return1;

else

return0;

#include<stdio.h>

#include<math.h>

voidfunl(inta,intb,intc){

floatt=sqrt(b*b-4*a*c);

printf(uxl=%f,x2=%f\nH,(-b+t)/2.0*a,(-b-t)/2.0*a);

}

voidfun2(inta9intb9intc){

printf(Hxl=x2=%f\nK,-b/2.0*a);

voidfun3(inta,intb,intc){

printf(“該方程沒有實根”);

}

intmain(intargc,char*argv[]){

inta,b,c;

scanf(M%d%d%dH,&a,&b,&c);

if(b*b-4*a*c>0)

funl(a,b,c);

elseif(b*b-4*a*c==0)

fun2(a,b,c);

else

fun3(a,b,c);

return0;

#include<stdio.h>

#include<math.h>

intfun(inta[],intn){

intiJ=0;

for(i=1;i<n;++i)

if(i%3==0&&i%7==0)

a[j++]=i；

returnj;

)

intmain(intargc,char*argv[]){

inta[100],n,m,i;

scanf(%d,&n);

m=fun(a，n);

for(i=0;i<m;++i)

printf(H%fH,sqrt(a[i]));

return0;

第五章

一、簡答

1.不,定，這要看指針的類型，比如int*p,則p+1就增加兩個字節(jié)

2.定義指針時表示定義的變量是指針類型，引用指針時，表示指針指針指向的

變量

3.p+n,p-n淇中n是int類型

二、填空題

1.地址

2.&*

3.指針

4.*p

5.1006

6.malloc

7.a+i*(a+i)

8.3

廿'\0'

改錯題

只能存放同類型的變量的地址，比如int*只能存放int型變量的地址

這個說法是正確的，沒有錯誤

不是，指的是指針所指向的變量的類型

只能是同類型的指針或者&a這樣的地址值

是可以改變的

單選

CDDAA6-10BCDDD

程序分析題

*xt

r+b[u]*x

10

4.CDG

5.80,-20

6.5

7.55

1711717

六、編程題

#include<stdio.h>

intmain(intargc,char*argv[]){

chars[100];

inti;

gets(s);

for(i=0;s[i]!=AO1;++i);

printf(n%d\nn,i);

return0;

)

2.

#include<stdio.h>

intfun(char*s,charc){

intcount=0;

for(;*s!='\0';++s)

if(*s==c)

++count;

returncount;

)

intmain(intargc,char*argv[]){

chars[100],c;

gets(s);

c=getchar();

printf(u%s%c\n'',s,c);

printf(u%d\nH,fun(s,c));

return0;

)

3.

#include<stdio.h>

intmain(intargc,char*argv[]){

chars[100];

inti,nl，ii2,ii3,n4,n5;

nl=n2=n3=n4=n5=0;

gets(s);

for(i=0;s[i]!=AO1;++i){

if(s[i]>=*A*&&s[i]<=Z)

++nl;

elseif(s[i]>=&&s[i]v=、')

++n2;

elseif(**==s[i])

++n3;

elseif（s[i]>='O'&&s[i]<=9）

++n4;

else

++n5;

}

printf（"大寫字母:%d\n"，nl）;

printf（"小寫字母:%d\n"，n2）;

printf（"空格:％d\n”，n3）;

printf（"數字:％d\n”，n4）;

printf（”其他字符:％d\n”，n5）;

return0;

第八早

一、簡答題

1

比如定義

structStudent{

charname[100];

intage;

}stu;

則,stu.age即可引用結構體成員

2.不是必須為所有的成員賦初值，因為語法上沒有強制要求。

二、填空題

1.21&a[0]p->xa[l]

2.13

3.“ab”“cd”

三、改錯題

1.可以同名

2.可以含有

3.不可以

四、單選題

BACBDD

五、程序分析題

1.Zhao

2.10x

3.200y

4^->.

5、364020

6、max=person[i].agemin=person[i].age

六、編程施

1.

#include<stdio.h>

structScore{

floatsi;

floats2;

)；

intinain(){

structScorestu;

scanf(H%f%f*,&stu.sl,&stu.s2);

printf(M%f\nn,(stu.sl+stu.s2)/2.0);

return0;

#include<stdio.h>

structStudent{

charstuNo[50];〃學號

floatsi;〃期中成績

floats2;〃期末成績

)；

intmain(){

structStudentstu[10];

inti;

for(i=0;i<10;++i)

scanf(n%s%f%f”,stu[i].stuNo,&stu[i].sl,&stu[i].s2);

for(i=0;i<10;++i){

printf，學號:％s\n”,stu[i].stuNo);

printf("期中成績:%f\iT,stu[i].sl);

printf("期末成績:％f\n”,stu[i].s2);

printf("平均成績:％f\n”，(stu[i].sl+stu[i].s2)/2.0);

)

return0;

第七章

一、簡答題

1.D代表數據節(jié)點的集合，R是D上的關系

2.邏輯結構是數據之間的外在關系，物理結構是數據在計算機內的存儲表示

3.參考第二頁

4.不是，還于算法的設計有關，一個好的算法可以降低時間復雜度

5.O(n),O(lgn),O(nlgn),O(n的平方+1),O(n3-n2),0(n5),0(2的n次方)

二、填空題

1、邏輯物理邏輯

2、時間復雜度空間復雜度

3、線性表二叉樹圖

4、線性

5、樹型

6、111多多多

7、O(n的平方)

8、O(n)O(n)

三、改錯題

1、無關

2、有關

3、無關

4：不是，是外在的關系，與存儲結構無關

四、單選

CCBCC6題A選項改為n(n-l)

第八章

一、簡答題

1、參考132頁、135頁、136頁

2、參考139頁

3、參考139頁

4、選擇順序存儲結構，因為順序表是隨機存取，訪問任意一個元素的時間復雜

度為O(1);

5、選擇鏈式存儲，因為鏈表插入刪除的開銷小

6、循環(huán)單鏈表，循環(huán)雙鏈表

7、單鏈表無法刪除

循環(huán)單鏈表可以刪除，時間復雜度為O(n)

循環(huán)雙鏈表可以刪除，時間復雜度為0(1)

二、填空題

1、順序存儲鏈式存儲

2、O(n)

3、O(n)0(1)

4、q->next=p->nextp->next=q

5、p->nexts->datat

6、p->next=head->nexthead->next=p

7^p->next->next

8^head->next=NULL

9、p->priors->next=ps

10、0(1)

三、改錯題

1、一定相鄰

2、該說法是正確的

3、該說法是正確的

4、需要移動節(jié)點

5、不會發(fā)生溢出現(xiàn)象

6、鏈表

四、單選

AABBABCAB10題為CDABCB

五、程序分析

1、刪除單鏈表

2、p->next!=q->priorp=p->nextq=q->prior

3、count=0p=p->next

六、程序設計題

1.

#include<stdio.h>

#defineMAX100

structLink{

intdata[MAX];

intn;

}；

intfindMin(structLink*p){

intmin=0,i;

for(i=1;i<p->n;++i)

if(p->data[min]>p->data[i])

min=i;

returnmin;

}

intmain(){

inti;

structLinkL;

scanf(H%dn,&L.n);

for(i=0;i<L.n;++i)

scanf(H%du,&L.data[i]);

for(i=0;i<L.n;++i)

printf(H%dH,L.data[i]);

printf，最小值是:%d\nu,L.data[HndMin(&L)]);

return0;

)

2.

#include<stdio.h>

#defineMAX100

structLink{

intdata[MAX];

intn;

)；

voidinsert(structLink*p,intiValue){

inti=p->n-1;

while(p->data[i]>iValue){

p->data[i+l]=p->data[i];

-i；

}

p->data[i+l]=iValue;

++p->n;

)

intmain(intargc,char*argv){

structLinkL;

inti,insertValue;

scanf(H%dn,&L.n);

for(i=0;i<L.n;++i)

scanf(n%dn,&L.data[i]);

scanf(H%dn,&insertValue);

insert(&L,insertValue);

for(i=0;i<L.n;++i)

printf(H%dn,L.data[i]);

return0;

)

3.

#defineMAX100

structLink{

intdata[MAX];

intn;

)；

voiddeleteLink(structLink*p){

>nti,j,k;

for(i=0;i<p->n;++i){

for(j=i+1;p->data[j]==p->data[i]&&j<p->n;++j);

if(j!=i+l){

inttemp=j-i-1;

for(k=i+1;j<p->n;++j,++k)

p->data[k]=p->data[j];

p->n-=temp;

}

}

}s

structNode{

intdata;

structNode*next;

)；

intgetLen(structNode*p){

intn=0;

while(p!=NULL){

++n;

p=p->next;

}

returnn;

structNode{

intdata;

structNode*next;

}；

voidsetNum(structNode求p,intnl,intn2){

while(p!=NULL){

if(p->data=nl)

p->data=n2;

p=p->next;

structNode{

intdata;

structNode*next;

)；

structNode*delNode(structNode*list,intn){

intflag=1,i=1;

structNode*p=list,*q=list->next;

if(n==1){

list=list->next;

free(p);

returnlist;

)

while(q!=NULL){

++i;

if(i==n){

p->next=q->next;

free(q);

q=p->next;

returnlist;

)

q=q->next;

p=p->next;

)

returnlist;

structNode{

intdata;

structNode求next;

}；

structNode*fun(structNode*list){

structNode*p=list,*q=list->next,*min,*pMin;

inttemp;

min=list;

while(q!=NULL){

if(q->data<min->data){

min=q;

pMin=p;

p=p->next;

q=q->next;

}

if(min!=list){

pMin->next=min->next;〃刪除最小節(jié)點

〃將最小節(jié)點插入到list節(jié)點之后

min->next=list->next;

list->next=min;

〃交換list節(jié)點和min節(jié)點的值

temp=list->data;

list->data=min->data;

min->data=temp;

)

returnlist;

}

8.

structNode{

intdata;

structNode*next;

)；

structNode*fun(structNode*list){

structNode*p=list,*list2=NULL,*q;

structNode*rear=(structNode*)malloc(sizeof(structNode));〃循環(huán)鏈表

的尾指針

rear->next=rear;

while(l){

q=p->next;〃保存下一個節(jié)點的地址

〃頭插法插入p

p->next=rear->next;

rear->next=p;

p=q;

if(p==list)

break;

)

returnrear;

)

第九章

一、簡答題

1、不同：棧是先進后出，隊列是先進先出

相同：都是線性結構，都有順序實現(xiàn)和鏈式實現(xiàn)兩種

2、不能得到435612的出棧序列，原因如下

1.1234依次進棧

2.43出棧

3.5入棧

4.5出棧

5.6入棧

6.6出棧

此時棧中元素為1,2。所以若1一定在2之后出棧。

同樣的分析方法，可知，135426的出棧序列是可以的。

3、共占5*6X4=120個字節(jié)

按行排序時，起始地址為1000+2*6+5=1017

按列排序時，起始地址為1000+5*5+2=1027

二、填空題

1、判棧滿添加元素

2、判棧空刪除元素

3、-1m-1

4、空?？贞?/p>

5、n-1

6、1212

7、

三、改錯題

1、這個說法是正確的

2、有存取限制

3、這個說法是正確的

4、這個說法是正確的

5、練棧也是線性結構

四、單選

CBAC5題的題意不清BDCCAABC

五、程序設計題

1.

#include<stdio.h>

#defineMAX100

structStack{

intdata[MAX];

inttop;

intpop(structStack*s){

if(s->top!=-1)

returns->data[s->top-];

else{

printf(HErrorH);

return-1;

}

}

intpush(structStack*s,intn){

if(MAX-1!=s->top)

returns->data[++s->top]=n;

else{

printf(HErrorM);

return-1;

)

}

intmain(){

structStacks;

inti;

s.top=-1;

for(i=0;i<10;++i)

push(&s,i);

for(i=0;i<10;++i)

printf(H%d”，pop(&s));

return0;

)

#include<stdio.h>

#defineMAX100

structStack{

intdata[MAX];

inttop;

};

〃棧的出棧

intpop(structStack*s){

if(s->top!=-1)

returns->data[s->top-];

else{

printf(nErrorH);

return-1;

}

}

〃棧的入棧

intpush(structStack*s,intn){

if(MAX-1!=s->top)

returns->data[++s->top]=n;

else{

printf(HErroru);

return-1;

)

)

structStacksi;〃模擬隊列的入隊的棧

structStacks2;〃模擬隊列的出隊的棧

〃初始化函數，使兩個棧為空，使用模擬的隊列時，要先執(zhí)行該函數

voidinit(){

si.top=s2.top=-1;

}

〃用棧模擬隊列的入隊

voidenDeque(intdata){

if(sl.top!=MAX-1)

push(&sl,data);

)

〃用隊列模擬出隊

intExDeque(){

if(s2.top!=-1)

returnpop(&s2);

else{

while(sl.top!=-1){

push(&s2,pop(&sl));

)

)

returnpop(&s2);

)

3.

#include<stdio.h>

#include<string.h>

#defineMAX100

structStack{

chardata[MAX];

inttop;

);

〃棧的出棧

intpop(structStack*s){

if(s>>top!=-1)

returns->data[s->top-];

else{

printf(uErroru);

return-1;

)

)

〃棧的入棧

intpush(structStack*s,intn){

if(MAX-1!=s->top)

returns->data[++s->top]=n;

else{

printf(HErrorM);

return-1;

intmain(){

structStacks;

charstr[MAX];

intlen,i;

slop=-1;

scanf(H%sH,str);

len=strlen(str);

for(i=0;i<len/2;++i)

push(&s,str[i]);

if(len%2)

++i;

for(;i<len;++i)

if(pop(&s)!=str[i])

break;

if(i==len)

printfC是回文數，，);

else

printf("不是回文數”);

return0;

)

4.

Push(l)Pop(l)Push(2)Pop(2)Push(3)Pop(3)此時輸出序列為1

23

Push(l)push(2)pop(2)pop(l)push(3)pop(3)此時輸出序列為213

Push(l)push(2)pop(2)push(3)pop(3)pop(2)pop(3)此時輸出序列為231

Push(l)push(2)push(3)pop(3)pop(2)pop(l)此時輸出為321

算法實現(xiàn)就是按上述步驟進行，就省略了

#include<stdio.h>

#include<string.h>

#defineMAX100

structStack{

chardata[MAX];

inttop;

)；

〃棧的出棧

intpop(structStack*s){

if(s->top!=-1)

returns->data[s->top-];

else(

printf(nErrorH);

return-1;

)

)

〃棧的入棧

intpush(structStack*s,intn){

if(MAX-1!=s->top)

returns->data[++s->top]=n;

else(

printf(HErrorM);

return-1;

)

)

intmain(){

structStacks;

charstr[MAX];

inti;

charch;

s.top=-1;

scanf(H%sH,str);

for(i=0;str[i]!=AO*;++i){

if(，C==str[i])

push(&s,str[i]);

elseif(*)*==str[i]){

if(-l==s.top)

break;

ch=pop(&s);

if(ch!=?(1)

break;

}

}

if(str[i]!='\0'II-1!=s.top)

printf("不匹配\n");

else

printf("匹配\n”)；

return0;

}

第十章

一、簡答題

1、參考161頁

2、公式不好寫，算法就是根據161頁性質4算出深度h,然后根據160頁性質

1求得葉子節(jié)點的個數

3、根據性質1,我們可以算出完全二叉樹的第八層上的節(jié)點的最大值應該比8

大，所以第八層是最大層，由8個節(jié)點推出上一層的葉子節(jié)點數，相加即可

4、不好畫圖，這道題目自己研究一下吧。

5、(1)根節(jié)點A,葉子節(jié)點CEFHIJKMN非終端節(jié)點ABDGL

(2)樹的度為3,各節(jié)點的度A3,B2,CO,D4,EFHIJKMN為0,G為3,

L為1。

(3)樹的深度是5,個節(jié)點深度Al,BCD2,EFGHIJ3,KLM

4,N5

6、a:011b:10c:00d:010e:11

帶權路徑長度為60

二、填空題

1、參考160頁

2、n—1

3、根前驅節(jié)點后繼

4、6

5、6

6、5

7、空二叉樹、僅有根節(jié)點的二叉樹、有子樹為空的二叉樹、左右子樹不為空的

二叉樹。左子樹為空的二叉樹

8、2的i—l次方(公式在word里不好寫)

9、487

10、n-2m+2

11、n-1

三、改錯

l^不能唯一確定

2、大于等于0小于等于2

3、這個說法是正確的

4、是相同的

四、單選

BCDBBDCD

五、算法設計題

1.

寫一下思路

利用隊列來處理，隊列的數據類型為

Struct{

StructNode*p;〃二叉樹的節(jié)點

Intfloor;//二叉樹的層次

)

設二叉樹的根節(jié)點為t,

n存儲節(jié)點的高度,初值置0

EnQueue(t)//樹根入隊,注意樹根節(jié)點要存儲在上面的結構體中，且floor=1

While(隊列不為空的時候){

Temp=ExQueue();〃出隊

//左孩子入隊，入隊前判斷是否為空，左孩子的floor=temp.n+1

EnQueue(temp->left)

〃右孩子入隊，入隊前判斷是否為空左孩子的floor=temp.ii+1

EnQueue(temp->left)〃右孩子入隊，入隊前判斷是否為空

)

最后一個出隊的節(jié)點的n值就是樹的高度

2.參考168頁總結2下面的例題，參數n應該變成全局變量

3.和第一題一樣，第一題就是按照層次遍歷的

4.

完全二叉樹的定義是最后一層從右到左缺少節(jié)點，

所以設flag=1表示所有的節(jié)點都有左右孩子節(jié)點

按層次遍歷二叉表，當遍歷到一個節(jié)點時，判斷是否有左右孩子節(jié)點，此時有

如下情況

1.沒有左右孩子節(jié)點或只有左節(jié)點，則后面的所有節(jié)點都應該是葉子節(jié)點，

此時flag=0,之后的每個節(jié)點都判斷是否為葉子節(jié)點，若都是，則為完

全二叉樹

2.若只有右節(jié)點，則不是完全二叉樹

二叉樹算法設計題考的最多的應該是遞歸遍歷，所有這幾道題看看就可以了

十一章

一、簡答

1、不唯一，同時存在若干個權值相同的邊時

2^都有關

3、深度：V1,v2,v3,v5,v4,v6,v7

廣度：vl,v2,v6,v3,v4,v7,v5

4、參考181頁

5、參考182頁

6、參考127頁

二、填空題

1、2

2、n—12/l*n(n-l)

3、1

4、出入

5、最小n-1

6、2e

7、頂點

8、i行為0

9、a,e,b,d,e,f

10、先根

11、層次

12、鄰接矩陣鄰接鏈表

三、改錯

1、正確的

2、2n個表節(jié)點

3、不等于

4、先根遍歷

5、正確的

6、完全有向圖對稱

四、單選

BBBAC

第十二章

一、簡答題

1.順序查找：必須為線性表

折半查找：必須為順序存儲結構，且有序

順序查找平均查找次數為n/2

折半查找平均查找次數在194頁第四行，因為公式不好寫，在書上查吧

2

查3時，4次

查8時，1次

查19時，4次

3.第一種7531498

第二種7598314

第三種7593148

第四種7953148

第五種7958314

此題不要背答案，主要理解二叉排序樹的構建過程

二、填空題

1.619

2.O(n)

3.插入排序

4.n—1

5.線性表的長度

三、改錯

1.不唯一

2.有關，參看簡答第一題

3?鏈式存儲也可以

4.該說法是正確的。

四、選擇

C第二題不會，呵呵.BAD

五、算法設計題

1.

#include<stdio.h>

#defineMAX100

structLink{

intdata[MAX];

intn;

)；

intserarch(Link*list,intsearchValue){

inti;

list->data[list->n]=searchValue;

for(i=1;list->data[i]!=list->data[list->n];++i);

returni;

)

intmain(){

structLink1;

inti,nl9n2;

scanf(H%dH,&l.n);

for(i=0;i<Ln;++i)

scanf(n%dM,&l.data[i]);

scanf(H%dn,&nl);

n2=serarch(&l,nl);

if(n2!=Ln+1)

printf(H%d\nH,n2);

return0;

structNode{

intdata;

structNode*left;