第二十届全国青少年信息学奥林匹克联赛初赛

一、单项选择题（共 20 题，每题 1.5 分，共计 30 分。每题有且仅有一个正确选项）

1. 以下哪个是面向对象的高级语言（ B ）

A.汇编语言   B.C++   C.Fortran   D.Basic

参考：对于计算机，分为低级语言和高级语言，低级语言：机器语言（01编码），高级语言：C++，P，C等，还有反人类的易语言，都称为汇编语言，故此题的高级语言就是C++。

/============================================================================================/

2. 1TB 代表的字节数量是（ D ）

A.2的10次方   B.2的20次方   C.2的30次方   D.2的40次方

参考：在存储单位中，每个单位的换算关系如下（从大到小）：1TB=1024GB，1GB=1024KB，1KB=1024MB，1MB=1024B，所以1TB=1024*1024*1024*1024B=2^40B，故选D

/============================================================================================/

3. 二进制数 00100100 和 00010101 的和是（ D ）

A. 00101000   B. 001010100   C. 01000101   D. 00111001

参考：列竖式，满二进一即可，00100100+00010101=00111001，故选D

/============================================================================================/

4. TCP 协议属于哪一层协议（ B ）

A. 应用层   B. 传输层   C. 网络层   D. 数据链路层

参考：TCP协议属于网络协议中的传输层，详见：

/============================================================================================/

5. 下列几个 32 位 IP 地址中，书写错误的是（ C ）

A. 162.105.128.27   B. 192.168.0.1   C. 256.256.129.1   D. 10.0.0.1

参考：对于一个IPv4地址，每位数中由小数点隔开，每个数字的范围为0~255，所以C中的256不符合，故选C

/============================================================================================/

6. 在无向图中，所有顶点的度数之和是边数的（ C ）倍

A. 0.5   B. 1   C. 2   D. 4

参考：这题可以简单的画一个三角形，没有箭头就是一个无向图了，每条边的出度入度和刚好就是边数的两倍，也就是说，每个顶点产生一条边，每个顶点都有一个出度和一个入度，等量代换便可知顶点的度数之和是边数的2倍，故选C

/============================================================================================/

7. 对长度为 n 的有序单链表，若检索每个元素的概率相等，则顺序检索到表中任一元素的平均检索长度为（ B ）

A. n/2   B. (n+1)/2   C. (n-1)/2   D. n/4

参考：对于顺序搜索单链表，平均检索长度计算为ASL=∑（i=1~n）PiCi=(1/n)*∑（i=1~n）*(1+2+3+4+5+…+n)=(1/n)*∑（i=1~n）*n(n+1)/2=(n+1)/2，在这个算式中，Pi为每个元素能被找到的几率（因为每个元素相同所以为1/n）

/============================================================================================/

8. 编译器的主要功能是（ B ）
A. 将一种高级语言翻译成另一种高级语言   B. 将源程序翻译成指令

C. 将低级语言翻译成高级语言   D. 将源程序重新组合

参考：计算机只能够识别01编码，我们用的高级语言是不能够识别，所以要编译器将高级语言翻译成机器语言（指令）才能运行，故选C

/============================================================================================/

9. 二进制数 111.101 所对应的十进制数是（ D ） 

A. 5.625   B. 5.5   C. 6.125   D. 7.625

参考：将二进制数转换为十进制数，需要从小数点处分隔开，这样整数部分为111，小数部分为0.101，对整数部分进行转换，从后往前，1*2^0+1*2^1+1*2^2=7，对小数部分进行转换，从前往后从小数点后一位开始往后，1*2^-1+0*2^-2+1*2^-3=0.625,这样整数部分和小数部分相加起来就是7+0.625=7.625，故选D。更详细的请参考：（第二题解析）

/============================================================================================/

10. 若有变量 int a，float x,y，且 a=7，x=2.5，y=4.7，则表达式 x+a%3*(int)(x+y)%2/4的值大约是（ A ）

A. 2.500000   B. 2.750000   C. 3.500000   D. 0.000000

参考：将表达式从前往后扫描，遇到x记录，然后计算a%3=1，然后遇到（x+y）=7.2，强制类型转换为int=7,7%2=1,1/4=0.25，但是由于C语言中计算结果都是不保留小数的，所以为0，加上前面的x，表达式的值=2.5+0=2.5，故选A

/============================================================================================/

11. 有以下结构体说明和变量定义，如图所示，指针 p、 q、 r 分别指向一个链表中的三个连续结点。

struct node {                       

int data;

struct node *next;

} *p, *q, *r;

现要将 q 和 r 所指结点的先后位置交换，同时要保持链表的连续，以下程序段中错误

的是（ D ）

A. q->next = r->next; p->next = r; r->next = q;

B. p->next = r; q->next = r->next; r->next = q;

C. q->next = r->next; r->next = q; p->next = r;

D. r->next = q; q->next = r->next; p->next = r;

参考：模拟一下交换的过程即可，但是D选项由于没有保存上一步的地址，所以会丢失，导致无法链起来，故选D

/============================================================================================/

12. 同时查找 2n 个数中的最大值和最小值，最少比较次数为（ C ） 

A. 3(n-2)/2   B. 4n-2   C. 3n-2   D. 2n-2

参考：这题的关键就是知道所用的查找方法，经过不懈推理，可以得出查找方法（这里我就不说我怎么推的了）：将2n个数每两个数分成一个数对，大的存放在一个数组中，小的存放在另一个数组里①，扫描大的数组，寻找出最大的数②，扫描小的数组，寻找出小的数③，就可以得出答案，①步需要n次，②步需要n-1次，③步也需要n-1次，所以三步加起来刚好就是3n+1，故选C

/============================================================================================/

13. 设 G 是有 6 个结点的完全图，要得到一棵生成树，需要从 G 中删去（ C ） 条边

A. 6   B. 9   C. 10   D. 15

参考：这题呢，可以直接画六个点出来，形成一个完全图，然后计算有多少条边记为n，删去只剩下5条边，则需要删去n-5=15-5=10条边，故选C

/============================================================================================/

14. 以下时间复杂度不是 O(n2)的排序方法是（ B ）

A. 插入排序   B. 归并排序   C. 冒泡排序   D. 选择排序

参考：归并排序作为很快的排序，是不会出现n^2级别的，而其他三个都需要n^2，故选B

/============================================================================================/

15. 以下程序段实现了找第二小元素的算法。 输入是 n 个不等的数构成的数组 S，输出 S 中第二小的数 SecondMin。在最坏情况下，该算法需要做（ C ）次比较

if (S[1] < S[2]) {

FirstMin = S[1];

SecondMin = S[2];

} else {

FirstMin = S[2];

SecondMin = S[1];

}

for (i = 3; i <= n; i++)

if (S[i] < SecondMin)

if (S[i] < FirstMin) {

SecondMin = FirstMin;

FirstMin = S[i];

} else {

SecondMin = S[i];

}
A. 2n  B. n-1  C. 2n-3  D. 2n-2

参考：去掉前面两个，即(n-2)，然后再扫描两次，即2*(n-1)，再加上最后一个=2*(n-1)+1=2n-3，故选C

/============================================================================================/

二、 不定项选择题（共 5 题，每题 1.5 分，共计 7.5 分；每题有一个或多个正确选项， 多选或少选均不得分）

1. 若逻辑变量 A、 C 为真， B、 D 为假， 以下逻辑运算表达式为真的有（ AB ）

A. (B ˅ C ˅ D) ˅ D ˄ A   B. ((¬A ˄B) ˅ C) ˄ ¬B

C. (A ˄ B) ˅ (C ˄ D ˅ ¬A)   D. A ˄ (D ˅ ¬C) ˄ B

参考：逻辑运算中，˅表示与，˄表示或，¬表示非

A项，从前往后，(B ˅ C ˅ D)假与真与假，结果为假，假与假或真，结果为真

B项，从前往后，（非真（假）或假）与真->假，假或非假（真）为真

C项，从前往后，（假或真）与（真或假与非真（假）->假），结果为假

D项，从前往后，真或（假与非真（假）->假）或假，结果为假

/============================================================================================/

2. 下列（ BCD ）软件属于操作系统软件。

A. Microsoft Word

B. Windows XP

C. Android

D. Mac OS X

E. Oracle

参考：Windows XP是微软推出的操作系统，现在国内大部分的用户使用的都是这个系统，A项的Microsoft Word是这个系统下的软件，Android系统是目前国内大部分手机的操作系统，Mac OS是苹果公司推出的操作系统，故此题选BCD。

/============================================================================================/

3. 在 NOI 比赛中，对于程序设计题，选手提交的答案不得包含下列哪些内容（ ABCDE ） 。

A. 试图访问网络

B. 打开或创建题目规定的输入/输出文件之外的其他文件

C. 运行其他程序

D. 改变文件系统的访问权限

E. 读写文件系统的管理信息

参考：在NOI比赛中，程序设计题目，能上传的只有源代码，其余的都不行，故选ABCDE。

/============================================================================================/

4. 以下哪些结构可以用来存储图（ AC ）

A. 邻接矩阵  B. 栈  C. 邻接表  D. 二叉树

参考：一般用来存储图的结构为邻接矩阵和邻接表，而栈和二叉树不能存储图，故选AC

/============================================================================================/

5. 下列各无符号十进制整数中，能用八位二进制表示的数有（ BD ）

A. 296  B. 133  C. 256  D. 199

参考：八位二进制，十进制的范围为：2⁷~2⁸-1，即：128~255，那么在这个区间的只有BD。

/============================================================================================/

三、 问题求解（共 2 题，每题 5 分，共计 10 分；每题全部答对得 5 分，没有部分分）

1. 由数字 1,1,2,4,8,8 所组成的不同的四位数的个数是___102___。

参考：

/============================================================================================/

2. 如图所示，图中每条边上的数字表示该边的长度，则从 A 到 E 的最短距离是___15____。

参考：这题可以使用狄杰特斯拉算法来求解，从A点开始，寻找与之相关的所有点，链接路径最短的（B），再从B开始，找与之相关所有点，链接路径最短的（C），这样下去，就找到了最短路径：A-B-C-F-H-D-E，总长度为：3+1+1+2+3+5=15

/============================================================================================/