您的位置:自考365 > 复习指导 > 历年试题 > 北大数据结构上机考题总结(1)

北大数据结构上机考题总结(1)

2006-06-12 14:54  北京自考热线 【 】【我要纠错

     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(); 
}
     4. 编一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 结尾),输出前序和中序遍历。其中:输入数据均为整数,输入时以空格分开。

本文转载链接:北大数据结构上机考题总结(1)

分享到:
  • 站内搜索
  • 课程搜索
  • 试题搜索

热门搜索:教材 报名 查分 免考 考试计划