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

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

自由练习

模拟考试

我的成绩

第1题

关于图灵机下面的说法哪个是正确的：

共 1.5 分　

第2题

关于 BIOS下面的说法哪个是正确的：

共 1.5 分　

第3题

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

共 1.5 分　

第4题

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

共 1.5 分　

第5题

一个包含 n 个分支结点（非叶结点）的非空满 k 叉树， k>=1，它的叶结点数目为：

共 1.5 分　

第6题

表达式 a*(b+c)-d 的后缀表达式是：

共 1.5 分　

第7题

最优前缀编码，也称 Huffman 编码。这种编码组合的特点是对于较频繁使用的元素给与较 短的唯一编码，以提高通讯的效率。下面编码组合哪一组不是合法的前缀编码。

共 1.5 分　

第8题

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

共 1.5 分　

第9题

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

Snipaste_2021-01-17_23-06-37.png

共 1.5 分　

第10题

全国信息学奥林匹克的官方网站为参与信息学竞赛的老师同学们提供相关的信息和资源， 请问全国信息学奥林匹克官方网站的网址是：

共 1.5 分　

第11题

关于 CPU下面哪些说法是正确的：


共 1.5 分　

第12题

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


共 1.5 分　

第13题

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


共 1.5 分　

第14题

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


共 1.5 分　

第15题

关于 HTML下面哪些说法是正确的：


共 1.5 分　

第16题

若 3 个顶点的无权图 G的邻接矩阵用数组存储为 {{0 ，1，1}，{1，0，1}，{0 ，1，0}} ， 假定在具体存储中顶点依次为 : v 1，v2，v3。关于该图，下面的说法哪些是正确的：


共 1.5 分　

第17题

在带尾指针（链表指针 clist 指向尾结点）的非空循环单链表中每个结点都以 next 字段 的指针指向下一个节点。假定其中已经有 2 个以上的结点。下面哪些说法是正确的：


共 1.5 分　

第18题

散列表的地址区间为 0-10, 散列函数为 H(K)=K mod 11。采用开地址法的线性探查法处理 冲突，并将关键字序列 26，25，72，38，8，18，59存储到散列表中，这些元素存入散列 表的顺序并不确定。假定之前散列表为空，则元素 59 存放在散列表中的可能地址有：


共 1.5 分　

第19题

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


共 1.5 分　

第20题

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


共 1.5 分　

第21题

拓扑排序是指将有向无 环图 G中的所有顶点排成一个线性序列，使得图中任意一对顶 点 u 和 v，若 ∈E(G)，则 u 在线性序列中出现在 v 之前，这样的线性序列成为拓扑序 列。如下的有向无环图，对其顶点做拓扑排序，则所有可能的拓扑序列的个数为 ______。

Snipaste_2021-01-18_00-02-58.png

共 5 分　

第22题

某个国家的钱币面值有 1, 7, 7 2, 7 3共计四种，如果要用现金付清 10015元的货物， 假设买卖双方各种钱币的数量无限且允许找零，那么交易过程中至少需要流通______张钱 币。

共 5 分　

第23题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;
int a,b;
int work(int a,int b)
{
    if (a%b)
    return work(b,a%b);
    return b;
}
int main()
{
    cin >> a >> b;
    cout << work(a,b) << endl;
    return 0;
}

输入： 123 321 

输出： _________

共 8 分　

第24题

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 <iostream>
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 

输出： _________

共 8 分　

第25题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
const int maxn=50;
const int y=2009;
int main()
{
    int n,c[maxn][maxn],i,j,s=0;
    cin >> n; 
    c[0][0]=1;
    for(i=1;i<=n;i++)
    {
        c[i][0]=1;
        for(j=1;j<i;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 << endl;
    return 0;
}

输入： 17 

输出:_______

共 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
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
using namespace std;
int main()
{
    int n,m,i,j,p,k;
    int a[100],b[100];
    cin >> n >> m;
    a[0]=n;
    i=0;
    p=0;
    k=0;
    do
    {
        for (j=0;j<i;j++)
        if (a[i]==a[j])
        {
            p=1;
            k=j;
            break;
        }
        if (p)
        break;
        b[i]=a[i]/m;
        a[i+1]=a[i]%m*10;
        i++;
    }while (a[i]!=0);
    cout << b[0] << ".";
    for (j=1; j<k; j++)
    cout << b[j];
    if (p)
        cout << "(";
    for (j=k;j<i;j++)
    cout << b[j];
    if (p)
    cout << ")";
    cout << endl; 
    return 0;
}

输入： 5 13 

输出： _________

共 8 分　

第27题

（最大连续子段和） 给出一个数列（元素个数不多于 100），数列元素均为负整数、正 整数、0。请找出数列中的一个连续子数列，使得这个子数列中包含的所有元素之和最大，在 和最大的前提下还要求该子数列包含的元素个数最多，并输出这个最大和以及该连续子数列 中元素的个数。例如数列为 4，-5，3，2，4 时，输出 9 和 3；数列为 1 2 3 -5 0 7 8 时， 输出 16和 7。

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
#include <iostream>
using namespace std;
int a[101];
int n,i,ans,len,tmp,beg,end;
int main()
{
    cin >> n;
    for (i=1;i<=n;i++)
    cin >> a[i];
    tmp=0;
    ans=0;
    len=0;
    beg= ① ;
    for (i=1;i<=n;i++)
    {
        if (tmp+a[i]>ans)
        {
        ans=tmp+a[i];
        len=i-beg;
        }
        else if ( ② &&i-beg>len)
        len=i-beg;
        if (tmp+a[i] ③ )
        {
        beg= ④ ;
        tmp=0;
        }
        else
        ⑤ ;
    }
    cout << ans << " " << len << endl; 
    return 0;
}


共 10 分　

第28题

( 寻找等差数列 ) 有一些长度相等的等差数列（数列中每个数都为 0~59 的整数），设 长度均为 L，将等差数列中的所有数打乱顺序放在一起。现在给你这些打乱后的数，问原先， L 最大可能为多大？先读入一个数 n（1<=n<=60），再读入 n 个数，代表打乱后的数。输出等 差数列最大可能长度 L。

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
using namespace std;
int hash[60];
int n, x, ans, maxnum;
int work(int now) 
{
    int first, second, delta, i;
    int ok;
    while ( ① && !hash[now])
    ++now;
    if (now > maxnum)
        return 1;
    first = now;
    for (second = first; second <= maxnum; second++)
    if (hash[second]) 
    {
        delta = ② ;
        if (first + delta * ③ > maxnum)
        break;
        if (delta == 0)
            ok = ( ④ );
        else{
        ok = 1;
        for (i = 0; i < ans; i++) 
        ok = ⑤ && (hash[first+delta*i]);
        } 
        if (ok)
        {
            for (i = 0; i < ans; i++)
            hash[first+delta*i]--;
            if (work(first))
            return 1;
            for (i = 0; i < ans; i++)
            hash[first+delta*i]++;
        }
    }
    return 0;
}
int main()
{ 
    int i;
    memset(hash, 0, sizeof(hash));
    cin >> n;
    maxnum = 0;
    for (i = 0; i < n; i++){
        cin >> x;
        hash[x]++;
        if (x > maxnum)
        maxnum = x;
    }
    for (ans = n; ans >= 1; ans--)
    if ( n%ans==0 && ⑥ ) {
        cout << ans << endl;
        break;
    }
    return 0;
}


共 18 分　

试卷信息

题量: 28 道
总分: 100 分 
一． 单项选择题 （1-10 共 10 题 ）；
二． 不定项选择题 （11-20 共 10 题） ；
三．问题求解（21-22 共 2题）；
四．阅读程序写结果（23-26 共 4 题）；
五.   完善程序题（27-28共 2 题）。
第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题