该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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

1. 一棵二叉树共有25个结点,其中5个是叶子结点,则度为1的结点数为（ ）。

{{ select(1) }}

• 16
• 10
• 6
• 4

2. 如果一棵二叉树的中序遍历是 BAC，那么它的先序遍历不可能是（ ）。

{{ select(2) }}

• ABC
• CBA
• ACB
• BAC

3. 已知 a=00111000B 和 b=2FH，则两者比较的正确关系是( )

{{ select(3) }}

• a>b
• a=b
• a<b
• 不能比较

4. 设任意一个十进制整数为 D，转换成二进制数为 B。根据数制的概念，下列叙述中正确的是（ ）

{{ select(4) }}

• 数字 B 的位数<数字 D 的位数
• 数字 B 的位数≤数字 D 的位数
• 数字 B 的位数≥数字 D 的位数
• 数字 B 的位数>数字 D 的位数

5.已知二叉树后序遍历序列是 dabec,中序遍历序列是 debac,它的前序遍历序列是（ ）

{{ select(5) }}

• acbed
• decab
• deabc
• cedba

6.有一个由 4000 个整数构成的顺序表，假定表中的元素已经按升序排列，采用二分查找定位一个元素。则最多需要几次比较就能确定是否存在所查找的元素。

{{ select(6) }}

• 11
• 12
• 13
• 14

7.假设某台式计算机内存储器的容量为 1KB，其最后一个字节的地址是（ ）

{{ select(7) }}

• 1023H
• 1024H
• 0400H
• 03FFH

8.假设某台式计算机的内存储器容量为 256MB，硬盘容量为 20GB。硬盘的容量是内存容量的（ ）

{{ select(8) }}

• 40 倍
• 60 倍
• 80 倍
• 100 倍

9.链表不具备的特点是（ ）。

{{ select(9) }}

• 可随机访问任何一个元素
• 插入、删除操作不需要移动元素
• 无需事先估计存储空间大小
• 所需存储空间与存储元素个数成正比

10.随着 Internet 的发展,越来越多的计算机感染病毒的可能途径之一是（ ）

{{ select(10) }}

• 从键盘上输入数据
• 通过电源线
• 所使用的光盘表面不清洁
• 通过 Internet 的 E-mail，附着在电子邮件的信息中

11.对长度为 n 的线性表排序,在最坏情况下,比较次数不是 n(n-1)/2 的排序方法是（ ）

{{ select(11) }}

• 快速排序
• 冒泡排序
• 直接插入排序
• 堆排序

12.无符号二进制整数111110转换成十进制数是（ ）

{{ select(12) }}

• 62
• 60
• 58
• 56

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

{{ select(13) }}

• 7
• 21
• 42
• 49

14.下列关于栈的叙述正确的是（ ）。

{{ select(14) }}

• 栈按"先进先出"组织数据
• 栈按"先进后出"组织数据
• 只能在栈底插入数据
• 不能删除数据

15.某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为（假设根结点在第1层）（ ）

{{ select(15) }}

• 3
• 4
• 6
• 7

二.阅读程序（判断题1.5分，选择题3分，共计40分）

1 #include <iostream>

2 #include <cstring>

3 using namespace std;

4 int main(){

5   char str[105]={0};

6   fgets(str,105,stdin);

7   for( int i = 0; i < strlen(str); i++){

8        if( str[i] >= 'a' && str[i] <='z')

9            if( str[i] == 'z' )

10               str[i] = 'a';

11           else

12               str[i] += 1;

13   }

14   cout << str << endl;

15   return 0;

16  }

判断题

1).本程序是将小写字母替换成大写字母（）

{{ select(16) }}

• √
• ×

2).若输入的字符串长度超过105不会出现问题（）

{{ select(17) }}

• √
• ×

3).若将第8行的&&改成||有可能出现不可见字符（）

{{ select(18) }}

• √
• ×

4).把12行改成str[i] +=32,那么会将除z以外的小写字母转成大写（）

{{ select(19) }}

• √
• ×

单选题

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

{{ select(20) }}

• ABCDZ
• BCDEa .
• bcdea
• BCDEA

6).输入数据gdkkn bzs，那么输出结果为（）

{{ select(21) }}

• hello
• GDKKN
• hello cat
• GDKKN BZS

1 #include <iostream>

2 using namespace std;

3 bool judge(int n){

4    int raw = n;

5    int r = 0;

6    while(n > 0){

7        r = r*10+n%10;

8        n /= 10;

9    }

10   if( r == raw)

11      return true;

12   else

13      return false;

14 }

15 int main(){

16   int n ;

17   cin >> n;

18   int count = 0;

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

20       if( judge(i) )

21          ++count;

22   cout << count << endl;

23   return 0;

24 }

判断题

1).若将第6行n>0改成n != 0 效果相同（）

{{ select(22) }}

• √
• ×

2).若将函数judge(int n)改成judge(int& n) 可能造成死循环（）

{{ select(23) }}

• √
• ×

3).如果n小于10，count有可能等于0（）

{{ select(24) }}

• √
• ×

4).若第5行int r = 0改成 int r，结果不会改变（） {{ select(25) }}

• √
• ×

单选题

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

{{ select(26) }}

• 10
• 55
• 0
• 9

6)输入数据30，那么输出结果为（）

{{ select(27) }}

• 30
• 11
• 2
• 9

1 #include<cstdio>

2 using namespace std;

3 int f(int n,int m){

4    if(n==0)

5        return m;

6    if(m==0)

7        return n;

8    return f(n%m,n)+f(m,m%n);

9 }

10 int main(){

11   int n,m;

12   scanf("%d%d",&n,&m);

13   printf("%d\n",f(n,m));

14   return 0;

15 }

判断题

1).如果输入0 0那么结果为0（）

{{ select(28) }}

• √
• ×

2).如果12行被注释，那么结果为0（）

{{ select(29) }}

• √
• ×

单选题

3).输入9 3结果为（）。

{{ select(30) }}

• 12
• 11
• 3
• 15

4).输入9 5结果为（）

{{ select(31) }}

• 14
• 29
• 17
• 1

5).如果n为质数，那么递归次数（）

{{ select(32) }}

• 大于n
• 等于n
• 小于n
• 不确定

6).输入11 7结果为（）

{{ select(33) }}

• 11
• 7
• 18
• 45

三、完善程序

（1）给定一个有序（非降序）数组A，可含有重复元素，求最小的i使得A[i]等于target，不存在则返回-1。

试补全程序。

#include <iostream>
using namespace std;
int BinarySearch(int A[],int n,int target){
    if(n <= 0){
        return -1;
    }
    int mid,start = 0,end = n-1;
    while(start < end){
        mid = __①__;
        if(A[mid] < target){
            start = __②__;
        }
        else{
            end = __③__;
        }
    }
    if(__④__){
        return -1;
    }
    else{
        return start;
    }
}
int main(){
    int A[] = {2,3,4,4,4,4,4,5,6,7,8};
    cout<<BinarySearch(___⑤___)<<endl;
    return 0;
}

1).①处应填（ ）。

{{ select(34) }}

• start + end
• （start + end）>> 1
• （start-end）/ 2
• end - 1

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

• mid
• mid+1
• mid-1
• start+1

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

• mid
• mid+1
• mid-1
• start+1

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

• A[mid]==target
• A[mid]>=target
• A[mid]!=target
• A[mid]<target

5).如果要搜素4这个值,⑤处应填（ ）。 {{ select(38) }}

• A,11,4
• A,10,4
• A,4,11
• A,4,10

2.编写程序实现两种不同进制之间的数据转换。输入数据共有三行，第一行是一个正整数，表示需要转换的数的进制n(2≤n≤16)，第二行是一个n进制数，若n>10则用大写字母A～F表示数码10～15，并且该n进制数对应的十进制的

值不超过1000000000，第三行也是一个正整数，表示转换之后的数的进制m(2≤m≤16)。

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
char c[32];
char t[32];
void change(int n,int base)
{
    int index = 0;
    while(n>0)
    {
        if( n%base >= 10)
            t[index++] = __①__;
        else
        t[index++] = __②__;
        __③___;
    }
}
int main()
{
    int base,taget;
    cin >> base >> c >> taget;
    int len = strlen(c);
    int value = 0;
    for( int i = 0; i < len; i++)
    {
        if( c[i] < 'A' )
            value += (__④__)*pow(base,len-1-i);
        else
        value += (__⑤__)*pow(base,len-1-i);
    }
    change(value,taget);
    int t_len = strlen(t);
    for(int i = t_len-1; i>= 0;i--)
    {
        cout << t[i];
    }
    cout << endl;
    return 0;
}

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

• n%base-10
• n%base-10+'a'
• n%base-10+'A'
• n%base+'A'

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

• n%base+'0'
• n%base-10+'0'
• n%base-10+0
• n%base+'\0'

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

• n %= base
• n /= base
• n -= base
• n |= base

4. ④处应填（ ）。

{{ select(42) }}

• c[i]+'0'
• c[i]- 0
• c[i]+0
• c[i]-'0'

5. ⑤处应填（ ）。

{{ select(43) }}

• c[i]+10
• c[i]-‘a’+10
• c[i]-‘0’+10
• c[i]-‘A’+10