一、 单项选择题（共 15 题，每题 2 分，共计 30 分。每题有且仅有一个正确选项。）

1、 1MB 等于（） {{ select(1) }}

• 10000 字节
• 1024 字节
• 1000×1000 字节
• 1024×1024 字节

2、 操作系统的作用是（） {{ select(2) }}

• 把源程序译成目标程序
• 便于进行数据管理
• 控制和管理系统资源
• 实现硬件之间的连接

3、在计算机内部用来传送、存贮、加工处理的数据或指令都是以 ( ) 形式进行的。 {{ select(3) }}

• 二进制码
• 八进制码
• 十进制码
• 智能拼音码

4、二进制数 00100100 和 00010100 的和是 ( ) 。 {{ select(4) }}

• 00101000
• 01100111
• 01000100
• 00111000

5、与二进制小数 0.1 相等的十六进制数是 ( ) 。

{{ select(5) }}

• 0.8
• 0.4
• 0.2
• 0.1

6、FTP 可以用于 ( )

{{ select(6) }}

• 远程传输文件
• 发送电子邮件
• 浏览网页
• 网上聊天

7、下面哪种软件不属于即时通信软件 ( ) 。

{{ select(7) }}

• QQ
• MSN
• 微信
• P2P

8、6 个顶点的连通图的最小生成树，其边数为 ( ) 。

{{ select(8) }}

• 6
• 5
• 7
• 4

9、链表不具备的特点是 ( ) 。 {{ select(9) }}

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

10、线性表若采用链表存储结构，要求内存中可用存储单元地址 ( ) 。 {{ select(10) }}

• 必须连续
• 部分地址必须连续
• 一定不连续
• 连续不连续均可

11、今有一空栈 S ，对下列待进栈的数据元素序列 a ， b ， c ， d ， e ， f 依次进行进栈，进栈，出栈，进栈，进栈，出栈的操作，则此操作完成后，栈 S 的栈顶元素为 {{ select(11) }}

• f
• c
• a
• b

12、前序遍历序列与中序遍历序列相同的二叉树为 ( ) {{ select(12) }}

• 根结点无左子树
• 根结点无右子树
• 只有根结点的二叉树或非叶子结点只有左子树的二叉树
• 只有根结点的二叉树或非叶子结点只有右子树的二叉树

13、如果根的高度为 1, 具有 61 个结点的完全二叉树的高度为 ( ) 。 {{ select(13) }}

• 5
• 6
• 7
• 8

14、下列选项中不属于视频文件格式的是 ( ) 。 {{ select(14) }}

• TXT
• AVI
• MOV
• RMVB

15、 设某算法的计算时间表示为递推关系式 T(n)=T(n-1)+n(n 为正整数 ) 及 T(0)=1 ，则该算法的时间复杂度为 ( ) 。 {{ select(15) }}

• O(logn)
• O(nlogn)
• O(n)
• O(n 2 )

二、 阅读程序

程序输入不超过数组或字符串定义的范围，判断题正确的填​A​，错误的填 B, 除特殊情况说明外，判断题每题 1.5 ​分​, 选择题每题 4 分，共计 40 分

1、

1.#include <iostream> 
2.#include <cstdio> 
3.using namespace std; 
4.int i, j, n;
5.int x[101], y[101];
6.int main() 
7.{
8.     cin >> n;
9.     for(i=1; i<=n; i++) cin >> x[i]; 
10.   for(i=1; i<=n-1; i++)
11.   for(j=i+1; j<=n; j++)
12.       if(x[i]>x[j])
13.            y[j]++;
14.      else if(x[i]<x[j]) 
15.            y[i]++;
16.     for(i=1; i<=n; i++) 
17.     printf("%5d\_", y[i]);
18.     cout << endl;
19.     return 0; 
20.}

判断题

1、（1 分）把第 13 行与第 15 行互换位置， 结果不会改变。

{{ select(16) }}

• √
• ×

2、( 1 分）第 14 行把if(x[i]<x[j])删掉效果一样。

{{ select(17) }}

• √
• ×

3、 第 11 行把 i+1 改成 1， 数组y 每个元素的值增加 1 倍。（）

{{ select(18) }}

• √
• ×

4、 数组 y[i]中存的是 x[i]在数列中从大到小的次序。（）

{{ select(19) }}

• √
• ×

选择题

5、 此程序的时间复杂度是

{{ select(20) }}

• O(log n)
• O(n log n)
• O(n^2)
• O(n)

6、此程序如果n 输入 4， 然后输入 2 4 1 3， 输出结果是（）

{{ select(21) }}

• 1 2 3 4
• 2 0 3 1
• 4 3 2 1
• 1 3 0 2

2、

1 #include <iostream>

2 #include <cstdio>

3 using namespace std;

4 int n,i,x;

5 int d[11];

6 int  main()
7 {
8     cin>>n;
9     for(int i=1;i<=n;i++)
10   {
11      cin>>x;
12      d[x] = d[x] + 1;
13   }
14   d[0] = 0;
15   for(int i=0;i<10;i++)
16        d[i] = d[i-1] + d[i]
17   for(int i=1;i<10;i++)
18        if(d[i]!=d[i-1])
19            printf("%3d:%4d_",i,d[i-1]+i)
20        return 0;
21 }

判断题

1、 (1 分）输入的 x 值应在[0,n-1]的范围内。

{{ select(22) }}

• √
• ×

2、 （1 分）把第 12 行改成“d[x]++", 不影响程序运行结果。

{{ select(23) }}

• √
• ×

3、 对任意在[1，9]之间的数 i, 都有d[i-1]<d[i]<d[i+1]。

{{ select(24) }}

• √
• ×

4、 把第 18 行改成”if(d[i]>d[i-1])", 程序运行的结果会发生改变。

{{ select(25) }}

• √
• ×

选择题

5、输入n=10 后， 接着输入：1 3 4 3 5 2 4 3 5 2 后， 程序输出结果为 {{ select(26) }}

• 1:1 2:2 3:3 4:2 5:3
• 1:1 2:2 3:4 4:7 5:9
• 1:0 2:1 3:2 4:1 5:2
• 1:1 2:2 3:3 4:4 5:5

6、把程序第 19 行改成“pringf("%3d", i);"后， 输入n=10 后， 接着输入：1 3 4 1 5 4 4 3 5 1 后， 程序输出结果为

{{ select(27) }}

• 1 2 3 4 5
• 3 2 3 2
• 4 3 4 3
• 1 3 4 5

3、

1.#include <iostream> 
2.#include <cstdio> 
3.using namespace std; 
4.int j, i, m;
5.int a[10]; 
6.int main() 
7.{
8.  for(i=2; i<=6; i++) 
9.    a[i]=i+1;
10.  do
11.  {
12.      m=2;
13.      for(i=3; i<=6; i++)
14.           if(a[m]>a[i]) m=i; 
15.           a[m]=a[m]+m;
16.          m=1;
17.
18.       for(i=2; i<=5; i++)
19.          for(j=i+1; j<=6; j++)
20.                if(a[i]<a[j]) m=0;
21.  }while(m==0);
22. printf("%d", a[2]);
23. return 0; 
24. }

判断题

1、程序结束是， a[2]的值一定是数组 a 中的最大值 {{ select(28) }}

• √
• ×

2、第 21 行”m==0"成立时， 数组 ai从大到小排序。

{{ select(29) }}

• √
• ×

3、程序输出时， a 数组满足：对任意的 2<=i<6, 有 a[i]>a[i+1]。

{{ select(30) }}

• √
• ×

4、删除第 16 行代码“m=1"程序结果会发生改变。

{{ select(31) }}

• √
• ×

选择题

5、程序的输出结果为

{{ select(32) }}

• 58
• 59
• 61
• 60

6、若输入11 5 0，那么结果为（）。

{{ select(33) }}

• O(n^2)
• O(nlogn)
• O(logn)
• O(n)

四、完善程序，单选题每小题三分，共计 30 分

1、斐波那契序列为 1，1，2，3，5，8，13，21，其元素产生的规则是前两个数为 1，从第 3 个数开始，每两个数等于它前面两个数之和，已知任意一个正整数可以表示为若干个互不相同的斐波那契数列之和，例如 36=21+13+2 下面的程序是由键盘输入一个正整数 n 输出组成 n 的互不相同的斐波那契数。算法说明：

1. 寻找小于等于 n 的最大斐波那契数列a 并以a 作为组成 n 的一个数.
2. 若 n!=a，则以n-a 作为 n 的新值重复步骤 1，若a=n 则结束

程序

1）①处应填（）

{{ select(34) }}

• a=c; b=a;
• a=b; b=c;
• ac; ba
• ab; bc

2. ②处应填（）

{{ select(35) }}

• b==n
• b<n
• a==n
• a<n

3. ③处应填（）

{{ select(36) }}

• return c
• return b
• return a+b
• return a

4. ④处应填（）

{{ select(37) }}

• printf(" %4d", a)
• printf(" + %4d", a)
• printf(" %4d", b)
• printf(" + %4d", b)

5. ⑤处应填（）

{{ select(38) }}

• p(a)
• p(b)
• p(n-a)
• p(n-b)

2、现在政府计划在某个区域的城市之间建立高速公路，已使得其中任意两个城市之间都有直接或间接的高速公路相连，费用为每公里为一个单位价格, 求最小费用。

输入：n(n<=100, 表示城市数目)。

接下来n 行, 每行两个数表示 xi, yi, 第 i 个城市的坐标。（单位千米）。输出：最小费用（保留 2 位小数）

程序如下：

1）①处应填（）

{{ select(39) }}

• sqrt((c[i].x-c[i].y)*(c[i].x-c[i].y)+(c[j].x-c[j].y)*(c[i].x-c[j].y));
• sqrt((c[i].x-c[j].x)*(c[j].x-c[i].x)+(c[i].y-c[j].y)*(c[i].y-c[j].y));
• sqrt((c[i].x-c[j].x)*(c[i].x-c[j].x)+(c[i].y-c[j].y)*(c[i].y-c[j].y));
• sqrt((c[i].x-c[i].y)*(c[j].x-c[j].y)+(c[i].x-c[i].y)*(c[j].x-c[j].y));

2. ②处应填（）

{{ select(40) }}

• p[i]=1;
• p[i]=0;
• p[n-i]=1;
• p[n-i]=0;

3. ③处应填（）

{{ select(41) }}

• p[j]==0&&d[p[j]][i]<minf
• p[j]!=0&&d[p[j]][j]<minf
• p[j]==0||d[p[j]][i]<minf
• p[j]!=0||d[p[j]][j]<minf

4. ④处应填（）

{{ select(42) }}

• k=minf;
• k==0;
• k=i;
• k=j;

5. ⑤处应填（）

{{ select(43) }}

• d[p[j]][j]>d[k][j]
• d[p[j]][i]<d[k][j]
• d[p[i][j]>d[k][j]
• d[p[i]][j]<d[k][i]