首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和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
99
问题
阅读下列说明和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时*/
}
若连接排列为{8,7,4,2,5,1,9,3,10,6},即如图4-1所示,则最大不相交连接数为(7),包含的连线为(8) (用(i,π(i))的形式给出)。
选项
答案
(7)4 (8)(3,4)(5,5)(7,9)(9,10)
解析
本问题考查该算法的一个实例,理解了题干就可以直接计算出该实例的解,即最大不相交连接数为4,连线为:(3,4)(5,5)(7,9)(9,10)。
转载请注明原文地址:https://kaotiyun.com/show/QKDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
PGP协议采用RSA和IDEA两种加密算法组成链式加密体系,这种方案的优点是(1)。PGP还可以对电子邮件进行认证,认证机制是用MD5算法产生(2)位的报文摘要,发送方用自己的RSA私钥对(3)进行加密,附加在邮件中进行传送。公钥只用来加密(4),文件是用
L2TP协议是一种基于(1)协议的二层隧道协议,它结合了Cisco的L2F和MicrosoftPPTP的优点。该协议报文在传输层封装(2)协议之上,为了保证传输的可靠性,L2TP协议对控制报文采取了(3)机制,并要求tunne1对端设备在隧道(tunne
如果在网络设计过程中划分了很多VLAN,则可采用VTP来简化其管理。交换机管理IP地址只能创建在(1)中,而VTP信息只能在(2)端口上传播。共享相同VLAN数据库的交换机构成一个(3)。不同交换机平台、不同的IOS版本支持的VLAN数量不同,从图6-18
阅读以下在政务网中基于MPLS的IP-VPN应用服务的技术说明,回答问题1至问题5。【说明】为了保证政务外网各系统的安全,必须要为各系统的网络互联提供安全隔离及网络服务质量保证,使用基于MPLS的IP-VPN是在IP网上解决这种安全隔离的一种较好
ISDN分哪几层?NT2(网络终端连接设备)提供哪两种交换功能?请说出(1)的含义。
ADSL技术可以充分利用现有铜线网络,只要在用户线路两端加装ADSL设备即可为用户提供服务。请从以下术语选择适当的编号,将图5-9所示的拓扑结构中(1)~(4)空缺处的名称填写完整。【供选择的答案】A.程控交换机B.二层交换机
阅读以下说明然后完成问题1、问题2、问题3、问题4,把答案填入相应的对应栏内。[说明]如图10-1是Cisco1900交换机划分为两个vain拓扑图,把E0/10划分为vlan2,把E0/20划分为vlan3。[*]
请说出图9-1的拓扑结构名称与特点。PC2、PC4与PCI、PC3、PC5要连网且能相互访问,需要增添什么设备?
从图7-1中可以看出采用什么拓扑结构与设计方法?在“电视模块”中一般采用75欧的CATV电缆传输模拟信号,如果在“电脑模块”中也要采用75欧的CATV电缆传输信号,该怎么实现?
双绞线可以制作成直连线和交叉线两种形式,在图3-12所示的拓扑结构中,交换机与路由器(Router)相连的双绞线应制作成什么形式?利用IEEE802.1QVLAN中继协议进行不同VLAN之间数据的路由时,需要在原有的以太网帧中加入4字节的IEEE
随机试题
机械式油管锚按锚定方式分为张力式、压缩式和()式三种。
视网膜细胞层,由外向内依次为()
A.肋软骨炎B.心包炎C.主动脉夹层动脉瘤D.食管炎E.肋间神经痛沿肋间神经轴走向分布的电击样胸痛多见于
神经损伤后,轴突再生的速率一般约为
《建筑法》规定,从事建筑活动的( ),应当依法取得相应的执业资格证书,并在执业资格证书许可的范围内从事建筑活动。
在项目融资程序中,需要在融资结构设计阶段进行的工作是()。
某机电安装工程项目,在防腐管道施工过程中,根据施工工艺安排,在管道焊接时,项目经理部根据施工现场的实际情况,本着尽可能选择优质低耗,决定采用劳动强度低的焊接方法,即电弧焊。然而,在焊接施工过程中,不慎将未焊接的管道掉落,造成了部分施工机械损坏,并有1人受重
张某从高校应届毕业后到A公司工作,渴望领导重用自己,希望得到实现自我价值的机会,这表明张某正处于职业生涯的()。
下图为某大洲地形剖面示意图。读图回答问题。下列叙述正确的是()。
下列______不属于网络安全技术研究的主要问题。
最新回复
(
0
)