NOIP2011初赛提高组(C++) 错题集

单选

1. 字符‘A’的ASCII码为十六进制41，则字符‘Z’的ASCII码为十六进制的（5A）

注意，为十六进制！！我就是没看见十六进制选错了。

1. 寄存器是（CPU）的重要组成部分。

2. 应用快排的分治思想，求第K大的数，理论上的最低的时间复杂度为：O(n)

3. 每个同学按照顺序来到操场按照高到矮的顺序站成一排，每个人都从排尾走向排头，找到第一个比自己高的，并站在他的后面。这种站队方法类似于（插入排序）、

不定项选择

1. 如果根节点的深度记为1，则一棵恰好有2011个叶子结点的二叉树的深度可能是（12 2011）

解析：首先，是二叉树，没有强调是不是满二叉树。而对于一棵满二叉树，深度为11的那一层有1024个节点，深度为12的那一层有2048个节点，符合2011个叶子节点的需求，所以深度最小是12。而深度最大的情况则是每一层只有两个节点，一个为叶子节点，一个为非叶子节点（如下图），深度为2011。

1. 现有一段文言文，要通过二进制哈夫曼编码进行压缩。简单起见，假设这段文言文只由4个汉字“之”、“乎”、“者”、“也”组成，它们出现的次数分别为700、600、300、400。那么，“也”字的编码长度可能是(2 3)。

   有两棵哈夫曼树，如下图

阅读程序

8#include <iostream>
#include <algorithm>
#include <cstring>

#define SIZE 10000
#define LENGTH 10

using namespace std;

int n, m, a[SIZE][LENGTH];

int h(int u, int v)
{
    int i, ans;
    ans = 0;

    for(i = 1 ; i <= n ; i ++ )
        if(a[u][i] != a[v][i]) ans ++ ;

    return ans;
}

int main()
{
    int sum, i, j;
    scanf("%d", &n);
    memset(a, 0, sizeof a);
    m = 1;

    while(1)
    {
        i = 1;
        while((i <= n) && (a[m][i] == 1)) i ++ ;
        if(i > n) break;

        m ++ ;
        a[m][i] = 1;
        for(j = i + 1 ; j <= n ; j ++ )
            a[m][j] = a[m - 1][j];
    }

    sum = 0;
    for(i = 1 ; i <= m ; i ++ )
        for(j = 1 ; j <= m ; j ++ )
            sum += h(i, j);

    printf("%d\n", sum);

    return 0;
}

输入：7
答案：57344
解析：
手动模拟易得，a[x]记录的是十进制数字x - 1的二进制表示的倒序，如下表：
a[1]: 0 0 0 0 0 0 0
a[2]: 1 0 0 0 0 0 0
a[3]: 0 1 0 0 0 0 0
…
a[127]: 0 1 1 1 1 1 1
a[128]: 1 1 1 1 1 1 1

观察发现，对于第 i 位，这128个数的二进制表示共有64个0和64个1，所以在128个数中任选两个，对于每一位数，都有128*64种不同的情况（128是共有128个数，而选择了一个数后必定知道它是0还是1，所以下一个数只能选非0或非1的数，也就是64个）。所以，对于七位二进制数，总共有7 * 128 * 64个数不同，答案是57344。