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

csdn推荐

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

目录

一、 查找同时空人员

【问题描述】

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

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

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

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

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

【输入形式】

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

【输出形式】

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

【样例输入】

28

F 060201 063539

B 063601 063802

C 063806 064607

D 064615 065816

A 065827 160003

D 160013 161605

C 161617 162633

B 162702 172333

C 080005 092537

A 100356 124732

C 125021 161619

F 162315 163857

B 163901 205602

C 210509 230108

D 230901 232556

B 060615 080239

E 120507 150309

C 162633 163621

B 163855 172209

D 200609 230901

A 070000 120203

F 130506 160000

B 160102 161503

C 161617 163058

E 163302 180709

D 190005 200729

D 000201 235051

C 003123 220806

【样例输出】

B

D

C

C

D

D

B

C

【样例说明】

先 输入了28条手机登录基站的日志信息,然后输入手机号,表示要查找与该手机号同时空的手机号。该手机号首先在6点6分15秒登录B 基站,在8点2分39秒登出B基站,在这个时间段内只有手机号 存在重叠;指定手机号登录登出过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 %cn",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

8 mysqrt

8 findA

8 findB

8 area

8 mysin

8 mycos

8 mysqrt

8 findC

8 area

8 mysin

8 mysqrt

8 max

8 output

【样例输出】

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("%sn",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 %dn",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("0n");
        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("%dn",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("%dn",c);
    for(int i=0;i<b;i++)
    {
        printf("%s(%d) ",S[0].stack[i].name,S[0].stack[i].frame);
    }
}

文章来源:https://blog.csdn.net/zxy13149285776/article/details/139884326



微信扫描下方的二维码阅读本文

© 版权声明
THE END
喜欢就支持一下吧
点赞8 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片

    暂无评论内容