NOIP 2007 普及组初赛试题
NOIP 2007 普及组初赛试题
（满分：100 分 考试时间：120 分钟）
一、单项选择题（共 20 题，每题 1.5 分，共计 30 分；每题有且仅有一个正确选项）
- 在以下各项中，（ ）不是 CPU 的组成部分
{{ select(1) }}
- 控制器
- 运算器
- 寄存器
- 主板
本题共 1.5 分
- 在关系数据库中，存放在数据库中的数据的逻辑结构以（ ）为主。
{{ select(2) }}
- 二叉树
- 多叉树
- 哈希表
- 二维表
本题共 1.5 分
- 在下列各项中，只有（ ）不是计算机存储容量的常用单位。
{{ select(3) }}
- Byte
- KB
- UB
- TB
本题共 1.5 分
- ASCII 码的含义是（ ）。
{{ select(4) }}
- 二→十进制转换码
- 美国信息交换标准代码
- 数字的二进制编码
- 计算机可处理字符的唯一编码
本题共 1.5 分
- 一个完整的计算机系统应包括（ ）。
{{ select(5) }}
- 系统硬件和系统软件
- 硬件系统和软件系统
- 主机和外部设备
- 主机、键盘、显示器和辅助存储器
本题共 1.5 分
- IT 的含义是（ ）。
{{ select(6) }}
- 通信技术
- 信息技术
- 网络技术
- 信息学
本题共 1.5 分
- LAN 的含义是（ ）。
{{ select(7) }}
- 因特网
- 局域网
- 广域网
- 城域网
本题共 1.5 分
- 冗余数据是指可以由其它数据导出的数据。例如，数据库中已存放了学生的数学、语文和英语的三科成绩，如果还存放三科成绩的总分，则总分就可以看作冗余数据。冗余数据往往会造成数据的不一致。例如，上面 4 个数据如果都是输入的，由于操作错误使总分不等于三科成绩之和，就会产生矛盾。下面关于冗余数据的说法中，正确的是（ ）。
{{ select(8) }}
- 应该在数据库中消除一切冗余数据
- 用高级语言编写的数据处理系统，通常比用关系数据库编写的系统更容易消除冗余数据
- 为了提高查询效率，在数据库中可以保留一些冗余数据，但更新时要做相容性检验
- 做相容性检验会降低效率，可以不理睬数据库中的冗余数据
本题共 1.5 分
- 在下列各软件，不属于 NOIP 竞赛（复赛）推荐使用的语言环境有（ ）。
编者注：由于试题为 2007年的试题，请根据 2007年的实际情况作答。
{{ select(9) }}
- gcc
- g++
- Turbo C
- Free Pascal
本题共 1.5 分
- 以下断电后仍能保存数据的有（ ）。
{{ select(10) }}
- 硬盘
- 高速缓存
- 显存
- RAM
本题共 1.5 分
- 在下列关于计算机语言的说法中，正确的有（ ）。
{{ select(11) }}
- 高级语言比汇编语言更高级，是因为它的程序的运行效率更高
- 随着 Pascal、C 等高级语言的出现，机器语言和汇编语言已经退出了历史舞台
- 高级语言比汇编语言程序更容易从一种计算机上移植到另一种计算机上
- 是一种面向对象的高级计算机语言
本题共 1.5 分
- 近 20 年来，许多计算机专家都大力推崇递归算法，认为它是解决较复杂问题的强有力的工具。在下列关于递归算法的说法中，正确的是（ ）。
{{ select(12) }}
- 在 1977 年前后形成标准的计算机高级语言 FORTRAN77 禁止在程序使用递归，原因之一是该方法可能会占用更多的内存空间
- 和非递归算法相比，解决同一个问题，递归算法一般运行得更快一些
- 对于较复杂的问题，用递归方式编程一般比非递归方式更难一些
- 对于已经定义好的标准数学函数 sin(x)，应用程序中的语句“y=sin(sin(x));”就是一种递归调用
本题共 1.5 分
- 一个无法靠自身的控制终止的循环成为“死循环”，例如，在 C++ 语言程序中，语句
while(1) printf("*");就是一个死循环，运行时它将无休止地打印*号。下面关于死循环的说法中，只有（ ）是正确的。
{{ select(13) }}
- 不存在一种算法，对任何一个程序及相应的输入数据，都可以判断是否会出现死循环，因而，任何编译系统都不做死循环检查
- 有些编译系统可以检测出死循环
- 死循环属于语法错误，既然编译系统能检查各种语法错误，当然也应该能检查出死循环
- 死循环与多进程中出现的“死锁”差不多，而死锁是可以检测的，因而，死循环也可以检测的
本题共 1.5 分
- 在 C++ 语言中,表达式
23|2^5的值是( )
{{ select(14) }}
- 18
- 1
- 23
- 32
本题共 1.5 分
- 在 C++ 语言中,判断 a 等于 0 或 b 等于 0 或c 等于 0 的正确的条件表达式是（ ）。
{{ select(15) }}
!((a!=0)||(b!=0)||(c!=0))!((a!=0)&&(b!=0)&&(c!=0))!(a==0&&b==0)||(c!=0)(a=0)&&(b=0)&&(c=0)
本题共 1.5 分
- 地面上有标号为 A、B、C 的三根柱，在 A 柱上放有 10个直径相同中间有孔的圆盘，从上到下依次编号为 1,2,3…，将 A 柱上的部分盘子经过 B 柱移入 C 柱，也可以在 B 柱上暂存。如果 B 柱上的操作记录为“进、进、出、进、进、出、出、进、进、出、进、出、出”。那么，在 C 柱上，从下到上的编号为（ ）。
{{ select(16) }}
- 2 4 3 6 5 7
- 2 4 1 2 5 7
- 2 4 3 1 7 6
- 2 4 3 6 7 5
本题共 1.5 分
- 与十进制数 1770 对应的八进制数是（ ）。
{{ select(17) }}
- 3350
- 3351
- 3352
- 3540
本题共 1.5 分
- 设
A=B=True，C=D=False，以下逻辑运算表达式值为假的有（ ）。
{{ select(18) }}
- (﹁A∧B)∨(C∧D∨A)
- ﹁(((A∧B)∨C)∧D)
- A∧(B∨C∨D)∨D
- (A∧(D∨C))∧B
本题共 1.5 分
- 的结果是（ ）。
{{ select(19) }}
本题共 1.5 分
- 已知 7 个节点的二叉树的先根遍历是1 2 4 5 6 3 7（数字为节点的编号，以下同），中根遍历是 4 2 6 5 1 7 3，则该二叉树的后根遍历是（ ）。
{{ select(20) }}
- 4 6 5 2 7 3 1
- 4 6 5 2 1 3 7
- 4 2 3 1 5 4 7
- 4 6 5 3 1 7 2
本题共 1.5 分
二、填空题
- （子集划分）将 𝑛个数 (1,2,…,𝑛)划分成 𝑟个子集。每个数都恰好属于一个子集，任何两个不同的子集没有共同的数，也没有空集。将不同划分方法的总数记为 𝑆(𝑛,𝑟)。例如，𝑆(4,2)=7，这 7 种不同的划分方法依次为 {(1),(234)},{(2),(134)},{(3),(124)},{(4),(123)}，{(12),(34)},{(13),(24)},{(14),(23)}。
当 𝑛=6,𝑟=3 时，𝑆(6,3)={{ input(21) }}
（提示：先固定一个数，对于其余的 5个数考虑 𝑆(5,3)与 𝑆(5,2)，再分这两种情况对原固定的数进行分析。）
本题共 5 分
-
（最短路线）某城市的街道是一个很规整的矩形网络（见下图），有 7 条南北向的纵街，5 条东西向的横街。现要从西南角的 A 走到东北角的 B ，最短的走法共有多少种？
{{ input(22) }}
本题共 5 分
- 看程序写结果：
#include<stdio.h>
int main()
{
int i, p[5], a, b, c, x, y = 20;
for ( i = 0; i <= 4; i++ )
scanf( "%d", &p[i] );
a = (p[0] + p[1]) + (p[2] + p[3] + p[4]) / 7;
b = p[0] + p[1] / ( (p[2] + p[3]) / p[4]);
c = p[0] * p[1] / p[2];
x = a + b - p[(p[3] + 3) % 4];
if ( x > 10 )
y += (b * 100 - a) / (p[p[4] % 3] * 5);
else
y += 20 + (b * 100 - c) / (p[p[4] % 3] * 5);
printf( "%d,%d\n", x, y );
return(0);
}
//注：本例中，给定的输入数据可以避免分母为 0 或数组元素下标越界。
输入：6 6 5 5 3
输出：{{ input(23) }}
本题共 8 分
- 看程序写结果：
#include<stdio.h>
void fun( int *a, int *b )
{
int *k;
k = a; a = b; b = k;
}
int main()
{
int a = 3, b = 6, *x = &a, *y = &b;
fun( x, y );
printf( "%d,%d ", a, b );
}
输出：{{ input(24) }}
本题共 8 分
看程序写结果：
#include "math.h"
#include "stdio.h"
int main()
{
int a1[51] = { 0 };
int i, j, t, t2, n = 50;
for ( i = 2; i <= sqrt( n ); i++ )
if ( a1[i] == 0 )
{
t2 = n / i;
for ( j = 2; j <= t2; j++ )
a1[i * j] = 1;
}
t = 0;
for ( i = 2; i <= n; i++ )
if ( a1[i] == 0 )
{
printf( "%4d", i ); t++;
if ( t % 10 == 0 )
printf( "\n" );
}
printf( "\n" );
}
- 每行四分
{{ input(25) }}
- 每行四分
{{ input(26) }}
本题共 8 分
- 看程序写结果：
#include "ctype.h"
#include "stdio.h"
void expand( char s1[], char s2[] )
{
int i, j, a, b, c;
j = 0;
for ( i = 0; (c = s1[i]) != '\0'; i++ )
if ( c == '-' )
{
a = s1[i - 1]; b = s1[i + 1];
if ( isalpha( a ) && isalpha( b ) || isdigit( a ) && isdigit( b ) )
/*函数 isalpha(a) 用于判断字符 a 是否为字母，isdigit(b) 用于判断字符 b 是否为数字,如果是,返回 1，否则返回 0 */
{
j--;
do
s2[j++] = a++;
while ( tolower( a ) < tolower( s1[i + 1] ) );
}
/*函数 tolower(a) 的功能是当字符 a 是大写字母,改为小写,其余情况不变*/
else s2[j++] = c;
}else s2[j++] = c;
s2[j] = '\0';
}
int main()
{
char s1[100], s2[300];
printf( "input s1:" );
gets( s1 );
expand( s1, s2 );
printf( "%s\n", s2 );
}
输入：wer2345d-h454-82qqq
输出：{{ input(27) }}
本题共 8 分
三、完善程序
完善程序1:
（求字符的逆序）下面的程序的功能是输入若干行字符串，每输入一行，就按逆序输出该行，最后键入 −1终止程序。请将程序补充完整。
#include <iostream.h>
#include <string.h>
int maxline = 200, kz;
int reverse( char s[] )
{
int i, j, t;
for ( i = 0, j = strlen( s ) - 1; i < j; 【①】 , 【②】 )
{
t = s[i]; s[i] = s[j]; s[j] = t;
}
return(0);
}
int main()
{
char line[100];
cout << "continue? -1 for end." <<endl;
cin>>kz;
while(【③】)
{
cin >> line;
【④】;
cout << line << endl;
cout << "continue ? -1 for end." << endl;
cin >> kz;
}
}
- ①填入(答案写法有多种，选一种即可，判题系统判错请忽略)：{{ input(28) }}
- ②(答案写法有多种，选一种即可，判题系统判错请忽略)填入：{{ input(29) }}
- ③填入：{{ input(30) }}
- ④填入：{{ input(31) }}
本题共 8 分
完善程序2：
（棋盘覆盖问题）在一个 个方格组成的棋盘中恰有一个方格与其它方格不同（图中标记为 −1 的方格），称之为特殊方格。现 L 型（占 3 个小方格）纸片覆盖棋盘上除特殊方格的所有部分，各纸片不得重叠，于是，用到的纸片数恰好是 。在下表给出的一个覆盖方案中，𝑘=2，相同的 3各数字构成一个纸片。下面给出的程序使用分治法设计的，将棋盘一分为四，依次处理左上角、右上角、左下角、右下角，递归进行。请将程序补充完整。
2 2 3 3
2 -1 1 3
4 1 1 5
4 4 5 5
#include <iostream.h>
#include <iomanip.h>
int board[65][65], tile; /* tile为纸片编号 */
void chessboard( int tr, int tc, int dr, int dc, int size )
/* dr,dc依次为特殊方格的行、列号 */
{
int t, s;
if ( size == 1 )
① ;
t = tile++;
s = size / 2;
if ( ② )
chessboard( tr, tc, dr, dc, s );
else{
board[tr + s -1][tc + s -1] = t;
[③];
}
if ( dr < tr + s && dc >= tc + s )
chessboard( tr, tc + s, dr, dc, s );
else{
board[tr + s -1][tc + s] = t;
④;
}
if ( dr >= tr + s && dc < tc + s )
chessboard( tr + s, tc, dr, dc, s );
else{
board[tr + s][tc + s -1] = t;
[⑤];
}
if ( dr >= tr + s && dc >= tc + s )
chessboard( tr + s, tc + s, dr, dc, s );
else{ board[tr + s][tc + s] = t;
[⑥]; }
}
void prtl( int b[][65], int n )
{
int i, j;
for ( i =1; i <= n; i++ )
{
for ( j =1; j <= n; j++ )
cout << setw( 3 ) << b[i][j];
cout << endl;
}
}
void main()
{
int size, dr, dc;
cout << "input size(4/8/16/64):" << endl;
cin >> size;
cout << "input the position of special block(x,y):" << endl;
cin >> dr >> dc;
board[dr][dc] = -1;
tile++;
chessboard( 1, 1, dr, dc, size );
prtl( board, size );
}
- ①填入：{{ input(32) }}
- ②填入(答案写法有多种，选一种即可，判题系统判错请忽略)：{{ input(33) }}
- ③填入：{{ input(34) }}
- ④填入：{{ input(35) }}
- ⑤填入：{{ input(36) }}
- ⑥填入：{{ input(37) }}
本题共 18 分