一）单项选择題：
1)俺国的顶级域名，有点含糊，它实际上有两个.cn 和 .com.cn，这里的标准答案不如说是排除法，选(A)

2)2.二进制数11 1011 1001 0111和01 0110 1110 1011进行逻辑与运算的结果是（）。
A. 01 0010 1000 1011 B. 01 0010 1001 0011
C. 01 0010 1000 0001 D. 01 0010 1000 0011
这个不说了，答案就是解析；选（D）

3).一个32位整型变量占用（）个字节。
A. 32 B. 128 C. 4  D. 8
正确答案： C
解析：一个字节是8位，32位整型变量，占用４个字节，选（C）

4).若有如下程序段，其中s、a、b、c均已定义为整型变量,且a、c均已赋值（c大于0）
s = a;
for （b = 1; b <= c; b++） s = s - 1;
则与上述程序段功能等价的赋值语句是（）
A. s = a - c; B. s = a - b;
C. s = s - c; D. s = b - c;
答案:A

5).设有100个已排好序的数据元素，采用折半查找时，最大比较次数为（）
A. 7 B. 10 C. 6 D. 8
正确答案： A   
答案x, 2^6 < x < 2^7

6)链表不具有的特点是（）
A. 插入删除不需要移动元素 B. 不必事先估计存储空间
C. 所需空间与线性表长度成正比 D. 可随机访问任一元素
正确答案： 也是原版照搬的老題目，答案(D)

7).把8个同样的球放在5个同样的袋子里，允许有的袋子空着不放，问共有多少种不同的分法？（）
提示：如果8个球都放在一个袋子里，无论是哪个袋子，都只算同一种分法。
A. 22 B. 24 C. 18 D. 20
其实就是放苹果，f(8,5)是多少？答案(C)

8).一棵二叉树如右图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点（根结点的下标为1,若某结点的下标为i ,则其左孩子位于下标2i处、右孩子位于下标2i+l处），则该数组的最大下标至少为（）。
A. 6 B. 10 C. 15 D. 12
完全二叉树的老題目，一个字没改，记住"左孩子=2*i,右孩子=2*i+1"，其实题面也给出答案了
答案(C)

9).100以内最大的素数是（）。
A. 89 B. 97 C. 91 D. 93
送分题。答案B

10)319和377的最大公约数是（）。
A. 27 B. 33 C. 29 D. 31
319和377的最大公约数是多少？用碾转相除法做做就知道了。答案(C)

11)
新学期开学了，小胖想减肥，健身教练给小胖制定了两个训练方案。
方案一：每次连续跑3公里可以消耗300千卡（耗时半小时）；
方案二：每次连续跑5公里可以消耗600千卡（耗时1小时）。
小胖每周周一到周四能抽出半小时跑步，周五到周日能抽出一小时跑步。
另外，教练建议小胖每周最多跑21公里，否则会损伤膝盖。
请问如果小胖想严格执行教练的训练方案，并且不想损伤膝盖，每周最多通过跑步消耗多少千卡？（）
A. 3000 B. 2500 C. 2400 D. 2520
答案(C)

12)—副纸牌除掉大小王有52张牌，四种花色，每种花色13张。
假设从这52张牌中随机抽取13张纸牌，则至少（）张牌的花色一致。
A. 4 B. 2 C. 3 D. 5
会打拱猪的都知道，答案是（A），如果从排列组合上看，为什么呢？

13)13.—些数字可以颠倒过来看，例如0、1、8颠倒过来还是本身，6颠倒过来是9, 9颠倒过来看还是6,其他数字颠倒过来都不构成数字。
类似的，一些多位数也可以颠倒过来看，比如106颠倒过来是901。假设某个城市的车牌只由5位数字组成，每一位都可以取0到9。
请问这个城市最多有多少个车牌倒过来恰好还是原来的车牌？（）
A. 60 B. 125 C. 75 D. 100
又是一題排列组合；xyzyx
答案(C)

14)假设一棵二叉树的后序遍历序列为DGJHEBIFCA,中序遍历序列为DBGEHJACIF,则其前序遍历序列为（）。
A. ABCDEFGHIJ
B. ABDEGHJCFI
C. ABDEGJHCFI
D. ABDEGHJFIC
答案（B）

15）是图灵奖(A)

二）阅读程序（与前几次的NOIP初赛，有很大不同，最的区别，需要自已组织输入数据，但是……，问的题不少，数据似乎需要不少，所以，这类题，如果不是看出它是做什么的，就先模拟一下）

1)第一题比较简单，主要是适应问答的新形式。
#include "bits/stdc++.h"
using namespace std;
char st[100];
int main(){
    scanf("%s",st);
    int n=strlen(st);
    for(int i=1;i<=n;i++){//原第8行
        if(n%i==0){
            char c=st[i-1];
            if(c>='a')
                st[i-1]=c-'a'+'A';
        }
    }
    printf("%s",st);
    return 0;
}
对错判断題：
1)输入的字符串，只能由小写字母或大写字母组成;(　　)//程序里似乎没这样说
2)若将第8行的i=1;改成i=0；程序运行出错；（　 ）//i-1的问題
3)若将第8行的i<=n;改为"i*i <=n"，程序运行结果不会改变；(  错 );
//这里不是说质因子
4)若输入的字符串全部由大写字母组成，那么输出的字符串就跟输入的字符串一样；(    )//没看出异样，应该可以

选择題：
5)若输入的字符串长度为18，那么输入的字符串与输出的字符串，至多有多少个字符不同？(问題在于“至多”，怎么定义条件？)
答案是B
6)输入的字符串长度为多少时，输入的字符串与输出的字符串相比，至多有36个字符不同？（在上述前提下，等于说，要多大的数，才有36个因数）
答数是（B）

2)第二题开始有点复杂，左左右右的不容易跟踪，还是动手模拟一下。可以先看看输入的问答要求：相同的，不同的，偶数的……，在10以内取一系列值，自已画个表格出来，模拟一下过程。这题就不会答错了。
实际上是记录两个数列之中，彼此最大的影射；
由于这题是“程序清楚，不容易想像”，自已创造比较简单的数据模拟，可以帮助自已很快看清楚。
#include "bits/stdc++.h"
using namespace std;
int n,m;
int a[100],b[100];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)a[i]=b[i]=0;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        if(a[x] < y && b[y] < x)//第13行
        {
            if(a[x] > 0) b[a[x]]=0;//第15行　旧记录复0
            if(b[y] > 0) a[b[y]]=0;//旧记录复0
            a[x]=y;    b[y]=x;//建立链记录；
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]==0) ++ans;//26行
        if(b[i]==0) ++ans;//27行
    }
    printf("%d\n",ans);
    }
假设输入的n,m都是正整数，x,y都在[1,n]范围内；
伪代码解读，似乎是一对对建立最小的链接，其他清０；
判断題
1)当m > 0时，输出的值一定小于2n。( )；//既然是计算剩下的数，应该对的
2)执行完第27行的++ans时，ans一定是偶数（　）；//不同组的x,y，有可能有一个数相同呢
3)a[i]和b[i]不可能同时大于0。( );
//这是什么意思？那俩是数组啊？可能是说，同步扫描a[]和b[],也就是问26行27行，是不是可能同时为0;这是不对称链接，不是a[i]和b[i]链接，说不通；
4)若程序执行到第13行时，x总是小于y，那么第15行不会被执行；(   )
//这是链接，跟x和y谁大谁小，没有关系；

解題同样是按照上述步骤：１）注解，２）根据題目，代入测试数据；
即便不确定伪代码解读，针对題目代入数据后，就清晰了。
问題在于，如果反复代入数据，时间可能就变得紧张了；
唯一的指望就是，代入一两次之后，对題目已经清楚了，后面不花多少时间。

选择題
5)若m个x两两不同，且m个y两两不同，则输出的值为是多少？
//代入测试数据再数，比“想它的道理”要容易；
//每个x都不同，y也不同，那么就是每一个链接都是新的；
A.2n-2m   B.2n+2    C.2n-2;   D.2n
答案A
6)若m个x两两不同，且m个y两两相同，则输出的值为是多少？
A.2n-2   B.2n    C.2m    D.2n-2m
同上。每題都想一想到透，时间未必比代进测试数据试一试短；
用测试数据，反而有重复性；
答案A

3)第三题并不比第二题复杂，但很容易先人为主，以为它是二分法。
这一題不容易代入数据，但是流程比较清楚。可以用比较小的数据代进入，再按倍数推算。
没有数据确定代入以前，看这些题，回答它的问，确实是让人有点抓瞎的。
如果乱猜的话，就很难命中了。
#include "iostream"
using namespace std;
const int maxn=10000;
int n;
int a[maxn];
int b[maxn];
int f(int l,int r,int depth){
    if(l>r) return 0;
    int min=maxn,mink;
    for(int i=l;i<=r;i++){
        if(min > a[i]){//第12行
            min=a[i];
            mink=i;
        }
    }
    int lres=f(l,mink-1,depth+1);
    int rres=f(mink+1,r,depth+1);
    return lres+rres+depth*b[mink];
}
int main(){
    cin>>n;
    for(int i=0;i < n;i++) cin>>a[i];
    for(int i=0;i < n;++i) cin>>b[i];
    cout<<f(0,n-1,1) <<endl;
    return 0;
}
这題如果不理解它是干什么的，不大好组织样例；
形状上看，它是“左右分治”的递归，有点象找根的二叉树，然后把深度×权值返回，最后结算在根节点；
1)如果a数组有重复的数字，则程序运行时会发生错误 (  )
//这是一个坑，如果把它认定是树，a[]就是树结点，树结点是不应该重复的；不过，这是数据结构的错，不是程序的错；这里问的是“程序出不出错”（如果用报错，还会明确一点），结论是不报错。虽然不明白，出題人这样想有什么意思。
2)如果b数组全为0，则输出为0;
//它的返回是与权值的乘积之和，如果全为０的话，那应该是0;

选择題：
3)当n=100时，最坏情况下，与第12行的比较运算执行的次数大约是多少？
//最好的情况是二叉树，最坏的情况，是一条链吧？而且每个数都相同，有几千次这題涉及到数据结构的极端化，似乎象软件测试的思路，又非常极端。初次接触的话，不是那么习惯。
//这题一开始也着了坑，当二分法处理，得出下一题的结果；再做下去，就发现下一题怎么又是600?仔细看看，//原来程序里是for(int i=l;i<=r;i++)，从头数到尾。最坏的情况，就是总是最后一个才是最小值。
4)当n=100时，最好情况下，与第12行的比较运算执行的次数大约是多少？
//它是二分，最好情况下，就是统统二分，似乎前面做过一条折半查找有7次的題呢。不过且慢，这里第一次扫描就是100次：它需要左右扫描，不是折半查找；所以应该是100+2*50+4*25……==600次；
5)当n=10时，若b数组满足，对任意0<=i < n, 都有b[i]=i+1，那么输出最大是多少？
//这題麻烦了，可选答案是386,383,384,385，都挺接近，不好大约算了。
不过代进去，不难，发现答案是1*1+2*2+……
6)当n=100时，若b数组满足，对任意0<=i < n, 都有b[i]=i+1，那么输出最小是多少？
//又麻烦了。前头10可以算，难道还算这100不成？有推倒重来的感觉，考试时不容易沉住气。但是可选答案很接近，不算还不行。它实际上考考生，是不是跟二叉树混得很熟，数它严格二分时，完全二叉树样子的节点总数,把每层再乘以深度加起来。计算量不少。答案是580

三）完善程序
(1)
（矩阵变幻）有一个奇幻的矩阵，在不停地变幻，其变幻方式为：数字0变成矩阵[[0,0],[0,1]],数字１变成矩阵[[1,1],[1,0]]。最初该矩阵只有一个元素0，变幻n次后，矩阵会变成什么样？
例如：矩阵最初为:[0];矩阵变幻1次后:[[0,0],[0,1]];矩阵变幻２次后：
[[0,0,0,0],[0,1,0,0],[0,0,1,1],[0,1,1,0]].
输入一行一个不超过10的正整数n。输出变幻n次后的矩阵。
试补全程序。
提示：
"<<"表示二进制左移运算符，例如(11)2 <<2 ==(1100)2
"^"是二进制的异或运算符。

#include "cstdio"
using namespace std;
int n;
const int max_size=1<<10;
int res[max_size][max_size];
void recursive(int x,int y,int n,int t)
{
    if(n==0){
        res[x][y]=(1);
        return;
    }
    int step=1<<(n-1);
    recursive((2),     n-1,t);
    recursive(x,y+step,n-1,t);
    recursive(x+step,y,n-1,t);
    recursive( (3),    n-1,!t
}
int main(){
    scanf("%d",&n);
    recursive(0,0,(4));
    int size=(5);
    for(int i=0;i < size;++i)
    {
        for(int j=0;j < size;++j)
            printf("%d",res[i][j]);
        puts("");    
    }
    return 0;
}
这題跟往常的完成程序，相差不大了。
1)t
2)x,y
3)x+step,y+step
4)n,0
5)1<<n
其实，答案还是挺有对称性的。可以先按填充做，
然后再看看选择；这样可以减少被误导的地方。

(2)
计数排序
计数排序是一个广泛使用的排序方法。下面的程序使用双关键字计数排序，将n对10000以内的整数，从小到大排序。
例如有三对整数(3,4),(2,4),(3,3)，那么排序之后应该是(2,4),(3,3),(3,4)。
输入第一行为n，接下来n行，第i行有两个数a[i]和b[i]，分别表示第i对整数的第一关键字和第二关键字。从小到大排序后输出。
数据范围1<=n<=10^7, 1<=a[i],b[i]<=10^4
提示：应先对第二关键字排序，再对第一关键字排序。数组ord[]存储第二关键字排序的结果，数组res[]存储双关键字排序的结果。
//这段开场白，几乎就是计数排序的一份简短教程。
//如果认为“这个排序没教过，不会”，那真的没法做了。
#include "bits/stdc++.h"
using namespace std;
const int maxn=1e8;
const int max=1e4;
int n;
unsigned a[maxn],b[maxn],res[maxn],ord[maxn];
unsigned cnt[maxs+1];
int main(){
    scanf("%d",&n);
    for(int i=0;i < n;i++) scanf("%d%d",&a[i],&b[i]);
    memset(cnt,0,sizeof(cnt));
    for(int i=0;i < n;i++) (1);//利用cnt数组统计数量
    for(int i=0;i < maxs;++i) cnt[i+1] +=cnt[i];
    for(int i=0;i < n;i++) (2);//记录初步排序结果
    memset(cnt,0,sizeof(cnt));
    for(int i=0;i < n;i++) (3);//利用cnt数组统计数量；
    for(int i=0;i < maxs;i++) cnt[i+1]+=cnt[i];
    for(int i=n-1;i>=0;--i) (4);//记录最终排序结果
    for(int i=0;i < n;i++) printf("%d %d\n", (5));
    return 0;
}

这題不容易通过对称性观察。
不过说解比较详细，如果看明白，它其实是通过“桶排序”实现数的排序的话，还是不难的。
1)++cnt[b[i]]
2)ord[--cnt[b[i]]] = i
3)++cnt[a[i]]
4)res[--cnt[a[ord[i]]]] = ord[i]
5)a[res[i]],b[res[i]]