北大“數(shù)據(jù)結(jié)構(gòu)”上機考試復習題總結(jié)二

北大”數(shù)據(jù)結(jié)構(gòu)〃上機考試復習題總結(jié)（2）

數(shù)據(jù)結(jié)構(gòu)練習題4

1.編一C程序，它能根據(jù)輸入的二叉樹中序和后序序列來構(gòu)造該二叉樹，并能輸出該二叉

樹的前序序列和該二叉樹的度為2的結(jié)點的個數(shù)并能判斷該二叉樹是否為二叉排序樹（若是

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

（注：程序的可執(zhí)行文件名必須是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程序，它能讀入一串整數(shù)(以-9999為結(jié)束標記)，再以與輸入次序相反的次序輸

出這串整數(shù)(輸入、出時，兩個相鄰的整數(shù)用空格隔開)。

(注：程序的可執(zhí)行文件名必須是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")；

數(shù)據(jù)結(jié)構(gòu)練習題5

1.編一C程序，它能讀入一個大寫英文字母串（字母個數(shù)不多于100,字母兩兩不同），

并構(gòu)造以這些字母為關(guān)鍵字的二叉排序樹，再輸出該二叉排序樹的后序序列和頁結(jié)點個數(shù)。

（注：程序的可執(zhí)行文件名必須是el.exe,存于你的賬號或其debug目錄下，否則無成績）

2.編一C程序，它能讀入兩組整數(shù)（每組整數(shù)都以-9999為結(jié)束標記，-9999不算在內(nèi)。個

數(shù)都不大于1000）,并以從小到大的次序輸出既在第一組整數(shù)中也在第二組整數(shù)中的所有整

數(shù)（同一個整數(shù)不能輸出兩次）。（輸入時，兩個相鄰的整數(shù)用空格隔開）。

（注：程序的可執(zhí)行文件名必須是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(“請輸入數(shù)組a：\n")；

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

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

if(a[i]==-9999)

break；

)

countA=i-l；

paixu(a,countA)；

printf(〃請輸入數(shù)組b：\n〃)；

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

(

scanf("%d",b[i]