一、单选题（共 15 题，每题 2 分，共计 30 分）

1. 在标准ASCII码表中，已知英文字母D的ASCII码是01000100，英文字母B的ASCII码是（　　）？ {{ select(1) }}

• 0100000
• 01000010
• 01000011
• 01000000

2.在下列各种排序算法中，不是以“比较”作为主要操作的算法是（ ）。

{{ select(2) }}

• 选择排序
• 冒泡排序
• 插入排序
• 基数排序

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

{{ select(3) }}

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

4.广度优先搜索时，需要用到的数据结构是（ ）。

{{ select(4) }}

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

5.控制器（CU）的功能是（　　）。 {{ select(5) }}

• 指挥计算机各部件自动、协调一致地工作
• 对数据进行算术运算或逻辑运算
• 控制对指令的读取和译码
• 控制数据的输入和输出

6.微机中，西文字符所采用的编码是（　　） {{ select(6) }}

• EBCDIC码
• ASCII码
• 国标码
• BCD码

7.Linux 是一种( )。

{{ select(7) }}

• 绘图软件
• 程序设计语言
• 操作系统
• 网络浏览器

8.如果根结点的深度记为 1，则一棵恰有 2011 个叶结点的二叉树的深度最少是（ ）。 {{ select(8) }}

• 10
• 11
• 12
• 13

9.如果 256 种颜色用二进制编码来表示，至少需要（ ）位 {{ select(9) }}

• 6
• 7
• 8
• 9

10.下面叙述正确的是？（ ）

{{ select(10) }}

• 算法的执行效率与数据的存储结构无关
• 算法的空间复杂度是指算法程序中指令(或语句)的条数
• 算法的有穷性是指算法必须能在执行有限个步骤之后终止
• 以上三种描述都不对

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

{{ select(11) }}

• 1600
• 2000
• 4000
• 16000

12.以下数据结构中不属于线性数据结构的是

{{ select(12) }}

• 队列
• 线性表
• 二叉树
• 栈

13.在一棵二叉树上第5层的结点数最多是（ ）

{{ select(13) }}

• 8
• 16
• 32
• 15

14.如果在一个非零无符号二进制整数之后添加一个0，则此数的值为原数的（）

{{ select(14) }}

• 4倍
• 2倍
• 1/2
• 1/4

15.以下不是微软公司出品的软件是（ ）？

{{ select(15) }}

• Powerpoint
• Word
• Excel
• Acrobat Reader

二.阅读程序

1 #include <cstdio>

2 using namespace std;  

3 int main(){         

4     int a,b;

5     cin >> a >> b ;      

6     if((++a<0)&&!(b--<=1))          

7          printf("%d,%d\\n",a,b);      

8     else          

9          printf("%d,%d\\n",b,a);     

10    return 0;

11 }

判断题

1).若第6行++a改为a++结果不会改变（）

{{ select(16) }}

• √
• ×

2).若a为0，那么将执行第7行代码（）

{{ select(17) }}

• √
• ×

3).若b为1，那么将执行第9行代码（）

{{ select(18) }}

• √
• × 4).若第6行++a<0为假，那么后面的条件将无效（）

{{ select(19) }}

• √
• ×

单选题

5).若输入数据 0 2，那么输出的结果为（）

{{ select(20) }}

• 1,1
• 1,2
• 2,1
• 2,0

2. 若输入数据 -2 3，那么输出结果为（） {{ select(21) }}

• -1, 3
• -2, 3
• -2, -2
• -1, 2

2、

#include <iostream>
#include <cstring>
using namespace std;
 int main(){
     char str[32] = {0};
     cin >> str;
     int len = strlen(str);
     for(int i = 0 ; i < len; i++){
         if( str[i] >= 'A' && str[i] <= 'Z')
             str[i] += 32;
         if( str[i] >= 'a' && str[i] <= 'z')
             str[i] -= 32;
     }
     cout << str << endl;
     return 0;
 }

判断题

1).若第10行str[i] += 32改为str[i] |= 32结果不会改变（）

{{ select(22) }}

• √
• ×

2).若第12行str[i] -= 32改为str[i] |= 32结果不会改变（） {{ select(23) }}

• √
• ×

3).程序功能为将大写转小写，小写转大写（） {{ select(24) }}

• √
• ×

4).若第8行 i < len改为 i < strlen(str)，程序可能会变慢（） {{ select(25) }}

• √
• ×

单选题

5).若输入AbCdEf，那么输出的结果为（） {{ select(26) }}

• ABCDEF
• abcdef
• aBcDeF
• AbCdEf

6).若输入HellO，并再14行增加 str[3]=’\0’,那么输出的结果为（） {{ select(27) }}

• Hello
• Hel
• hel
• HEL

#include<iostream>
 using namespace std;
 int f(int n,int k){
     int sum=0; 
     if(k<=0)
         return 1;
     sum+=f(n-1,k-1);
     if(n>k)
         sum+=f(n-1,k);
     return sum;
 }
 int main(){
     int n,k;
     cin >> n >> k;
     cout<<f(n,k);
     return 0;
 }

判断题

1)k<=0为递归的结束条件（） {{ select(28) }}

• √
• ×

2).如果俩个参数相等，将会减少递归的次数（） {{ select(29) }}

• √
• ×

单选题

3).若输入6 6，那么输出的结果为（） {{ select(30) }}

• 6
• 1
• 3
• 5

4).若输入3 2，那么输出的结果为（）

{{ select(31) }}

• 3
• 4
• 5
• 6

5).若输入6 3，那么输出的结果为（）

{{ select(32) }}

• 21
• 15
• 18
• 20

6).（4分）若输入两个值相同，那么输出结果（）

{{ select(33) }}

• 不确定
• 两个数的和
• 两个数的乘积
• 等于一

三、完善程序

（1）（子矩阵）输入一个n1*m1的矩阵a，和n2*m2的矩阵b，问a中是否存在子矩阵和b相等。若存在，输出所有子矩阵左上角的坐标；若不存在输出“There is no answer”。

试补全程序

#include <iostream> 

using namespace std;  

const int SIZE = 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;

}

1).① 处应填（ ）

{{ select(34) }}

• b[i][j] = a[i][j]
• cin >> b[n2][m2]
• cin >> b[i][j]
• b[i][j] += a[i][j]

2).②处应填（)。

{{ select(35) }}

• m1-m2
• m1-m2+1
• m1-m2-1
• m1+m2-1

3).③处应填（ ）。 {{ select(36) }}

• good=true
• good=false
• good=!good
• haveAns=true

4).④处应填（ ）。 {{ select(37) }}

• m1
• n1
• m2
• n2

5).⑤处应填（ ）。 {{ select(38) }}

• haveAns=false
• haveAns=true
• haveAns=!haveAnse
• good=true

2.（全排列）下面程序的功能是利用递归方法生成从 1 到 n(n<10)的 n 个数的全部可能的排列（不一 定按升序输出）。例如，输入 3，则应该输出（每行输出 5 个排列）： 123 132 213 231 321 312

试补全程序

#include <iostream>   

#include <iomanip>   

int n,a[10];  // a[1],a[2],…,a[n]构成 n 个数的一个排列   

long count=0;  // 变量 count 记录不同排列的个数，这里用于控制换行   

void perm(int k){

 int j,p;   

 if(   ①   ){

  count++;      

  for(p=1;p<=n;p++)    

   cout <<setw(1)<<a[p];  　    

  cout <<"  ";

  if(     ②   )  

   cout <<endl;    

  return; 

 }    

 for(j=k;j<=n;j++){

  swap(a[k],a[j]);

      ③    ;      ④    ;}    

} 

void main(){

 int i;     

 cout <<"Entry n:"<<endl;     

 cin >>n;     

 for(i=1;i<=n;i++)  

  a[i]=i;   

 ⑤    ;   

}

1).①处应填（ ）。 {{ select(39) }}

• k==n
• k==0
• k>=0
• k==n+1

2).②处应填（ ）。 {{ select(40) }}

• count==5
• count/5 == 0
• count%5 != 0t
• count%5 == 0

3).③处应填（ ）。 {{ select(41) }}

• perm(k)
• perm(k+1)
• perm(i)
• perm(i+1)

4).④处应填（ ）。

{{ select(42) }}

• swap(a[k],a[i])
• swap(a[i],a[j])
• swap(a[k],a[j])
• swap(a[k],a[n])

5).⑤处应填（ ）。

{{ select(43) }}

• perm(1)
• perm(n)
• perm(0)
• perm(n+1)