数据结构练习题1
1 ．编一C程序，它能根据读入的数据构造有向图G，并输出G的邻接矩阵和DFS遍历序列（从V0开始），图的输入形式为n Vi0 Vj0 Vi1 Vj1 Vi2 Vj2...Vim Vjm -1 -1（-1，-1为输入结束标记），它们都是整数，且100>n>0，其余的值都>=0且<n。

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

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

（注：程序的可执行文件名必须是 e2.exe，存于你的账号或其debug目录下。）
数据结构练习题2
1．编一C程序，它能读入两组整数（每组整数都是66个整数），它们分别是下三角矩阵A和下三角矩阵B的按行优先排列的元素（A和B的其它元素均为零）。计算并输出矩阵A与B的乘积。
（注：程序的可执行文件名必须是 e1.exe，存于你的账号或其debug目录下。）
#include <stdio.h>
#include <stdlib.h>

void main()
{
int i,j, k1,k2,c[66],s,k,count=0,flag=0;
int a[66];
int b[66];
printf("请输入66个数到a中：\n");

for(i=0;i<66;i++)
scanf("%d",&a[i]);

printf("请输入66个数到b中：\n");

for(i=0;i<66;i++)
scanf("%d",&b[i]);

for(i=0;i<11;i++){
for(k=0;k<11;k++)
{s=0;
for(j=0;j<11&&i>=j;j++)
k1=i*(i+1)/2+j;
if(j>=k)
k2=j*(j+1)/2+i;
else
continue;
s+=a[k1]*b[k2];
flag=1;
}
if(flag)
{
c[count++]=s;
flag=0;
}
}

for(i=0;i<66;i++)
printf("%d",c[i]);

}

2．编一C程序，它能对输入的一串整数（不多于1000个，以-9999为结束标记）到数组a中，再对a的元素进行直接插入排序（从小到大排序），输出排序结果和所用关键字比较次数。（输入时，两个相邻的整数用空格隔开)。

（注：程序的可执行文件名必须是 e2.exe，存于你的账号或其debug目录下。）
#include <stdio.h>
#include <stdlib.h>

void main()
{
int i,j, k1,k2,c[66],s,k,count=0,flag=0;
int a[66];
int b[66];
printf("请输入66个数到a中：\n");

for(i=0;i<66;i++)
scanf("%d",&a[i]);

printf("请输入66个数到b中：\n");

for(i=0;i<66;i++)
scanf("%d",&b[i]);

for(i=0;i<11;i++){
for(k=0;k<11;k++)
{s=0;
for(j=0;j<11&&i>=j;j++)
k1=i*(i+1)/2+j;
if(j>=k)
k2=j*(j+1)/2+i;
else
continue;
s+=a[k1]*b[k2];
flag=1;
}
if(flag)
{
c[count++]=s;
flag=0;
}
}

for(i=0;i<66;i++)
printf("%d",c[i]);

}

数据结构练习题3
1． 编一C程序，它能根据输入的二叉树前序和中序序列来构造该二叉树，并能输出该二叉树的后序序列和该二叉树叶的结点的个数以及该二叉树高度。（输入次序是：表示前序序列的字符串、表示中序序列的字符串）。

（注：程序的可执行文件名必须是 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 pre[],int pres,int pree,char in[],int is,int ie,Tnode **r)
{
int i;
if(pres>pree||is>ie)
*r=NULL;
else{
*r=malloc(sizeof(Tnode));
for(i=is;i<=ie;i++)
if(pre[pres]==in[i])
{
MKTree(pre,pres+1,pres+i-is,in,is,is+i-1,&(*r)->lchild);
MKTree(pre,pres+i+is+1,pree,in,is+i+1,ie,&(*r)->rchild);
break;
}
}
}

void postorder(Tnode *r)
{
if(r)
{
postorder(r->lchild);
postorder(r->rchild);
printf("%c",r->d);
}
}

int num(Tnode *r)
{
if(r==NULL)
return 0;
else
if(r->lchild==NULL&&r->rchild==NULL)
return 1;
else
return num(r->lchild)+num(r->rchild);
}
int height(Tnode *r)
{
int h1,h2;
if(r==NULL)
return 0;
else
{
h1=height(r->lchild);
h2=height(r->rchild);
return 1+(h1>h2)?h1:h2;
}
}

void main()
{
Tnode *r;
char pre[MAX],in[MAX];
printf("input preorder and inorder \n");
gets(pre);
gets(in);
MKTree(pre,0,strlen(pre)-1,in,0,strlen(in)-1,&r);
printf("The postorder is as follow:\n");
postorder(r);
printf("\n there are %d leaves in the tree\n",num(r));
printf("h=%d\n",height(r));
}

2．编一C程序，它能读入一串（n个）整数（以-9999为结束标记），并判断第1个整数在后(n-1)个整数中出现的次数，再输出该次数。（输入时，两个相邻的整数用空格隔开)。
（注：程序的可执行文件名必须是 e2.exe，存于你的账号或其debug目录下。）

数据结构练习题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");