试题内容
试题四(共15分)
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。
【说明】
在一块电路板的上下两端分别有n个接线柱。根据电路设计,用(i,π(i))表示将上端接线柱i与下端接线柱π(i)相连,称其为该电路板上的第i条连线。如图4-1所示的π(i)排列为{8,7,4,2,5,1,9,3,10,6}。对于任何1≤i
在制作电路板时,要求将这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(i=2;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))的形式给出)。
软题库参考答案:暂时没有答案(仅供参考)
软题库解析:正在加载....
你可能感兴趣的试题
试题三(共15分)
阅读下列说明,回答问题1至问题3,将解答填入答题纸的对应栏内。
【说明】
某种出售罐装饮料的自动售货机(Vending Machine)的工作过程描述如下:
(l)顾客选择所需购买的饮料及数量。
(2)顾客从投币口向自动售货机中投入硬币(该自动售货机只接收硬币)。硬币器收集投入的硬币并计算其对应的价值。如果所投入的硬币足够购买所需数量的这种饮料且饮料数量足够,则推出饮料,计算找零,顾客取走饮料和找回的硬币;如果投入的硬币不够或者所选购的饮料数量不足,则提示用户继续投入硬币或重新选择饮料及数量。
(3)一次购买结束之后,将硬币器中的硬币移走(清空硬币器),等待下一次交易。自动售货机还设有一个退币按钮,用于退还顾客所投入的硬币。已经成功购买饮料的
钱是不会被退回的。
现采用面向对
阅读下列说明和Java代码,将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
某软件系统中,已设计并实现了用于显示地址信息的类Address(如图6-1所示),现要求提供基于Dutch语言的地址信息显示接口。为了实现该要求并考虑到以后可能还会出现新的语言的接口,决定采用适配器(Adapter)模式实现该要求,得到如图6-1所示的类图。
【Java代码】
import java.util.*;
Class Address{
public void street(){//实现代码省略}
public void zip(){//实现代码省略}
public void city(){//实现代码省略}
∥其他成员省略
}
class DutchAddress{<
试题1
阅读下列说明和数据流图,回答问题1至问题3。
说明
某图书管理系统的主要功能是图书管理和信息查询。对于初次借书的读者,系统自动生成读者号,并与读者基本信息(姓名、单位、地址等)一起写入读者文件。
系统的图书管理功能分为四个方面:购入新书、读者借书、读者还书以及图书注销。
1.购入新书时需要为该书编制入库单。入库单内容包括图书分类目录号、书名、作者、价格、数量和购书日期,将这些信息写入图书目录文件并修改文件中的库存总量(表示到目前为止,购入此种图书的数量)。
2.读者借书时需填写借书单。借书单内容包括读者号和所借图书分类目录号。系统首先检查该读者号是否有效,若无效,则拒绝借书;若有效,则进一步检查该读者已借图书是否超过最大限制数(假设每位读者能同时借阅的书不超过5本),若已达到最大限制数,则拒绝借书;否则允许借书,同时将图书分类目录号、读者号和借阅日期等信息写入借书文件中。
3.读者还书时需填写还书单。系统根据读者号和图书分类目录号,从借书文件中读出与该图书相关的借阅记录,标明还书日期,再写回到借书文件