第十六届全国 青少年信息学 奥林匹克联赛 初赛试题
（ 提高组C 语言二小时完 成）
●● 全部试题答案 均要求写在答 卷纸上，写在试卷纸上 一律无效●●
一.单项选择题（共10题，每题1.5分，共计15分。每题有且仅有 一个正确选项 。） 1.与16进制数 A1.2等值的 进制数是（C ）
A.101.2 B.111.4 C.161.125 D.177.25
解析1: 进制 的?表 原式等于10?（A）×161＋1×160＋2×16-1=161.125 2.一个字节（byte）由（ ）个二进制位组 成。
A.8 B.16 C.32 D.以上都有可能 解析2: 一个字节（byte）由（ 8 ）个二进制位组 成， 一个字节等?于八比特 3.一下逻辑表达 式的值恒为真 的是（ ）
A.P∨（┐P∧Q)∨（┐P∧┐Q) B.Q∨（┐P∧Q)∨(P∨┐Q)
C.P∨Q∨(P∧┐Q)∨(┐P∧Q) D.P∨┐Q∨(P∧┐Q)∨(┐P∧┐Q) 解析3 个逻辑 ?的 题，可以进 一 ?的假设。设P,Q都为假 \∨\表示\或\ 于 ?的“或者”， \∧\表示\与\ 于 ?说的“并且” \┐\表示\非\真或真为真 真或假为真 假或假为假 假与假为假，假与真为假，真与真为真。真为真，非真为假，假为假，非假为真。 4.Linux下 可执 文件的 默认扩展名为 （ ）
A.exe B.com C.dll D.都不是 解析4 Linux下 常见的文件名 后缀、文件类型 1、系统文件*.conf配置 文件*.rpm rpm包*.a 一种存档文件 *.lock 一种琐文件*.~ 备份文件
*. 隐藏文件
2:程序或脚本*.c c语言源程序 文件*.cpp c++语言源程序*.h c或c++头文件 *.o 程序对象文件 *.pl perl语言 源程序*. php php语言源 程序*.tcl tcl脚本程 序*.so/.lib 库文件 *.sql sql语言文 件
3:格式文件*.txt 无格式的 cii码文件 *.html/.htm 静态web页 ipt文件*.au 一种声音文件 *.wav 一种声音文件 *.xpm一种图 像文件*.png一种图 形,图像文件4:存档与压缩文 件
*.tar tar归档文 件*.Z/.gz/.bz2压缩文 件*.tar.gz/.tgz/.tar.bz2/.tbz为压缩 后的tar包
linux本 身是没有扩展 名这个概念的 。只有文件属性 里可以 义可 执 权限
5.如果在某个进 制下等式7*7=41成立，那么在该进制 下等式12*12=（ ）也成立。 A.100 B.144 C.164 D.196 解析5
设进制为z得 到:12=1×z1+2×z0
12*12=（1×z1+2）*（1×z1+2）= z2+4z+4=1×z2+4×z1+4×z0=144 6.提出“存储程序”的计算机工作 原理的是（ ）。
A.克劳德·香农 B.戈登·摩尔 C.查尔斯·巴比奇 D.冯·诺依曼 解析6 克劳德·香农 克劳德·艾尔伍德·香农（ n ，1916年 月30日—2001年 月26日）美国数学 ，信息学的 ?人。 冯.诺依曼，计算机 ，第一 计算机?设计出 后?，没有内存，冯.诺依曼提出了 存储程序的概?念和思路
阿兰·麦席森·图灵 ，6月23日 于英国伦敦。是英国著名的数学 和逻辑学 ，被称为计算机 科学 、人工智能 ，是计算机逻辑 的奠基者，提出了“图灵机”和“图灵测试”等重要概念。人们为纪念其 在计算机领域 的卓越贡献而 设立“图灵奖”。 7.前缀表达式“+3*2+5 2”的值是（ ）
A.23 B.25 C.37 D.65 解析7 前缀表达式就 是不含括 的 算术表达式，而且它是将运算 写在前面，操作数写在后面的表 达式，为纪念其发明 者波兰数学 ewicz也 称为“波兰式”。例如，- 1 + 2 3，它等价于1-(2+3)。
对于一个前缀 表达式的求值 而言，首先要从右至 左扫描表达式 ，从右边第一个 字
开 判断 ，如果 前字 是数字则一直 到数字串的末 尾再记录下 ，如果是运算 ，则将右边离得 最近的两个“数字串”作 应的运算 ，以此作为一个 新的“数字串”并记录下 。一直扫描到表 达式的最左端 时，最后运算的值 也就是表达式 的值。例如，“+3 +5 1 ”前缀表达式求 值，扫描到12时 ，记录下这个数 字串，扫描到5时，记录下这个数 字串， 扫描到+时，将+右移做 邻两 数字串的运算 ，记为12+5，结果为17，记录下这个新 数字串，并继续向左扫 描，扫描到2时，记录下这个数 字串，扫描到*时，将*右移做 邻两 数字串的运算 ，记为2*17，结果为34，记录下这个新?字 ， 后继续扫描?，扫描到3记录?下 ，再继续扫描到?“+”， 运算 右移?，记为3+34=37.
8.主存储器的存 取速度比 央 处理器（CPU）的工作速度慢 很多，从而使得后者 的效率受到影 响。而根据局部性 原理，CPU所访 的存储单元通 常都趋于聚集 在一个较小的 连续区域 。于是，为了提高系统 整体的执 效 率，在CPU 引 入了（ ）
A.寄存器 B.高速缓存 C.闪存 D.外存 解析8 寄存器是 央处理器内的组成部分 。寄存器是有限 存贮容量的高 速存贮部件，它们可用 暂 存指令、数据和位址。 闪存（ ）是一种长寿命 的非易失性（在断电情况下 仍能保持所存 储的数据信息 ）的存储器由于其断电时 仍能保存数据 ，闪存通常被用 保存设置信 息，如在电脑的 IOS 外储存器是指 除计算机内存及CPU缓存以外的储存器 ，此类储存器一 般断电后仍 能保存数据。常见的外储存 器有硬盘、软盘、光盘、U盘等。 “高速缓存”的 的是为了? 数据访 的?速度适应CP?U的处理速度?，其基于的原理?是内存 “程序执 与数?据访 的局域?性 为”， 一 程序执? 时 和 ?内，被访 的 码?集 于一部分?。
9.完全二叉树的 顺序存储方案 ，是指将完全二 叉树的结点从 上至下、从左至右一次 存放到一个顺 序结构的数组 。假 根结点存 放在数组的 位置，则第K 结点 的 结点如果 存在的话，应 存放在数 组的（ ） 位置。
A.2k B.2k+1 C.k/2下取整 D.(k+1)/2下取整
解析9 于二叉树的?性质 (1) 在二叉树 ，第i层的结点 总数不超过 ^(i-1)； (2) 深度为h的二 叉树最多有 ^h-1个结点(h>=1)，最少有h个结 点； (3) 对于任意一棵 二叉树，如果其叶结点 数为N0，而度数为2的 结点总数为 2，则N0=N2+1；
(4) 具有n个结点 的完全二叉树的深度为 t（log2n）+1 (5)有N个结点的 完全二叉树 结点如果用顺 序方式存储，则结点 有 如下 系 若I为结点编 则 如果I<>1，则其 结点的 编 为I/2； 如果2*I<=N，则其左儿子（ 左子树的根 结点）的编 为2*I；若2*I>N，则无左儿子； 如果2*I+1<=N，则其右儿子的 结点编 为 *I+1；若2*I+1>N，则无右儿子。 (6)给 N个节点 ，能构成h(N)种不同的二叉 树。 h(N)为卡特兰数的第N项。h(n)=C(n,2*n)/(n+1)。
（7）设有i个枝点 ，I为所有枝点 的道路长度总 和，J为叶的道路 长度总和J=I+2i 10.一下竞赛 动 历史最悠久 的是（ ）
A.全国青少年信 息学奥林匹克 联赛（NOIP）
B.全国青少年信 息学奥林匹克 竞赛（NOI）
C.国际信息学奥 林匹克竞赛（IOI）
D.亚太地区信息 学奥林匹克竞 赛（APIO） 解析10
全国青少年信 息学奥林匹克 联赛（NOIP）全国青少年信 息学奥林匹克联赛（ ces，简称NOIP）自1995年 至今已举办 7次。每年由 国计算机学 会（CCF）统一组织。 全国青少年信 息学奥林匹克 （NOI）是国内包括港 澳在内的省级 表队最高水 平的大赛，自1984年 至今，在国内包括香 港、澳门，已组织了 次竞赛 动。 国际信息学奥?林匹克竞赛（IOI）首届竞赛于 989 年在保加利亚 的布拉维茨举 ，有13个国 的46名选手 参赛。此后IOI每 年举办一届， 亚太地区信息 学奥林匹克竞 赛（APIO）亚洲与太平洋 地区信息学奥林匹克（Asia-Paci ad, APIO），是一个面向亚太地区在校 学 的 信息学科竞赛 。旨在给青少年 提供更多的赛 事机会，推动亚太地区 的信息学奥林 匹克的发展。该竞赛性质为 区域性的网上 准同步赛，每年五月的第 一或第二个星 期六举办，2007年举?办第一届，主办方为澳大?利亚， 国区的 办?方是 ， 国人 大学?，2008年是?沈阳，东 大学，2009年是?天津，天津大学，2010年是? ， 航大学，2011年是? ， 国人 大学?，2012年是? ， 大学
二.不 项选择题 （共10题，每题1.5分，共计15分。每题有一个或 多个正确选项 。多选或少选均 不得分。）
1.元素R1、R2、R3、R4、R5入栈的顺 序为R1、R2、R3、R4、R5。如果第一个出 栈的是R3，那么第五个出 栈的可能是（ ）。
A.R1 B.R2 C.R4 D.R5 解析1 入栈依次进入 ，那么 R3入 栈时，堆栈应该是 R1，R2，R3
此时R3出栈 。就是 R1，R2 后不论 R4，R5如何出入 栈，R1必 会在 R2 后出栈 ，所以第五个出 栈的不会是 2，R2最多只能 在第四个出栈 。 2.P 语言、C语言、和C++语言都属于（ ）
A.高级语言 B.自 语言 C.解释型语言 D.编译性语言
3.原地排序是指 在排序过程 （除了存储待排 序元素以外的 ）付诸 的大 小与数据规模 无 的排序算 法。一下属于原地 排序的有（ ）
A.冒泡排序 B.插入排序 C.基数排序 D.选择排序 4.在整数的补码 表示法 ，以下说法正确 的是（ ） A.只有负整数的 编码最高为
B.在编码的位数 确 后，所能表示的最 小整数和最大 整数的绝对值 同 C.整数0只有唯 一的一个编码
D.两个用补码表 示的数 加时 ，如果在最高位 产 进位，则表示运算溢 出
5.一颗二叉树的 前序遍历序列 是 B FG，后序遍历序列 是 B DA，则根结点的左 子树的结点个 数可能是（ ）
A.0 B.2 C.4 D.6
6.在下列 L语句 ，可以正确产 一个指向 I官方网站的 超链接的是（ ）
D. 解析6 HTML语言?
建一个 ML文档
设置文档标题 和其它在网页 不显示的信 息 建自动发送 电子邮件的链 接 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）的直线 解析8 立体 何 题?。 9.双向链表 有 两个指针域 link和 link，分别指向该结 点的前驱及后 继。设p指向链表 的一个结点 ，它的左右结点 均非 。现要求删除结 点P,则下面语句序 列 正确的是（ ） A.p->rlink->llink = p->rlink; p->llink->rlink = p->llink; free(p); B.P->llink->rlink = p->rlink; p->rlink->llnik = p->llink; free(p); C.p->rlink->llink = p->llink; p->rlink->llink->rlink = p->rlink; free(p); D.p->llink->rlink = p->rlink; p->llink->rlink->llink = p->llink; free(p); 10.今年（2010）发 的事件有 （ ） A.惠普实验室研 究员 ikar自称 证明了P≠ P