信息学奥赛基础知识讲义 本文关键词：讲义，基础知识，信息学，奥赛
信息学奥赛基础知识讲义 本文简介：[信息学奥赛基础知识讲义]基础部分一、进制：2进制数与8进制、10进制、16进制数的换算换算1：将N进制数换算成10进制数（N可以为2,8,16或其它自然数）换算2：将10进制数换算成N进制数（N可以为2,8,16或其它自然数）1.下列无符号数中，最小的数是（）A.（11011001）2B.（75）
信息学奥赛基础知识讲义 本文内容：
[信息学奥赛基础知识讲义]
基础部分
一、进制：2进制数与8进制、10进制、16进制数的换算
换算1：将N进制数换算成10进制数（N可以为2,8,16或其它自然数）
换算2：将10进制数换算成N进制数（N可以为2,8,16或其它自然数）
1.下列无符号数中，最小的数是（
）
A.（11011001）2
B.（75）10
C.（37）8
D.（2A）16
7、小张用十六进制，八进制和十进制写下了如下一个等式：
52-19=33
式中三个数是各不相同进位制的数，试问52,19,33，分别为______。
（A）8，10，
16
（B）10,16,8
(c)
8,16,10
(D)
10,8,16
二、数据的存储和编码
所有的数据都是以二进制存储在计算机的存储器中的，数据的传送、存储、加工、处理或指令都是以二进制形式进行的。
对于数值:弄清原码、反码、补码以及定点数和浮点数。负数在计算机中以补码形式存放，小数在计算机中是以浮点数形式存放。
0的原码表示法有两种，+0和—0
8位定点整数的补码表示范围为-128_____+127
14、计算机中的数有浮点数与定点数两种，其中用浮点数表示的数，通常由（
）这两部分组成。
A.指数与基数
B.
尾数与小数
C.
阶码与尾数
D.整数与小数
8、如果用一个字节表示一个整数，最高位用作符号位，其他位表示数值，例如
00000001表示+1，10000001表示-1
（1）
试问这样表示法的整数a的范围应是————————
A、-127=0）个数据元素的有限序列
3、特征：（1）数据表中的元素具有相同的特性（相同的数据类型）
3、
（2）元素之间具备线性关系（有顺序，并且是一对一的关系）
相关名词：表头、表尾
eg:
线性表是：
A、有限序列，可以为空；B、有限序列，不能为空
C、无限序列，可以为空
D、无限序列，不能为空
三、常用的两种线性表模型
队列：
特点：只能在表的一端进行插入，在表的另一端进行删除的线性表
相关名词：队首、队尾
堆栈：
特点：只能在表的一端进行插入和删除操作
应用：求解数学表达式、实现递归算法
相关名词：栈顶、栈底
eg:
设栈S的初始状态为空，现有个元素组成的序列（1，2，3，4，5），对该序列在S栈上依次进行如下操作（从序列中的1开始，出栈后不再进栈）：进栈，进栈，进栈，出栈，进栈，出栈，进栈，请问出栈的元素序列是:
四、线性表的存储：（顺序存储和链表存储）
顺序存储：是按数据元素在存储器中的相对位置来表示数据元素间的逻辑关系
程序描述：用一维数组来描述顺序存储结构,二维数组的每一个元素为一个线性表
链表存储：用一组任意的存储单元来存储数据元素，元素之间的关系通过指针来
表现。
程序描述：用指针
eg：找同学
两种存储结构的特点对比
顺序表
链表
一个表必须用一组连续的内存地址存储
内存地址可以是连续的也可以是不连续的
插入和删除元素难度大
插入和删除元素简单（不需移动元素，只需修改头尾指针即可）
存取数据快（只要确定了起始位置，线性表中任一数据元素可随机存取）
存取数据慢
17.线性表若采用链表存贮结构,要求内存中可用存贮单元地址（
）
A.必须连续
B.部分地址必须连续
C.一定不连续
D.连续不连续均可
18.下列叙述中,正确的是（
）
A.线性表的线性存贮结构优于链表存贮结构
B.队列的操作方式是先进后出
C.栈的操作方式是先进先出
D.二维数组是指它的每个数据元素为一个线性表的线性表
14、线性表有两种存储结构：一是顺序表，二是链表。试问：
（1）有一个线性表，在处理过过程中表的长度会根据需要动态发生变化，在这种情况下应选用哪种存储结构
（2）有一个线性表，很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素，应采用哪种存储结构
15.已知数组A中，每个元素A[I,J]在存贮时要占3个字节，设I从1变化到8，J从1变化到10，分配内存时是从地址SA开始连续按行存贮分配的。试问：A[5,8]的起始地址为（
）
A.SA+144
B.SA+180
C.SA+222
D.SA+225
(4*10+8)*3
1.在下面各世界顶级的奖项中，为计算机科学与技术领域做出杰出贡献的科学家设立的奖项是（
）。
A.
沃尔夫奖
B.
诺贝尔奖
C.
菲尔兹奖
D.
图灵奖
2.
在下列各软件中，不属于
NOIP
竞赛（复赛）推荐使用的语言环境有（
）。
A.
gcc/g++
B.
Turbo
Pascal
C.
RHIDE
D.
free
pascal
3.
以下断电之后仍能保存数据的有（
）。
A.
寄存器
B.
ROM
C.
RAM
D.
高速缓存
4．Linux
是一种(
)。
A.
绘图软件
B.
程序设计语言
C.
操作系统
D.
网络浏览器
5.
CPU
是(
)的简称。
A.
硬盘
B.
中央处理器
C.
高级程序语言
D.
核心寄存器
6.
在计算机中，防火墙的作用是（
）。
A.
防止火灾蔓延
B.防止网络攻击
C.
防止计算机死机
D.
防止使用者误删除数据
7.
在下列关于计算机语言的说法中，不正确的是（
）。
A.
Pascal和C都是编译执行的高级语言
B.
高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上
C.
C++是历史上的第一个支持面向对象的计算机语言
D.
与汇编语言相比，高级语言程序更容易阅读
8.
在下列关于计算机算法的说法中，不正确的是（
）。
A.
一个正确的算法至少要有一个输入
B.
算法的改进，在很大程度上推动了计算机科学与技术的进步
C.
判断一个算法的好坏的主要标准是算法的时间复杂性与空间复杂性
D.
目前仍然存在许多涉及到国计民生的重大课题，还没有找到能够在计算机上实施的有效算法
9.
在下列各种排序算法中，不是以“比较”作为主要操作的算法是（
）。
A.
选择排序
B.
冒泡排序
C.
插入排序
D.
基数排序
10．在编程时（使用任一种高级语言，不一定是
Pascal），如果需要从磁盘文件中输入一个很大的二
维数组（例如
1000*1000
的
double
型数组），按行读（即外层循环是关于行的）与按列读（即外层
循环是关于列的）相比，在输入效率上（
）。
A.
没有区别
B.
按行读的方式要高一些
C.
按列读的方式要高一些
D.
取决于数组的存储方式。
11．在
Pascal
语言中，表达式
(21
xor
2)的值是（
）
A.
441
B.
42
C.23
D.24
12．在
Pascal
语言中，判断
a
不等于
0
且
b
不等于
0
的正确的条件表达式是（
）
A.
not
a=0
or
not
b=0
B.
not((a=0)and(b=0))
C.
not(a=0
and
b=0)
D.
(a0)and
(b0)
13．某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从
这一时刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出,出”。假设车辆入站的
顺序为
1，2，3，……，则车辆出站的顺序为（
）。
A.
1,2,3,4,5
B.
1,2,4,5,7
C.
1,4,3,7,6
D.
1,4,3,7,2
14．高度为
n
的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为
n-1
的满二叉树。
在这里，树高等于叶结点的最大深度，根结点的深度为
0，如果某个均衡的二叉树共有
2381
个结点，
则该树的树高为（
）。
A.
10
B.
11
C.
12
D.
13
15.
与十进制数
1770
对应的八进制数是（
）。
A.
3350
B.
3351
C.
3352
D.
3540
16．将
5
个数的序列排序，不论原先的顺序如何，最少都可以通过（
）次比较，完成从小到大的排序。
A.
6
B.
7
C.
8
D.
9
17.
设A=B=D=true，C=false，以下逻辑运算表达式值为真的有（
）。
A.
(?
A∧B)∨(C∧D)
B.?
((A∨B∨D)∧C)
C.
A∧(B∨C∨D)
D.
(A∧B∧C)∨
D
18.
(2010)16
+
(32)8的结果是（
）。
A.
(8234)10
B.
(202B)16
C.
(20056)8
D.
(100000000110)2
19.
设栈S的初始状态为空，元素a,b,c,d,e
依次入栈，以下出栈序列不可能出现的有（
）。
A.
a,b,c,e,d
B.
b,c,a,e,d
C.
a,e,c,b,d
D.
d,c,e,b,a
20.
已知
6
个结点的二叉树的先根遍历是
1
2
3
4
5
6（数字为结点的编号，以下同），后根遍历是
3
2
5
6
4
1，则该二叉树的可能的中根遍历是（
）
A.
3
2
1
4
6
5
B.
3
2
1
5
4
6
C.
2
1
3
5
4
6
D.
2
3
1
4
6
5
练习二
1.
在字符串“ababacbabcbdecced”中出现次数最多的字母出现了（
）次。
A.
6
B.
5
C.
4
D.
3
E.
2
2.
设全集
I
=
{a,b,c,d,e,f,g,h}，集合
A
=
{a,b,c,d,e,f}，B
=
{c,d,e}，C
=
{a,d}，那
么集合
A
?
B?
~
C
为（
）。
A.
{c,e}
B.
{d,e}
C.
{e}
D.
{c,d,e}
E.
{d,f}
3.
和十进制数
23
的值相等的二进制数是（
）。
A.
10110
B.
11011
C.
11011
D.
10111
E.
10011
4.
完全二叉树的结点个数为
11，则它的叶结点个数为（
）。
A.
4
B.3
C.5
D.
2
E.
6
5.
平面上有五个点
A(5,3),B(3,5),C(2,1),D(3,3),E(5,1)。以这五点作为完全图
G
的顶点，
每两点之间的直线距离是图
G
中对应边的权值。以下哪条边不是图
G
的最小生成树中
的边（
）。
A.
AD
B.
BD
C.
CD
D.
DE
E.
EA
6.
Intel
的首颗
16
位处理器是（
）。
A.
8088
B.
80386
C.
80486
D.
8086
E.
Pentium
7.
处理器
A
每秒处理的指令数是处理器
B
的
2
倍。某一特定程序
P
分别编译为处理器
A
和处理器
B
的指令，编译结果处理器
A
的指令数是处理器
B
的
4
倍。已知程序
P
在处
理器
A
上执行需要
1
个小时，那么在输入相同的情况下，程序
P
在处理器
B
上执行需
要（
）小时。
A.
4
B.
2
C.
1
D.
1
/
2
E.
1
/
4
8.
以下哪个不是计算机的输出设备（
）。
A.
音箱
B.
显示器
C.
打印机
D.
扫描仪
E.
绘图仪
9.
下列活动中不属于信息学奥赛的系列活动的是（
）。
A.
NOIP
B.
NOI
C.
IOI
D.
冬令营
E.
程序员等级考试
10.
以下断电之后仍能保存数据的是（
）。
A.
硬盘
B.
寄存器
C.
显存
D.
内存
E.
高速缓存
11.
以下哪个软件不是即时通信软件（
）。
A.
网易泡泡
B.
MSN
Messenger
C.
Talk
D.
3DS
Max
E.
12.
下列关于高级语言的说法错误的是（
）。
A.
Fortran
是历史上的第一个面向科学计算的高级语言
B.
Pascal
和
C
都是编译执行的高级语言
C.
C++是历史上的第一个支持面向对象的语言
D.
编译器将高级语言程序转变为目标代码
E.
高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上
13.
下列设备不具有计算功能的是（
）。
A.
笔记本电脑
B.
掌上电脑
C.
智能手机
D.
电子计算器
E.
液晶显示器
14.
常见的邮件传输服务器使用（
）协议接收邮件。
A.
HTTP
B.
SMTP
C.
TCP
D.
FTP
E.
POP3
15.
下列浏览器中，由微软公司开发的浏览器是（
）。
A.
Internet
Explore
B.
Netscape
C.
Opera
D.
Firefox
E.
Mozilla
16.
一位艺术史学家有
20000
幅真彩色图像，每幅图像约占
3M
空间。如果将这些图像以位
图形式保存在
CD
光盘上（一张
CD
光盘的容量按
600M
计算），大约需要（
）张
CD
光盘。
A.
1
B.
10
C.
100
D.
1000
E.
10000
17.
设
A
=
true，B
=
false，C
=
false，D
=
true，以下逻辑运算表达式值为真的是（
）。
A.
(A∧B)∨(C∧D)
B.
((A∧B)∨C)∧D
C.
A∧((B∨C)
∧D)
D.
(A∧(B∨C))∨D
E.
(A∨B)∧(C∧D)
18.
(3725)8
+
(B)16
的运算结果是（
）。
A.
(3736)8
B.
(2016)10
C.
(1111110000)2
D.
(3006)10
E.
(7B0)16
19.
二叉树
T
的宽度优先遍历序列为
A
B
C
D
E
F
G
H
I，已知
A
是
C
的父结点，D
是
G
的
父结点，F
是
I
的父结点，树中所有结点的最大深度为
3（根结点深度设为
0），可知
F
的父结点是（
）。
A.
无法确定
B.
B
C.
C
D.
D
E.
E
20.
设栈
S
的初始状态为空，元素
a,b,c,d,e,f,g
依次入栈，以下出栈序列不可能出现的是（
）。
A.
a,b,c,e,d,f,g
B.
b,c,a,f,e,g,d
C.
a,e,d,c,b,f,g
D.
d,c,f,e,b,a,g
E.
g,e,f,d,c,b,a
练习三
1.
美籍匈牙利数学家冯·诺依曼对计算机科学发展所做出的贡献是（
）。
A.
提出理想计算机的数学模型，B.
成为计算机科学的理论基础。
C.
是世界上第一个编写计算机程序的人。
D.
提出存储程序工作原理，E.
并设计出第一台具有存储程序功能的计算机EDVAC。
F.
采用集成电路作为计算机的主要功能部件。
G.
指H.
出计算机性能将以每两年翻一番的速度向前发展。
2.
下列哪个不3.
是CPU（中央处理单元）（
）。
A.
Intel
Itanium
B.
DDR
SDRAM
C.
AMD
Athlon64
D.
AMD
Opteron
E.
IBM
Power
5
4.
下列网络上常用的名5.
字缩写对应的中文解释错误的是（
）。
A.
WWW（World
Wide
Web）：万B.
维网。
C.
URL（Uniform
Resource
Locator）：统一资源定位器。
D.
HTTP（Hypertext
Transfer
Protocol）：超文本传输协议。
E.
FTP（File
Transfer
Protocol）：快速传输协议。
F.
TCP（Transfer
Control
Protocol）：传输控制协议。
6.
下面哪个部件对于个人桌面电脑的正常运行不7.
是必需的（
）。
A.
CPU
B.
图形卡（显卡）
C.
光驱
D.
主板
E.
内存
8.
下列哪个软件属于操作系统软件（
）。
A.
Microsoft
Word
B.
金山词霸
C.
Foxmail
D.
WinRAR
E.
Red
Hat
Linux
9.
下列哪个不10.
是计算机的存储设备11.
（
）。
A.
文件管理器
B.
内存
C.
高速缓存
D.
硬盘
E.
U盘
12.
下列说法中错误的是（
）。
A.
CPU的基本功能就是执行指B.
令。
C.
CPU访问内存的速度快于访问高速缓存的速度。
D.
CPU的主频是指E.
CPU在1秒内完成的指F.
令周期数。
G.
在一台计算机内部，H.
一个内存地址编码对应唯一的一个内存单元。
I.
数据总线的宽度决定了一次传递数据量的大小，J.
是影响计算机性能的因素之一。
13.
彩色显示器所显示的五彩斑斓的色彩，14.
是由红色、蓝色和（
）色混合而15.
成的。
A.
紫
B.
白
C.
黑
D.
绿
E.
橙
16.
用静电吸附墨粉后转移到纸张上，17.
是哪种输出设备18.
的工作方式（
）。
A.
针式打印机
B.
喷墨打印机
C.
激光打印机
D.
笔式绘图仪
E.
喷墨绘图仪
19.
一台计算机如果要利用电话线上网，20.
就必须配置能够对数字信号和模拟信号进行相互转换的设备，21.
这种设备22.
是（
）。
A.
调制解调器
B.
路由器
C.
网卡
D.
网关
E.
网桥
23.
下列哪个不24.
是数据库软件的名25.
称（
）。
A.
MySQL
B.
SQL
Server
C.
Oracle
D.
金山影霸
E.
Foxpro
26.
下列哪个程序设计语言不27.
支持面向对象程序设计方法（
）。
A.
C++
B.
Object
Pascal
C.
C
D.
Smalltalk
E.
Java
28.
由3个a，29.
1个b和2个c构成的所有字符串中，30.
包含子串“abc”的共有（
）个。
A.
20
B.
8
C.
16
D.
12
E.
24
31.
某个车站呈狭长形，32.
宽度只能容下一台车，33.
并且只有一个出入口。已知某时刻该车站状态为空，34.
从这一时刻开始的出入记录为：“进，35.
出，36.
进，37.
进，38.
出，39.
进，40.
进，41.
进，42.
出，43.
出，44.
进，45.
出”。假设车辆入站的顺序为1，46.
2，47.
3，48.
……，49.
则车辆出站的顺序为（
）。
A.
1,2,3,4,5
B.
1,2,4,5,7
C.
1,3,5,4,6
D.
1,3,5,6,7
E.
1,3,6,5,7
50.
二叉树T，51.
已知其前序遍历序列为1
2
4
3
5
7
6，52.
中序遍历序列为4
2
1
5
7
3
6，53.
则其后序遍历序列为（
）。
A.
4
2
5
7
6
3
1
B.
4
2
7
5
6
3
1
C.
4
2
7
5
3
6
1
D.
4
7
2
3
5
6
1
E.
4
5
2
6
3
7
1
54.
满二叉树的叶结点个数为N，55.
则它的结点总数为（
）。
A.
N
B.
2
N
C.
2
N
–
1
D.
2
N
+
1
E.
2N
–
1
56.
十进制数2004等值于八进制数（
）。
A.
3077
B.
3724
C.
2766
D.
4002
E.
3755
57.
(2004)10
+
(32)16的结果是（
）。
A.
(2036)10
B.
(2054)16
C.
(4006)10
D.
(100000000110)2
E.
(2036)16
58.
在下图中，59.
从顶点（
）出发存在一条路径可以遍历图中的每条边一次，而60.
且仅遍历一次。
A.
A点
B.
B点
C.
C点
D.
D点
E.
E点
61.
某大学计算机专业的必修课及其先修课程如下表所示：
课程代号
C0
C1
C2
C3
C4
C5
C6
C7
课程名称
高等数学
程序设计语言
离散数学
数据结构
编译技术
操作系统
普通物理
计算机原理
先修课程
C0,C1
C1,C2
C3
C3,C7
C0
C6
请你判断下列课程安排方案哪个是不合理的（
）。
A.
C0,C6,C7,C1,C2,C3,C4,C5
B.
C0,C1,C2,C3,C4,C6,C7,C5
C.
C0,C1,C6,C7,C2,C3,C4,C5
D.
C0,C1,C6,C7,C5,C2,C3,C4
E.
C0,C1,C2,C3,C6,C7,C5,C4
篇2：化学奥赛培训方案
化学奥赛培训方案 本文关键词：奥赛，化学，方案，培训
化学奥赛培训方案 本文简介：新邵县第八中学化学奥林匹克竞赛辅导方案新邵县第八中学孙艳一、辅导目的化学竞赛是培养学生学习化学的兴趣爱好、创新意识、创新思维和初步创新能力为目的的课外活动，同时，参与化学竞赛辅导能使教师的知识结构更加完善、专业能力得到提升，是促进教师专业化发展的有效途径。因此，新邵八中化学组决定开展中学化学奥林匹克
化学奥赛培训方案 本文内容：
新邵县第八中学化学奥林匹克竞赛辅导方案
新邵县第八中学
孙
艳
一、辅导目的
化学竞赛是培养学生学习化学的兴趣爱好、创新意识、创新思维和初步创新能力为目的的课外活动，同时，参与化学竞赛辅导能使教师的知识结构更加完善、专业能力得到提升，是促进教师专业化发展的有效途径。因此，新邵八中化学组决定开展中学化学奥林匹克竞赛培训，组织高二理科各班在化学学科上有兴趣、有潜力，成绩优秀的学生组成了一个化学竞赛班，集中讲解竞赛涉及的内容和考题题型，提高学生的解题能力，扩大学生的知识面，
二、辅导安排
1.按照学生自愿原则进行化学奥赛辅导报名，进行考试筛选出12人，最终统计参加培训学生名单及人数。
2.确定辅导地点：凌云楼高二教师办公室
3.培训形式：集中培训
4.辅导时间：每周一次，周三18：30
—
19:20
5.制定教学计划，确定每阶段辅导内容与资料。第一阶段：大学《无机化学》教学，主要包括原子结构、元素周期律和元素周期表、元素的相对分子质量计算以及分子结构；第二阶段：大学《结构化学》的教学，主要包括晶体结构、分子间作用力等；第三阶段：大学《分析化学》教学，主要包括有效数字、气体与溶液相关计算以及容量分析；第四阶段：大学《有机化学》的教学；第五阶段：训练历年奥林匹克竞赛真题，达到初赛要求
。辅导资料由辅导团队商议后统一购买。
6.设置检查表格，落实好学生学习任务完成的监督、考查。
三、辅导对象：
高二年级理科班部分学生（12人）
四、辅导教材、资料：
《无机化学》、《有机化学》、《分析化学》、《结构化学》、《高中化学竞赛真题精解与方法指导（沈臻豪）》
五、辅导内容：
初赛基本要求，近几年竞赛试题讲解分析。具体的竞赛辅导资料由各知识点负责教师选择、落实。
6、
辅导团队
队长：孙
艳
队员：曾永红、刘南北、
何方
对辅导教师的要求：
每位教师按要求精心组织竞赛内容，力求习题精选，知识点覆盖全面，涉及常见易错点。当堂讲解知识点及习题，有针对性和突破性的专题辅导。
7、
辅导措施：
1、注重基础知识训练。
由于竞赛命题大多以课本为依据，因此在辅导时要紧扣课本，严格按照由浅入深、由易到难、由简到繁、循序渐进的原则，适时联系课本内容。
2、不拘泥于课本，适当扩展深度。
由于竞赛题目往往比平时考试试题难，教师必须在课本的基础上加以延伸、拓宽，或教给学生新的知识。
3、精讲赛题，启迪思维。
竞赛是一种高思维层次、高智力水平的角逐，一种独立的创造性活动。因此，竞赛试题可以多方面地培养人的观察、归纳、类比、知觉的方法，它能给学生施展才华、发展智慧的机会。教师在讲解竞赛题时，应向学生强调认真审题的重要性，并提醒学生适时联系以前解过的题，用其已掌握的方法或解题思路，以求对竞赛题作出合理的解答和更全面深刻的理解，并通过解题后的回顾，教会学生总结，研究自己的解题过程，培养学生发现问题、发现规律的能力。
4、设计专题训练，帮助学生掌握知识。
竞赛题以其难度大、新意浓的特点考查学生的灵活性，解竞赛题虽然没有常规的思维模式可套，但因其源于课本而高于课本，所以它离不开基础知识和特有的思维规律，因而在辅导中需要确定一些专题进行讲授和训练。但指导教师在设计专题时，应注意题目要有一定的梯度和新鲜感，以达到真正培养学生能力的目的。
九、辅导课时：
共
课时（具体课时由各知识点负责教师决定）
知识点
课时
负责教师
第一阶段：无机化学
基态原子电子排布
孙
艳
元素周期律与元素周期系
电离能、亲和能、电负性
路易斯结构
价键理论
原子杂化轨道
价层电子互斥理论
离域π键及相关应用
分子间作用力和氢键
第二阶段：结构化学
晶体的特征
何方
金属晶体
离子晶体
原子晶体
第三阶段：分析化学
配位化合物的概念
刘南北
配位化合物的类型
配合物异构现象
配合物的磁性和空间结构
配合物的晶体场理论
有效数字及相关计算
第四阶段：电化学基础
氧化态和氧化值
曾永红
氧化还原半反应
原电池的表示方法
标准电极电势
电极电势的应用
第五阶段：有机化学
待定
待定
待定
第六阶段：历年真题训练
真题体验
孙
艳
2018年3月
篇3：1999年至历年信息学奥赛提高组初赛试题
1999年至历年信息学奥赛提高组初赛试题 本文关键词：初赛，历年，信息学，试题，奥赛
1999年至历年信息学奥赛提高组初赛试题 本文简介：福建省莆田第一中学信息学奥赛兴趣小组整理：林梓雨第十七届（2011）全国青少年信息学奥林匹克联赛初赛试题（提高组Pascal语言两小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（共20题，每题1.5分。共计30分。每题有且仅有一个正确选项。）1．在二进制下，11
1999年至历年信息学奥赛提高组初赛试题 本文内容：
福建省莆田第一中学
信息学奥赛兴趣小组
整理：林梓雨
第十七届（2011）全国青少年信息学奥林匹克联赛初赛试题
（
提高组
Pascal语言
两小时完成
）
●●
全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效
●●
一、单项选择题（共20题，每题1.5分。共计30分。每题有且仅有一个正确选项。）
1．在二进制下，1100011
+（
）=
1110000。
A．1011B．1101C．1010
D．1111
2．字符“A”的ASCII码为十六进制41，则字符“Z”的ASCII码为十六进制的（
）。
A．66
B．5AC．50
D．视具体的计算机而定
3．右图是一棵二叉树，它的先序遍历是（
）。
A．ABDEFC
B．DBEFACC．DFEBCA
D．ABCDEF
4．寄存器是（
）的重要组成部分。
A．硬盘
B．高速缓存
C．内存D．中央处理器（CPU）
5．广度优先搜索时，需要用到的数据结构是（
）。
A．链表
B．队列C．栈D．散列表
6．在使用高级语言编写程序时，一般提到的“空间复杂度”中的“空间”是指（
）。
A．程序运行时理论上所占的内存空间
B．程序运行时理论上所占的数组空间
C．程序运行时理论上所占的硬盘空间
D．程序源文件理论上所占的硬盘空间
7．应用快速排序的分治思想，可以实现一个求第K大数的程序。假定不考虑极端的最坏情况，理论上可以实现的最低的算法时间复杂度为（
）。
A．O(n2)B．O(n
log
n)C．O(n)D．O(1)
8．为解决Web应用中的不兼容问题，保障信息的顺利流通，（
）制定了一系列标准，涉及HTML、XML、CSS等，并建议开发者遵循。
A．微软
B．美国计算机协会（ACM）
C．联台国教科文组织D．万维网联盟（W3C）
9．体育课的铃声响了，同学们都陆续地奔向操场，按老师的要求从高到矮站成一排。每个同学按顺序来到操场时，都从排尾走向排头，找到第一个比自己高的同学，并站在他的后面。这种站队的方法类似于（
）算法。
A．快速排序B．插入排序C．冒泡排序D．归并排序
10．1956年（
）授予肖克利（William
Shockley）、巴丁（John
Bardeen）和布拉顿（Walter
Brattain)，以表彰他们对半导体的研究和晶体管效应的发现。
A．诺贝尔物理学奖
B．约翰?冯?诺依曼奖
C．图灵奖
D．高德纳奖（Donald
E．Knuth
Prize）
二、不定项选择题（共10题，每题1．5分，共计15分。每题有一个或多个正确选项。多选或少选均不得分。）
1．如果根结点的深度记为1，则一棵恰有2011个叶子结点的二叉树的深度可能是（
）。
A．10B．11C．12
D．2011
2．在布尔逻辑中，逻辑“或”的性质有（
）。
A．交换律：P
V
Q
=
Q
V
P
B．结台律：P
V
(
Q
V
R
)
=
(
P
V
Q
)
V
R
C．幂等律：P
V
P
=
P
D．有界律：P
V
1
=
1
（1表示逻辑真）
3．一个正整数在十六进制下有100位，则它在二进制下可能有（
）位。
A．399B．400C．401
D．404
4．汇编语言（
）。
A．是一种与具体硬件无关的程序设计语言
B．在编写复杂程序时，相对于高级语言而言代码量较大，且不易调试
C．可以直接访问寄存器、内存单元、I/O端口
D．随着高级语言的诞生，如今已完全被淘汰，不再使用
5．现有一段文言文，要通过二进制哈夫曼编码进行压缩。简单起见，假设这段文言文只由4个汉字“之”、“乎”、“者”、“也”组成，它们出现的次数分别为700、600、300、400。那么，“也”字的编码长度可能是（
）。
A．1B．2C．3
D．4
6．生物特征识别，是利用人体本身的生物特征进行身份认证的一种技术。目前，指纹识别、虹膜识别、人脸识别等技术己广泛应用于政府、银行、安全防卫等领域。以下属于生物特征识别技术及其应用的是（
）。
A．指静脉验证B．步态验证C．ATM机密码验证D．声音验证
7．对于序列“7、5、1、9、3、6、8、4”，在不改变顺序的情况下，去掉（
）会使逆序对的个数减少3。
A．7B．5C．3
D．6
8．计算机中的数值信息分为整数和实数（浮点数）。实数之所以能表示很大或者很小的数，是由于使用了（
）。
A．阶码B．补码C．反码D．较长的尾数
9．对右图使用Dijkstra算法计算S点到其余各点的最短路径
长度时，到B点的距离d[B]初始时赋为8，在算法的执行过程
中还会出现的值有（
）。
A．3B．7C．6
D．5
10．为计算机网络中进行数据交换而建立的规则、标准或约定的集合成为网络协议。下列英文缩写中，（
）是网络协议。
A．HTTPB．TCP/IPC．FTP
D．WWW
三、问题求解（共2题，每题5分，共计10分）
1．平面图是可以画在在平面上，且它的边仅在顶点上才能相交的简单
无向图。4个顶点的平面图至多有6条边，如右图所示。那么，5个顶
点的平面图至多有______条边。
2．定义一种字符串操作，一次可以将其中一个元素移到任意位置。举例说明，对于字符串”BcA”，可以将A移到B之前，变成字符串”ABC”。如果要将字符串”DACHEBGIF”变成”ABCDEFGHI”，最少需要________次操作。
四、阅读程序写结果（共4题，每题8分，共计32分）
1．
Const
SIZE
=
100;
var
n,i,sum,x
:
integer;
a
:
array[1SIZE]
of
integer;
begin
readln(n);
fillchar(a,sizeof(a),0);
for
i:=
1
to
n
do
begin
read(x);
inc(a[x]);
end;
i
:=
0;
sum
:=
0;
while
sum
ans
then
ans
:=
len;
for
i
:=
1
to
n
do
if
(not
visited[i])
and
(e[x,i]
-1)
then
dfs(i,len
+
e[x,i]);
visited[x]
:=
false;
end;
begin
readln(n,m);
for
i
:=
1
to
n
do
for
j
:=
1
to
n
do
e[i][j]
:=
-1;
for
i
:=
1
to
m
do
begin
readln(a,b,c);
e[a][b]
:=
c;
e[b][a]
:=
c;
end;
for
i
:=
1
to
n
do
visited[i]
:=
false;
ans
:=
0;
for
i
:=
1
to
n
do
dfs(i,0);
writeln(ans);
end.
输入：
4
6
1
2
10
2
3
20
3
4
30
4
1
40
1
3
50
2
4
60
输出：__________
4.
const
SIZE
=
10000;
LENGTH
=
10;
var
sum
:
longint;
n,m,i,j
:
integer;
a
:
array[1SIZE,1LENGTH]
of
integer;
function
h(u,v
:
integer)
:
integer;
var
ans,i
:
integer;
begin
ans
:=
0;
for
i
:=
1
to
n
do
if
a[u][i]
a[v][i]
then
inc(ans);
h
:=
ans;
end;
begin
readln(n);
filichar(a,sizeof(a),0);
m
:=
1;
repeat
i
:=
1;
while
(i
n
then
break;
inc(m);
a[m][i]
:=1;
for
j
:=
i
+
1
to
n
do
a[m][j]
:=
a[m
-
1][j];
until
false;
sum
:=0;
for
i
:=
1
to
m
do
for
j
:=
1
to
m
do
sum
:=
sum
+
h(i,j);
writeln(sum);
end.
输入：7
输出：____________
五、完善程序（第1题，每空2分，第2题，每空3分，共计28分）
1.
（大整数开方）输入一个正整数n（1≤n
0
then
ans.len
:=
a.1en
+
b.1en
else
ans.len
:=a.1en
+
b.1en
–
1;
end;
times
:=
ans;
end;
function
add(a,b
:
hugeint)
:
hugeint;
var
i
:
integer;
ans
:
hugeint;
begin
fillchar(ans.num,sizeof(ans.num),0);
if
a.1en
>
b.1en
then
ans.len
:=
a.1en
else
ans.len
:=
b.len;
for
i
:=
1
to
ans.1en
do
begin
ans.num[i]
:=___③___;
ans.num[i
+
1]
:=
ans.num[i
+
1]
+
ans.num[i]
div
10;
ans.num[i]
:=
ans.num[i]
mod
10;
end;
if
ans.num[ans.1en
+
1]
>
0
then
inc(ans.len);
add:=ans;
end;
function
average(a,b
:
hugeint)
:
hugeint;
var
i
:
integer;
ans
:
hugeint;
begin
ans
:=
add(a,b);
for
i
:=
ans.1en
downto
2
do
begin
ans.num[i
-
1]
:=
ans.num[i
-
1]
+
(___④___)
10;
ans.num[i]
:=
ans.num[i]
div
2;
end;
ans.num[i]
:=
ans.num[i]
div
2;
if
ans.num[ans.len]
=
0
then
dec(ans.len);
average
:=
ans;
end;
function
plustwo(a
:
hugeint)
:
hugeint;
var
i
:
integer;
ans
:
hugeint;
begin
ans
:=
a;
ans.num[1]
:=
ans.num[1]
+
2;
i
:=
1;
while(i
=
10)
do
begin
ans.num[i
+
1]
:=
ans.num[i
+
1]
+
ans.num[i]
div
10;
ans.num[i]
:=
ans.num[i]
mod
10;
inc(i);
end;
if
ans.num[ans.len
+
1]
>
0
then___⑤___;
plustwo
:=
ans;
end;
function
over(a,b
:
hugeint)
:
boolean;
var
i
:
integer;
begin
if(___⑥___)then
begin
over
:=
false;
exit;
end;
if
a.1en
>
b.1en
then
begin
over
:=
true;
exit;
end;
for
i
:=
a.len
downto
1
do
begin
if
a.num[i]
b.num[i]
then
begin
over
:=
true;
exit;
end;
end;
over
:=
false;
end;’
begin
readln(s);
fillchar(target.num,sizeof(target.num),0);
target.1en
:=
1ength(s);
for
i
:=
1
to
target.1en
do
target.num[i]
:=
ord(s[target.1en
–
i
+
1])
-
___⑦___;
filichar(left.num,sizeof(1eft.num),0);
left.1en
:=
1;
left.num[i]
:=
1;
right
:=
target;
repeat
middle
:=
average(1eft,right);
if
over(___⑧___)
then
right
:=
middle
else
1eft
:=
middle;
until
over(plustwo(1eft),right);
for
i
:=
left.1en
downto
1
do
write(1eft.num[i]);
writeln;
end.
2.
（笛卡尔树）对于一个给定的两两不等的正整数序列，笛卡尔树是这样的一棵二叉树：首先，它是一个最小堆，即除了根结点外，每个结点的权值都大于父节点的权值；其次，它的中序遍历恰好就是给定的序列。例如，对于序列7、2、12、1、10、5、15、3，下图就是一棵对应的笛卡尔树。现输入序列的规模n（1≤n
maxDeep
then
begin
maxDeep
:=
deep;
num
:=
1;
end
else
if
deep
=
maxDeep
then
___①___;
min
:=
INFINITY;
for
i
:=
1eft
to
right
do
if
min
>
a[i]
then
begin
min
:=
a[i];
___②___;
end;
if
left
欢迎访问NOI网站
B．欢迎访问NOI网站
C．h
t
t
p
:
/
/
w
w
w
.
n
o
i
.
c
n
D．欢迎访问NOI网站
7.
关于拓扑排序，下列说法正确的是(
)。
A．所有连通的有向图都可以实现拓扑排序
B．对同一个图而言，拓扑排序的结构是唯一的
C．拓扑排序中入度为0的结点总会排在入度大于0的结点的前面
D．拓扑排序结果序列中的第一个结点一定是入度大于0的点
8.
一个平面的法线是指与该平面垂直的直线。过点(1,1,1)、（0,3,0）、(2,0,0)的平面的法线是（
）。
A．过点（1，1，1）、（2，3，3）的直线B．过点（1，1，1）、（3，2，1）的直线
C．过点（0，3，0）、（-3，1，1）的直线D．过点（2，0，0）、（5，2，1）的直线
9.双向链表中有两个指针域llink和rlink，分别指向该结点的前驱及后继。设p指向链表中的一个结点，他的左右结点均为非空。现要求删除结点p，则下列语句序列中正确的是(
)。
A．p->rlink->llink=p->rlink;
p->llink->rlink=p->llink;
delete
p;
B．p->llink->rlink=p->rlink;
p->rlink->llink
=
p->llink;
delete
p;
C．p->rlink->llink
=
p->llink;
p->rlink->llink
->rlink
=
p->rlink;
delete
p;
D．p->llink->rlink
=
p->rlink;
p->llink->rlink->link
=
p->llink;
delete
p;
10.
今年(2010年)发生的事件有（
）。
A．惠普实验室研究员Vinay
Deolalikar
自称证明了P≠NP
B．英特尔公司收购计算机安全软件公司迈克菲(McAfee)
C．苹果公司发布iPhone
4手机D．微软公司发布Windows
7
操作系统
三、问题求解
1．LZW编码是一种自适应词典编码。在编码的过程中，开始时只有一部基础构造元素的编码词典，如果在编码的过程中遇到一个新的词条，则该词条及一个新的编码会被追加到词典中，并用于后继信息的编码。
举例说明，考虑一个待编码的信息串：“xyx
yy
yy
xyx”。初始词典只有3个条目，第一个为x,编码为1；第二个为y，编码为2；第三个为空格，编码为3；于是串“xyx”的编码为1-2-1（其中-为编码分隔符），加上后面的一个空格就是1-2-1-3。但由于有了一个空格，我们就知道前面的“xyx”是一个单词，而由于该单词没有在词典中，我们就可以自适应的把这个词条添加到词典里，编码为4，然后按照新的词典对后继信息进行编码，以此类推。于是，最后得到编码：1-2-1-3-2-2-3-5-3-4。
我们可以看到，信息被压缩了。压缩好的信息传递到接受方，接收方也只要根据基础词典就可以完成对该序列的完全恢复。解码过程是编码过程的逆操作。现在已知初始词典的3个条目如上述，接收端收到的编码信息为2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6，则解码后的信息串是”____________”。
2.无向图G有7个顶点，若不存在由奇数条边构成的简单回路，则它至多有__________条边。
3.记T为一队列，初始时为空，现有n个总和不超过32的正整数依次入列。如果无论这些数具体为何值，都能找到一种出队的方式，使得存在某个时刻队列T中的数之和恰好为9，那么n的最小值是___________。
四、阅读程序写结果
1.
const
size
=
10;
var
i,j,cnt,n,m
:
integer;
data
:
array[1size]
of
integer;
begin
readln(n,m);
for
i
:=
1
to
n
do
read(data[i]);
for
i
:=
1
to
n
do
begin
cnt
:=
0;
for
j
:=
1
to
n
do
if
(data[i]
right
then
begin
if
successful
then
begin
for
i
:=
1
to
n
do
writeln(r[i],);
found
:=
true;
end;
exit;
end;
for
i:=
left
to
right
do
begin
swap(r[left],r[i]);
perm(left
+
1,right);
swap(r[left],r[i]);
end;
end;
begin
readln(n,m);
fillchar(map,sizeof(map),false);
for
i
:=
1
to
m
do
begin
readln(x,y);
map[x][y]
:=
true;
map[y][x]
:=
true;
end;
for
i
:=
1
to
n
do
r[i]
:=
i;
found
:=
false;
perm(1,n);
if
not
found
then
writeln(
No
soloution
);
end.
输入:
9
12
1
2
2
3
3
4
4
5
5
6
6
1
1
7
2
7
3
8
4
8
5
9
6
9
输出：__________
五、完善程序
1.(过河问题)
在一个月黑风高的夜晚,有一群人在河的右岸,想通过唯一的一根独木桥走到河的左岸.在伸手不见五指的黑夜里,过桥时必须借照灯光来照明,不幸的是,他们只有一盏灯.另外,独木桥上最多能承受两个人同时经过,否则将会坍塌.每个人单独过独木桥都需要一定的时间,不同的人要的时间可能不同.两个人一起过独木桥时,由于只有一盏灯,所以需要的时间是较慢的那个人单独过桥所花费的时间.现在输入N(2
b
then
max
:=
a
else
max
:=
b;
end;
function
go(stage
:
boolean)
:
integer;
var
i,j,num,tmp,ans
:
integer;
begin
if
(stage
=
RIGHT_TO_LEFT)
then
begin
num
:=
0;
ans
:=0;
for
i
:=
1
to
n
do
if
pos[i]
=
Rignt
then
begin
inc(num);
if
time[i]
>
ans
then
ans
:=
time[i];
end;
if
__________
then
begin
go
:=
ans;
exit;
end;
ans
:=
INFINITY;
for
i
:=
1
to
n
–
1
do
if
pos[i]
=
RIGHT
then
for
j
:=
i+1
to
n
do
if
pos[j]
=
RIGHT
then
begin
pos[i]
:=
LEFT;
pos[j]
:=
LEFT;
tmp
:=
max(time[i],time[j])
+
_______;
if
tmp
=1，它的叶结点数目为：
A)
nk
+
1
B)
nk-1
C)
(k+1)n-1
D.
(k-1)n+1
6.
表达式a*(b+c)-d的后缀表达式是：
A)
abcd*+-
B)
abc+*d-
C)
abc*+d-
D)
-+*abcd
7、最优前缀编码，也称Huffman编码。这种编码组合的特点是对于较频繁使用的元素给与较短的唯一编码，以提高通讯的效率。下面编码组合哪一组不是合法的前缀编码。
A)（00，01，10，11）
B)（0，1，00，11）
C)（0，10，110，111）
D)（1，01，000，001）
8、快速排序平均情况和最坏情况下的算法时间复杂度分别为：
A)
平均情况
O(nlog2n)，最坏情况O(n2)
B)
平均情况
O(n)，
最坏情况O(n2)
C)
平均情况
O(n)，
最坏情况O(nlog2n)
D)
平均情况
O(log2n)，
最坏情况O(n2)
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
10、全国信息学奥林匹克的官方网站为参与信息学竞赛的老师同学们提供相关的信息和资源，请问全国信息学奥林匹克官方网站的网址是：
A)
http://www.jsfw8.com/B)
http://www.jsfw8.com/
二．
不定项选择题
（共10题，每题1.5分，共计15分。每题正确答案的个数不少于1。多选或少选均不得分）。
1、关于CPU下面哪些说法是正确的：
A)
CPU全称为中央处理器（或中央处理单元）。
B)
CPU能直接运行机器语言。
C)
CPU最早是由Intel公司发明的。
D)
同样主频下，32位的CPU比16位的CPU运行速度快一倍。
2、关于计算机内存下面的说法哪些是正确的：
A)
随机存储器（RAM）的意思是当程序运行时，每次具体分配给程序的内存位置是随机而不确定的。
B)
一般的个人计算机在同一时刻只能存/取一个特定的内存单元。
C)
计算机内存严格说来包括主存（memory）、高速缓存（cache）和寄存器（register）三个部分。
D)
1MB内存通常是指1024*1024字节大小的内存。
3、关于操作系统下面说法哪些是正确的：
A.
多任务操作系统专用于多核心或多个CPU架构的计算机系统的管理。
B.
在操作系统的管理下，一个完整的程序在运行过程中可以被部分存放在内存中。
C.
分时系统让多个用户可以共享一台主机的运算能力，为保证每个用户都得到及时的响应通常会采用时间片轮转调度的策略。
D.
为了方便上层应用程序的开发，操作系统都是免费开源的。
4、关于计算机网络，下面的说法哪些是正确的：
A)
网络协议之所以有很多层主要是由于新技术需要兼容过去老的实现方案。
B)
新一代互联网使用的IPv6标准是IPv5标准的升级与补充。
C)
TCP/IP是互联网的基础协议簇，包含有TCP和IP等网络与传输层的通讯协议。
D)
互联网上每一台入网主机通常都需要使用一个唯一的IP地址，否则就必须注册一个固定的域名来标明其地址。
5、关于HTML下面哪些说法是正确的：
A)
HTML全称超文本标记语言，实现了文本、图形、声音乃至视频信息的统一编码。
B)
HTML不单包含有网页内容信息的描述，同时也包含对网页格式信息的定义。
C)
网页上的超链接只能指向外部的网络资源，本网站网页间的联系通过设置标签来实现。
D)
点击网页上的超链接从本质上就是按照该链接所隐含的统一资源定位符（URL）请求网络资源或网络服务。
6、若3个顶点的无权图G的邻接矩阵用数组存储为{{0，1，1}，{1，0，1}，{0，1，0}}，假定在具体存储中顶点依次为:
v1，v2，v3
关于该图，下面的说法哪些是正确的：
A)该图是有向图。
B)该图是强连通的。
C)该图所有顶点的入度之和减所有顶点的出度之和等于1。
D)从v1开始的深度优先遍历所经过的顶点序列与广度优先的顶点序列是相同的。
7、在带尾指针（链表指针clist指向尾结点）的非空循环单链表中每个结点都以next字段的指针指向下一个节点。假定其中已经有2个以上的结点。下面哪些说法是正确的：
A)
如果p指向一个待插入的新结点，在头部插入一个元素的语句序列为：
p^.next:=
clist^.next;
clist^.next:=
p;
B)
如果p指向一个待插入的新结点，在尾部插入一个元素的语句序列为：
p^.next:=
clist;
clist^.next:=
p;
C)
在头部删除一个结点的语句序列为：
p:=
clist^.next;
clist^.next:=
clist^.next^.next;
dispose(p);
D)
在尾部删除一个结点的语句序列为。
p:=
clist;
clist:=
clist
^.next;
dispose(p);
8、散列表的地址区间为0-10,散列函数为H(K)=K
mod
11。采用开地址法的线性探查法处理冲突，并将关键字序列26，25，72，38，8，18，59存储到散列表中，这些元素存入散列表的顺序并不确定。假定之前散列表为空，则元素59存放在散列表中的可能地址有：
A)
5
B)
7
C)
9
D)
10
9、排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变，下列哪些排序算法是稳定的：
A)
插入排序
B)
基数排序
C)
归并排序
D)
冒泡排序
10、在参加NOI系列竞赛过程中，下面哪些行为是被严格禁止的：
A)
携带书写工具，手表和不具有通讯功能的电子词典进入赛场。
B)
在联机测试中通过手工计算出可能的答案并在程序里直接输出答案来获取分数。
C)
通过互联网搜索取得解题思路。
D)
在提交的程序中启动多个进程以提高程序的执行效率。
三．问题求解（共2题，每空5分，共计10分）
1．拓扑排序是指将有向无环图G中的所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若
∈E(G)，则u在线性序列中出现在v之前，这样的线性序列成为拓扑序列。如下的有向无环图，对其顶点做拓扑排序，则所有可能的拓扑序列的个数为
。
3
2
1
5
4
7
6
8
9
2．某个国家的钱币面值有1,7,72,73共计四种，如果要用现金付清10015元的货物，假设买卖双方各种钱币的数量无限且允许找零，那么交易过程中至少需要流通
张钱币。
四．阅读程序写结果（共4题，每题8分，共计32分