初赛模拟赛I 试题解析

这次的题目来源于oifans的模拟赛。在这里表示感谢。由于是第一次举办初赛模拟赛，所以题目有的地方不尽如人意，我们将一步步改进。

一、单项选择题（共 10 题，每题 1.5 分，共计 15 分。每题有且仅有一个正确答案）

1.本题考察计算机基本硬件CPU当中运算器的功能，选B

2.CD-ROM是Compact Disc Read-Only Memory的缩写，意为只读光盘，选A

3.Fedora、Redhat AS、Ubuntu以及红旗桌面都是Linux的发行版，Netware是另一种操作系统，选D

4.根据栈的性质，应选B

5.此表达式为“按位或”运算，25或31，化为二进制，进行按位或运算，应该是31，选E

6.本题考察运算的优先级，选C

7.考察对完全二叉树的理解及扩展，选C

8.有n个顶点的连通无相图，边数至少为n-1，选A

9.考察IT业时事，应该是惠普（HP），选E

10.考察进制转化，选D

二、多项选择题（共 10 题，每题 1.5 分，共计 15 分。每题正确答案的个数大于或等于 1。多选或少选均不得分）

11.AC符合标准，B是内网IP地址，D中最后一个数超过了255，故D错。选AC

12.根据Pascal和C的语言规定，用户自定义标识符必须由数字和字母组成，且开头必须是字母（C语言可包含“_”），而A的系统预留的标识符，故ABCD均不符合标准，选ABCD

13.考察进制运算，选ABCD

14.考察栈的性质，A正确，B、C无法实现，而D需要栈的大小为5，所以选A

15.Dos、Windows 9X系列都是单用户操作系统，Windows NT/2000 Server/2003、Linux、Unix都为多用户操作系统，对于Windows 2000 Pro、Windows XP、Windows Vista的界定尚有争议，故选BCD

16.希尔排序的时间复杂度并不是O(nlog2n)，故选ABC

17.GIF、PSD、PNG、JPG、BMP……都是常见图形格式文件的扩展名，而OGG是一种音乐文件的扩展名。故选ACD

18.阿兰·麦席森·图灵（Alan Mathison Turing）是英国人，D中存储程序和程序控制是冯·诺依曼提出的，BC都正确，故选BC

19.内存、L1高速缓存都是RAM，断电后无法保存数据，故选AB

20.将高级语言程序转换为可执行文件称为编译，故选D

三、问题求解（共 2 题，每题 5 分，共计 10 分）

1.分类讨论，当m=6，n=5时，可分为（500000,410000,311000,320000,211100,221000,111110），选法数

2.3次，具体方案：

A.先将球分成3，3，4三堆，两堆3个的上天平称（第一次），如果平衡，则->B，如果不平衡，则->C

B.证明这6个都合格，剩余的4个其中有1个不合格，再分3个出来跟3个合格球称（第二次），如果平衡，则->B1，如果不平衡，则->B2

B1.证明剩余的1个不合格，跟合格球称（第三次）可知轻重

B2.证明不合格球在这3个之中，根据跟合格球的对比也已经知道不合格球是轻或重。将其中2球放天平称（第三次），平衡则剩余1球不合格，不平衡则根据轻重可判断哪1球不合格

C.将重的一端设为a堆，轻的一端设为b堆，剩余4个已证明合格，设为c堆。

a堆取1个，b堆取2个，放天平左边；b堆再取1个，c堆取2个，放天平右端。（第二次）

如果左边重右边轻，则->C1

如果左边轻右边重，则->C2

如果平衡，则->C3

C1.证明左边的a球是重球或者右边的b球是轻球，这2球任取1个跟合格球称（第三次），如果平衡则另1球不合格，如果不平衡，则上称的球不合格，并且都知道轻或重

C2.证明左边的2个b堆球其中有1个轻球，同C1一样，只要取其中1球跟合格球称（第三次），可知道哪1个球是轻球

C3.证明a堆剩余2个有1个重球，将这2球在天平上一对比（第三次）就知道哪一个是重球了

四、阅读程序写结果（共 4 题，每题 8 分，共计 32 分）

1.考察基本的运算和程序阅读，注意负数的取模和取整除运算的方法，答案为14:35，注意结果输出格式！

2.考察对“希尔排序”这一常用排序方法的认识，了解主程序在排序后问题很简单（和原数相同为1，不同为0），注意最后倒序输出，结果为0010010100。

3.考察基本的字符串函数，答案为mr。

4.首先看出work函数其实是在求 ，根据程序发现是求 ，根据公式 可得，此式=212-1=4095