北大“數據結構”上機考試復習題總結（2）

數據結構練習題4

1. 編一C程序，它能根據輸入的二叉樹中序和后序序列來構造該二叉樹，并能輸出該二叉樹的前序序列和該二叉樹的度為2的結點的個數并能判斷該二叉樹是否為二叉排序樹（若是輸出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程序，它能讀入一串整數（以-9999為結束標記），再以與輸入次序相反的次序輸出這串整數（輸入、出時，兩個相鄰的整數用空格隔開）。

（注：程序的可執(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”）；

}

數據結構練習題5

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

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

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

（注：程序的可執(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（“請輸入數組a： \n”）；

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

{

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

if（a[i]==-9999）

break；

}

countA=i-1；

paixu（a，countA）；

printf（“請輸入數組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”）；