北大“數(shù)據(jù)結(jié)構(gòu)”上機考試復習題總結(jié)（2） -自考串講筆記

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

　　1. 編一C程序，它能根據(jù)輸入的二叉樹中序和后序序列來構(gòu)造該二叉樹，并能輸出該二叉樹的前序序列和該二叉樹的度為2的結(jié)點的個數(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為結(jié)束標記），再以與輸入次序相反的次序輸出這串整數(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ù)結(jié)構(gòu)練習題5

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

　?。ㄗⅲ撼绦虻目蓤?zhí)行文件名必須是 e1.exe，存于你的賬號或其debug目錄下，否則無成績）

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