北大“数据结构”上机考试复习题总结（2） -自考串讲笔记

　　数据结构练习题4

　　1. 编一C程序，它能根据输入的二叉树中序和后序序列来构造该二叉树，并能输出该二叉树的前序序列和该二叉树的度为2的结点的个数并能判断该二叉树是否为二叉排序树（若是输出Yes；否则输出No）。（输入次序是：表示中序序列的字母串、表示后序序列的字母串）。

　　（注：程序的可执行文件名必须是 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为结束标记），再以与输入次序相反的次序输出这串整数（输入、出时，两个相邻的整数用空格隔开）。

　　（注：程序的可执行文件名必须是 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，字母两两不同），并构造以这些字母为关键字的二叉排序树，再输出该二叉排序树的后序序列和页结点个数。

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

　　2. 编一C程序，它能读入两组整数（每组整数都以-9999为结束标记，-9999不算在内。个数都不大于1000），并以从小到大的次序输出既在第一组整数中也在第二组整数中的所有整数（同一个整数不能输出两次）。（输入时，两个相邻的整数用空格隔开）。

　　（注：程序的可执行文件名必须是 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”）；