北大“數(shù)據(jù)結構”上機考試復習題總結（2）

數(shù)據(jù)結構練習題4

1. 編一C程序，它能根據(jù)輸入的二叉樹中序和后序序列來構造該二叉樹，并能輸出該二叉樹的前序序列和該二叉樹的度為2的結點的個數(shù)并能判斷該二叉樹是否為二叉排序樹（若是輸出Yes；否則輸出No）。（輸入次序是：表示中序序列的字母串、表示后序序列的字母串）。

（注：程序的可執(zhí)行文件名必須是 e1.exe，存于你的賬號或其debug目錄下。）

#include stdio.h

#include malloc.h

#include string.h

void exit（int）；

#define MAX 100

typedef struct node{

char d；

struct node *lchild，*rchild；

}Tnode；

void MKTree（char in[]，int is，int ie，char post[]，int posts，int poste，Tnode **r）

{

int i；

if（is ie||posts poste）

*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）- lchild）；

MKTree（in，i+1，ie，post，posts+i-is，poste-1， （*r）- rchild）；

break；

}

if（i ie）{

printf（“Error：input contain an error ！\n”）；

exit（9）；

}

}

}

void BST（char in[]，int is，int ie）

{

int i；

if（is==ie）

printf（“yes\n”）；

else

{

for（i=is；i =ie；i++）

{

if（in[i] in[i+1]）

continue；

else

break；

}

if（i==ie）

printf（“YES\n”）；

else

printf（“NO\n”）；

}

}

void preorder（Tnode *r）

{

if（r）

{

printf（“%c”，r- d）；

preorder（r- lchild）；

preorder（r- rchild）；

}

}

int seconde（Tnode *r）

{

if（r==NULL）

return 0；

else

if（（r- lchild）！=NULL （r- rchild）！=NULL）

return 1；

else

return seconde（r- lchild）+seconde（r- rchild）；

}

void main（）

{

Tnode *r；

char post[MAX]，in[MAX]；

printf（“input inorder and postorder ！\n”）；

gets（in）；

gets（post）；

MKTree（in，0，strlen（in）-1，post，0，strlen（post）-1， r）；

printf（“the preorder is as follows：\n”）；

preorder（r）；

printf（“\n there are %d seconde in the tree \n”，seconde（r））；

printf（“if the tree is BST：\n”）；

BST（in，0，strlen（in）-1）；

}

2.編一C程序，它能讀入一串整數(shù)（以-9999為結束標記），再以與輸入次序相反的次序輸出這串整數(shù)（輸入、出時，兩個相鄰的整數(shù)用空格隔開）。

（注：程序的可執(zhí)行文件名必須是 e2.exe，存于你的賬號或其debug目錄下。）

#include stdio.h

#define max 10000

main（）

{

int a[max]；

int n=0，i，d；

printf（“please enten tne number：\n”）；

do{

scanf（“%d”， d）；

if（d==-9999）

break；

n++；

a[n]=d；

}while（9）；

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

printf（“%4d”，a[i]）；

printf（“\n”）；

}

數(shù)據(jù)結構練習題5

1. 編一C程序，它能讀入一個大寫英文字母串（字母個數(shù)不多于100，字母兩兩不同），并構造以這些字母為關鍵字的二叉排序樹，再輸出該二叉排序樹的后序序列和頁結點個數(shù)。

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

2. 編一C程序，它能讀入兩組整數(shù)（每組整數(shù)都以-9999為結束標記，-9999不算在內。個數(shù)都不大于1000），并以從小到大的次序輸出既在第一組整數(shù)中也在第二組整數(shù)中的所有整數(shù)（同一個整數(shù)不能輸出兩次）。（輸入時，兩個相鄰的整數(shù)用空格隔開）。

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

#include stdio.h

void paixu（int r[]，int n）

{

int i，j，k；

int exchange；

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

{

exchange=0；

for（j=n-1；j =i；j——）

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

{

k=r[j+1]；

r[j+1]=r[j]；

r[j]=k；

exchange=1；

}

if（！exchange）

break；

}

}

int jiaoji（int m[]，int n[]，int l[]，int countaa，int countbb）

{

int w，x，y；

int i=0，j=0，k=0；

for（w=0；w =countaa；w++）

{

for（x=w+1；x =countaa；x++）

{

if（m[w]==m[x]）

{

countaa——；

for（y=x；y =countaa；y++）

{

m[y]=m[y+1]；

}

x——；

}

}

}

while（i =countaa）

{

for（j=0；j =countbb；j++）

{

if（m[i]==n[i]）

{

l[k]=m[i]；

k++；

break；

}

}

i++；

}

return k；

}

void main（）

{

int a[1000]，b[1000]，c[2000]；

int excange=0，i，countA，countB，countC；

printf（“請輸入數(shù)組a： \n”）；

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

{

scanf（“%d”， a[i]）；

if（a[i]==-9999）

break；

}

countA=i-1；

paixu（a，countA）；

printf（“請輸入數(shù)組b： \n”）；

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

{

scanf（“%d”， b[i]）；

if（b[i]==-9999）

break；

}

countB=i-1；

paixu（b，countB）；

countC=jiaoji（a，b，c，countA，countB）；

printf（“\n\n”）；

for（i=0；i =countC-1；i++）

printf（“%d”，c[i]）；

printf（“\n”）；