爱喝兽奶帝天荒

这个屌丝很懒，什么也没留下！

热门标签

考前刷题练手感（北航期末往年数据结构编程题）

作者：爱喝兽奶帝天荒 | 2024-06-23 02:44:09

踩

本次因为是考前一天极速刷题，所以没有讲解，若有问题可私信。

一、查找同时空人员

【问题描述】

假设一共有6个手机基站，都具有记录手机连接基站状态的能力，当手机进入和离开基站固定范围后，基站将及时记录手机的连接信息：

1、约定基站覆盖范围不存在重合，也就是同一个手机在同一时间内只会处于一个基站覆盖范围内；

2、同一个手机在同一个基站上多次连续登录，属于正常情况，说明该手机不断出入该基站的覆盖范围。

编写程序，读入某一天多个基站的手机登录日志信息（服务商提供的日志信息是按手机进入基站的时间排好序，详见样例输入）和一个要查找的人员手机号，查找与该人员同时空人员的手机号（即与该手机号基站相同且进入与离开时间有重叠的手机号；若一手机号的进入时间与另一手机号的离开时间完全相同，两手机号也算有重叠。）。输出与指定手机号有时空重叠的手机号及所在基站。

基站的手机登录日志信息包括：手机号（11位的数字，按字符串处理）、基站编号（一共为6个基站，分别用大写字母A、B、C、D、E、F表示）、登录时间和登出时间（用长度为6的数字串表示，例如：093756，表示9点37分56秒）。

【输入形式】

先输入手机登录日志信息的条数（小于1000条），然后按上述格式分行输入手机登录日志信息，手机号、基站编号、登录时间和登出时间之间以一个空格分隔。

【输出形式】

按照手机号由小至大进行排序，分行输出与指定手机号有时空重叠的手机号及所在基站编号，手机号与基站编号之间以一个空格分隔。手机号相同时按基站字母序排序输出。

【样例输入】

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<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<string.h>
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
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

二、老鼠回家-无回路

【问题描述】

老鼠离家去找食物，要经过不断探索才能找到食物。某老鼠非常聪明，在原路返回时能够避免找食物时多走的冤枉路，找到直接回家的路。

编写程序，读入该老鼠找食物过程中的轨迹记录，然后分析出其原路回家的最佳路径（即：走过的路，但不包括冤枉路）。在此冤枉路指的是原路返回的路；而且假设老鼠走过的路不会形成环。

算法提示：使用栈保存老鼠走过的轨迹；每当读入老鼠新的轨迹时，检查栈顶元素，判断新轨迹能否与栈顶轨迹抵消（全部或部分），然后进行入栈或出栈操作，示例见样例说明。

【输入形式】

输入为一系列老鼠轨迹。老鼠轨迹以行进方向和步数对来表示。行进方向包括：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<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<string.h>
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);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

三、函数调⽤关系

【问题描述】

给定某能正常运⾏结束的⽤户函数调⽤栈信息（当⼀个函数被调⽤时将⼊栈，当调⽤返回时，将出栈）。编写程序，对函数调⽤栈信息进⾏分析，依据函数⼊栈和出栈信息，分析函数调⽤关系，即⼀个函数调⽤了哪些不同函数。并按运⾏时调⽤序输出调⽤关系。

说明：

在⼀个函数中，同⼀函数有可能被调⽤多次，输出调⽤关系时只输出⼀次；若⼀个函数没有调⽤其它函数，则不输出调⽤关系；

函数运⾏时调⽤序是指函数在调⽤栈中的出现序。

程序中不存在递归调⽤。函数名符合C语⾔标识符的规定，函数名⻓度不超过20，每个函数最多调⽤不超过10个不同函数，程序中⽤户定义的函数个数不超过100。
1
2
3
4
5

算法提示：当⼀个函数⼊栈时，它就是当前栈顶函数调⽤的⼀个函数。

【输⼊形式】

假设⽤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<stdio.h>
#include<string.h>
#include<stdlib.h>
#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]);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

注：以下两道题为助教原创题目：

四、东二食堂模拟

在这里插入图片描述

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#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++;
   }   
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

五、栈帧

在这里插入图片描述

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
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);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/爱喝兽奶帝天荒/article/detail/748490

考前刷题练手感（北航期末往年数据结构编程题）

目录

一、 查找同时空人员

二、 老鼠回家-无回路

三、函数调⽤关系

四、东二食堂模拟

五、栈帧

一、查找同时空人员

二、老鼠回家-无回路