一、单项选择题(共15题，每题2分，共计30分:每题有且仅有一个正确选项)

1. 在二进制下，1011001 + （）=1100110。

{{ select(1) }}

• 1011
• 1101
• 1010
• 1111

2. 字符"0"的ASCII码为48，则字符"9"的ASCII码为（）。

{{ select(2) }}

• 39
• 57
• 120
• 视具体的计算机而定

3. 一片容量为8G的SD卡能储存大约（）张大小为2MB的数码照片。

{{ select(3) }}

• 1600
• 2000
• 4000
• 16000

4. 摩尔定律(Moore's law)是由英特尔创始人之一戈登.摩尔(Gordon Moor)提出来的。根据摩尔定律，在过去几十年一级在可预测的未来纪念，单块集成电驴的集成度大约每( )个月翻一番。

{{ select(4) }}

• 1
• 6
• 18
• 36

5. 无向完全图是图中每对顶点之间都恰好有一条边的简单图。已知无向完全图G有7个顶点，则它共有（）条边。

{{ select(5) }}

• 7
• 21
• 42
• 49

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

{{ select(6) }}

• 硬盘
• 高速缓存cash
• 内存
• 中央处理器（CPU）

7. 如果根节点的深度记为1，则一棵恰有2011个叶结点的二叉树的深度最少是（）。

{{ select(7) }}

• 10
• 11
• 12
• 13

8. 育课的铃声响了，同学们都陆续地奔向操场，按老师的要求从高到矮站成一排。每个同学校顺序来到操场时，都从排尾走到排头，找到第一个比自己高的同学，并站在他的后面。这种站队的方法类似于()算法。

{{ select(8) }}

• 快速排序
• 插入排序
• 冒泡排序
• 归并排序

9. 一个正整数在二进制下有100位，则它在十六进制下有( )位。

{{ select(9) }}

• 7
• 13
• 25
• 不能确定

10. 广度优先搜索时，需要用到的数据结构是( )。

{{ select(10) }}

• 链表
• 队列
• 栈
• 散列表

11. 在使用高级语言编写程序时，一般提到的“空间复杂度”中的“空间”是指( )。

{{ select(11) }}

• 程序运行时理论上所占的内存空间
• 程序运行时理论上所占的数组空间
• 程序运行时理论上所占的硬盘空间
• 程序源文件理论上所占的硬盘空间

12. 在含有n个元素的双向链表中查询是否存在关键字为k的元素，最坏情况下运行的时间复杂度是( )。

{{ select(12) }}

• O(1)
• O(log n)
• O(n)
• O(n log n)

13. 生物特征识别，是利用人体本身的生物特征进行身份认证的一种技术。目前，指纹识别、虹膜识别、人脸识别等技术已广泛应用于政府、银行、安全防卫等领域。一下不属于生物特征识别技术及其应用的是()。

{{ select(13) }}

• 指静脉验证
• 步态验证
• ATM机密码验证
• 声音验证

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

{{ select(14) }}

• 1
• 2
• 3
• 4

15. 关于汇编语言，下列说法错误的是()

{{ select(15) }}

• 是一种与具体硬件相关的程序设计语言
• 在编写复杂程序时，相对于高级语言而言代码量较大，且不易调试
• 可以直接反问寄存器、内存单元、以及I/O端口
• 随着高级语言的诞生，如今已完全被淘汰，不再使用

16. ()是一种选优搜索法，按选优条件向前搜索，以达到目标。当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。:

{{ select(16) }}

• 回溯法
• 枚举法
• 动态规划
• 贪心

17. 1956年( )授予肖克利、巴丁和布拉顿，以表彰他们对半导体的研究和晶体管效应的发现。

{{ select(17) }}

• 诺贝尔物理学奖
• 约翰·冯·诺依曼奖
• 图灵奖
• 高德纳奖

18. 对一个有向图而言，如果每个节点都存在到达其他任何节点的路径，那么就称它是强连通的。例如，下图就是一个强连通图。事实上，在删掉边()后，它依然是强连通的。

{{ select(18) }}

• a
• b
• c
• d

19. 从ENIAC到当前最先进的计算机，冯·诺依曼体系结构始终占有重要地位。冯诺依曼提醒结构的核心内容是( )。

{{ select(19) }}

• 采用开关电路
• 采用半导体器件
• 采用存储程序和程序控制原理
• 采用键盘输入

二、填空题 每题5分

20. 每份考卷都有一个8位二进制序列号。当且仅当一个序列号含有偶数个1时，它才是有效的。 例如，0000000、01010011都是有效的序列号，而11111110不是。那么，有效的序列号共有___个。

{{ input(20) }}

21. 定义字符串的基本操作为:出除一个字符\插入一个字特和将一个字持修改成另外一个字符这三种操作。将字符串A变成字符串B的最少操作步数，称为字符串A到字符串B的编辑距离。 字符串'ABCDEFG"到字符串“BADECG”的编辑距离为___。

（答案不要加空格，如：n=1不要写成n =1）

{{ input(21) }}

#include<iostream>
using namespace std;
int main(){
    int i,n,m,ans;
    cin>>n>>m;
    i=n;
    ans=0;
    while(i<=m){
        ans+=i;
        i++
    }
    cout<<ans<<endl;
    return 0;
}

输入:10 20 输出:_____

（答案不要加空格，如：n=1不要写成n =1）

{{ input(22) }}

#include<iostream>
#include<string>
using namespace std;
int main(){
    string map = "2223334445556667778889999";
    string tel;
    int i;
    cin >> tel;
    for(i=0;i<tel.length(); i++)
        if((tel[i]>='0') && (tel[i]<='9'))
            cout << tel[i];
        else if((tel[i]>='A') && (tel[i]<='Z'))
            cout << map[tel[i]-'A'];
    cout << endl;
    return 0:
}

输入:CCF-NOIP-2011 输出:______

（答案不要加空格，如：n=1不要写成n =1）

{{ input(23) }}

#include<iostream>
#include<cstring>
using namespace std;
const int SlZE = 100;

int main(){
    int n,i,sum,x,a[SlZE];
    cin >> n;
    memset(a,0,sizeof(a));
    for(i= 1;i<=n;i++){
        cin>>x;
        a[x]++;
    }
    i=0:
    sum=0:
    while(sum<(n/2+1)){
        i++;
        sum += a[i];
    }
    
    cout<<i<<endl;
    return 0;
}

输入: 11 4 5 6 6 4 3 3 2 3 2 1 输出:_____

（答案不要加空格，如：n=1不要写成n =1）

{{ input(24) }}

#include<iostream>
using namespace std;
int solve(int n,int m){
    int i,sum;
    if(m==1) return 1;
    sum=0;
    for(i=1;i<n;i++)
        sum += solve(i,m-1);
    return sum;
}

int main(){
    int n,m;
    cin >> n >> m;
    cout << solve(n,m) << endl;
    return 0;
}

输入:7 4 输出:_______

（答案不要加空格，如：n=1不要写成n =1）

{{ input(25) }}

三、阅读理解

1.(子矩阵)给输入一个n1m1的矩阵a，和n2m2的矩阵b，问a中是否存在子矩阵和b相等。若存在，输出所有子矩阵左上角的坐标:若不存在输出"There is no answer"。

#include<iostream>
using namespace std;
const int SlZE = 50;
int n1,m1,n2,m2,a[SIZE][SIZE],b[SIZE][SIZE];
int main(){
    int i,j,k1,k2;
    bool good,haveAns;
    
    cin>>n1>>m1;
    for(i=1;i<=n1;i++)
        for(j=1;j <= m1; j++)
            cin>>a[i][j];
    cin>>n2>>m2;
    for(i=1;i<=n2; i++)
        for(j=1;j<=m2; j++)
            __①__;
            
    haveAns = false;
    for(i=1;i<=n1-n2+1;i++)
        for(j=1;j<= __②__; j++){
            __③__;
            
            for(k1=1;k1<=n2;k1++)
                for(k2=1;k2<=__④__;k2++){
                    if(a[i+k1-1][j+k2-1]!=b[k1][k2])
                        good=false:
                }
            if(good){
                cout<<i<<' '<<j<<endl;
                __⑤__;
            }
        }
    if(!haveAns)
        cout<<"There is no answer"<<endl,
    
    return 0;
}

（答案不要加空格，如：n=1不要写成n =1）

26. ①

{{ input(26) }}

27. ②

{{ input(27) }}

28. ③

{{ input(28) }}

29. ④

{{ input(29) }}

30. ⑤

{{ input(30) }}

2.(大整数开方)输入一个正整数n(1≤n≤10的100次方)，试用二分法计算它的平方根的整数部分。

#include<iostream>
#include<string>
using namespace std;

const int SlZE=200;
struct hugeint{
    int len, num[SIZE];
};

//其中len表示大整数的位数;num[1]表示个位，num[2]表示十位，以此类推
hugeint times(hugeint a,hugeint b){
    // 计算大整数a和b的乘积
    int i,j;
    hugeint ans;
    memset(ans.num, 0, sizeof(ans.num));
    for(i=1; i<=a.len; i++)
        for(j=1;j<=b.len; j++)
            __①__ += a.num[i]*b.num[j];
    for(i=1;i <= a.len+b.len; i++){
        ans.num[i+1] +=ans.num[i]/10;
        ___②___;
    }
    if(ans.num[a.len + b.len]>0)
        ans.len = a.len+b.len;
    else
        ans.len = a.len+b.len-1;
    return ans;
}

hugeint add(hugeint a,hugeint b){
//计算大整数a和b 的和
    int i;
    hugeint ans;
    memset(ans.num,0,sizeof(ans.num));
    if(a.len>b.len)
        ans.len=a.len;
    else
        ans.len=b.len;
    for(i=1;i<=ans.len;i++){
        ans.num[i]+=___③___;
        ans.num[i+1]+= ans.num[i]/10;
        ans.num[i]%=10;
    }
    if(ans.num[ans.len+1]>0)
        ans.len++;
    return ans;
}

hugeint average(hugeint a,hugeint b){
//计算大整数a和b的平均数的整数部分
    int i;
    hugeint ans;
    ans=add(a,b);
    for(i=ans.len;i>=2;i--){
        ans.num[i-1]+=(__④__)*10;
        ans.num[i]/=2;
    }
    
    ans.num[1]/=2;
    if(ans.num[ans.len]==0)
        ans.len--;
    return ans;
}

hugeint plustwo(hugeint a){
// 计算大整数a加2之后的结果
    int i 
    hugeint ans;
    ans=a;
    ans.num[1]+=2;
    i-1;
    while( (i<=ans.len)&&(ans.num[i]>=10)){
        ans.num[i+1]+=ans.num[i]/10;
        ans.num[i]%=10;
        i++;
    }
    if(ans.num[ans.len+1]>0)
        ___⑤___;
    return ans;
}

bool over(hugeint a,hugeint b){
// 若大整数a>b则返回true，否则返回false
    int i;
    if(__⑥__)
        return false;
    if( a.len>b.len)
        return true;
    for(i=a.len;i>=1;i--){
        if(a.num[i]<b.num[i])
            return false;
        if(a.num[i]>b.num[i])
            return true;
    }
    return false;
}

int main(){
    string s;
    int i;
    hugeint target,left,middle,right;
    cin>>s;
    memset(target.num,0,sizeof(target.num));
    target.len=s.length();
    for(i=1;i<=target.len;i++)
        target.num[i]=s[target.len-i]-___⑦___;
    memset(left.num,0,sizeof(left.num));
    left.len=1;
    left.num[1]=1;
    right=target;
    do{
        middle=average(left,right);
        if(over(___⑧___))
            right=middle;
        else
            left=middle;
    }while(!over(plustwo(left),right));
    for(i=left.len;i>=1;i--)
        cout<<left.num[i];
    return 0;
}

（答案不要加空格，如：n=1不要写成n =1）

31. ①

{{ input(31) }}

32. ②

{{ input(32) }}

33. ③

{{ input(33) }}

34. ④

{{ input(34) }}

35. ⑤

{{ input(35) }}

36. ⑥

{{ input(36) }}

37. ⑦

{{ input(37) }}

38. ⑧

{{ input(38) }}