CSP-J1 (NOIP普及组)近十年初赛考点整理

进制

1.十进制小数125.125对应的8进制数是（）NOIP 2009 普及组初赛
A. 100.1
B. 175.175
C. 175.1
D. 100.175

解析：B

$ 1758 = 1 \times 8^2 + 7 \times 8 + 5 = 125 0.18 = \frac{1}{8} = 0.125 $
所以，$ 175.18 = 125.125 $

2.一个字长为8位的整数的补码是11111001，则它的原码是（）。NOIP 2010 普及组初赛

A. 00000111
B. 01111001
C. 11111001
D. 10000111

解析：D

正数的原码、反码、补码都一样。
负数的补码为原码取反加$1$，原码为补码减$1$取反（注意最高位的$1$是符号位，不用取反）。

3.在二进制下，1011001 + （） = 1100110。NOIP 2011 普及组初赛

A. 1011
B. 1101
C. 1010
D. 1111

解析：B

相加即可，超过1要进位

4.十六进制数9A在（）进制下是232。NOIP 2012 普及组初赛

A. 四
B. 八
C. 十
D. 十二

解析：B

十六进制$9A$转化为十进制：$9 \times 16 + 10 = 154$
八进制$232$化为十进制：$2 \times 8^2 + 3 \times 8 + 2 = 154$

常识

1.计算机如果缺少（），将无法正常启动。NOIP 2012 普及组初赛

A. 内存
B. 鼠标
C. U盘
D. 摄像头

解析：A

2.目前计算机芯片（集成电路）制造的主要原料是（），它是一种可以在沙子中提炼出的物质。NOIP 2012 普及组初赛

A. 硅
B. 铜
C. 锗
D. 铝

解析：A

3.（）不属于操作系统。NOIP 2012 普及组初赛

A. Windows
B. DOS
C. Photoshop
D. NOI Linux

解析：C
Photoshop是一种图像处理软件

4.目前个人电脑的（）市场占有率最靠前的厂商包括Intel、AMD等公司。NOIP 2012 普及组初赛

A. 显示器
B. CPU
C. 内存
D. 鼠标

解析：C

5.1946年诞生于美国宾夕法尼亚大学的ENIAC属于（）计算机。NOIP 2012 普及组初赛

A. 电子管
B. 晶体管
C. 集成电路
D. 超大规模集成电路

解析：A

ENIAC，全称为Electronic Numerical Integrator And Computer，即电子数字积分计算机。ENIAC是世界上第一台通用计算机，也是继ABC（阿塔纳索夫-贝瑞计算机）之后的第二台电子计算机。ENIA使用的元件是电子管。它于1946年2月14日在美国宣告诞生。
晶体管计算机是第二代电子计算机。1954年，美国贝尔实验室研制成功第一台使用晶体管线路的计算机，取名“催迪克”（TRADIC），装有800个晶体管。在20世纪50年代之前第一代，计算机都采用电子管作元件。
1958年，美国德州仪器的工程师Jack Kilby发明了集成电路（IC），将三种电子元件结合到一片小小的硅片上。更多的元件集成到单一的半导体芯片上，计算机变得更小，功耗更低，速度更快。这一时期的发展还包括使用了操作系统，使得计算机在中心程序的控制协调下可以同时运行许多不同的程序。1964年—1972年的计算机叫集成电路计算机。
1967年和1977年分别出现了大规模和超大规模集成电路。由大规模和超大规模集成电路组装成的计算机，被称为第四代电子计算机。

6.矢量图（Vector Image）图形文件所占的贮存空间比较小，并且无论如何放大、缩小或旋转等都不会失真，是因为它（）。

A. 记录了大量像素块的色彩值来表示图像
B. 用点、直线或者多边形等基于数学方程的几何图元来表示图像
C. 每个像素点的颜色信息均用矢量表示
D. 把文件保存在互联网，采用在线浏览的方式查看图像

解析：B

7.（）是主要用于显示网页服务器或者文件系统的HTML文件的内容，并让用户与这些文件交互的一种软件。NOIP 2012 普及组初赛

A. 资源管理器
B. 浏览器
C. 电子邮件
D. 编译器

解析：B

8.地址总线的位数决定了CPU可直接寻址的内存空间大小，例如地址总线为16位，其最大的可寻址空间为64KB。如果地址总线是32位，则理论上最大可寻址的内存空间为（）。NOIP 2012 普及组初赛

A. 128KB
B. 1MB
C. 1GB
D. 4GB

解析：D

9.蓝牙和Wi-Fi都是（）设备。NOIP 2012 普及组初赛

A. 无线广域网
B. 无线城域网
C. 无线局域网
D. 无线路由器

解析：C

10.仿生学的问世开辟了独特的科学技术发展道路。人们研究生物体的结构、功能和工作原理，并将这些原理移植于新兴的工程技术中。以下关于仿生学的叙述，错误的是（）NOIP 2012 普及组初赛

A. 由研究蝙蝠，发明雷达
B. 由研究蜘蛛网，发明因特网
C. 由研究海豚，发明声纳
D. 由研究电鱼，发明伏特电池

解析：B

11.中国计算机学会于（）年创办全国青少年计算机程序设计竞赛。

A.1983

B.1984

C.1985

D.1986

解析:B

数据结构

1.（）是一种先进先出的线性表。NOIP 2012 普及组初赛

A. 栈
B. 队列
C. 哈希表（散列表）
D. 二叉树

解析：B

2.如果一个栈初始时为空，且当前栈中的元素从栈底到栈顶依次为a，b，c，另有元素d已经出栈，则可能的入栈顺序是（）。NOIP 2012 普及组初赛
A. a, d, c, b
B. b, a, c, d
C. a, c, b, d
D. d, a, b, c

解析：D

栈的特征是先进后出。a必然比b元素早入栈，b必然比c元素早入栈。
本题的出入栈顺序为：d入栈–>d出栈–>a入栈–>b入栈–>c入栈。

树

1.如果一棵二叉树的中序遍历是BAC，那么它的先序遍历不可能是（）。NOIP 2012 普及组初赛

A. ABC
B. CBA
C. ACB
D. BAC

解析：C

中序遍历为BAC的情况有上面五种，对应的前序遍历分别是ABC, CAB, BAC, CBA, BCA

根节点深度为$0$，一棵深度为$h$ 的满$k$（$k>1$）叉树，即除最后一层无任何子节点外，每一层上的所有结点都有$k$ 个子结点的树，共有（）个结点。 NOIP 2018 普及组初赛

A.$\frac{k^{h+1}-1}{k-1}$

B.$k^{h-1}$

C.$k^h$

D.$\frac{k^{h-1}}{k-1}$

解析:

1）假设$h=2，k=2$，画出完美二叉树，共$7$个节点。

2）对4个答案代入运算，结果为$A$

如果想理解和推导公式：

算法思想

1.使用冒泡排序对序列进行升序排列，每执行一次交换操作系统将会减少1个逆序对，因此序列 5，4，3，2，1需要执行（）次操作，才能完成冒泡排序。NOIP 2012 普及组初赛

A. 0
B. 5
C. 10
D. 15

解析：C

第一轮4次；第二轮3次，第3轮2次，第4轮1次，加起来就是10次。

2.（）就是把一个复杂的问题分成两个或更多的相同类似的子问题，再把子问题分解成更小的子问题……直到最后的子问题可以简单地直接求解。而原问题的解就是子问题解的并。NOIP 2012 普及组初赛

A. 动态规划
B. 贪心
C. 分治
D. 搜索

解析：C

分治算法不是具体的算法，而是一种算法思想。
典型的分治算法有二分查找法和快速排序法。

3.在程序运行过程中，如果递归调用的层数过多，会因为（）引发错误。NOIP 2012 普及组初赛

A. 系统分配的栈空间溢出
B. 系统分配的堆空间溢出
C. 系统分配的队列空间溢出
D. 系统分配的链表空间溢出

解析:A

网络有关

1.无论是TCP/IP模型还是OSI模型，都可以视为网络的分层模型，每个网络协议都会被归入某一层中。如果用现实生活中的例子来比喻这些“层”，以下最恰当的是（）。

A. 中国公司的经理与波兰公司的经理交互商业文件

B. 军队发布命令

C. 国际会议中，每个人都与他国地位对等的人直接进行会谈

D. 体育比赛中，每一级比赛的优胜者晋级上一级比赛

解析：A

OSI七层网络模型和TCP/IP四层网络模型如上图所示。
对于通信的双方来说，双方的上下层之间可以互相通信，然后双方通过最底层与对方通信。

B是上级向下级下达命令。
C是地位对待的层可以直接互相通信。
D是下层逐级上升。

2.（）是目前互联网上常用的E-mail服务协议。

A. HTTP
B. FTP
C. POP3
D. Telnet

解析：C

超文本传输协议HTTP(HyperText Transfer Protocol)是互联网上应用最为广泛的一种网络协议。打开某个网址就会用到这个协议。

FTP(File Transfer Protocol）是文件传输协议。

POP3是Post Office Protocol 3的简称，即邮局协议的第3个版本,它规定怎样将个人计算机连接到Internet的邮件服务器和下载电子邮件的电子协议。它是因特网电子邮件的第一个离线协议标准,POP3允许用户从服务器上把邮件存储到本地主机（即自己的计算机）上,同时删除保存在邮件服务器上的邮件，而POP3服务器则是遵循POP3协议的接收邮件服务器，用来接收电子邮件的。

SMTP 的全称是“Simple Mail Transfer Protocol”，即简单邮件传输协议。它是一组用于从源地址到目的地址传输邮件的规范，通过它来控制邮件的中转方式。SMTP 协议属于 TCP/IP 协议簇，它帮助每台计算机在发送或中转信件时找到下一个目的地。SMTP 服务器就是遵循 SMTP 协议的发送邮件服务器。
SMTP 认证，简单地说就是要求必须在提供了账户名和密码之后才可以登录 SMTP 服务器，这就使得那些垃圾邮件的散播者无可乘之机。
增加 SMTP 认证的目的是为了使用户避免受到垃圾邮件的侵扰。

IMAP全称是Internet Mail Access Protocol，即交互式邮件存取协议，它是跟POP3类似邮件访问标准协议之一。不同的是，开启了IMAP后，您在电子邮件客户端收取的邮件仍然保留在服务器上，同时在客户端上的操作都会反馈到服务器上，如：删除邮件，标记已读等，服务器上的邮件也会做相应的动作。所以无论从浏览器登录邮箱或者客户端软件登录邮箱，看到的邮件以及状态都是一致的。

Telnet协议是TCP/IP协议族中的一员，是Internet远程登陆服务的标准协议和主要方式。它为用户提供了在本地计算机上完成远程主机工作的能力。在终端使用者的电脑上使用telnet程序，用它连接到服务器。终端使用者可以在telnet程序中输入命令，这些命令会在服务器上运行，就像直接在服务器的控制台上输入一样。可以在本地就能控服务器。要开始一个telnet会话，必须输入用户名和密码来登录服务器。Telnet是常用的远程控制Web服务器的方法。

数学

设含有$10$个元素的集合的全部子集数为$S$，其中由$7$个元素组成的子集数为$T$，则$\frac{T}{S}$的值为（）。

A.$\frac{5}{32}$

B.$\frac{15}{128}$

C.$\frac{1}{8}$

D.$\frac{128}{21}$

解析:B

子集总数$S$为 $2^{10}= 1024$

$7$个元素集合数$T$为$C（10,7）=\frac{10!}{3!\times7!}= 120$

$\frac {T}{S} = \frac{120}{1024} = \frac{15}{128}$

2.2017年10月1日是星期日，1999年10月1日是( )。

A. 星期三 B. 星期日

C. 星期五 D. 星期二

解析：

什么年是闰年？你首先想到的可能是能被4整除的年就是闰年。实际上这是不正确的，公历里闰年的定义是这种：能被400整除的，或者
不能被100整除而能被4整除的年就是闰年，换一句话说，非世纪年份中能被4整除的，和世纪年份中能被400整除的是闰年。依照这个定义，公元2000年是闰年，而公元1900年是平年。可是假设再问你，公元100年是不是闰年？这个是世纪年份，而不能被400整除，所以这个年份是平年，假设你这样想，那你就错了。我们如今用的公历，是格里高里历，是公元1582年以后通行的，之前记录日期用的是儒略历，和如今用的公历不同，儒略历中闰年的定义非常easy的，能被4整除的是闰年，不能被4整除的是平年。所以，公元100年还处于儒略历时期，所以历史上该年份是闰年。所以闰年的完整定义是：公元1582年前，能被4整除的年份；公元1582年后，世纪年中能被400整除的，和非世纪年中能被4整除的年份。总的来说，闰年的定义是比較复杂，远不是一般人以为的那么简单。这不仅是一个数学问题，还是一个历史问题。

2000是闰年，2004，2008，2012，2016年应该者是闰年，共5个，即5个366天，13个非闰年，共$13 \times 365+5 \times 366=4745+1830=6575$天,$6575 \div 7=939……2$,因1999年是向前找，所以是星期五，选C

3.甲、乙、丙三位同学选修课程，从 4 门课程中，甲选修 2 门，乙、丙各选修3 门，则不同的选修方案共有( )种。

A. 36 B. 48 C. 96 D. 192

解析:甲有6种，乙、丙每人4种，共$6\times4\times4=96$种，答案C