計算機軟件基礎(chǔ)一課后習(xí)題答案

第一章

-、簡答題

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

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

能為其分配存儲空間。

3.參考書上第二頁

二、填空題

1.算法

2..C,.obj,.exe

3.提出問題，構(gòu)造模型，選擇方法，編寫程序，上機調(diào)試

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,結(jié)束本次循環(huán)

break,結(jié)束循環(huán)

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

二、填空題

1.順序結(jié)構(gòu)，選擇結(jié)構(gòu)，循環(huán)結(jié)構(gòu)

2.ifelse和switch

3.語句1,語句2

4.零

5.break,continue

6.7,0

7.>:,雙目

三、單選

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

21-25ADCCB26-29BCCA

四、程序分析題

1.endlend

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]!=;++i){

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

++nl;

elseif(str[i]>='a'&&strfi]v=2)

++n2;

elseif(str[i]>=*0*&&str[i]<=9)

++n3;

else

++n4;

)

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

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

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

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

return0;

#include<stdio.h>

#include<stdlib.h>

intmain(){

intarray[4],min,max,i;

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

scanf(H%dM,&array[i]);

min=max=array[OJ;

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

if(arrayfi]<min)

min=array[ij;

elseif(array[i]>max)

max=arrayfi];

)

printf(Mmin=%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(0%f\n",money+lixi);

return0;

#include<stdio.h>

intmain(){

intx,y;

scanf(n%dH,&x);

if(x>100)

y=x+8;

elseif(x<-10)

y=-x+8;

else

y=o;

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

return0;

5.

#include<stdio.h>

intmain(){

inti,j,k,m=3;

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

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

printfC'n);

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

printf(,,*K);

printfC'Xn");

)

return0;

#include<stdio.h>

intmain(){

printf(M*****3”)；

printf(H**\n");

printf(H**\n");

return0;

第三章

一、簡答

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

址

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

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

二、填空題

1.0

2.按行存放

3.1014

4.str[14]

5.

三、改錯

1.是。

2.只能是常量

3.一定相同

4.不會給錯誤信息

5.沒有提供字符串類型

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

四、單選

1-5DBCAC6-10CDDCB11-13CDC

五、程序分析題

1.AzyD

2.123

3.45

4.4somestring*test

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

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

7.aasum/nx[i]<ave

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

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

10.1245600000

1234560000

六、編程題

1.

#include<stdio.h>

intmain(intargc,char*argv[]){

inta[ll],i,n;

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

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

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

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

scanf("%d",&n);

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

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

)

a[i+l]=n;

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

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

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

printf("\n");

return0;

#include<stdio.h>

#include<string.h>

intmain(intargc,char*argv[]){

chara[100],b[100J,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]=W;

strcat(a,b);

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

return0;

)

3.

#include<stdio.h>

intmain(intargc,char*argv[]){

charsl[100],chars2[100];

inti;

gets(sl);

gets(s2);

char*stringl=si,*string2=s2;

do{

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

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

for(i=0;sl[i]!=A0'&&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]!=W';++i){

if(i==0II(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)

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

sl[end]=\O';

puts(sl);

return0;

第四章

一、簡答題

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

2.函數(shù)的返回值，函數(shù)的形參

3.實參與形參之間是值傳遞的關(guān)系

二、填空題

1.庫用戶自定義

2.3

3.gets()

4.strlen()

5.strcpyO

6.全局局部

7.有返回值無返回值

8.return

9.void

10.前

11.調(diào)用

三、改錯

1.表示不同的變量

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

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

4.可以沒有形參

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

6.以該函數(shù)定義的返回值為準

7.嵌套調(diào)用指函數(shù)調(diào)用函數(shù)

四、單選

1-5BDACC6-10DAACC11-13BCC

五、程序分析題

1.jstr[j-l]

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

3.i<nx=fun(4)

4.1:a=1,b=1

2:a=29b=2

3:a=3,b=3

六、編程題

1.

intfun(intyear){

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

return1;

else

return0;

}

2.

#include<stdio.h>

#include<math.h>

voidfunl(inta,intb,intc){

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

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

}

voidfun2(inta,intb,intc){

printf(nxl=x2=%Ann,-b/2.0*a);

)

voidfun3(inta,intb,intc){

printf，該方程沒有實根”)；

intmain(intargc,char*argv[]){

inta,b9c;

scanf(n%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;

}

3.

#include<stdio.h>

#include<math.h>

intfun(inta[],intn){

inti,j=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(H%dH,&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

9.，b'‘\0'

三、改錯題

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

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

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

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

5.是可以改變的

四、單選

1-5CDDAA6-10BCDDD

五、程序分析題

2.r+b[u]

3.10

4.CDG

5.80,-20

6.5

7.55

1711717

六、編程題

1.

#include<stdio.h>

intmain(intargc,char*argv[]){

chars[100];

inti;

gets(s);

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

printf(u%d\nH,i);

return0;

)

2.

#include<stdio.h>

intfun(char*s,charc){

intcount=0;

for(;*s!=AO*;++s)

if(*s==c)

++count;

returncount;

}

intmain(intargc,char*argv[]){

chars[100],c;

gets(s);

c=getchar();

printf(n%s%c\nH,s,c);

printf(H%d\nn,fun(s,c));

return0;

)

3.

#include<stdio.h>

intmain(intargc,char*argv[]){

chars[100];

inti,nl,n2,n3,n4,n5;

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

gets(s);

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

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

++nl;

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

++n2;

elseif(',==s[i])

++n3;

elseif(s[i]>='O'&&s[i]<='9')

++n4;

else

++n5;

}

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

printf（"小寫字母:％d\n”,n2）;

printff'空格:％d\n”，n3）;

printf（"數(shù)字:％d\n”,n4）;

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

return0;

}

第八章

一、簡答題

1

比如定義

structStudent{

charname[100];

intage;

}stu;

則,stu.age即可引用結(jié)構(gòu)體成員

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;

)；

intmain(){

structScorestu;

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

printf(n%f\nM,(stu.sl+stu.s2)/2.0);

return0;

)

2.

#include<stdio.h>

structStudent{

charstuNo[50];〃學(xué)號

floatsi;〃期中成績

floats2;〃期末成績

)；

intmain(){

structStudentstu[10];

inti;

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

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

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

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

printf(“期中成績:％f\n”,stu[i].sl);

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

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

)

return0;

)

第七章

一、簡答題

1.D代表數(shù)據(jù)節(jié)點的集合，R是D上的關(guān)系

2.邏輯結(jié)構(gòu)是數(shù)據(jù)之間的外在關(guān)系，物理結(jié)構(gòu)是數(shù)據(jù)在計算機內(nèi)的存儲表示

3.參考第二頁

4.不是，還于算法的設(shè)計有關(guān)，一個好的算法可以降低時間復(fù)雜度

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

二、填空題

1、邏輯物理邏輯

2、時間復(fù)雜度空間復(fù)雜度

3、線性表二叉樹圖

4、線性

5、樹型

6、111多多多

7、O(n的平方)

8、O(n)O(n)

三、改錯題

1、無關(guān)

2、有關(guān)

3、無關(guān)

4、不是，是外在的關(guān)系，與存儲結(jié)構(gòu)無關(guān)

四、單選

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

第八章

一、簡答題

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

2、參考139頁

3、參考139頁

4、選擇順序存儲結(jié)構(gòu)，因為順序表是隨機存取，訪問任意一個元素的時間復(fù)雜

度為O(1);

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

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

7、單鏈表無法刪除

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

循環(huán)雙鏈表可以刪除，時間復(fù)雜度為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

六、程序設(shè)計題

1.

#include<stdio.h>

#defineMAX100

structLink{

intdata[MAX];

int9

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(u%dH,&L.n);

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

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

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

printf(n%dM,L.data[i]);

printf("最小值是：%d\nH,L.data[findMin(&L)]);

return0;

#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%dH,&L.n);

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

scanf(H%du,&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){

inti,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;

)

7.

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、不同：棧是先進后出，隊列是先進先出

相同：都是線性結(jié)構(gòu)，都有順序?qū)崿F(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、判?？談h除元素

3、-1m-1

4、空?？贞?/p>

5、n-1

6^1212

7、

三、改錯題

1、這個說法是正確的

2、有存取限制

3、這個說法是正確的

4、這個說法是正確的

5、練棧也是線性結(jié)構(gòu)

四、單選

CBAC5題的題意不清BDCCAABC

五、程序設(shè)計題

1.

#include<stdio.h>

#defineMAX100

structStack{

intdata[MAX];

inttop;

}；

intpop(structStack*s){

if(s>>top!=-1)

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

else{

printf(MErrorM);

return-1;

)

)

intpush(structStack*s，intn){

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

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

else{

printf(HErroru);

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%dn,pop(&s));

return0;

#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(HErrorn);

return-1;

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

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

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

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(HErrorn);

return-1;

)

}

〃棧的入棧

intpush(structStack*s,intn){

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

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

else{

printf(HErrorH);

return-1;

intinain(){

structStacks;

charstr[MAX];

intlen,i;

s.top=-1;

scanf(H%sM,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)

printf,是回文數(shù)”);

else

printf("不是回文數(shù)”)；

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)就是按上述步驟進行，就省略了

5.

#include<stdio.h>

#include<string.h>

#defineMAX100

structStack{

chardata[MAX];

inttop;

);

〃棧的出棧

intpop(structStack*s){

if(s->top!=-1)

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

else{

printf(uErrorH);

return-1;

)

}

〃棧的入棧

intpush(structStack*s,intn){

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

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

else{

printf(HErroru);

return-1;

)

)

intmain(){

structStacks;

charstr[MAX];

inti;

charch;

s.top=-1;

scanf(H%sM,str);

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

==str[i])

push(&s,str[i]);

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

if(-l==s.top)

break;

ch=pop(&s);

if(ch!='(')

break;

)

}

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

printf("不匹配\n”);

else

printf("匹配\n");

return0;

}

第十章

一、簡答題

1、參考161頁

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

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

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

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

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

帶權(quán)路徑長度為60

二、填空題

1、參考160頁

2、n—1

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

4、6

5、6

6、5

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

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

8^2的i—1次方（公式在word里不好寫）

9、487

10-,n-2m+2

11、n-1

三、改錯

1、不能唯一確定

2、大于等于。小于等于2

3、這個說法是正確的

4、是相同的

四、單選

BCDBBDCD

五、算法設(shè)計題

1.

寫一下思路

利用隊列來處理，隊列的數(shù)據(jù)類型為

Struct{

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

Intfloor;〃二叉樹的層次

}

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

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

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

While（隊列不為空的時候）{

Temp=ExQueue();〃出隊

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

EnQueue(temp->left)

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

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

}

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

2.參考168頁總結(jié)2下面的例題，參數(shù)n應(yīng)該變成全局變量

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

4.

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

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

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

如下情況

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

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

全二叉樹

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

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

十一章

一、簡答

1、不唯一，同時存在若干個權(quán)值相同的邊時

2、都有關(guān)

3、深度：VI,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、先根

n、層次

12、鄰接矩陣鄰接鏈表

三、改錯

1、正確的

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

3、不等于

4、先根遍歷

5、正確的

6、完全有向圖對稱

四、單選

BBBAC

第十二章

一、簡答題

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

折半查找：必須為順序存儲結(jié)構(gòu)，且有序

順序查找平均查找次數(shù)為n/2

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

2

查3時，4次

查8時，1次

查19時，4次

3.第一種7531498

第二種7598314

第三種7593148

第四種7953148

第五種7958314

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

二、填空題

1.619

2.O(n)

3.插入排序

4.n—1

5.線性表的長度

三、改錯

1.不唯一

2.有關(guān)，參看簡答第一題

3.鏈式存儲也可以

4.該說法是正確的。

四、選擇

C第二題不會，呵呵.BAD

五、算法設(shè)計題

1.

#include<stdio.h>

#defineMAX100

structLink{

intdata[MAX];

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(u%dn,&l.n);

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

scanf(H%dH,&l.data[i]);

scanf(n%dn,&nl);

n2=serarch(&l,nl);

if(n2!=l.n+1)

printf(H%d\nn,n2);

return0;

)

structNode{

intdata;

structNode*left;