noip提高组c初赛试题与答案

2009 第十五届全国青少年信息学奥林匹克联赛初赛试题

提高组 C++ 语言 二小时完成 ）

全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效

． 单项选择题 （共 10 题，每题分，共计 15 分。每题有且仅有一个正确答 案。） 1、关于图灵机下面的说法哪个是正确的：

图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作 用。

2、关于BIOS 下面的说法哪个是正确的:

BIOS 里包含了键盘、鼠标、声卡、图形界面显器等常用输入输出设备的 驱动程序。

BIOS 能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。

3、已知大写字母A 的ASCII 编码为65（十进制），则大写字母J 的 十六进制ASCII 编码为:

4、在字长为 16位的系统环境下，一个 16位带符号整数的二进制补码为 101。 其对应的十进制整数应该是:

n 个分支结点（非叶结点）的非空满 k 叉树，k>=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）

A) 图灵机是世界上最早的电子计算机。

B) 由于大量使用磁带操作，图灵机运行速度很慢。

C) 图灵机只是一个理论上的计算模型。

D) A) BIOS 是计算机基本输入输出系统软件的简称。

B) C) BIOS 一般由操作系统厂商来开发完成。

D) A) 48 B) 49 C) 50 D)

以上都不是 A) 19 B) -19 C) 18 D) -18

5、一个包含

目为:

A) nk + 1

B ） （0，1，00，11）

C ）（0，10，110，111）

D ）（1，01，000，001）

8、快速排序平均情况和最坏情况下的算法时间复杂度分别为：

9、右图给出了一个加权无向图， 从顶点 V 0 开始用 prim 算法求最 小生成树。则依次加入最小生成 树的顶点集合的顶点序列为:

10、全国信息学奥林匹克的官方网站为参与信息学竞赛的老师同学们提供相关的

信息和资源，请问全国信息学奥林匹克官方网站的网址是:

A ）

B ）

D ） 二． 不定项选择题 （共 10 题，每题分， 共计 15 分。每题正确答案的个数不少于 1。多选或少选均不得分） 。

1、关于CPU 下面哪些说法是正确的:

同样主频下，32位的CPU 比16位的CPL 运行速度快一倍。

2、关于计算机内存下面的说法哪些是正确的:

A ）随机存储器（RAM 的意思是当程序运行时，每次具体分配给程序的内存 位置是随机而不确定的。

B ） 一般的个人计算机在同一时刻只能存 / 取一个特定的内存单元。

C ）计算机内存严格说来包括主存（memory 、高速缓存（cache ）和寄存器

（ register ）三个部分。

A) 平均情况 O(nlog 2n) ， B) 平均情况 O(n) ，

最坏情况 O （n 2

） 最坏情况 O （n 2

） C) 平均情况 O(n) ， D) 平均情况 O(log 2n) ，

最坏情况 O （nlog

2n ） 最坏情况 O （n 2）

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

A) CPU 全称为中央处理器（或中央处理单元）。

B) CPU 能直接运行机器语言。

C) CPU ft 早是由In tel 公司发明的。

D)

从v i 开始的深度优先遍历所经过的顶点序列与广度优先的顶点序列是相

7、在带尾指针(链表指针 clist 指向尾结点)的非空循环单链表中每个结点都

D) 1MB 内存通常是指1024*1024字节大小的内存。

3、关于操作系统下面说法哪些是正确的：

A. 多任务操作系统专用于多核心或多个 CPL 架构的计算机系统的管理。

B. 在操作系统的管理下，一个完整的程序在运行过程中可以被部分存放在

内存中。

C. 分时系统让多个用户可以共享一台主机的运算能力，为保证每个用户都

得到及时的响应通常会采用时间片轮转调度的策略。

D. 为了方便上层应用程序的开发，操作系统都是免费开源的。

4、关于计算机网络，下面的说法哪些是正确的：

A) 网络协议之所以有很多层主要是由于新技术需要兼容过去老的实现方 案。

B) 新一代互联网使用的 IPv6 标准是 IPv5 标准的升级与补充。

C) TCP/IP 是互联网的基础协议簇，包含有TCP 和IP 等网络与传输层的通讯 协议。

D) 互联网上每一台入网主机通常都需要使用一个唯一的 IP 地址，否则就必 须注册一个

固定的域名来标明其地址。

5、关于HTML 下面哪些说法是正确的:

A) HTML 全称超文本标记语言，实现了文本、图形、声音乃至视频信息的统 一编

码。

B) HTMI 不单包含有网页内容信息的描述，同时也包含对网页格式信息的定 义。

C) 网页上的超链接只能指向外部的网络资源，本网站网页间的联系通过设 置标签

来实现。

D) 点击网页上的超链接从本质上就是按照该链接所隐含的统一资源定位符

(URL 请求网络资源或网络服务。

6若3个顶点的无权图G 的邻接矩阵用数组存储为｛｛0，1,1｝，｛1，0, 1｝，｛0， 1，

0｝｝，假定在具体存储中顶点依次为：V 1，V 2，V 3。关于该图，下面的说法 哪些是正确的:

A) 该图是有向图。

B) 该图是强连通的。

C) 该图所有顶点的入度之和减所有顶点的出度之和等于 1。

D) 同的。

以next 字段的指针指向下一个节点。假定其中已经有2个以上的结点。下面 哪些说法是正确的：

如果p 指向一个待插入的新结点，在头部插入一个元素的语句序列为:

p->n ext = clist- >n ext; clist- >n ext = p;

如果p 指向一个待插入的新结点，在尾部插入一个元素的语句序列为:

P = clist- >n ext; clist- >n ext = clist- >n ext- >n ext; delete p;

P = clist; clist = clist ->n ext; delete p;

8、散列表的地址区间为0-10,散列函数为H(K)=K mod11。采用开地址法的线性 探查法处理冲

突，并将关键字序列 26, 25，72, 38，8，18, 59存储到散列 表中，这些元素存入散列表的顺序并不确定。假定之前散列表为空，则元素 59存放在散列表中的可能地址有：

A) 5 B) 7 C) 9 D) 10

9、排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变, 下列哪些排序算

法是稳定的：

A)插入排序 B) 基数排序 C) 归并排序 D) 冒泡排序

10、在参加NOI 系列竞赛过程中，下面哪些行为是被严格禁止的:

携带书写工具，手表和不具有通讯功能的电子词典进入赛场。

在联机测试中通过手工计算出可能的答案并在程序里直接输出答案来获 取分数。

三.问题求解(共2题，每空5分，共计10 分) 1.拓扑排序是指将有向无环图G 中的所有顶点排成一个线性序列，使得图 中任意一对顶点u 和V ,若vu , v> € E(G),则u 在线性序列中出现在V 之前， 这样的线性序列成为拓扑序列。如下的有向无环图，对其顶点做拓扑排序，则所 有可能的拓扑序列的个数为 。

A) B)

C) p->n ext = clist ；clist->next = p;

在头部删除一个结点的语句序列为:

D) 在尾部删除一个结点的语句序列为。

A) B) C) 通过互联网搜索取得解题思路。

D) 在提交的程序中启动多个进程以提高程序的执行效率。

输出:

2, 7 3共计四种，如果要用现金付清10015 那么交易过程中至少 四.阅读程序写结果（共4题，每题8分，共计32 分） 1.

#in elude

using n ames pace std;

int a,b;

int work(i nt a,i nt b){

if (a%b)

return work(b,a%b);

return b;

int mai n(){

cin ? a >> b;

cout << work(a,b) << en dl;

return 0;

输入：123 321

2.某个国家的钱币面值有1, 7, 7

元的货物，假设买卖双方各种钱币的数量无限且允许找零, 需要

流通 张钱币。

9

2．

#include

using namespace std;

int main()

int a[4],b[4];

int i,j,tmp;

for (i=0;i<4;i++)

cin >> b[i];

for (i=0;i<4;i++)

a[i]=0;

for (j=0;j<=i;j++)

a[i]+=b[j];

b[a[i]%4]+=a[j];

tmp=1;

for (i=0;i<4;i++)

a[i]%=10;

b[i]%=10;

tmp*=a[i]+b[i];

cout << tmp << endl;

return 0;

输入：2 3 5 7

}

输出:

3.

#in elude

using n ames pace std;

const int max n=50;

const int y=2009;

int main()

int n,c[max n][max n],i,j,s=0;

cin ? n;

c[0][0]=1;

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

c[i][0]=1;

for(j=1;j

c[i][j]=c[i-1][j-1]+c[i-1][j];

c[i][i]=1;

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

s=(s+c[ n][i])%y;

cout << s << en dl;

return 0;

输入：17

输出: