Dotcpp  >  试卷列表  >  NOIP第十四届全国青少年信息学奥林匹克联赛初赛试题[2008提高组]

NOIP第十四届全国青少年信息学奥林匹克联赛初赛试题[2008提高组]

自由练习

模拟考试

我的成绩

第1题

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

共 1.5 分　

第2题

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

共 1.5 分　

第3题

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

共 1.5 分　

第4题

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

共 1.5 分　

第5题

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

共 1.5 分　

第6题

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

共 1.5 分　

第7题

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

共 1.5 分　

第8题

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

共 1.5 分　

第9题

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

共 1.5 分　

第10题

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

共 1.5 分　

第11题

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


共 1.5 分　

第12题

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


共 1.5 分　

第13题

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


共 1.5 分　

第14题

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


共 1.5 分　

第15题

(2008) 10 + (5B) 16 的结果是（ ）。


共 1.5 分　

第16题

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


共 1.5 分　

第17题

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


共 1.5 分　

第18题

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


共 1.5 分　

第19题

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


共 1.5 分　

第20题

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


共 1.5 分　

第21题

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

Snipaste_2021-01-18_15-42-21.png

共 5 分　

第22题

书架上有 21 本书，编号从 1 到 21 ，从其中选 4 本，其中每两本的编号都不相邻的 选法一共有 ______ 种。

共 5 分　

第23题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<stdio.h>
int main()
{
  int i, a, b, c, d, f[4];
  for(i = 0; i < 4; i++)
   scanf("%d", &f[i]);
  a = f[0] + f[1] + f[2] + f[3];
  a = a / f[0];
  b = f[0] + f[2] + f[3];
  b = b / a;
  c = (b * f[1] + a) / f[2];
  d = f[(b / c ) % 4];
  if(f[(a + b + c + d) % 4] > f[2])
    printf("%d\n", a + b);
  else
    printf("%d\n", c + d);
  return 0;
}

输入： 9 19 29 39 

输出： _______________

共 8 分　

第24题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<stdio.h>
void foo(int a, int b, int c)
{
  if(a > b) 
   foo(c, a, b);
  else
   printf("%d,%d,%d\n", a, b, c);
}
int main()
{
  int a, b, c;
  scanf("%d %d %d", &a, &b, &c);
  foo(a, b, c);
  return 0;
}

输入： 2 1 3 

输出 :__________

共 8 分　

第25题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<stdio.h>
void f(int a, int b, int c)
{
  printf("%d%d%d/", a, b, c);
  if(a == 3 && b == 2 && c == 1)
return;
  if(b < c)
    f(a, c, b);
  else if(a < b)
  {
    if(a < c)
      f(c, a, b);
    else
      f(b, c, a);
  }
}
int main()
{
  int a, b, c;
  scanf("%d %d %d", &a, &b, &c);
  f(a, b, c);
  printf("\n");
  return 0; 
}

输入 : 1 3 2 

输出： ________________________

共 8 分　

第26题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <stdio.h>
#include <string.h>
int i,j,len;
char s[50];
int main()
{
  scanf("%s", s);
  len = strlen(s);
  for (i = 0;i < len; ++i)
  {
     if (s[i] >= 'A' && s[i] <= 'Z') s[i] -= 'A' - 'a';
  }
  for (i = 0;i < len; ++i)
  {
     if (s[i] < 'x') s[i] += 3; else s[i] += -23;
  }
  printf("%s/", s);
  for (j = 1;j < 4;j ++)
  {
     for (i = 0;i < len-j; i = i + j)
     {
        s[i] = s[i + j] ;
     }   
  }
  printf("%s\n", s);
  return 0;
}

输入： ABCDEFGuvwxyz 

输出： __________________________

共 8 分　

第27题

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <stdlib.h>
#include <stdio.h>
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 ++)
   scanf("%d", &a[i]);
  scanf("%d", &n);
  ans = FindKth(1,m,n);
  printf("%d\n", 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 所在的行列（注意：输入数据保证矩阵中的数各不相同） 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <stdio.h>
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;
  scanf( "%d", &n );
  for (i = 1;i <= n;i ++)
  for (j = 1;j <= n;j ++)
  scanf( "%d", &a[i][j]);
  scanf( "%d", &k );
  FindKPosition();
  printf("%d %d\n", answerx, answery);
  return 0;
}


共 10 分　

试卷信息

题量: 28 道
总分: 100 分 
一、 单项选择题 （1-10 共 10 题） ；
二、 不定项选择题 （11-20 共 10 题）；
三．问题求解（21-22 共 2 题）；
四．阅读程序写结果（23-26 共 4 题）。
第1题 第2题 第3题 第4题 第5题 第6题 第7题 第8题 第9题 第10题 第11题 第12题 第13题 第14题 第15题 第16题 第17题 第18题 第19题 第20题 第21题 第22题 第23题 第24题 第25题 第26题 第27题 第28题