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

1. 一个32位整型变量占用（）个字节。

{{ select(1) }}

• 4
• 8
• 32
• 128

2. 二进制数11.01在十进制下是（）。

{{ select(2) }}

• 3.25
• 4.125
• 6.25
• 11.125

3. 下面的故事与（）算法有着异曲同工之妙。从前有座山，山里有个庙，庙里有个老和尚在给小和尚讲故事：从前有座山，山里有个庙，庙里有个老和尚在给小和尚讲故事.

{{ select(3) }}

• 枚举
• 递归
• 贪心
• 分治

4. 逻辑表达式（）的值与变量A的真假无关。

{{ select(4) }}

• (AvB)^ ¬A
• (AvB)^ ¬B
• (A^B) v (¬A^B)
• (AvB) ^ ¬A ^ B

5. 将（2,6,10,17)分别存储到某个地址区间为0~10的哈希表中，如果哈希函数h(x) = (),将不会产生冲突，其中a mod b 表示a除以b的余数。

{{ select(5) }}

• x mod 11
• x 2 mod 11
• 2x mod 11
• ⌊√⌋ mod 11, 其中⌊√⌋表示√下取整

6. 在十六进制表示法中， 字母A相当于十进制的（）。

{{ select(6) }}

• 9
• 10
• 15
• 16

7. 下图中所使用的数据结构是（）。

{{ select(7) }}

• 哈希表
• 栈
• 队列
• 二叉树

8. 在windows资源管理器中，用鼠标右键单击一个文件时，会出现一个名为“复制”的操作选项，它的意思是（）。

{{ select(8) }}

• 用剪切板中的文件替换该文件
• 在该文件所在文件夹中，将该文件克隆一份
• 将该文件赋值到剪切板，并保留原文件
• 将该文件赋值到剪切板，并删除原文件

9. 已知一颗二叉树有10个结点，则其中至少有（）个结点有2个子节点。

{{ select(9) }}

• 4
• 5
• 6
• 7

10. 在一个无向图中，如果任意两个点之间都存在路径相连，则称其为连通图。下图是一个有4个顶点、6条边的连通图，若要使他不在是连通图，至少要删去其中的（）条边。

{{ select(10) }}

• 1
• 2
• 3
• 4

11. 二叉树的（）第一个访问的结点是根节点。

{{ select(11) }}

• 先序遍历
• 中序遍历
• 后续遍历
• 以上都是

12. 以A0作为起点，对下面的无向图进行深度优先遍历时，遍历顺序不可能是（）。

{{ select(12) }}

• A0, A1, A2, A3
• A0, A1, A3, A2
• A0, A2, A1, A3
• A0, A3, A1, A2

13. IPv4协议使用32位地址，随着其不断被分配，地址资源日趋枯竭。因此它正逐渐被使用（）位地址的IPv6协议所取代。

{{ select(13) }}

• 40
• 48
• 64
• 128

14. ()的平均时间复杂度为O（nlog n）,其中n是待排序的元素个数。

{{ select(14) }}

• 快速排序
• 插入排序
• 冒泡排序
• 基数排序

15. 下面是根据欧几里得算法编写的函数，它所计算的是a和b的（）。

int euclid(int a, int b){ if(b == 0) return a; else return euclid(b,a%b); }

{{ select(15) }}

• 最大公共质因子
• 最小公共质因子
• 最大公约数
• 最小公倍数

16. 通常在搜索引擎中，对某个关键词加上双引号表示。（）

{{ select(16) }}

• 排除关键词，不显示任何包含该关键字的结果
• 将关键词分解，在搜索结果中必须包含其中的一部分
• 精确搜索，只显示包含整个关键词的结果
• 站内搜索，只显示关键词所指向网站的内容

17. 中国的国家顶级域名是（）。

{{ select(17) }}

• .cn
• .ch
• .chn
• .china

18. 把64位非零浮点数强制转换成32位浮点数后，不可能（）。

{{ select(18) }}

• 大于原数
• 小于原数
• 等于原数
• 与原数符号相反

19. 下列程序中，正确计算1,2,.....,100这100个自然数之和sum（初始值为0）的是（）。

{{ select(19) }}

• i = 1;do{sum +=i;i++;}while(i<=100);
• i = 1;do{sum +=i;i++;}while(i> 100);
• i = 1;while(i<100){sum +=i;i++;}
• i = 1;while(i>=100){sum +=i;i++;}

20. CCF NOIP复赛全国统一评测时使用的系统软件是（）。

{{ select(20) }}

• NOI Windows
• NOI Linux
• NOI Mac OS
• NOI DOS

二、填空题

21. 7个同学围坐一圈，要选2个不相邻的作为代表，有_____种不同的选法。

{{ input(21) }}

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

{{ input(22) }}

{{ input(23) }}

{{ input(24) }}

{{ input(25) }}

#include<stdio.h>
int main(){
    int a,b;
    cin >> a>> b;
    cout << a <<"+" << b<< "="<<a+b<<endl;
}

输入：3 5 输出________

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

{{ input(26) }}

#include<stdio.h>
int main(){
    int a,b,u,i,num;
    scanf("%d%d%d",&a,&b,&u);
    num = 0;
    for(i=a;i<=b;i++){
        if((i%u) == 0)
            num++;
    }
    printf("%d\n",num);
    return 0;
}

输入：1 100 15 输出：________

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

{{ input(27) }}

#include<stdio.h>
const int SIZE = 100;
int main(){
    int n,f,i,left,right,middle,a[SIZE];
    scanf("%d%d",&n,&f);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
        left = 1;
        right = n;
        do{
            middle = (left + right)/2;
            if(f <= a[middle])
                right = middle;
            else
                left = middle + 1;
        }while(left < right);
    printf("%d\n",left)
    return 0;
}

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

{{ input(28) }}

  #include<stdio.h>
  const int SIZE = 100;
  int main(){
      int height[SIZE],num[SIZE],n,ans;
      int i,j;
      scanf("%d",&n);
      for(i = 0; i<n;i++){
          scanf("%d",&height[i]);
          num[i] =1;
          for(j = 0;j<i;j++){
              if(height[j] <height[i]) && (num[j] >= num[i])
                  num[i] = num[j] + 1;
          }
      }
      ans = 0;
      for(i=0;i<n;i++){
          if(num[i] >ans) ans = num[i];
      }
      pritnf("%d\n",ans);
      return 0;
  }

输入： 6 2 5 3 11 12 4 输出:______

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

{{ input(29) }}

三、阅读理解 1、（序列重排）全局数组变量a定义如下：

#define SIZE 100
int a[SIZE], n;
它记录着一个长度为n的序列a[1],a[2],...,a[n].
现在需要一个函数，以整数p(1<=p<=n)为参数，实现如下功能：
将序列a的前p个数与后n-p个数对调，且不改变这个p个数（或n-p个数）之间的相对位置。
例如：长度为5的序列1,2,3,4,5,当p=2时重排结果为3,4,5,1,2。
有一种朴素的算法可以实现这一需求，其时间复杂度为O(n),空间复杂度为O（n):
void swap1(int p){
    int i,j,b[SIZE];
    for(i=1;i<=p;i++)
        b[__①__] = a[i];//(3分）
    for(i=p+1;i<=n;i++)
        b[i-p] = __②__;//(3分)
    for(i=1;i<=__③__;i++)//(3分)
        a[i] = b[i];
}
我门也可以用时间换空间，使用时间复杂度为O(n^2^），空间复杂度为O(1)的算法：
void swap2(int p){
    int i,j,temp;
    for(i=p+1;i<=n;i++){
        temp =a[i];
        for(j=i;j>=__④__lj--) //(3分)
            a[j] = a[j-1];
            __⑤__ = temp; //(3分)
    }
}

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

30. ①

{{ input(30) }}

31. ②

{{ input(31) }}

32. ③

{{ input(32) }}

33. ④

{{ input(33) }}

34. ⑤

{{ input(34) }}

2、（二叉查找树）二叉查找树具有如下性质：每个结点的值都大于其左子树上所有结点的值、小于其右子树上所有结点的值。 试判断一颗树是否为二叉查找树。输入的第一行包含一个整数n，表示这棵树有n个定点，编号分别为1，2，...，n,其中编号为1 的为根节点。 之后的第i行有三个数value，left_child,right_child,分别表示该结点关键字的值、左子节点的编号、右子节点的编号； 如果不存在左子节点或右子节点，则用0代替。输出1表示这棵树是二叉查找树，输出0则表示不是。

#include<stdio.h>
#define SIZE 100
#define INFINITE 1000000
struct node{
    int left_child,right_child,value;
}

node a[SIZE];
int is_bst(int root,int lower_bound,int upper_bound){
    int cur;
    if(root == 0)
        return 1;
    cur = a[root].value;
    if((cur>lower_bound) && (__①__) && //3分
        (is_bst(a[root].left_child, lower_bound, cur) == 1) &&
        (is_bst( __①__, __③__, __④__) == 1))//3分 ,3分 ,3分
        return 1;
    return 0;
}

int main(){
    int i,n;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d%d%d",&a[i].value, &a[i].left_child, &a[i].right_child);
        printf("%d\n",is_bst(__⑤__, -INFINITE,INFINITE));//2分
    return 0;
}

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

35. ①

{{ input(35) }}

36. ②

{{ input(36) }}

37. ③

{{ input(37) }}

38. ④

{{ input(38) }}

39. ⑤

{{ input(39) }}