-
考前刷题练手感（北航期末往年数据结构编程题）
本次因为是考前一天极速刷题，所以没有讲解，若有问题可私信。
一、 查找同时空人员
【问题描述】
假设一共有6个手机基站，都具有记录手机连接基站状态的能力，当手机进入和离开基站固定范围后，基站将及时记录手机的连接信息：
1、约定基站覆盖范围不存在重合，也就是同一个手机在同一时间内只会处于一个基站覆盖范围内；
2、同一个手机在同一个基站上多次连续登录，属于正常情况，说明该手机不断出入该基站的覆盖范围。
编写程序，读入某一天多个基站的手机登录日志信息（服务商提供的日志信息是按手机进入基站的时间排好序，详见样例输入）和一个要查找的人员手机号，查找与该人员同时空人员的手机号（即与该手机号基站相同且进入与离开时间有重叠的手机号；若一手机号的进入时间与另一手机号的离开时间完全相同，两手机号也算有重叠。）。输出与指定手机号有时空重叠的手机号及所在基站。
基站的手机登录日志信息包括：手机号（11位的数字，按字符串处理）、基站编号（一共为6个基站，分别用大写字母A、B、C、D、E、F表示）、登录时间和登出时间（用长度为6的数字串表示，例如：093756，表示9点37分56秒）。
【输入形式】
先输入手机登录日志信息的条数（小于1000条），然后按上述格式分行输入手机登录日志信息，手机号、基站编号、登录时间和登出时间之间以一个空格分隔。
【输出形式】
按照手机号由小至大进行排序，分行输出与指定手机号有时空重叠的手机号及所在基站编号，手机号与基站编号之间以一个空格分隔。手机号相同时按基站字母序排序输出。
【样例输入】
28
18222336979 F 060201 063539
18222336979 B 063601 063802
18222336979 C 063806 064607
18222336979 D 064615 065816
18222336979 A 065827 160003
18222336979 D 160013 161605
18222336979 C 161617 162633
18222336979 B 162702 172333
13810013509 C 080005 092537
13810013509 A 100356 124732
13810013509 C 125021 161619
13810013509 F 162315 163857
13810013509 B 163901 205602
13810013509 C 210509 230108
13810013509 D 230901 232556
13557912211 B 060615 080239
13557912211 E 120507 150309
13557912211 C 162633 163621
13557912211 B 163855 172209
13557912211 D 200609 230901
13985992766 A 070000 120203
13985992766 F 130506 160000
13985992766 B 160102 161503
13985992766 C 161617 163058
13985992766 E 163302 180709
13985992766 D 190005 200729
15857596331 D 000201 235051
13877882206 C 003123 220806
13557912211
【样例输出】
13810013509 B
13810013509 D
13877882206 C
13985992766 C
13985992766 D
15857596331 D
18222336979 B
18222336979 C
【样例说明】
先 输入了28条手机登录基站的日志信息，然后输入手机号13557912211，表示要查找与该手机号同时空的手机号。该手机号首先在6点6分15秒登录B 基站，在8点2分39秒登出B基站，在这个时间段内只有手机号18222336979 存在重叠；指定手机号登录登出过E基站，但没有存在重叠的手机号；指定手机号在C基站与3个手机号发生重叠，其余重叠情况类似。按照这些手机号由小至大进行排序，分行输出与指定手机号有时空重叠的手机号及所在基站编号，手机号相同时按基站字母序排序输出。
【评分标准】
该题要求查找与指定手机号同时空的手机号，提交程序名为same.c。
#include#include #include #include typedef struct node { char phone[12]; char station; int in; int out; }NODE; int N; NODE* arr; char tar[12]; int tarnum=0; int flag; NODE same[100]; int samenum=0; void SameTime(); int ifHaveSame(NODE,NODE); void Insert(NODE); void OutPut(); int main() { scanf("%d",&N); arr=(NODE*)malloc(sizeof(NODE)*N); for(int i=0;i<N;i++) { scanf("%s %c %d %d",arr[i].phone,&arr[i].station,&arr[i].in,&arr[i].out); } scanf("%s",tar); for(int i=0;i<N;i++) { if(strcmp(tar,arr[i].phone)==0) { tarnum++; flag=i; while(strcmp(tar,arr[++i].phone)==0) tarnum++; break; } } SameTime(); OutPut(); } void SameTime() { for(int i=0;i<N;i++) { int cmp=strcmp(tar,arr[i].phone); if(cmp==0) { int n=tarnum-1; while(n--) i++; } else { for(int j=flag;j<tarnum+flag;j++) { if(arr[i].station==arr[j].station) { if(ifHaveSame(arr[i],arr[j])) Insert(arr[i]); } } } } } int ifHaveSame(NODE a,NODE b) { if(a.in<=b.out&&a.out>=b.in) return 1; else return 0; } void Insert(NODE n) { int i=0; for(;i<samenum;i++) { if(strcmp(same[i].phone,n.phone)==0&&same[i].station==n.station) return; } if(i==samenum) { same[samenum++]=n; } } int cmp1(const void* p1,const void* p2) { return strcmp((*(NODE*)p1).phone,(*(NODE*)p2).phone); } int cmp2(const void* p1,const void* p2) { return (*(NODE*)p1).station-(*(NODE*)p2).station; } void OutPut() { qsort(same,samenum,sizeof(NODE),cmp1); for(int i=0;i<samenum;i++) { int start=i; int num=1; while(i+1<samenum&&strcmp(same[i].phone,same[i+1].phone)==0) { i++; num++; } if(num>1) qsort(same+start,num,sizeof(NODE),cmp2); } for(int i=0;i<samenum;i++) { printf("%s %c\n",same[i].phone,same[i].station); } } 二、 老鼠回家-无回路
【问题描述】
老鼠离家去找食物，要经过不断探索才能找到食物。某老鼠非常聪明，在原路返回时能够避免找食物时多走的冤枉路，找到直接回家的路。
编写程序，读入该老鼠找食物过程中的轨迹记录，然后分析出其原路回家的最佳路径（即：走过的路，但不包括冤枉路）。在此冤枉路指的是原路返回的路；而且假设老鼠走过的路不会形成环。
算法提示：使用栈保存老鼠走过的轨迹；每当读入老鼠新的轨迹时，检查栈顶元素，判断新轨迹能否与栈顶轨迹抵消（全部或部分），然后进行入栈或出栈操作，示例见样例说明。
【输入形式】
输入为一系列老鼠轨迹。老鼠轨迹以行进方向和步数对来表示。行进方向包括：1-上、2-下、3-左、4-右，步数为一个整数值，行进方向和步数为0时表示输入结束。例如：1-4，表示向上行进4步，1和4之间为英文减号“-”。各行进步数间以一个空格分隔。最后的0-0后为换行符。老鼠行走的总步数不超过1000步。
以上图为例（图中数字为路的长度，以老鼠的步数为单位），老鼠从家开始找食物的轨迹输入如下：
1-2 3-4 1-7 2-3 4-3 3-3 2-4 4-4 1-6 4-2 2-2 1-2 3-4 1-3 0-0
【输出形式】
按照上述要求输出老鼠从食物回家的最佳路径，输出格式同输入，最后一步后有无空格均可。
【样例输入】
1-2 3-4 1-7 2-3 4-3 3-3 2-4 4-4 1-6 4-2 2-2 1-2 3-4 1-3 0-0
【样例输出】
2-3 4-2 2-8
【样例说明】
老 鼠从家出发，开始向上走，前3次轨迹后栈的状态如下图所示；轨迹4因为是往下走3步，与栈顶的往上走7步（1-7）相比较，属于原路返回的路，可以从栈顶 轨迹中核减掉，结果如下图所示；轨迹6、7、8都是往回走，结果如下图所示；其它轨迹类似，轨迹14后找到食物，最后输出原路回家的最佳路径，既将栈中的轨迹反向输出（部分轨迹要合并）。
【评分标准】
该题要求找到回家的最佳路径，提交程序名为path.c。
#include#include #include #include enum set {UP=1,DOWN,LEFT,RIGHT}; typedef struct node { enum set orient; int distance; }NODE; NODE* stack[1000]; int top=0; void Push(int,int); int isContrast(int,int); void Return(); int main() { int ori,distance; scanf("%d-%d",&ori,&distance); while(ori!=0) { Push(ori,distance); scanf("%d-%d",&ori,&distance); } Return(); } void Push(int o,int d) { NODE* new=(NODE*)malloc(sizeof(NODE)); new->orient=o,new->distance=d; if(top==0){ stack[top++]=new; return; } NODE* topitem=stack[top-1]; int judge=isContrast(topitem->orient,o); if(judge==1) { if(topitem->distance==d) top--; else if(topitem->distance>d) { topitem->distance-=d; } else { topitem->orient=o; topitem->distance=d-topitem->distance; } } else { stack[top++]=new; } } int isContrast(int a,int b) { if(a==UP&&b==DOWN||a==DOWN&&b==UP) return 1; if(a==LEFT&&b==RIGHT||a==RIGHT&&b==LEFT) return 1; return 0; } void Return() { int i=0; for(;i<top;i++) { int start=i; int num=1; while(i+1<top&&stack[i]->orient==stack[i+1]->orient) { num++; stack[start]->distance+=stack[i+1]->distance; i++; } if(num>1) { i=i-num+1; memmove(stack+start+1,stack+start+num,sizeof(NODE)*(top-start-num)); top=top-num+1; } } for(int j=top-1;j>=0;j--) { if(stack[j]->orient==UP) printf("%d-%d ",DOWN,stack[j]->distance); else if(stack[j]->orient==DOWN) printf("%d-%d ",UP,stack[j]->distance); else if(stack[j]->orient==LEFT) printf("%d-%d ",RIGHT,stack[j]->distance); else if(stack[j]->orient==RIGHT) printf("%d-%d ",LEFT,stack[j]->distance); } } 三、函数调⽤关系
【问题描述】
给定某能正常运⾏结束的⽤户函数调⽤栈信息（当⼀个函数被调⽤时将⼊栈，当调⽤返回时，将出栈）。编写程序，对函数调⽤栈信息进⾏分析，依据函数⼊栈和出栈信息，分析函数调⽤关系，即⼀个函数调⽤了哪些不同函数。并按运⾏时调⽤序输出调⽤关系。
说明：
在⼀个函数中，同⼀函数有可能被调⽤多次，输出调⽤关系时只输出⼀次；若⼀个函数没有调⽤其它函数，则不输出调⽤关系； 函数运⾏时调⽤序是指函数在调⽤栈中的出现序。 程序中不存在递归调⽤。函数名符合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较晚，但要先输出其调⽤关系。
#include#include #include #define MAXLEN 21 #define MAXNUM 100 typedef struct node { char name[21]; char functions[MAXNUM][MAXLEN]; int funcnum; }FUNC; FUNC* arr[100]; int index=0; char stack[200][MAXLEN]; int top=0; void Push(); void OutPut(); int main() { int op; do { scanf("%d",&op); if(op==8) { Push(); } else if(op==0) top--; }while(top!=0); OutPut(); } void Push() { char func[21]; scanf("%s",&func); int i=0; for(;i<index;i++) { if(strcmp(arr[i]->name,func)==0) break; } if(i==index) { FUNC* new=(FUNC*)malloc(sizeof(FUNC)); new->funcnum=0; strcpy(new->name,func); arr[index]=new; index++; } if(top==0) { strcpy(stack[top],func); top++; } else { char* topitem=stack[top-1]; int i=0; for(;i<index;i++) { if(strcmp(arr[i]->name,topitem)==0) { int j=0; for(;j<arr[i]->funcnum;j++) if(strcmp(arr[i]->functions[j],func)==0) break; if(j==arr[i]->funcnum) { strcpy(arr[i]->functions[j],func); arr[i]->funcnum++; } break; } } strcpy(stack[top],func); top++; } } void OutPut() { for(int i=0;i<index;i++) { if(arr[i]->funcnum) { printf("%s:",arr[i]->name); int j=0; for(;j<arr[i]->funcnum-1;j++) { printf("%s,",arr[i]->functions[j]); } printf("%s\n",arr[i]->functions[j]); } } } 注：以下两道题为助教原创题目：
四、东二食堂模拟
#include#include #include #define MAX 200 typedef struct node { int wtime; int starttime; int id; int face; }STU; STU queue[MAX]; STU wtime[MAX]; int ix=0; int N; int Index=0; int Head=0; void Push(STU); void breakqueue(int); int upgratewtime(int); int cmp(const void* p1,const void* p2) { return (*(STU*)p1).id-(*(STU*)p2).id; } int main() { scanf("%d",&N); STU tmp; for(int i=0;i<N;i++) { scanf("%d %d %d",&tmp.starttime,&tmp.id,&tmp.face); tmp.wtime=tmp.starttime; Push(tmp); } int second=queue[0].starttime; for(;;second++) { breakqueue(second); if(queue[Head].starttime<=second) wtime[ix++]=queue[Head++]; if(!upgratewtime(second)&&Head==N) break; } qsort(queue,N,sizeof(STU),cmp); for(int i=0;i<N;i++) { printf("%d %d\n",queue[i].id,queue[i].wtime); } return 0; } int upgratewtime(int sec) { int i=Head; int flag=0; for(;i<N&&queue[i].starttime<=sec;i++) { queue[i].wtime++; flag=1; } return flag; } void breakqueue(int sec) { int i=Head+1; for(;i<N;i++) { if(queue[i].starttime==sec) { if(i-Head<queue[i].face) { STU tmp=queue[i]; memmove(queue+1+Head,queue+Head,sizeof(STU)*(i-Head)); queue[Head]=tmp; } } } } void Push(STU s) { if(Index==0) { queue[Index]=s; Index++; return; } int i=Index-1; int j=i; for(;j>=0;j--) { if(queue[j].starttime>s.starttime) queue[j+1]=queue[j]; else { queue[j+1]=s; Index++; break; } } if(j==-1) { queue[0]=s; Index++; } } 五、栈帧
#include#include #include typedef struct node { char name[50]; int frame; }FUNC; typedef struct state { FUNC stack[100]; int frametotal; int funcnum; }STATE; FUNC stack[100]; int top=-1; FUNC functions[20]; STATE S[100]; int indexst=0; int N; void Insert(); int find(char*); void updatestate(); int cmp1(const void* p1,const void*p2) { return (*(STATE*)p2).funcnum-(*(STATE*)p1).funcnum; } int cmp2(const void* p1,const void*p2) { return (*(STATE*)p2).frametotal-(*(STATE*)p1).frametotal; } void output(); int main() { scanf("%d",&N); if(N==0) { printf("0\n"); printf("0"); return 0; } for(int i=0;i<N;i++) { scanf("%s %d",&functions[i].name,&functions[i].frame); } char ope[20]; do { scanf("%s",ope); if(strcmp(ope,"call")==0) { Insert(); updatestate(); } else if(strcmp(ope,"return")==0) { top--; updatestate(); } else if(strcmp(ope,"frame")==0) { int x; scanf("%d",&x); int j=top-x; for(int w=0;w<j;w++) { top--; } updatestate(); } }while(top!=-1); output(); } void Insert() { char ope_func[50]; scanf("%s",ope_func); int frame=find(ope_func); ++top; strcpy(stack[top].name,ope_func); stack[top].frame=frame; } void updatestate() { memcpy(S[indexst].stack,stack,sizeof(FUNC)*(top+1)); S[indexst].funcnum=top+1; S[indexst].frametotal=0; for(int i=0;i<top+1;i++) { S[indexst].frametotal+=stack[i].frame; } indexst++; } int find(char* tar) { for(int i=0;i<N;i++) { if(strcmp(functions[i].name,tar)==0) return functions[i].frame; } } void output() { qsort(S,indexst,sizeof(STATE),cmp1); int a=S[0].funcnum; printf("%d\n",a); for(int i=0;i<a;i++) { printf("%s(%d) ",S[0].stack[i].name,S[0].stack[i].frame); } printf("\n"); qsort(S,indexst,sizeof(STATE),cmp2); int b=S[0].funcnum; int c=S[0].frametotal; printf("%d\n",c); for(int i=0;i<b;i++) { printf("%s(%d) ",S[0].stack[i].name,S[0].stack[i].frame); } } -
相关阅读:
8 年 Java 开发含泪刷题，架构岗现在好难进，有点崩溃
如何设计一个短地址服务
机器学习（17）---支持向量机(SVM)
Jmeter的使用教程（安装）
React--组件的生命周期
【OceanBase概念】国产数据库OceanBase的那些事儿（1）初识OceanBase
【MySQL基础】常用指令详解
在spring boot中调用第三方接口时重试问题
《30天吃掉那只 TensorFlow2.0》 3-3 高阶API示范
7.nginx动静分离（添加Tomcat-3，部署p2p项目）
- 原文地址：https://blog.csdn.net/zxy13149285776/article/details/139884326