专业软件设计师网站|培训机构|服务商(加客服微信:cnitpm或QQ:947530340进软件设计师学霸群)

软题库 培训课程
当前位置:信管网 >> 软件设计师 >> 案例分析 >> 文章内容
2022年上半年软件设计师案例分析真题模拟试题及答案(5)
来源:信管网 2022年05月07日 【所有评论 分享到微信
  • 试题一:阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。
    【说明】
    在一块电路板的上下两端分别有n个接线柱。根据电路设计,用(i,π(i))表示将上端接线柱i与下端接线柱π(i)相连,称其为该电路板上的第i条连线。如图4-1所示的π(i)排列为{8,7,4,2,5,1,9,3,10,6}。对于任何1≤iπ(j)。
    在制作电路板时,要求将这n条连线分布到若干绝缘层上,在同一层上的连线不相交。现在要确定将哪些连线安排在一层上,使得该层上有尽可能多的连线,即确定连线集Nets={(i,π(i)),1≤i≤n}的最大不相交子集。

    【分析问题】
    记N(i,j)={t|(t,π(t))∈Nets,t≤i,π(t)≤j}。N(i,j)的最大不相交子集为MNS(i,j),size(i,j)=|MNS(i,j)|。
    经分析,该问题具有最优子结构性质。对规模为n的电路布线问题,可以构造如下递归式:

    【C代码】
    下面是算法的C语言实现。
    (1)变量说明
    size[i][j]:上下端分别有i个和j个接线柱的电路板的第一层最大不相交连接数
    pi[i]:π(i),下标从1开始
    (2)C程序   #include"stdlib.h"
    #include
    #define N   10         /*问题规模*/
    Int m=0;            /*记录最大连接集合中的接线柱*/
    Void maxNum(intpi[],intsize[N+1][N+1],intn){/*求最大不相交连接数*/
    int i,j;
    for(j=0;j for(j=pi[i];j<=n;j++)(1); /*当j>=π(1)时*/
    for(i=2;i for(j=0;j for(j=pi[i];j<=n;j++) { /*当j>=c[i]时,考虑两种情况*/
    size[i][j]=size[i-l][j]>=size[i-l][pi[i]-l]+1?size[i-l][j]:
    size[i-l][pi[i]-l]+l;
    }
    }
    /*最大连接数*/
    size[n][n]=size[n-l][n]>=size[n-l][pi[n]-l]+1?size[n-l][n]:size[n-l][pi[n]-l]+l:
    }
    /*构造最大不相交连接集合,net[i]表示最大不相交子集中第i条连线的上端接线柱的序号*/
    void constructSet(int pi[],int size[N+1][N+1],int n,int net[n]){
    int i,j=n;
    m=0;
    for(i=n;i>1;i--)     {/*从后往前*/
    if(size[i][j]!=size[i-l][j]){/*(i,pi[i])是最大不相交子集的一条连线*/
    (3);                 /*将i记录到数组net中,连接线数自增1*/
    j=pi[i]-1;             /*更新扩展连线柱区间*/
    }
    }
    if(j>=pi[l])net[m++]=l;         /*当i=1时*/
    }
    【问题1】(6分)
    根据以上说明和C代码,填充C代码中的空(1)~(3)。
    【问题2】(6分)
    根据题干说明和以上C代码,算法采用了(4)算法设计策略。
    函数maxNum和constructSet的时间复杂度分别为(5)和(6)(用O表示)。
    【问题3】(3分)
    若连接排列为{8,7,4,2,5,1,9,3,10,6},即如图4-1所示,则最大不相交连接数为(7),包含的连线为(8)(用(i,π(i))的形式给出)。

    查看答案

    参考答案:

    参考解析:www.cnitpm.com/st/3816623561.html

    信管网考友试题答案分享:

  • 试题二:阅读以下说明和C代码,将应填入  (n)  处的字句写在的对应栏内。
    【说明】
    在一个简化的绘图程序中,支持的图形种类有点(point)和圆(circle),在设计过程中采用面向对象思想,认为所有的点和圆都是一种图形(shape),并定义了类型shape t、 point t和circle t分别表示基本图形、点和圆,并且点和圆具有基本图形的所有特征。
    【C代码】
    typedef enum { point,circle } shape type;   /* 程序中的两种图形:点和圆 */
    typedef struct {             /* 基本的图形类型 */
    shape_type  type;        /* 图形中类标识:点或者圆*/
    void (*destroy) ();       /* 销毁图形操作的函数指针*/
    void (*draw) ();          /* 绘制图形操作的函数指针*/
    } shape_t;
    typedef struct {  shape_t common;  int x;  iht y;  } point_t;  /* 定义点类
    型, x, y为点坐标*/
    void destroyPoint (point_t* this)  { free (this); printf ("Point destoryed!
    \n"); } )  /* 销毁点对象*/
    void drawPoint(point_t* this)  { printf("P(%d,%d)", this->x, this->y);  }
    /* 绘制点对象*/
    shape_t* createPoint (va_list* ap)  (/* 创建点对象,并设置其属性*/
    point_t*  p_point;
    if ( (p_point= (point_t*)malloc (sizeof (point_t)) ) ==NULL) returnNULL;
    p_point->common, type = point; p_point->common, destroy = destroyPoint;
    p_point->common.draw = drawPoint;
    p_point->x = va_arg(*ap, int);       /* 设置点的横坐标*/
    p_point->y = va_arg(*ap, int);       /* 设置点的纵坐标*/
    return  (shape_t*)p_ooint;               /*返回点对象指针*/
    }
    typedef struct {    /*定义圆类型*/
    shape_t  common;
    point_t  4center;     /*圆心点*/
    int   radius;          /*圆半径*/
    } circle_t;
    void destroyCircle(circle_t* this){
    free(  (1)  );        free(this);      printf("Circle destoryed!\n");
    }
    void drawCircle(circle_t* this)  {
    print f ("C (");
    (2)  .draw(this->center);   /*绘制圆心*/
    printf(",%d) ",  this->radius);
    }
    shape_t* createCircle(va_list4 ap)  {     /*创建一个圆,并设置其属性*/
    circle_t4  p circle;
    if ((p_circle = (circle_t4)malloc (sizeof (circle_t)) ) ==NULL ) return NULL;
    p_circle->common.type = circle; p_circle->common.destroy = destroy
    Circle;
    p_circle->common.draw = drawCircle;
    (3)    = createPoint(ap);      /* 设置圆心*/
    p_circle->radius = va_arg(*ap, int);     /* 设置圆半径*/
    return  p_circle;
    }
    shape_t* createShape(shape_type st, "')  {    /* 创建某一种具体的图形*/
    va_list   ap;                      /*可变参数列表*/
    shape_t4  p_shape = NULL;
    (4)   (ap, st);
    if( st == point )   p shape = createPoint(&ap);   /* 创建点对象*/
    if( st == circle )  p shape = createCircle(&ap);   /*创建圆对象*/
    va_end (ap);
    return p_shape;
    }
    int main( )  {
    int i;                  /* 循环控制变量,用于循环计数*/
    shape_t* shapes[2];     /* 图形指针数组,存储图形的地址*/
    shapes[0] = createShape( point, 2, 3);       /* 横坐标为2,比值坐标为3*/
    shapes[ii = createShape( circle, 20,  40, 10);   /* 圆心坐标(20,40),
    半径为 10*/
    for(i=0 i<2; i++) { shapes[i]->draw(shapes[i]);  printf("\n");  } /*
    纵制数组中图形*/
    for( i = 1; i >= 0; i-- )  shapes[i]->destroy(shapes[i]);   /* 销毁
    数组中图形*/
    return 0;
    }
    【运行结果】
    P(2,3)
    (5)
    Circle destoryed !
    Point destoryed !

    查看答案

    参考答案:

    参考解析:www.cnitpm.com/st/2456118617.html

    信管网考友试题答案分享:

阅读推荐:

【点击查看:2022年上半年软件设计师真题答案及解析

【点击查看:历年软件设计师真题答案下载及在线做题

【点击查看:信管网软件设计师培训课程

更多有关2022年上半年软件设计师真题模拟试题的信息,请关注信管网软件设计师真题频道【点击查看

扫码关注公众号

温馨提示:因考试政策、内容不断变化与调整,信管网网站提供的以上信息仅供参考,如有异议,请以权威部门公布的内容为准!

信管网致力于为广大信管从业人员、爱好者、大学生提供专业、高质量的课程和服务,解决其考试证书、技能提升和就业的需求。

信管网软考课程由信管网依托10年专业软考教研倾力打造,官方教材参编作者和资深讲师坐镇,通过深研历年考试出题规律与考试大纲,深挖核心知识与高频考点,为学员考试保驾护航。面授、直播&录播,多种班型灵活学习,满足不同学员考证需求,降低课程学习难度,使学习效果事半功倍。

相关内容

发表评论  查看完整评论  

推荐文章