BUAA 2020级“数据结构与程序设计”期末考试【含往年试题下载】
文章目录试卷下载期末考试1. 机试异常检测（简）「代码1」「代码2」「代码3」2. 函数调⽤关系「代码1」「代码2」「代码3」3. 服务优化「代码」试卷下载2020级“数据结构与程序设计”期末考试 （试卷下载，提取码:buaa）2019级"数据结构与程序设计"期末考试（含参考题解） （试卷下载，提取码:buaa）2018级数据结构与程序设计（信息类）期末考试_编程题 （试卷下载，提取码:buaa）
试卷下载
2020级“数据结构与程序设计”期末考试 （试卷下载，提取码:buaa）
2019级"数据结构与程序设计"期末考试（含参考题解） （试卷下载，提取码:buaa）
2018级数据结构与程序设计（信息类）期末考试_编程题 （试卷下载，提取码:buaa）
期末考试
主要贴出大佬考试时的AC代码。
1. 机试异常检测（简）
【问题描述】
某教学平台具有考试登录异常检测功能，检测规则如下：
1、考试开始后，如果同⼀账号在不同机器上登录，系统将报警输出异常登录信息（可能存在私⾃换机器的情况）；
2、考试开始后，如果同⼀账号在同⼀机器上多次登录，属于正常情况，系统不报警。
编写程序，读⼊某次考试学⽣的登录⽇志信息，对其进⾏异常检测，输出异常登录信息。⽇志信息包括学⽣学号（即学⽣账号，唯⼀标识学⽣身份的信息，⽤⼀整数表示，不超过int的表示范围）、学⽣姓名（⽤不含空⽩符的字符串表示，字符个数不超过15）、机器号（⽤⼀整数表示，不超过int的表示范围）、登录时间（⽤包含6个数字的字符串表示，例如：093756，表示9点37分56秒）。
【输⼊形式】
先从控制台输⼊⽇志信息条数（不超过200条），然后按照登录先后顺序分⾏输⼊⽇志信息，每条信息包括学号、姓名、机器号和登录时间，以⼀个空格分隔各数据。
【输出形式】
按照学号从⼩到⼤的顺序输出登录异常账号信息（仅包括学号和姓名），每条信息独占⼀⾏，学号和姓名以⼀个空格分隔。如果没有异常登录信息，则什么都不输出。
【样例输⼊】
21
191028 wangdi 15 093000
192387 litong 39 093000
190877 liugang 37 093001
197583 huangqinian 196 093004
195211 liuhao 201 093005
193098 zhaogang 377 093006
190001 zhousheng 1 093007
190009 wuhong 12 093007
197583 huangqinian 197 093008
195877 lisisi 202 093008
192387 litong 309 093009
191000 tonghao 201 093402
197583 huangqinian 196 093500
191028 wangdi 15 093507
190010 wangzhuang 85 093558
195333 zhangye 63 093600
197583 huangqinian 195 094100
195211 liuhao 200 095103
190010 wangzhuang 287 095509
193098 zhaogang 377 095606
191028 wangdi 15 095709
【样例输出】
190010 wangzhuang
192387 litong
195211 liuhao
197583 huangqinian
【样例说明】
输⼊了21条登录⽇志信息，其中有四位学⽣（学号分别为190010、192387、195211和197583）在多台机器上登录，属于异常登录， 输出异常账号登录信息；注意：学号为191028的学⽣在15号机器上有多次登录，属于正常重复登录。
「代码1」
#include <stdio.h>
struct Login{
int num;
char name[20];
int computer;
char time[10];
//学号、姓名、机器号和登录时间
}info[300];
void bubbleSort(struct Login k[ ], int n);
int main(int argc, const char * argv[]) {
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d %s %d %s",&info[i].num,info[i].name,&info[i].computer,info[i].time);
bubbleSort(info, n);
//同一账号在不同机器上登录，系统将报警输出异常登录信息
//遍历，直到学号！=，或到末尾，然后从当前位置继续向下遍历
int j,k,flag=0;
for(j=0;j<n-1;){
for(k=j+1;k<n;k++){
if(info[j].num!=info[k].num || k==n-1){//学号不同，或遍历到末尾
j=k;//从当前位置继续向下比较
flag=0;
break;
}
else if(flag==0 && info[j].computer!=info[k].computer){
printf("%d %s\n",info[j].num,info[j].name);
flag=1;//表示该学生已输出过
}
}
}
return 0;
}
//冒泡排序
void bubbleSort(struct Login k[ ], int n)
{
int i, j, flag=1;
struct Login temp;
for(i=n-1; i>0; i--)
{
for(j=0;j<i;j++){
if(k[j].num>k[j+1].num){ //红色语句
temp=k[j];
k[j]=k[j+1];
k[j+1]=temp; /* 交换两个元素的位置 */
}
}
}
}
「代码2」
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
struct node{
char time[11];
int computer;
int no;
char name[51];
}student[1001],m;
int main()
{
int n,i,j,k;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%s%d%d%s",student[i].time,&student[i].computer,&student[i].no,student[i].name);
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(student[i].no>student[j].no||(student[i].no==student[j].no&&student[i].computer>student[j].computer))
{
m=student[i];
student[i]=student[j];
student[j]=m;
}
}
}
for(i=0;i<n;i++)
{
j=i;
while(j+1<n&&student[j].no==student[j+1].no)
j++;
int x=student[i].computer;
for(k=i+1;k<=j;k++)
{
if(student[k].computer!=x)
{
printf("%d %s\n",student[i].no,student[i].name);
break;
}
}
i=j;
}
return 0;
}
「代码3」
#include<stdio.h>
#include<string.h>
struct student{
int id;
char name[20];
int x;
char time[10];
}a[205];
int XX[999999];
int main(){
int n;
scanf("%d",&n);
int i,j;
for(i=0;i<n;i++){
scanf("%d%s%d%s",&a[i].id,a[i].name,&a[i].x,a[i].time);
}
struct student temp;
for(i=0;i<n;i++){
for(j=0;j<n-i-1;j++){
if(a[j].id>a[j+1].id){
temp=a[j+1];
a[j+1]=a[j];
a[j]=temp;
}
}
}
for(i=0;i<n-1;i++){
if(a[i].id==a[i+1].id&&a[i].x!=a[i+1].x&&XX[a[i].id]==0){
printf("%d %s\n",a[i].id,a[i].name);
XX[a[i].id]=1;
}
}
}
2. 函数调⽤关系
【问题描述】
给定某能正常运⾏结束的⽤户函数调⽤栈信息（当⼀个函数被调⽤时将⼊栈，当调⽤返回时，将出栈）。编写程序，对函数调⽤栈信息进⾏分析，依据函数⼊栈和出栈信息，分析函数调⽤关系，即⼀个函数调⽤了哪些不同函数。并按运⾏时调⽤序输出调⽤关系。
说明：
-
在⼀个函数中，同⼀函数有可能被调⽤多次，输出调⽤关系时只输出⼀次；若⼀个函数没有调⽤其它函数，则不输出调⽤关系；
-
函数运⾏时调⽤序是指函数在调⽤栈中的出现序。
-
程序中不存在递归调⽤。函数名符合C语⾔标识符的规定，函数名⻓度不超过20，每个函数最多调⽤不超过10个不同函数，程序中⽤户定义的函数个数不超过100。
算法提示：当⼀个函数⼊栈时，它就是当前栈顶函数调⽤的⼀个函数。
【输⼊形式】
假设⽤8表示函数⼊栈操作；⽤0表示当前函数出栈。当操作为8（⼊栈）时，输⼊形式为：
<操作> <函数名>
当操作为0（出栈）时，输⼊形式为：
<操作>
所有⼊栈操作和出栈操作都是从标准输⼊分⾏输⼊，假设调⽤栈中函数个数最多不超过200。开始时，调⽤栈为空，当调⽤栈再次为空时，输⼊结束。
【输出形式】
按运⾏时调⽤先后顺序输出函数调⽤关系到标准输出，每⾏为⼀个函数的调⽤关系信息，包括：函数名及被调⽤函数，函数与被调⽤函数间⽤⼀个英⽂冒号“:”分隔，被调⽤函数间⽤⼀个英⽂逗号“,”分隔，最后⼀个函数名后跟⼀个回⻋。若⼀个函数没有调⽤其它函数，则不输出。
【样例输⼊】
8 main
8 input
0
8 mysqrt
0
8 findA
0
8 findB
8 area
8 mysin
0
8 mycos
0
8 mysqrt
0
0
0
8 findC
8 area
8 mysin
0
0
8 mysqrt
8 max
0
0
0
8 output
0
0
【样例输出】
main:input,mysqrt,findA,findB,findC,ouput
mysqrt:max
findB:area
area:mysin,mycos,mysqrt
findC:area,mysqrt
【样例说明】
按照运⾏时调⽤函数的先后顺序，依次输出了main、mysqrt、findB、area和findC的函数调⽤关系。其中main函数调⽤了6个函数，按照运⾏时调⽤序依次输出。注意：mysqrt函数先于findB等函数出现在栈中，虽然mysqrt调⽤max较晚，但要先输出其调⽤关系。
「代码1」
（非考试AC代码）
由于字符串的处理有些麻烦，可以将题目中的函数的字符串类型替换成INT整形进行简化。
因此我们首先做一个转换，把字符串存储起来，再以数组的下标代替函数，相当于给函数名编了号。接下来应用这个编号进行函数调用。
具体所需的关键数组包括下面三个，一个line为栈，name用来存储函数名，其一维下标自然就是编号。另外一个ans用来存放函数调用关系。int line[100]; int ans[100][10]; char name[MAX][20];————————————————
文章：https://blog.csdn.net/weixin_53241840/article/details/118284659
「代码2」
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
struct node{
char name[51];
int cnt;
}z[1001];
struct node1{
char name[51];
int cnt1;
struct node2 *next;
}function[1001],m;
struct node2{
char name[51];
struct node2 *next;
}*p,*traverse[1001];
struct node3{
char name[51];
int Count;
}f[1001];
void clear(char x[])
{
int i;
for(i=0;i<51;i++)
x[i]=0;
}
char name1[51],name2[51];
int main()
{
int type,traverse1=0,traverse2=0,traverse3=0,i,j,k,count=0;
while(1)
{
scanf("%d",&type);
if(type==0)
{
int yes=1;
if(traverse1==1)
break;
strcpy(name1,z[traverse1-1].name);
strcpy(name2,z[traverse1-2].name);
for(i=0;i<traverse2;i++)
{
if(strcmp(name2,function[i].name)==0)
break;
}
if(i<traverse2)
{
for(p=function[i].next;p!=NULL;p=p->next)
{
if(strcmp(p->name,name1)==0)
{
yes=0;
break;
}
}
if(yes)
{
p=(struct node2*)malloc(sizeof(struct node2));
strcpy(p->name,name1);
p->next=NULL;
traverse[i]->next=p;
traverse[i]=p;
}
}
else
{
strcpy(function[traverse2].name,name2);
p=(struct node2*)malloc(sizeof(struct node2));
strcpy(p->name,name1);
p->next=NULL;
function[traverse2].next=p;
for(k=0;k<traverse3;k++)
{
if(strcmp(f[k].name,name2)==0)
break;
}
function[traverse2].cnt1=f[k].Count;
traverse[traverse2]=p;
traverse2++;
}
traverse1--;
clear(z[traverse1].name);
clear(name1);
clear(name2);
}
else if(type==5)
{
scanf("%s",z[traverse1].name);
strcpy(f[traverse3].name,z[traverse1].name);
f[traverse3].Count=count;
z[traverse1].cnt=count;
traverse1++;
traverse3++;
count++;
}
}
for(i=0;i<traverse2-1;i++)
{
for(j=i+1;j<traverse2;j++)
{
if(function[i].cnt1>function[j].cnt1)
{
m=function[i];
function[i]=function[j];
function[j]=m;
}
}
}
for(i=0;i<traverse2;i++)
{
printf("%s:",function[i].name);
for(p=function[i].next;p!=NULL;p=p->next)
{
printf("%s",p->name);
if(p->next!=NULL)
printf(";");
}
printf("\n");
}
return 0;
}
「代码3」
#include<stdio.h>
#include<string.h>
struct in{
int type;
char s[50];
int put[50];
int i;
}A[500];
int stack[500];
int main(){
int top=0;
int i=0;
while(scanf("%d",&A[i].type)!=EOF){
if(A[i].type==8){
scanf("%s",A[i].s);
}
i++;
}
int n=i,j;
for(i=0;i<n;i++){
if(A[i].type==8){
stack[top++]=i;
}
else if(A[i].type==0){
if(top==1){
break;
}
else{
A[stack[top-2]].put[(A[stack[top-2]].i)++]=stack[top-1];
top--;
}
}
}
for(i=0;i<n;i++){
if(A[i].type!=0){
for(j=i+1;j<n;j++){
if(strcmp(A[j].s,A[i].s)==0){
int u;
for(u=0;u<A[j].i;u++){
A[i].put[A[i].i++]=A[j].put[u];
}
A[j].type=0;
}
}
}
}
int k;
for(i=0;i<n;i++){
if(A[i].i!=0){
for(j=0;j<A[i].i;j++){
for(k=j+1;k<A[i].i;k++){
if(strcmp(A[A[i].put[j]].s,A[A[i].put[k]].s)==0){
A[i].put[k]=-1;
}
}
}
}
}
//shuchu
for(i=0;i<n;i++){
if(A[i].i!=0&&A[i].type!=0){
printf("%s:",A[i].s);
printf("%s",A[A[i].put[0]].s);
for(j=1;j<A[i].i;j++){
if(A[i].put[j]!=-1)
printf(",%s",A[A[i].put[j]].s);
}
printf("\n");
}
}
}
3. 服务优化
【问题描述】
假设某机场所有登机⼝（Gate）呈树形排列（树的度为3），安检处为树的根，如下图所示。图中的分叉结点（编号⼤于等于100）表示分叉路⼝，登机⼝⽤⼩于100的编号表示（其⼀定是⼀个叶结点）。通过对机场所有出发航班的⽇志分析，得知每个登机⼝每天的平均发送旅客流量。作为提升机场服务⽔平的⼀个措施，在不改变所有航班相对关系的情况下（即：出发时间不变，原在同⼀登机⼝的航班不变），仅改变登机⼝（例如：将3号登机⼝改到5号登机⼝的位置），使得整体旅客到登机⼝的时间有所减少（即：从安检⼝到登机⼝所经过的分叉路⼝最少）。
编写程序模拟上述登机⼝的调整，登机⼝调整规则如下：
1）⾸先按照由⼤到⼩的顺序对输⼊的登机⼝流量进⾏排序，流量相同的按照登机⼝编号由⼩到⼤排序；
2）从上述登机⼝树的树根开始，将登机⼝按照从上到下（安检⼝在最上⽅）、从左到右的顺序，依次对应上⾯排序后将要调整的登机⼝。
例如上图的树中，若只考虑登机⼝，则从上到下有三层，第⼀层从左到右的顺序为：5、6、14、13，第⼆层从左到右的顺序为：7、8、9、10、1、2、18、17、16、15，第三层从左到右的顺序为：11、12、3、4、20、19。若按规则1排序后流量由⼤⾄⼩的前五个登机⼝为3、12、16、20、15，则将流量最⼤的3号登机⼝调整到最上层且最左边的位置（即：5号登机⼝的位置），12号调整到6号，16号调整到14号，20号调整到13号，15号调整到第⼆层最左边的位置（即7号登机⼝的位置）。
【输⼊形式】
1）⾸先按层次从根开始依次输⼊树结点之间的关系。其中分叉结点编号从数字100开始（树根结点编号为100，其它分叉结点编号没 有规律但不会重复），登机⼝为编号⼩于100的数字（编号没有规律但不会重复，其⼀定是⼀个叶结点）。树中结点间关系⽤下⾯⽅式描述：
R S1 S2 S3 -1
其中R为分叉结点，从左⾄右S1，S2，S3分别为树叉R的⼦结点，其可为树叉或登机⼝，由于树的度为3，S1，S2，S3中⾄多可以2个为空，最后该⾏以-1和换⾏符结束。各项间以⼀个空格分隔。如：
100 101 102 103 -1
表明编号100的树根有三个⼦叉，编号分别为101、102和103，⼜如：
104 7 8 -1
表明树叉104上有2个编号分别为7和8的登机⼝。
假设分叉结点数不超过100个。分叉结点输⼊的顺序不确定，但可以确定：输⼊某个分叉结点信息时，其⽗结点的信息已经输⼊。
输⼊完所有树结点关系后，在新的⼀⾏上输⼊-1表示树结点关系输⼊完毕。
2）接下来输⼊登机⼝的流量信息，每个登机⼝流量信息分占⼀⾏，分别包括登机⼝编号（1~99之间的整数）和流量（⼤于0的整数），两整数间以⼀个空格分隔。登机⼝数⽬与前⾯构造树时的登机机⼝数⽬⼀致。
【输出形式】
按照上述调整规则中排序后的顺序（即按旅客流量由⼤到⼩，流量相同的按照登机⼝编号由⼩到⼤）依次分⾏输出每个登机⼝的调整结果：先输出调整前的登机⼝编号，然后输出字符串"->"（由英⽂减号字符与英⽂⼤于字符组成），再输出要调整到的登机⼝编号。
【样例输⼊】
100 101 102 103 -1
103 14 108 13 -1
101 5 104 6 -1
104 7 8 -1
102 105 106 107 -1
106 1 110 2 -1
108 16 15 -1
107 18 111 17 -1
110 3 4 -1
105 9 109 10 -1
111 20 19 -1
109 11 12 -1
-1
17 865
5 668
20 3000
13 1020
11 980
8 2202
15 1897
6 1001
14 922
7 2178
19 2189
1 1267
12 3281
2 980
18 1020
10 980
3 1876
9 1197
16 980
4 576
【样例输出】
12->5
20->6
8->14
19->13
7->7
15->8
3->9
1->10
9->1
13->2
18->18
6->17
2->16
10->15
11->11
16->12
14->3
17->4
5->20
4->19
【样例说明】
样例输⼊了12条树结点关系，形成了如上图的树。然后输⼊了20个登机⼝的流量，将这20个登机⼝按照上述调整规则1排序后形成的顺序为：12、20、8、19、7、15、3、1、9、13、18、6、2、10、11、16、14、17、5、4。最后按该顺序将所有登机⼝按照上述调整规则2进⾏调整，输出调整结果。
「代码」
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
struct node{
int name;
int next[4];
int nextnode[4];
int nodenum;
}gate[1001];
struct node1{
int gatenum;
int sum;
}a[1001],m;
int b[1001],line[1001];
int main()
{
int allgate=0,i,j,k,traverse=0,traverse1=0,nodenum;
while(1)
{
scanf("%d",&nodenum);
gate[traverse].name=nodenum;
if(nodenum==-1)
break;
for(i=0;i<traverse;i++)
{
for(j=0;j<gate[i].nodenum;j++)
{
if(gate[i].nextnode[j]==nodenum)
{
gate[i].next[j]=traverse;
}
}
}
while(1)
{
scanf("%d",&gate[traverse].nextnode[traverse1]);
if(gate[traverse].nextnode[traverse1]==-1)
{
gate[traverse].nodenum=traverse1;
traverse1=0;
break;
}
if(gate[traverse].nextnode[traverse1]<100)
allgate++;
traverse1++;
}
traverse++;
}
for(i=0;i<allgate;i++)
scanf("%d%d",&a[i].gatenum,&a[i].sum);
for(i=0;i<allgate-1;i++)
{
for(j=i+1;j<allgate;j++)
{
if(a[i].sum<a[j].sum||(a[i].sum==a[j].sum&&a[i].gatenum>a[j].gatenum))
{
m=a[i];
a[i]=a[j];
a[j]=m;
}
}
}
int start=0,end=0;
traverse=0;
for(i=0;i<gate[0].nodenum;i++)
{
if(gate[0].nextnode[i]<100)
b[traverse++]=gate[0].nextnode[i];
else
line[end++]=gate[0].next[i];
}
while(start!=end)
{
int x=line[start++];
for(i=0;i<gate[x].nodenum;i++)
{
if(gate[x].nextnode[i]<100)
b[traverse++]=gate[x].nextnode[i];
else
line[end++]=gate[x].next[i];
}
}
for(i=0;i<allgate;i++)
printf("%d<-%d\n",b[i],a[i].gatenum);
return 0;
}
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
12
0- 0
已为社区贡献5条内容
所有评论(0)