2024双学位课程-数据机构与算法-第四次机考

公告
请留意阅读

数据结构与算法(2024年春)机考(第4次)
账号将被绑定在首次登录的 IP 上
可以查阅纸质资料,不可以使用任何电子设备,手机等电子设备请关机并放置于书包内,禁止交流。
考试结束后会有代码相似度检查(换变量名、换位置是没有用的哦)

2024年6月13日,8:00 ~ 9:30,共计90分钟

没有罚时

OI制,提交后测评所有Case(而不是遇到Wrong Answer就停止),有部分分

可以使用 C(支持C99标准) 和/或 C++(C++11) 提交

这些代码供你参考

/*

使用优先队列实现Dijkstra
dist[MAXN]记录路径长度和

*/

void DijkstraPQ(int startv,int endw)
{
    int i,j,k,min;
    priority_queue<pathSum> pq;  //队列元素(pre,v,costSum)pre,以及通过pre到达v的路径长度
    bool s[MAXN]={false};
    for(i=1;i<=MAXN;i++) dist[i]=INF;

    //以“startv”作为源点,初始化S和dist数组,由于题目不要求记录路径所以不存pre
    dist[startv]=0;
    s[startv]=true;


    for(auto &e:edgeFrom[startv])  pq.push({e.u,e.v,e.cost});

    while(!pq.empty())
    {
        pathSum tmp=pq.top();
        pq.pop();

        if(tmp.v==endw)//已找到到达目的地的最短路
        {
            cout<<tmp.costSum<<endl;
            exit(0);
        }
        if (s[tmp.v]) continue;  //优先队列中的元素不能更新,所以可能有无效边
        /*
            出队的顶点tmp.v加入到最短路径树,检查所有从v出发的边,更新队列
        */
        s[tmp.v]=true;
        dist[tmp.v]=tmp.costSum;
        //cout<<"a path add into the shortest Tree: ("<<tmp.pre<<" "<<tmp.v<<" "<<tmp.costSum<<")"<<endl;

        for(auto &e:edgeFrom[tmp.v]) //,一条边,e(u,v, cost)
        {
            int w=e.v;
            if(!s[w]&&(dist[w]>tmp.costSum+e.cost))
            {
                dist[w]=tmp.costSum+e.cost;
                pq.push({tmp.v,w,dist[w]});
                /*  算法逻辑应该是:
                    if(pq contians w), update w to  {tmp.v,w,dist[w]} ;
                    else pq.insert({tmp.v,w,dist[w]});
                    由于优先队列不支持按w索引修改,所以都插入。pop时增加判断
                */

            }
        }
    }
    return;
}

void siftdown(int a[], int i, int n) 
{   int j,t;
    t=a[i];
    while ( (j=2*i+1)< n  )  //当i有子结点的时候才需要调整
     { //让j指向a[i]左子结点和右子结点(如果有)中键值较大的一个
        if (j<n-1  &&  a[j]<a[j+1] ) j++;
        if  (t < a[j]) //如果t比子结点小,不符合堆的定义
        {   a[i]=a[j];  //将较大的值放入根a[i]。
            //a[j]=t; //“交换”,因为还要继续向下调整,                   所以可省略a[j]=t的操作
            i=j;  //  结点a[j]作为新的将要调整的子树的根,                           }
         else break;//t不小于左右子结点,符合定义,终止循环
     }
     a[i]=t;    //若循环中省略,则循环终止后, t填入当前停止的结点
}


void swim(int a[], int k) 
//适用条件: a[k]是序列最后一个结点,之前的结点是一个堆。
//方法:由于a[k]比它的父结点大,破坏了堆,通过交换它和它的父结点来修复
{   
    while ( k>0 && a[(k-1)/2]< a[k]  ) 
     {      swap(a[(k-1)/2],a[k] ); 
                //将较大的值和它的父结点交换
            k= (k-1)/2;  
            //  结点k作为新的将要调整的结点
     }
}


void floyd(int n)
{   int i,j,k;
    for(i=1;i<=n;i++)   //读入有向边,为递推矩阵赋初值
      for(j=1;j<=n;j++)     {   a[i][j]=cost[i][j];
                    path[i][j]=0;    }
    //嵌套循环,递推求A(k)
    for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
               for(j=1;j<=n;j++)
            if(a[i][k]+a[k][j]<a[i][j])
                { a[i][j]=a[i][k]+a[k][j];
                  path[i][j]=k;
                }
}

比赛信息

  • 时长: 1 小时 40 分钟
  • 开始时间: 2024-06-13 07:50 (5 月,4 周前)
已结束
NaN