首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和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
38
问题
阅读下列说明和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代码,算法采用了(4)算法设计策略。
函数maxNum和constructSet的时间复杂度分别为(5)和(6)(用O表示)。
选项
答案
(4)动态规划 (5)O(n
2
) (6)O(n)
解析
题干在叙述过程中,较明显的提到了动态规划策略的几个特点,如最优子结构,递归式,自底向上求解等,因此这是一个动态规划算法。算法的时间复杂度分析也较简单。函数maxNum中有两重循环,时间复杂度为O(n
2
)。函数constructSet中有一重循环,时间复杂度为O(n)。
转载请注明原文地址:https://jikaoti.com/ti/JMi7FFFM
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
如果以前已经配置过这台服务器为VPN服务器,现在需要重新配置,该怎么操作?VPN按技术可分为哪三类?
从工作的频段、数据传输速率、优缺点以及它们之间的兼容性等方面,对IEEE802.11a、IEEE802.11b和IEEE802.11g进行比较。简述WLAN用户通过RADIUS服务器登录的过程。
请回答以下有关组网的问题1~3。【说明】某公司规模扩大,既要考虑保证目前土建装修的效果不被破坏,又要满足网络扩容和企业工作实际需求,同时还要保证投资不要过大,经过深入分析和研究对比,决定采用无线局域网组网来解决网络扩容的问题,网络拓扑结构如
非对称数字用户线(AsymmetricDigitalSubscriberLine,ADSL)是一种利用现有的传统电话线路高速传输数字信息的技术。ADSL技术可以充分利用现有铜线网路,只要在用户线路两端加装ADSL设备即可为用户提供服务。ADSL系统构
在交换机上可以配置虚拟局域网(VLAN),以下是部分配置清单。回答问题1、问题2、问题3、问题4和问题5,将解答填入对应栏内。>enablegconfigtEnterconfigurationcommands,oneperli
上述配置中是否有问题?请指出并说明理由。解释配置中画线部分内容含义?
阅读以下说明,回答【问题1】~【问题4】,将解答填入空白处。【说明】某小型单位的网络图如图5所示,Cisco路由器有ISDN模块,单位通过ISDN连接Internet。ISDN是指近年来供最终用户使用的一套数字服务,包括电话网络的数字化,以便ISP
请用100字以内的文字说明该网管软件项目采用快速原型开发方法的优缺点。项目管理就是以项目为对象的系统管理方法,通过一个临时性的专门的柔性组织,对项目进行高效率的计划、组织、指导和控制,以实现项目全过程的动态管理和项目目标的综合协调与优化。除了本题涉及到
在如图1-23所示的网络拓扑结构图中,被路由协议可以使封装后的数据包通过互连网络进行中继传输,它由(1)使用。【供选择的答案】A.PCIB.RouterA和RouterBC.Internet网D.Rcrate
请问无线局域网的工作模式有哪几种?当不使用AP时,必须把一组需要互相通信的无线网卡的什么值设为相同?
随机试题
罹患率可以表示为
患者,男,42岁,既往体健,自诉乏力、口渴,多饮多食6个月。查24小时尿量为3000ml,尿比重为1.035。诊断应考虑
A.承山B.申脉C.昆仑D.次髎E.照海善于治疗痛经、腰骶痛的腧穴是
下列不属于艾灸的是
导致所有者权益减少的经济事项包括()。
商品运动对流通渠道的选择,很大程度上取决于交易的规模。工业用的生产原料,一般都会选择()。
当已知未成年人的个人隐私涉及()时可以允许相关人员开拆、查阅。
A、 B、 C、 D、 C每个图形均含有封闭图形,且奇数项的图形均由直线组成,偶数项均为由直线和曲线组成的非全封闭图形。故选C。
查询第一作者为“张三”的所有书名及出版社,正确的SQL语句是
A、Inthe15thcentury.B、Inthe6thcentury.C、Inthe5thcentury.D、Inthe16thcentury.D时间数字题。浏览选项可知,该题考查时问数字。文章开始就提到,Mr.Finc
最新回复
(
0
)