- 北大“数据结构”上机考试复习题总结（2）
- 发布日期时间：2007-3-16 来源：不详 点击数： 作者：佚名
数据结构练习题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（
文章转载请注明来源于：汕头自考网
|
|
