全国计算机技术与软件专业技术资格（水平）、考试
china_nejcer
2009年下半年下午-网络规划与设计师-下午试题及答案与解析（软考真题-案例分析）、 1 / 17 2009年下半年上午 网络规划与设计师
全国软考真题-答案与解析（含论文）
试题一（共20分）
阅读以下说明，回答问题1至问题4，将解答填入答题纸对应的解答栏内。
【说明】
阅读以下关于某城市公交集团企业网络设计的叙述，回答问题1、问题2和问题3。
某城市公交集团营运公司根据城市发展的需要，制定了公交集团2006年至2010年的信息规划。在规划中明确提出在集团范围内建设一个用于公交车辆监控、调度的企业网络，利用先进的信息化技术改造传统的管理和运作模式，大力提升公共交通的服务水平和提高运行效率、降低运行成本。
公交集团营运公司是一家拥有四个二级分公司、1万多名职工、2000名办公人员的国有独资公司，目前拥有公交场站50个、公交营运线路250条，日营运车辆5000辆，平均运距为6公里，线路总长度4000公里，每年营运的载客人数为1亿人次，年营运收入130亿元。
公交集团企业网络覆盖集团总部与四个二级分公司，要求在五年内能够对所有公交车辆完成实时轨迹监控和调度，同时能够为公交集团内部信息系统的运行提供网络支撑环境。
【问题1】
在需求分析阶段，设计单位了解到公交集团办公人员的工作时间是早上8:00至下午6:00，公交线路的运营时间是早上5:00至晚上10:00，在非工作时间，监控和调度网络基本处于闲置状态。
公交集团企业网络的应用主要包括四类，分别是车辆监控调度、办公和集团营运业务、场站视频监控和互联网访问。各类应用的当前需求调查情况如表1所示。
全国计算机技术与软件专业技术资格（水平）、考试
china_nejcer
2009年下半年下午-网络规划与设计师-下午试题及答案与解析（软考真题-案例分析）、 2 / 17
NOIP2009年普及组初赛题目及答案解析
一、单项选择题（共20题，每题1.5分，共计30分。每题有且仅有一个正确答案。）
1、关于图灵机下面的说法哪个是正确的：（D）
A.图灵机是世界上最早的电子计算机。
B.由于大量使用磁带操作，图灵机运行速度很慢。
C.图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。
D.图灵机只是一个理论上的计算模型。
【解析】所谓的图灵机就是指一个抽象的机器，它有一条无限长的纸带，纸带分成了一个一个的小方格，每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态，还有一些固定的程序。在每个时刻，机器头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。
2、关于计算机内存下面的说法哪个是正确的：（B）
A.随机存储器（RAM）的意思是当程序运行时，每次具体分配给程序的内存位置是随机而不确定的。
B.1MB内存通常是指1024*1024字节大小的内存。
C.计算机内存严格说来包括主存（memory）、高速缓存（cache）和寄存器（register）三个部分。
D.一般内存中的数据即使在断电的情况下也能保留2个小时以上。
【解析】A项：RAM不是位置随机，而是随时访问。所谓“随机存储”，指的是“当存储器中的消息被读取或写入时，所需要的时间与这段信息所在的位置无关。”
B项：1MB=1024KB,1KB=1024B
C项：计算机内存包括严格来说包括只读存储器（RAM）、随机存储器（ROM）和高速缓存（CACHE）。如果不严格来说只包含只读存储器和随机存储器。
D项：内存中的数据断电立即丢失。
3、关于BIOS下面说法哪个是正确的：（A）
A.BIOS是计算机基本输入输出系统软件的简称。B.BIOS里包含了键盘、鼠标、声卡、显卡、打印机等常用输入输出设备的驱动程序。
C.BIOS一般由操作系统厂商来开发完成。
历年NOIP选题题解汇总
联赛前上vijos板刷往年联赛题，使⽤在线编辑编写代码，祝我rp++。
废话不多说，挑⽐较有意思的记⼀下。
题⽬是按照年份排序的，最早只到了03年。
有些题⽬因为 我还没写/很早之前写的忘了 所以就没写题解。
NOIP2003
神经⽹络：按照题⽬怎么说怎么做，BFS即可。注意输出层是指出度为0的层，不是指深度最⼤的。
传染病防治：爆搜题，枚举每⼀层减掉哪个。复杂度不可算，理论在O(2^30*8!)左右，但好像强势不满。想了⼀会貌似卡不掉？
NOIP2004
⾍⾷算：知⼆推三，边搜边判。
NOIP2005
篝⽕晚会：⾸先你得知道两个排列可以看成若⼲个环，⽽且每个点只要转⼀次就可以转出来……⽽这题正好是两个排列的形式，即找到⼀个1-n的环和原环匹配最多就是不要动的⼈。把每个⼈在环中的1的位置记下来取最多的就好了。
过河：把边权>=100的缩成100，因为长度过长没有意义，⼤于100了前⾯的情况必然可以凑出来，然后在1000下暴⼒DP即可。注意特判S=T的情况，还有不要以为给出的点都在L内。
等价表达式：随便找⼏个数字(1~20)带进去算在模意义下都相等就可以了(跟解⽅程的思想有点像？)，重点是化为后缀表达式处理的trick。
NOIP2006
2^k进制数：⼤整数组合数。
NOIP2007
先坑着
NOIP2008
传纸条：显然的⽹络流，其实化为四维DP可做。
双栈排序：若存在iA[j]，即A[j]在A[i]前⾯弹栈。因为A[i]最终也要出栈，所以⽐A[i]还要⼤的、在[i,j]中间的⼀定不能和A[i]在同⼀个栈中，即构成⼆分图。判断有解就是⼆分图染⾊。输出……反正我铁定WA的输出因为数据⽔过去了，不予置评。
NOIP2009 Hankson的趣味题：醉题，复杂度O(nsqrt(B)logB)但是跑得过？反正我是不会什么更好的解法……
最优贸易：SPFA求出从1出发能买进的最低阶，从n出发沿反向边能卖出的最⾼价，最后枚举边减掉就好了。
第二十六届全国信息学奥林匹克竞赛
NOI 2009
第一试
竞赛时间：2009年7月27日上午8:00-13:00
题目名称 变换序列 诗人小G 二叉查找树
目录 transform poet treapmod
可执行文件名 transform poet treapmod
输入文件名 transform.in poet.in treapmod.in
输出文件名 transform.out poet.out treapmod.out
每个测试点时限 1秒 30 秒 1 秒
测试点数目 10 10 10
每个测试点分值 10 10 10
是否有部分分 无 有 无
题目类型 传统 传统 传统
提交源程序须加后缀
对于Pascal语言 transform.pas poet.pas treapmod.pas
对于C 语言 transform.c poet.c treapmod.c
对于C++ 语言 transform.cpp poet.cpp treapmod.cpp
注意：最终测试时，所有编译命令均不打开任何优化开关
变换序列
【问题描述】
对于N个整数0, 1, ……, N-1，一个变换序列T可以将i变成Ti，其中}1,,1,0{NTi且}1,,1,0{}{10NTNii。}1,,1,0{,Nyx，定义x和y之间的距离},min{),(yxNyxyxD。给定每个i和Ti之间的距离D(i,Ti)，你需要求出一个满足要求的变换序列T。如果有多个满足条件的序列，输出其中字典序最小的一个。
说明：对于两个变换序列S和T，如果存在p
【输入文件】
输入文件transform.in的第一行包含一个整数N，表示序列的长度。接下来的一行包含N个整数Di，其中Di表示i和Ti之间的距离。
【输出文件】
输出文件为transform.out。
如果至少存在一个满足要求的变换序列T，则输出文件中包含一行N个整数，表示你计算得到的字典序最小的T；否则输出”No Answer”（不含引号）。注意：输出文件中相邻两个数之间用一个空格分开，行末不包含多余空格。
