首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 在一块电路板的上下两端分别有n个接线柱。根据电路设计,用(i,π(i))表示将上端接线柱i与下端接线柱Ⅱ(i)相连,称其为该电路板上的第i条连线。如图4.1所示的π(i)排列
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 在一块电路板的上下两端分别有n个接线柱。根据电路设计,用(i,π(i))表示将上端接线柱i与下端接线柱Ⅱ(i)相连,称其为该电路板上的第i条连线。如图4.1所示的π(i)排列
admin
2017-09-13
56
问题
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。
【说明】
在一块电路板的上下两端分别有n个接线柱。根据电路设计,用(i,π(i))表示将上端接线柱i与下端接线柱Ⅱ(i)相连,称其为该电路板上的第i条连线。如图4.1所示的π(i)排列为{8,7,4,2,5,1,9,3,10,6}。对于任何l≤i
π(j)。
在制作电路板时,要求将这n条连线分布到若干绝缘层上,在同一层上的连线不相交。现在要确定将哪些连线安排在一层上,使得该层上有尽可能多的连线,即确定连线集Nets={(i,π(i)),1≤i≤n}的最大不相交子集。
【分析问题】
记N(i,j)={t|(t,n(t))~Nets,t≤i,7c(t)≤j)。N(i,j)的最大不相交子集为MNS(i,j),size(i,j)=IMNS(i,j)|。
经分析,该问题具有最优子结构性质。对规模为n的电路布线问题,可以构造如下递归式:
【C代码】
下面是算法的C语言实现。
(1)变量说明
size
[j]:上下端分别有i个和j个接线柱的电路板的第一层最大不相交连接数
pi
:π(i),下标从1开始
(2)C程序
#include“stdlib”
#include
#define N 1 0 /*问题规模*/
int m=0; /*记录最大连接集合中的接线柱*/
void maxNum(int pi[],int si ze IN+1][N+1],int n) { /*求最大不相交
连接数*/
int i,j;
for(j=0;j
for(j:pi[1];j<=n;j++) (1); /*当j>=π(1)时*/
for(i=2;i
for(j=0;j
;j++) (2) ; /*当j
时*/
for(j=pi
;j<=n;j++) { /*当j>=C
时,考虑两种情况*/
size
[j]=size[i一1][j]>=size[i一1][pi
一1]+l?size[i一1][j]:
size[i一1][pi
一1]+1;
}
}
/*最大连接数*/
size[n][n] =size[n一1][n] >=si ze[n一1][pi[n]一1]+1? size[n一1][n]:
si ze[n一1][pi[n]一1]+1;
}
/*构造最大不相交连接集合,net
表示最大不相交子集中第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
[j]!=size[i一1][j]){ /*(i,pi
)是最大不相交子集的一条连线*/
(3) ; /*将i记录到数组net中,连接线数自增1*/
j=pi
-1; /*更新扩展连线柱区间*/
}
}
if(j >=pi[1]) net[m++] =1; /*当i=1时*/
}
根据以上说明和C代码,填充C代码中的空(1)~(3)。
选项
答案
(1)size[1][j]=1 (2)size[i][j]=size[i-1][i] (3)net[m++]=i或其等价形式
解析
本题考查算法设计和C语言实现算法的能力。
本题要求考试对常用的算法设计策略,包括分治法、动态规划、贪心算法、回溯法等有基本的掌握,并理解每类算法策略中的几个典型实例。
一般不要求考生设计问题的求解算法,但要求考生能够理解题目给出的算法设计思路,并补充C程序。如本题中的空(1),可以根据题干中递归式第一部分和C代码中的注释,得到答案size[1][j]=1。
空(2)则根据阅读题干中递归式第二部分和C代码中的注释,得到答案size
[j]=size[i-1]
。
空(3)则依据C代码中的注释,即可得到答案net[m++]=i。
转载请注明原文地址:https://kaotiyun.com/show/GKDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
在Internet上捕获并分析图8-16所示的网络中两个内部网络经由Internet通信的L2TPv2数据帧,请从以下4个选项中选择正确的答案填写到图8-17的(1)~(4)空缺处的相应位置。【供选择的答案】A.L2TPv2头
阅读以下应用L2TPv2协议实现VPN安全接入的技术说明,根据要求回答问题1至问题5。【说明】某企业应用L2TPv2协议部署企业的虚拟专用网(VPN),以方便企业的VIP用户及出差员工通过公共Internet安全地访问企业内部LAN资源,其网络拓
SSL是一个协议独立的加密方案,在网络信息分组的应用层和传输层之间提供了安全的通道。SSL主要包括SSL修改密文协议、SSL握手协议、SSL告警协议、SSL记录协议等,其协议栈见图7-16。请根据SSL协议栈结构,将(1)~(4)处空缺的协议名称填写完整。
如果在网络设计过程中划分了很多VLAN,则可采用VTP来简化其管理。交换机管理IP地址只能创建在(1)中,而VTP信息只能在(2)端口上传播。共享相同VLAN数据库的交换机构成一个(3)。不同交换机平台、不同的IOS版本支持的VLAN数量不同,从图6-18
阅读以下关于某硬件防火墙相关配置的技术说明,根据要求回答问题1至问题4。【说明】某单位在部署内部局域网时选用了一款硬件防火墙,该防火墙分别带有“WAN”、“LAN”“DMZ”、“FUN”等4个网络接口,支持Web界面、命令行等多种管理模式。该单位
非对称数字用户线(AsymmetricDigitalSubscriberLine,ADSL)是一种利用现有的传统电话线路高速传输数字信息的技术。ADSL技术可以充分利用现有铜线网路,只要在用户线路两端加装ADSL设备即可为用户提供服务。ADSL系统构
阅读以下关于ADSL宽带接入Internet的技术说明,请结合网络拓扑结构图,根据要求回答问题1至问题5。【说明】某边远山区的行政机关需要与该地区的市委行政机关进行网络互连,提高行政办事效率,并要求与Internet网互连,从而打开该山区原信息
ISDN分哪几层?NT2(网络终端连接设备)提供哪两种交换功能?请说出ISDN与传统PSTN的区别。
请用100字以内的文字说明该网管软件项目采用快速原型开发方法的优缺点。根据试题的描述信息分析,在最理想的情况下,需要多少天才能完成此网管软件开发任务?如果按保守的估计,则需要多少天才可完成此开发任务?(请列出简要的计算过程)
在如图1-23所示的网络拓扑结构图中,被路由协议可以使封装后的数据包通过互连网络进行中继传输,它由(1)使用。【供选择的答案】A.PCIB.RouterA和RouterBC.Internet网D.Rcrate
随机试题
为了保证建设工程的实施能够有足够的时间、空间、人力、财力和物力来保证计划的可行性,首先应在充分考虑( )等因素的前提下制定计划。
下列选项中,不属于贷前调查方法的是()。
下列对税负转嫁的说法,正确的是()。
生产物流控制内容不包括()。
在西方教育史上,被认为史现代教育代言人的是()
单位举办绿色环保宣传周活动,但是没有专项经费,宣传中也不允许耗费纸张,你怎么开展此次活动?
按照《巴塞尔协议Ⅲ》的要求,为了防止银行信贷增长过快并导致系统性风险的积累,要求银行在经济上行期提取一定比例的(),以便经济下行时释放。
在FDM中,主要通过(1)技术,使各路信号的带宽(2)。使用FDM的所有用户(3)。从性质上说,FDM比较适合于传输(4),FDM的典型应用是(5)。
Itisduetotheinventionofthecomputerthatmanhasbeenabletoworksomanywondersinthepastfewyears.Acase______is
A.decreasingB.underlinesC.deliveredD.missionsE.becauseF.putoffG.demandH.thoughI.playJ.improvingK.t
最新回复
(
0
)