计算机软件基础课后习题答案

第一章

一、简答题

1.参考书上第五页图1—7

2.因为C语言是强类型语言，语法规定必须先定义后使用，只有先定义，系统才

能为其分配存储空间。

3.参考书上第二页

二、填空题

1.算法

2..C,.obj,.exe

3.提出问题，构造模型，选择方法，编写程序，上机调试

4.1

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

6.6

7.0

三、改错题

1.参考书上第二页，算法与程序的区别

2.只能定义为一种类型

3.必须先定义，后使用

4.可以随时修改

5.只有char型变量才只存储一个字节

6.a还是实型变量

7.b中的值不丢失

8.i的类型不变

四、单选

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

一、简答

1.参考书上23页

2.while先判断，后执行，dowhile先执行，后判断，循环体至少执行一次

3.参考书上29页

4.continue,结束本次循环

break,结束循环

区别在于，continue只结束本次循环重新进行下次循环，而break结束整个循环

二、填空题

1.顺序结构，选择结构，循环结构

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个字节

二、填空题

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.统计输入字符串中空格的个数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.按照调用的先后顺序执行

3.各自有自己的存储单元

4.可以没有形参

5.分配在动态存储区

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就增加两个字节

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代表数据节点的集合，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、循环单链表，循环双链表

7、单链表无法删除

循环单链表可以删除，时间复杂度为O(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、需要移动节点

5、不会发生溢出现象

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;〃删除最小节点

〃将最小节点插入到list节点之后

min->next=list->next;

list->next=min;

〃交换list节点和min节点的值

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));〃循环链表

的尾指针

rear->next=rear;

while(l){

q=p->next;〃保存下一个节点的地址

〃头插法插入p

p->next=rear->next;

rear->next=p;

p=q;

if(p==list)

break;

)

returnrear;

)

第九章

一、简答题

1、不同：栈是先进后出，队列是先进先出

相同：都是线性结构，都有顺序实现和链式实现两种

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

1.1234依次进栈

2.43出栈

3.5入栈

4.5出栈

5.6入栈

6.6出栈

此时栈中元素为1,2。所以若1一定在2之后出栈。

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

3、共占5*6X4=120个字节

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

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

二、填空题

1、判栈满添加元素

2、判栈空删除元素

3、-1m-1

4、空栈空队

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;〃模拟队列的出队的栈

〃初始化函数，使两个栈为空，使用模拟的队列时，要先执行该函数

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

算法实现就是按上述步骤进行，就省略了

#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求得叶子节点的个数

3、根据性质1,我们可以算出完全二叉树的第八层上的节点的最大值应该比8

大，所以第八层是最大层，由8个节点推出上一层的叶子节点数，相加即可

4、不好画图，这道题目自己研究一下吧。

5、(1)根节点A,叶子节点CEFHIJKMN非终端节点ABDGL

(2)树的度为3,各节点的度A3,B2,CO,D4,EFHIJKMN为0,G为3,

L为1。

(3)树的深度是5,个节点深度Al,BCD2,EFGHIJ3,KLM

4,N5

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

带权路径长度为60

二、填空题

1、参考160页

2、n—1

3、根前驱节点后继

4、6

5、6

6、5

7、空二叉树、仅有根节点的二叉树、有子树为空的二叉树、左右子树不为空的

二叉树。左子树为空的二叉树

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;〃二叉树的节点

Intfloor;//二叉树的层次

)

设二叉树的根节点为t,

n存储节点的高度,初值置0

EnQueue(t)//树根入队,注意树根节点要存储在上面的结构体中，且floor=1

While(队列不为空的时候){

Temp=ExQueue();〃出队

//左孩子入队，入队前判断是否为空，左孩子的floor=temp.n+1

EnQueue(temp->left)

〃右孩子入队，入队前判断是否为空左孩子的floor=temp.ii+1

EnQueue(temp->left)〃右孩子入队，入队前判断是否为空

)

最后一个出队的节点的n值就是树的高度

2.参考168页总结2下面的例题，参数n应该变成全局变量

3.和第一题一样，第一题就是按照层次遍历的

4.

完全二叉树的定义是最后一层从右到左缺少节点，

所以设flag=1表示所有的节点都有左右孩子节点

按层次遍历二叉表，当遍历到一个节点时，判断是否有左右孩子节点，此时有

如下情况

1.没有左右孩子节点或只有左节点，则后面的所有节点都应该是叶子节点，

此时flag=0,之后的每个节点都判断是否为叶子节点，若都是，则为完

全二叉树

2.若只有右节点，则不是完全二叉树

二叉树算法设计题考的最多的应该是递归遍历，所有这几道题看看就可以了

十一章

一、简答

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个表节点

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;