北大“数据结构”上机考试复习题总结二

北大”数据结构〃上机考试复习题总结（2）

数据结构练习题4

1.编一C程序，它能根据输入的二叉树中序和后序序列来构造该二叉树，并能输出该二叉

树的前序序列和该二叉树的度为2的结点的个数并能判断该二叉树是否为二叉排序树（若是

输出Yes；否则输出No）。（输入次序是：表示中序序列的字母串、表示后序序列的字母串）。

（注：程序的可执行文件名必须是el.exe,存于你的账号或其debug目录下。）

#includestdio.h

#includemalloc.h

#includestring.h

voidexit（int）；

#defineMAX100

typedefstructnode{

chard；

structnode*lchild,*rchild；

}Tnode；

voidMKTree（charin[],intis,intie,charpost[],intposts,intposte,Tnode**r）

（

inti；

if（isie||postsposte）

*r=NULL；

else{

*r=malloc(sizeof(Tnode))；

(*r)-d=post[poste]；

for(i=is；i=ie；i++)

if(post[poste]==in[i])

(

MKTree(in,is,i-1,post,posts,posts+i-is-1,(*r)-Ichild)；

MKTree(in,i+1,ie,post,posts+i-is,poste-1,(*r)-rchild)；

break；

)

if(iie){

printf("Error：inputcontainanerror!\n〃)；

exit(9)；

voidBST(charin[],intis,intie)

(

inti；

if(is==ie)

printf(〃yes\n〃)；

else

for(i=is；i=ie；i++)

if(in[i]in[i+l])

continue；

else

break；

)

if(i==ie)

printf(〃YES\n〃)；

else

printf(〃NO\n〃)；

)

)

voidpreorder(Tnode*r)

(

if(r)

(

printf(〃％c〃，r-d)；

preorder(r-Ichild)；

preorder(r-rchild)；

intseconde(Tnode*r)

if(r==NULL)

return0；

else

if((r-Ichild)!=NULL(r-rchild)!=NULL)

return1；

else

returnseconde(r-Ichild)+seconde(r-rchild)；

)

voidmain()

(

Tnode*r；

charpost[MAX],in[MAX]；

printf("inputinorderandpostorder!\n")；

gets(in)；

gets(post)；

MKTree(in,0,strlen(in)-1,post,0,strlen(post)-1,r)；

printf("thepreorderisasfollows：\n〃)；

preorder(r)；

printf(Anthereare%dsecondeinthetree\n,/,seconde(r))；

printf(z1fthetreeisBST：\nw)；

BST(in,0,strlen(in)-1)；

2.编一C程序，它能读入一串整数(以-9999为结束标记)，再以与输入次序相反的次序输

出这串整数(输入、出时，两个相邻的整数用空格隔开)。

(注：程序的可执行文件名必须是e2.exe,存于你的账号或其debug目录下。)

#includestdio.h

#definemax10000

main()

(

inta[max]；

intn=0,i,d；

printf(zzpleaseententnenumber：\n")；

do{

scanf("%d〃，d)；

if(d==-9999)

break；

n++；

a[n]=d；

}while(9)；

for(i=n；i0；i-----)

printf(〃%4d〃，a[i])；

printf(An")；

数据结构练习题5

1.编一C程序，它能读入一个大写英文字母串（字母个数不多于100,字母两两不同），

并构造以这些字母为关键字的二叉排序树，再输出该二叉排序树的后序序列和页结点个数。

（注：程序的可执行文件名必须是el.exe,存于你的账号或其debug目录下，否则无成绩）

2.编一C程序，它能读入两组整数（每组整数都以-9999为结束标记，-9999不算在内。个

数都不大于1000）,并以从小到大的次序输出既在第一组整数中也在第二组整数中的所有整

数（同一个整数不能输出两次）。（输入时，两个相邻的整数用空格隔开）。

（注：程序的可执行文件名必须是e2.exe,存于你的账号或其debug目录下，否则无成绩）

Wincludestdio.h

voidpaixu（intr[],intn）

（

inti,j,k；

intexchange；

for（i=0；i=n；i++）

（

exchange=0；

for（j=n-l；j=i；j-----）

if（r[j+l]r[j]）

（

k=r[j+l]；

r[j+l]=r[j];

r[j]=k；

exchange=l；

if(!exchange)

break；

)

}

intjiaoji(intm[],intn[],intl[],intcountaa,intcountbb)

(

intw,x,y；

inti=0,j=0,k=0；

for(w=0；w=countaa；w++)

(

for(x=w+l；x=countaa；x++)

(

if(m[w]==m[x])

(

countaa-----；

for(y=x；y=countaa；y++)

(

m[y]=m[y+l]；

)

x-----；

)

)

while(i=countaa)

for(j=0；j=countbb；j++)

(

if(m[i]==n[i])

(

l[k]=m[i]；

k++；

break；

)

)

i++;

)

returnk；

)

voidmain()

(

inta[1000],b[1000],c[2000]；

intexcange=0,i,countA,countB,countC；

printf(“请输入数组a：\n")；

for(i=0；i=1000；i++)

scant("%d〃，a[i])；

if(a[i]==-9999)

break；

)

countA=i-l；

paixu(a,countA)；

printf(〃请输入数组b：\n〃)；

for(i=0；i=1000；i++)

(

scanf("%d",b[i]