【真题】暑假备战CSP-J/S：NOIP2008提高组初赛(第一轮)试题及参考答案(PDF版、无水印可直接打印)

小码匠

发布于 2023-08-31 14:55:59

3450

发布于 2023-08-31 14:55:59

文章被收录于专栏：小码匠和老码农

资料下载

公众号内回复【NOIP2008S】即可获取下载链接，直接打印电子版让孩子做即可，文件包含

试题真题
参考答案

第 1 题

在以下各项中，（）不是操作系统软件。

A. Solaris
B. Linux
C. Sybase
D. Windows Vista
E. Symbian

本题共 1.5 分

第 2 题

微型计算机中，控制器的基本功能是（）。

A. 控制机器各个部件协调工作
B. 实现算术运算和逻辑运算
C. 存储各种控制信息
D. 获取外部信息 E. 存放程序和数据

本题共 1.5 分

第 3 题

设字符串S=Olympic，S的非空子串的数目是（）。

A. 29
B. 28
C. 16
D. 17
E. 7

本题共 1.5 分

第 4 题

完全二叉树共有2*N-1个结点，则它的叶节点数是（）。

A. N-1
B. 2*N
C. N
D. 2N-1
E. N/2

本题共 1.5 分

第 5 题

将数组{8, 23, 4, 16, 77, -5, 53, 100}中的元素按从大到小的顺序排列，每次可以交换任意两个元素，最少需要交换（）次。

A. 4
B. 5
C. 6
D. 7
E. 8

本题共 1.5 分

第 6 题

设栈S的初始状态为空，元素a，b，c，d，e，f依次入栈S，出栈的序列为b，d，c，f，e，a，则栈S的容量至少应该是（）。

A. 6
B. 5
C. 4
D. 3
E. 2

本题共 1.5 分

第 7 题

与十进制数28.5625相等的四进制数是（）。

A. 123.21
B. 131.22
C. 130.22
D. 130.21
E. 130.20

本题共 1.5 分

第 8 题

递归过程或函数调用时，处理参数和返回地址，通常使用一种称为（）的数据结构。

A. 队列
B. 多维数组
C. 线性表
D. 链表
E. 栈

本题共 1.5 分

第 9 题

TCP/IP是一组构成互联网基础的网络协议，字面上包括两组协议：传输控制协议（TCP）和网际协议（IP）。TCP/IP 协议把Internet网络系统描述成具有四个层次功能的网络模型,其中提供源节点和目的节点之间的信息传输服务，包括寻址和路由器选择等功能的是（）。

A. 链路层
B. 网络层
C. 传输层
D. 应用层
E. 会话层

本题共 1.5 分

第 10 题

对有序数组{5, 13, 19, 21, 37, 56, 64, 75, 88, 92, 100}进行二分查找，等概率的情况下查找成功的平均查找长度（平均比较次数）是（）。

A. 35/11
B. 34/11
C. 33/11
D. 32/11
E. 34/10

本题共 1.5 分

第 11 题(多选题)

在下列关于图灵奖的说法中，正确的有（）。

A. 图灵奖是美国计算机协会于1966年设立的，专门奖励那些对计算机事业作出重要贡献的个人
B. 图灵奖有“计算机界诺贝尔奖”之称
C. 迄今为止，还没有华裔计算机科学家获此殊荣
D. 图灵奖的名称取自计算机科学的先驱、英国科学家阿兰·图灵

本题共 1.5 分

第 12 题(多选题)

计算机在工作过程中，若突然停电，（）中的信息不会丢失。

A. 硬盘
B. CPU
C. ROM
D. RAM

本题共 1.5 分

第 13 题(多选题)

设A=true，B=false，C=true，D=false，以下逻辑运算表达式值为真的有（）。

A. (A∧B)∨(C∧D∨A)
B. ((A∧B)∨C)∧D
C. (B∨C∨D)∨D∧A
D. A∧(D∨C)∧B

本题共 1.5 分

第 14 题(多选题)

Web2.0是近年来互联网的热门概念之一，其核心思想是互动与分享。下列网站中，（）是典型的Web2.0应用。

A. Sina
B. Flickr
C. Yahoo
D. Google

本题共 1.5 分

第 15 题(多选题)

(2008)_{10} + (5B)_{16}

的结果是（）。

(833)_{16}

(2099)_{10}

(4063)_{8}

(100001100011)_{2}

本题共 1.5 分

第 16 题(多选题)

二叉树T，已知其先根遍历是1 2 4 3 5 7 6（数字为结点的编号，以下同），后根遍历是4 2 7 5 6 3 1，则该二叉树的可能的中根遍历是（）。

A. 4 2 1 7 5 3 6
B. 2 4 1 7 5 3 6
C. 4 2 1 7 5 6 3
D. 2 4 1 5 7 3 6

本题共 1.5 分

第 17 题(多选题)

面向对象程序设计（Object-Oriented Programming）是一种程序设计的方法论，它将对象作为程序的基本单元，将数据和程序封装在对象中，以提高软件的重用性、灵活性和扩展性。下面关于面向对象程序设计的说法中，正确的是（）。

A. 面向对象程序设计通常采用自顶向下设计方法进行设计。
B. 面向对象程序设计方法具有继承性（inheritance）、封装性（encapsulation）、多态性（polymorphism）等几大特点。
C. 支持面向对象特性的语言称为面向对象的编程语言，目前较为流行的有C++、JAVA、C#等。
D. 面向对象的程序设计的雏形来自于Simula语言，后来在SmallTalk语言的完善和标准化的过程中得到更多的扩展和对以前思想的重新注解。至今，SmallTalk语言仍然被视为面向对象语言的基础。

本题共 1.5 分

第 18 题(多选题)

设T是一棵有n个顶点的树，下列说法正确的是（）。

A. T是连通的、无环的
B. T是连通的，有n-1条边
C. T是无环的，有n-1条边
D. 以上都不对

本题共 1.5 分

第 19 题(多选题)

NOIP竞赛推荐使用的语言环境有（）。

A. Dev-C++
B. Visual C++
C. free pascal
D. Lazarus

本题共 1.5 分

第 20 题(多选题)

在下列防火墙（firewall）的说法中，正确的有（）。

A. 防火墙是一项协助确保信息安全的设备，其会依照特定的规则，允许或是限制数据通过
B. 防火墙可能是一台专属的硬件或是安装在一般硬件上的一套软件
C. 网络层防火墙可以视为一种 IP 数据包过滤器，只允许符合特定规则的数据包通过，其余的一概禁止穿越防火墙
D. 应用层防火墙是在 TCP/IP的“应用层”上工作，可以拦截进出某应用程序的所有数据包

本题共 1.5 分

第 21 题

有6个城市，任何两个城市之间都有一条道路连接，6个城市两两之间的距离如下表所示，则城市1到城市6的最短距离为_____________。

	城市1	城市2	城市3	城市4	城市5	城市6
城市1	0	2	3	1	12	15
城市2	2	0	2	5	3	12
城市3	3	2	0	3	6	5
城市4	1	5	3	0	7	9
城市5	12	3	6	7	0	2
城市6	15	12	5	9	2	0

答案：

本题共 5 分

(找第k大的数) 给定一个长度为1,000,000的无序正整数序列，以及另一个数n( 1<= n <= 1000000)，接下来以类似快速排序的方法找到序列中第n大的数（关于第n大的数：例如序列{1，2，3，4，5，6}中第3大的数是4）。

#include <iostream>
using namespace std;

int a[1000001],n,ans = -1;
void swap(int &a,int &b)
{
    int c;
    c = a; a = b;    b = c;
}

int FindKth(int left, int right, int n)
{
    int tmp,value,i,j;
    if (left == right) return left;
    tmp = rand()% (right - left) + left;
    swap(a[tmp],a[left]);
    value =       ①         
    i = left;
    j = right;
    while (i < j)
    {
        while (i < j &&       ②       ) j --;
        if (i < j) {a[i] = a[j]; i ++;} else break;
        while (i < j &&        ③        ) i ++;
        if (i < j) {a[j] = a[i]; j --;} else break;
    }
        ④         
    if (i < n) return  FindKth(     ⑤      );
    if (i > n) return      ⑥                    
    return i;
}

int main()
{
    int i;
    int m = 1000000;
    for (i = 1;i <= m;i ++)
        cin >> a[i];
    cin >> n;
    ans = FindKth(1,m,n);
    cout << a[ans];
     return 0;
}

①答案：
②答案：
③答案：
④答案：
⑤答案：
⑥答案：

本题共 18 分

第 28 题

（矩阵中的数字）有一个n*n(1<=n<=5000)的矩阵a，对于1<=i < n,1<=j<=n, a[i,j] < a[i + 1,j] a[j,i] < a[j,i+1]。即矩阵中左右相邻的两个元素，右边的元素一定比左边的大。上下相邻的两个元素，下面的元素一定比上面的大。给定矩阵a中的一个数字k，找出k所在的行列（注意：输入数据保证矩阵中的数各不相同）。

#include <iostream>
using namespace std;
int n,k,answerx,answery;
int a[5001][5001];
void FindKPosition()
{
	int i = n,j = n;
	while (j > 0)
	{
		if (a[n][j] < k) break;               
		j --;
	}
        ①        
	while (a[i][j] != k)
	{
		while (              ②              && i > 1) i --;
		while (              ③              && j <= n) j ++;
	}
	              ④             
	              ⑤             
}

int main()
{
	int i,j;
	cin >> n;
	for (i = 1;i <= n;i ++)
		for (j = 1;j <= n;j ++)
			cin >> a[i][j];
	cin >> k;
	FindKPosition();
	cout << answerx << " " << answery << endl;
     return 0;
}