C) http://www.noi.cn/
D) http://www.xinxixue.com/ 【分析】选择C 官网
20、 在参加NOI系列竞赛过程中，下面哪一种行为是 不被严格禁止的： A) 携带书写工具，手表和不具有通讯功能的电子词典进入赛场。
B) 在联机测试中通过手工计算出可能的答案并在程序里直接输出答案来获取分数。
C) 通过互联网搜索取得解题思路。
D) 在提交的程序中启动多个进程以提高程序的执行效果。
【分析】选择A 在NOI系列赛中，有时候会允许带书写工具和手表等的。 B项是明令禁止的，列为作弊行为。 C当然不行，一般不会连外部网络 D造成服务器宕机，影响赛事
二. 问题求解（共2题，每空5分，共10分）
1. 小陈现有2个任务A，B要完成，每个任务分别有若干步骤如下：A=a1->a2->a3，B=b1->b2->b3->b4->b5。在任何时候，小陈只能专心做某个任务的一个步骤。但是如果愿意，他可以在做完手中任务的当前步骤后，切换至另一个任务，从上次此任务第一个未做的步骤继续。每个任务的步骤顺序不能打乱，例如??a2->b2->a3->b3??是合法的，而?? a2->b3->a3->b2??是不合法的。小陈从B任务的b1步骤开始做，当恰做完某个任务的某个步骤后，就停工回家吃饭了。当他回来时，只记得自己已经完成了整个任务A，其他的都忘了。使计算小陈饭前已做的可能的任务步骤序列共有 __________ 种。
【分析】70
解法一：
相当于以前的A到B路程的问题，呵呵～～ a3 0 1 4 10 20 35
a2 0 1 3 6 10 15 a1 0 1 2 3 4 5
0 1 1 1 1 1 b1 b2 b3 b4 b5
能明白吧。然后把a3那一行加起来1+4+10+20+35=70。
解法二：
排列组合+加法原理
B任务中的b1一定做，而且肯定是第一个做的。除了b1外， 第一类：完成A任务 只有1种。
第二类：完成A任务和b2 有C(4,1)=4种。 第三类：完成A任务和b2、b3 有C(5,2)=10种。 第四类：完成A任务和b2、b3、b4 有C(6,3)=20种。 第五类：完成A任务和b2、b3、b4、b5有C(7,4)=35种。 加起来1+4+10+20+35=70。 2. 有如下的一段程序： 1. a:=1; 2. b:=a; 3. d:=-a; 4. e:=a+d; 5. c:=2*d; 6. f:=b+e-d; 7. g:=a*f+c;
现在要把这段程序分配到若干台（数量充足）用电缆连接的PC上做并行执行。每台PC执行其中的某几个语句，并可随时通过电缆与其他PC通讯，交换一些中间结果。假设每台PC每单位时间可以执行一个语句，且通讯花费的时间不计。则这段程序最快可以在_______单位时间内执行完毕。注意：任意中间结果只有在某台PC上已经得到，才可以被其他PC引用。例如若语句4和6被分别分配到两台PC上执行，则因为语句6需要引用语句4的计算结果，语句6必须在语句4之后执行。 【分析】5
可以画出一个拓扑图
1——>2——>4——6——7
\\——>3——/ / \\————5——/
第一时间1，第二时间2和3，第三时间4和5，第四时间6，第五时间7。
|
第十五届全国青少年信息学奥林匹克联赛初赛试题
（ 提高组 Pascal 语言 二小时完成 ）
○○ 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 ○○
一、单项选择题 （共10题，每题1.5分，共计15分，每题有且仅有一个正确答案。）
1、关于图灵机下面的说法哪个是正确的：
A）图灵机是世界上最早的电子计算机。
B）由于大量使用磁带操作，图灵机运行速度很慢。
C）图灵机只是一个理论上的计算模型。
D）图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。 【分析】选择C
A最早的计算机是ENIAC
B图灵机是计算机模型，没有运行速度，更谈不上磁带操作 D图灵机是英国人阿兰图灵提出的理论，
阿兰图灵本人在二战中破译德军密码系统发挥重要作用，而不是图灵机发挥作用。
2、关于BIOS下面的说法哪个是正确的：
A）BIOS是计算机基本输入输出系统软件的简称。
B）BIOS里包含了键盘、鼠标、声卡、图形界面显器等常用输入输出设备的驱动程序。
C）BIOS一般由操作系统厂商来开发完成。
D）BIOS能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。
【分析】选A
其实bios=Basic Input Output System。但是对于是否是软件这一说法还存在争议呢！
B中BIOS只存一些系统启动的基本信息，这些设备的驱动程序是不存的。 C项中BIOS一般是由单独的芯片厂家生产的，最著名的都是台湾的三家。 D项中，固件BIOS根本这些功能。
3、已知大写字母A的ASCII编码为65（十进制），则大写字母J的十六进制ASCII编码为：
A）48 B）49 C）50 D）以上都不是 【分析】选择D 64+9=74
4、在字长为16位的系统环境下，一个16位带符号整数的二进制补码为1111111111101101。其对应的十进制整数应该是：
A）19 B）-19 C）18 D）-18
【分析】选择B
1111111111101101的原码为1000000000010011 也就是-19，最高位为符号位。
5、一个包含n个分支结点（非叶结点）的非空满k叉树，k>=1，它的叶结点数目为：
A）nk+1 B）nk-1 C）(k+1)n-1 D）(k-1)n+1 【分析】选择D
考多叉树的性质，N0=(K-1)N+1，考试的时带入K=2时候，验证二叉树能得到结果。
6、表达式a*(b+c)-d的后缀表达式是：
A）abcd*+- B）abc+*d- C）abc*+d- D）-+*abcd
【分析】选择B
主要是考树的遍历，要明白前缀、中缀和后缀表达式。
构造二叉树，操作数做叶子节点，运算符做非叶节点。按中序遍历就可以得到中缀表达式。
7、最优前缀编码，也称Huffman编码。这种编码组合的特点是对于较频繁使用的元素给与较短的唯一编码，以提高通讯的效率。下面编码组合哪一组不是合法的前缀编码：
A）（00，01，10，11）
B）（0，1，00，11）
C）（0，10，110，111）
D）（1，01，000，001）
【分析】选择B
0是00的前缀码，这部分是数据结构中哈夫曼编码处的知识。
8、快速排序平均情况和最坏情况下的算法时间复杂度分别为： A）平均情况O(nlog(2,n))，最坏情况O(n^2)
B）平均情况O(n)，最坏情况O(n^2)
C）平均情况O(n)，最坏情况O(nlog(2,n))
D）平均情况O(log(2,n))，最坏情况O(n^2)
【分析】选择A
最好的时候是n×log（2，n），最坏情况的是退化成冒泡排序，复杂度为O（n^2）。
9、左图给出了一个加权无向图，从顶点V0开始用prim算法求最小生成树。则依次加入最小生成树的顶点集合的顶点序列为：
A）V0，V1，V2，V3，V5，V4
B）V0，V1，V5，V4，V3，V3
C）V1，V2，V3，V0，V5，V4
D）V1，V2，V3，V0，V4，V5