2009第十五届全国青少年信息学奥林匹克联赛初赛试题
(提高组C语言 二小时完成)
? ? 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效
一.单项选择题
(共10题，每题1.5分，共计15分。每题有且仅有一个正确答案。)
??
1、 关于图灵机下面的说法哪个是正确的：
A图灵机是世界上最早的电子计算机。
B) C) D)
由于大量使用磁带操作，图灵机运行速度很慢。 图灵机只是一个理论上的计算模型。
图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。
【分析】选择C
A最早的计算机是ENIAC
B图灵机是计算机模型，没有运行速度，更谈不上磁带操作 D图灵机是英国人阿兰图灵提出的理论，
阿兰图灵本人在二战中破译德军密码系统发挥重要作用，而不是图灵机发挥作用
2、 关于BIOS下面的说法哪个是正确的：A
A) BIOS是计算机基本输入输出系统软件的简称。
B) BIOS里包含了键盘、鼠标、声卡、图形界面显器等常用输入输出设备的驱动程序。 C) BIOS 一般由操作系统厂商来开发完成。
D) BIOS能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。
其实bios=Basic In put Output System。但是对于是否是软件这一说法还存在争议呢！ 系统启动的基本信息，这些设备的驱动程序是不存的。 最著名的都是台湾的三家。
D项中，固件BIOS根本这些功能
B中BIOS只存一些
C项中BIOS 一般是由单独的芯片厂家生产的，
3、 已知大写字母A的ASCII编码为65 (十进制)，则大写字母J的 十六进制ASCII编码为：
A) 48 B) 49 C) 50 D)以上都不是
4、 在字长为16位的系统环境下，一个16位带符号整数的二进制补码为 1111111111101101。其对应的 十进制整
数应该是：
A) 19 B) - 19 C) 18 D) - 18
1111111111101101的原码为1000000000010011也就是-19,最高位为符号位 5、 一个包含n个分支结点(非叶结点)的非空满
A) nk + 1 B) n k- 1 C) (k+1) n- 1 D. (k-1) n+1
k叉树，k>=1，它的叶结点数目为：D
NOIP2009 初赛
—］提高组 C 语言 1
. 一_二^
考多叉树的性质，N0=(K-1)N+1，考试的时带入K=2时候，验证二叉树能得到结果
NOIP2009 初赛 提高组C语言 2
6.表达式a*(b+c)- d的后缀表达式是：B
A) abcd*+- B) abc+*d - C) abc*+d- D) - +*abcd
主要是考树的遍历，要明白前缀、中缀和后缀表达式。
构造二叉树，操作数做叶子节点，运算符做非叶节点。按中序遍历就可以得到中缀表达式
7、最优前缀编码，也称 Huffman编码。这种编码组合的特点是对于较频繁使用的元素给与较短的唯
编码，以提咼通讯的效率。下面编码组合哪一组不是合法的前缀编码。
B
A) (00， 01， 10， 11) B) (0, 1, 00，11) C) (0， 10， 110， 111) D)
(1， 01， 000， 001)
0是00的前缀码，这部分是数据结构中哈夫曼编码处的知识 8快速排序平均情况和最坏情况下的算法时间复杂度分别为：
A
A) 平均情况 O(nlog2n)，最坏情况0(n2
)
B) 平均情况O(n)， 最坏情况O(n2
)
C) 平均情况 O(n)，
最坏情况O(nlog2n)
D)
平均情况O(log2n)，最坏情况O(n2
)
最好的时候是nXog (2，n)，最坏情况的是退化成冒泡排序，复杂度为
0 (nA2)
9、左图给出了一个加权无向图， 从
顶点Vo开始用prim算法求最 小生成树。则依次加入最小生成 树的顶点集合的顶点序列为A:
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
加入的边依次为 v0v1、v1v2、v1v3 (或v2v3)、
v1v5、 v3v4
10、全国信息学奥林匹克的官方网站为参与信息学竞赛的老师同学们提供相关的信息和资源，请问全国学奥林匹克官方网站的网址是：C
NOIP2009 初赛
—］提高组 C 语言 3
. 一_二^
信息
A) http://www. noi.com/ C) http://www. noi.c n/
B) http://www. noi.org/
D) http://www.xinxixue.com/
不定项选择题 （共10题，每题1.5分，共计15分。每题正确答案的个数不少于
1。多选或少选
均不得分）。
1、 关于CPU下面哪些说法是正确的：AB
A） CPU全称为中央处理器（或中央处理单元）。 B） CPU能直接运行机器语言。 C） CPU最早是由In tel公司发明的。 D）
同样主频下，32位的CPU比16位的CPU运行速度快一倍。
D项中，位数只
C项中，In tel最早发明的是微处理器，而 CPU之前就由电子管、晶体管实现着呢
能说明处理的字长，所在的系统硬件指令不同，速度很难说谁快
2、 关于计算机内存下面的说法哪些是正确的： BD
A）
随机存储器（RAM ）的意思是当程序运行时，每次具体分配给程序的内存位置是 随机而不确
定的。
B） C）
一般的个人计算机在同一时刻只能存/取一个特定的内存单元。
计算机内存严格说来包括主存（memory）、高速缓存（cache）和寄存器（register）三个部分。
D） 1MB内存通常是指1024*1024字节大小的内存。
一般是对字节的一个单元串行操作。
1MB=1024KB=1024*1024B
A中RAM不是位置随机，而是随时访问，所谓 随机存取”指的是当存储器中的消息被读取或写入时， 所需要
的时间与这段信息所在的位置无关。
C中高速缓存和寄存器的物理实现是集成在 CPU中，这两部分不属于冯诺依曼体系中的五大部分的任意 一个部
分。
3、 关于操作系统下面说法哪些是正确的：BC
A. B. C.
多任务操作系统专用于多核心或多个 CPU架构的计算机系统的管理。
在操作系统的管理下，一个完整的程序在运行过程中可以被部分存放在内存中。
分时系统让多个用户可以共享一台主机的运算能力，为保证每个用户都得到及时的响应通常会采 用时间片轮转调度的策略。
D.
为了方便上层应用程序的开发，操作系统都是免费开源的。
A多任务系统可以是单个 CPU构架的，普通的PC都是多任务的。 D操作系统不是都免费开源
NOIP2009 初赛
提高组C语言 4
4、 关于计算机网络，下面的说法哪些是正确的： C
A） B）
网络协议之所以有很多层主要是由于新技术需要兼容过去老的实现方案。 新一代互联网使用的IPv6标准是IPv5标准的升级与补充。
C） TCP/IP是互联网的基础协议簇，包含有 TCP和IP等网络与传输层的通讯协议。 D）互联网上每一台入网主机通常都需要使用一个唯一的
IP地址，否则就必须注册一个固定的域名
来标明其地址。
A网络协议分层不是为了兼容，而是根据网络分层模型来的。
B新的IPv6是IPv4的升级。D即使注
册了域名也要有IP地址的
5、 关于HTML下面哪些说法是正确的：BD
A） HTML全称超文本标记语言，实现了文本、图形、声音乃至视频信息的统一编码。 B） HTML不单包含有网页内容信息的描述，同时也包含对网页格式信息的定义。 C） D）
网页上的超链接只能指向外部的网络资源，本网站网页间的联系通过设置标签来实现。 点击网页上的超链接从本质上就是按照该链接所隐含的统一资源定位符 网络服务。
（URL）请求网络资源或
A没有都统一编码
C本网站页面也可以用超链接，就是绝对路径。也可以用相对路径。
6、 若3个顶点的无权图G的邻接矩阵用数组存储为｛｛0，1, 1｝，｛1，0，1｝，｛0，1，0｝｝，假定在具体
存储中顶点依次为：V1, V2, V3。关于该图，下面的说法哪些是正确的：
A） B） C） D）
ABD
该图是有向图。 该图是强连通的。
该图所有顶点的入度之和减所有顶点的出度之和等于
1。
从V1开始的深度优先遍历所经过的顶点序列与广度优先的顶点序列是相同的。
next字段的指针指向下
7、 在带尾指针（链表指针clist指向尾结点）的非空循环单链表中每个结点都以
一个节点。假定其中已经有 2个以上的结点。下面哪些说法是正确的：
A）
如果p指向一个待插入的新结点，在头部插入一个元素的语句序列为：
p->n ext = clist- >n ext; clist- >n ext = p;
B）
如果p指向一个待插入的新结点，在尾部插入一个元素的语句序列为：
p->next = clist； clist->next = p;
C）
在头部删除一个结点的语句序列为：
p = clist- >n ext; clist- >n ext = clist- >n ext- >n ext; free（p）;
D）
在尾部删除一个结点的语句序列为。
p = clist; clist = clist ->n ext; free（p）;
NOIP2009 初赛
—］提高组 C 语言 5
. 一_二^
相关推荐：
loading