北大数据结构上机试题总结（1）

2006年06月12日来源：北京自考热线字体：大小打印

1. 编一C程序，它能读入集合A的一串整数（以-9999为结束标记，整数个数小于1000）和集合B 的一串整数（以-9999为结束标记，整数个数小于1000），计算并以从小到大的次序输出A-B 的所有元素(为A或B输入时，同一个数可能出现多次，而A与B的差集中同一个数不能出现多次)。（注：程序的可执行文件名必须是 e1.exe）

（注：程序的可执行文件名必须是 e4.exe）
*/
#include <stdio.h>

void BubbleSort(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 DisaSameYs(int r[],int n)
{//消除数组r[]中的重复元素,并返回消除后数组剩余的元素个数
int w,x,y;
for(w=0;w<=n;w++)
{
  for(x=w+1;x<=n;x++)
  {
   if(r[w]==r[x])
   {
    n--;
    for(y=x;y<=n;y++)
    {
     r[y]=r[y+1];
    }//endfor
    x--;
   }//endif
  }//endfor
}//endfor

return n;
}

int cha(int m[],int n[],int l[],int Countaa,int Countbb)
{//求差集
int i=0,j=0,k=0;
int exch;
while(i<=Countaa)
{
  exch=0;//交换变量为0
  for(j=0;j<=Countbb;j++)
  {//用集合的第一个元素分别和另一个集合的各元素相比较
   //然后再用第二个元素(直到更后一个元素)和另一个集合的各元素相比较
   if(m[i]==n[j])
   {//如果相同，交换变量变为1
exch=1;
    break;
   }//endif
}//endfor
  if(!exch)
{//如果没有相同的就保存m[i]到l[]中
   l[k]=m[i];
   k++;
  }
  i++;
}//endwhile

return k;
}

/*
void testds(int r[],int n)
{//测试消除数组中的重复元素的效果用下列循环输出
int z;
for(z=0;z<=n;z++)
{
printf("%d",r[z]);
}
printf("\n");
}
*/

void main()
{
int a[1000], b[1000],c[2000];
int exchange=0;
int i,j,k,CountA,CountB,CountC;

printf("input a\n");
for(i=0;i<=1000;i++)
{
  scanf("%d",&a[i]);
  if(a[i]==-9999)
  break;
}
CountA=i-1;
BubbleSort(a,CountA);

CountA=DisaSameYs(a,CountA);
// testds(a,CountA);

printf("\ninput b\n");
for(i=0;i<=1000;i++)
{
  scanf("%d",&b[i]);
  if(b[i]==-9999)
  break;
}
CountB=i-1;
BubbleSort(b,CountB);

CountB=DisaSameYs(b,CountB);
//testds(b,CountB);

CountC=cha(a,b,c,CountA,CountB);

printf("\n\n");
for(i=0;i<=CountC-1;i++)
{
printf("%d ",c[i]);
}
printf("\n");
}

模式匹配

#include <stdio.h>
#include <string.h>

typedef struct{
// int ch[2000];
char ch[2000];
int length;
}SeqString;

int NaiveStrMatch(SeqString T,SeqString P)
{
int i,j,k;
int m=P.length;
int n=T.length;
for(i=0;i<=n-m;i++)
{
  j=0;k=i;
  while(j<m&&T.ch[k]==P.ch[j])
  {
   k++;j++;
  }
  if(j==m)
   return i;

}//endfor
return -1;
}//NaiveStrMatch

SeqString CreatStr(SeqString R)
{
int i;
printf("input data\n");
for(i=0;i<2000;i++)
{
//  scanf("%d",&R.ch[i]);
//  if(R.ch[i]==-9999)
  scanf("%s",&R.ch[i]);
  if(!(strcmp(&R.ch[i],"-9999")))
  break;
}
R.length=i-1;
return R;
}

void main()
{
int n;
SeqString Str1;
Str1=CreatStr(Str1);
SeqString Str2;
Str2=CreatStr(Str2);
n=NaiveStrMatch(Str1,Str2);
printf("%d\n",n);
}

2、编一C程序，它能读入集合A的一串整数（以-9999为结束标记，整数个数小于1000）和集合B的一串整数（以-9999为结束标记，整数个数小于1000），计算出A与B的交集，并以由小到大的次序输出A与B的交集中的所有整数（输入整数时，相邻的两个用空格隔开。为A或B输入时，同一个数可能出现多次，而A与B的交集中同一个数不能出现多次）。（注：程序的可执行文件名必须是 e2.exe）

//注意调试程序时要多输入重复数据调试；本程序是根据青龙提供的程序改编，消除了重复数据的错误！；

#include <iostream.h>
#include <stdio.h>

void BuCountbbleSort(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 BingJi(int m[],int n[],int l[],int Countaa,int Countbb)
{//求集合的并集
int i=0,j=0,k=0;
while(i<=Countaa&&j<=Countbb)
{
  if(m[i]<n[j])
  {//如果 m[i]<n[j]则取小的值m[i],然后i++;
   l[k]=m[i];
   k++;
   i++;
  }//endif
  else if(m[i]>n[j])
  {//如果 m[i]>n[j]则取小的值n[j],然后j++;
   l[k]=n[j];
   k++;
   j++;
  }//end elseif
  else
  {//如果 m[i]==n[j],可以任取一个值，然后i++;j++;
   l[k]=m[i];
   k++;
   i++;
   j++;
  }//endelse
}//endwhile

if(i>Countaa)
{//如果i>Countaa,即数组m[i]中的元数个数较少，
  //则把n[j]中的剩余元素，都付给l[]。
  while(j<=Countbb)
  {
   l[k]=n[j];
   j++;
   k++;
  }//endwhile
}//endif

if(j>Countbb)
{//如果j>Countbb,即数组n[i]中的元数个数较少，
  //则把m[j]中的剩余元素，都付给l[]。
  while(i<=Countaa)
  {
   l[k]=m[i];
   i++;
   k++;
  }//endwhile
}//endif

return k;//返回生成的数组的元数个数
}//end BuCountbbleSort

int JiaoJi(int m[],int n[],int l[],int Countaa,int Countbb)
{//求集合的交集

///////////////////////////////////
//消除数组m[]中的重复元素
int w,x,y;
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];
    }//endfor
    x--;
   }//endif
  }//endfor
}//endfor

/*
//测试消除数组中的重复元素的效果用下列循环输出
int z;
for(z=0;z<=Countaa;z++)
{
printf("%d",m[z]);
}
printf("\n");
*/

//消除结束
///////////////////////////////////

///////////////////////////////////
//求交集
int i=0,j=0,k=0;
while(i<=Countaa)
{
  for(j=0;j<=Countbb;j++)
  {//用集合的第一个元素分别和另一个集合的各元素相比较
   //然后再用第二个元素(直到更后一个元素)和另一个集合的各元素相比较
   if(m[i]==n[j])
   {//如果有相同的就保存到l[]中，这样同时消掉了n[]中的重复元素
    l[k]=m[i];
    k++;
    break;
   }//endif
}//endfor
  i++;
}//endwhile
//求交集结束
//////////////////////////////////

return k;
}

void main()
{
int a[1000], b[1000],c[2000];
int exchange=0;
int i,CountA,CountB,CountC;

printf("input a\n");
for(i=0;i<=1000;i++)
{
  scanf("%d",&a[i]);
  if(a[i]==-9999)
   break;
}//endfor
CountA=i-1;

BuCountbbleSort(a,CountA);//先将集合A排序

printf("\ninput b\n");
for(i=0;i<=1000;i++)
{
  scanf("%d",&b[i]);
  if(b[i]==-9999)
   break;
}//endfor
CountB=i-1;

BuCountbbleSort(b,CountB);//集合B排序

// CountC=BingJi(a,b,c,CountA,CountB);
CountC=JiaoJi(a,b,c,CountA,CountB);

printf("\n\n");
for(i=0;i<=CountC-1;i++)
{
  printf("%d ",c[i]);
}
printf("\n");
}
     3. 编一C程序，它能根据读入的数据构造有向图G，并输出G的DFS遍历序列（从V0开始），图的输入形式为n V0 Vi0 V1 Vi1 V2 Vi2...Vi Vin -1 -1（-1，-1为输入结束标记，其余的值都>=0且<n），它们都是整数，且100>n>0。
（注：程序的可执行文件名必须是 e3.exe）
#include <stdio.h>
typedef enum {False,True} Boolean;

int G[100][100];
int n;

void CreatG() /*建立图的邻接矩阵G[][]*/
{int i,j;
printf("Input the number of the node:");
scanf("%d",&n);
printf("\n");
for (i=0;i<n;i++)
for (j=0;j<n;j++)
G[i][j]=0;
do
{ scanf("%d %d",&i,&j);
G[i][j]=1;
}while ((i!=-1)&&(j!=-1));
}

void TopSort() /*拓扑排序,输出拓扑序列*/
{ int i,j;
int degree[100]; /*按照无前驱顶点优先思想,degree[]存放个节点的入度.*/
Boolean visited[100],flag=True;
printf("The Topolgical Order as follow:");
for (i=0;i<n;i++)
{ degree[i]=0;
visited[i]=False;
}
printf("\n");
while(flag==True)
{
for (i=0;i<n;i++)
for (j=0;j<n;j++)
degree[i]=G[j][i]+degree[i];
i=0;
while ((i<n)&&(degree[i]!=0)||visited[i]==True) i++; /*更先输出入度为0的顶点.*/
if (i<n) /*所有节点均已输出结束,否则说明存在环,无拓扑序列*/
{printf(" %d",i);
visited[i]=True;
for(j=0;j<n;j++)
{G[i][j]=0; degree[j]=0;}
}
else flag=False;
}
}

main()
{ CreatG();
TopSort();
}
４. 编一C程序，它能读入一串整数（以-9999为结束标记）并对它们进行从小到大直接插入排序，同时输出排序时对这些整数进行比较的总次数（输入整数时，相邻的两个用空格隔开，整数个数<2000）。（注：程序的可执行文件名必须是 e4.exe）
#include<stdio.h>

void main()
{
int a[2000],i,j,k=0,CountA;
printf("input data\n");
for(i=1;i<=2001;i++)
{
  scanf("%d",&a[i]);
  if(a[i]==-9999)
   break;
}
CountA=i-1;

for(i=2;i<=CountA;i++)
  if(a[i]<a[i-1])
  {
   a[0]=a[i];
   j=i-1;

  do{
    a[j+1]=a[j];
    j--;
    k++;
   }while(a[0]<a[j]);
a[j+1]=a[0];
  }

printf("\n");
for(i=1;i<=CountA;i++)
printf("%d ",a[i]);
printf("\nThe times of comparing = %d",k);
printf("\n");
}
5. 编一C程序，它能根据读入的数据构造有向图G，图的输入形式为n V0 Vi0 V1 Vi1 V2 Vi2...Vi Vin -1 -1（-1 -1是输入结束标记），它们都是整数，且100>n>0，其余的值都>=0且<n,输出图G的拓扑序列。（注：程序的可执行文件名必须是 e5.exe）

6. 编一C程序，它能读入一串整数（不多于2000，并以-9999为结束标记）及另一整数n，判断n是否在那一串数中，若是，则输出yes及该数在那串整数中的序号（序号从0开始），否则输出no。(输入整数时，相邻的两个用空格隔开)。
（注：程序的可执行文件名必须是 e6.exe）
#include <stdio.h>

typedef struct{
int data[2000];
int length;
}SeqList;

void main()
{
int i,k=0,num;
SeqList a;
printf("input data\n");
for(i=0;i<2000;i++)
{
  scanf("%d",&a.data[i]);
  if(a.data[i]==-9999)
   break;
}
a.length=i-1;

printf("input the number\n");
scanf("%d",&num);
for(i=0;i<=a.length;i++)
{
  k++;
  if(a.data[i]==num)
  {
   printf("yes\n");
   printf(" is at %d",k);
   printf("\n");

  }
}
printf("\nno\n");
}
     7. 根据输入的中序和后序建立二叉树，用前序输出并计算树的深度。
     8. 输入前序和中序构造二叉树，并输出后序和度为1的结点个数。
     9. 输入一串整数，判断第N个数在前N-1个序列中出现了几次，输出次数。
     10．建立一个空二叉排序树，输入一串数据（以-9999 结尾），输出前序和中序遍历。其中：输入数据均为整数，输入时以空格分开。