北大数据结构上机考题总结1.docx
《北大数据结构上机考题总结1.docx》由会员分享，可在线阅读，更多相关《北大数据结构上机考题总结1.docx（13页珍藏版）》请在冰点文库上搜索。
北大数据结构上机考题总结1
1. 编一C程序，它能读入集合A的一串整数（以-9999为结束标记，整数个数小于1000）和集合B 的一串整数（以-9999为结束标记，整数个数小于1000），计算并以从小到大的次序输出A-B 的所有元素（为A或B输入时，同一个数可能出现多次，而A与B的差集中同一个数不能出现多次）。
（注：
程序的可执行文件名必须是 e1.exe）
（注：
程序的可执行文件名必须是 e4.exe）
*/
#include
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] {
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
#include
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 {
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
#include
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] {
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] {//如果 m[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>0。
（注：
程序的可执行文件名必须是 e3.exe）
#include
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;ifor （j=0;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{ degree[i]=0;
visited[i]=False;
}
printf（"\n"）;
while（flag==True）
{
for （i=0;ifor （j=0;jdegree[i]=G[j][i]+degree[i];
i=0;
while （（i=0）||visited[i]==True） i++; /*最先输出入度为0的顶点.*/
if （i{printf（" %d",i）;
visited[i]=True;
for（j=0;j {G[i][j]=0; degree[j]=0;}
}
else flag=False;
}
}
main（）
{ CreatG（）;
TopSort（）;
}
４. 编一C程序，它能读入一串整数（以-9999为结束标记）并对它们进行从小到大直接插入排序，同时输出排序时对这些整数进行比较的总次数（输入整数时，相邻的两个用空格隔开，整数个数<2000）。
（注：
程序的可执行文件名必须是 e4.exe）
#include
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[0]=a[i];
j=i-1;
do{
a[j+1]=a[j];
j--;
k++;
}while（a[0]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且 （注：
程序的可执行文件名必须是 e5.exe）
6. 编一C程序，它能读入一串整数（不多于2000，并以-9999为结束标记）及另一整数n，判断n是否在那一串数中，若是，则输出yes及该数在那串整数中的序号（序号从0开始），否则输出no。
（输入整数时，相邻的两个用空格隔开）。
（注：
程序的可执行文件名必须是 e6.exe）
#include
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 结尾），输出前序和中序遍历。
其中：
输入数据均为整数，输入时以空格分开。
升级会员 