一、选择题（共 20 题，每题 1.5 分，共计 30 分；有单选和多选题）

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

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

2. 下列说法正确的是（ ）。 {{ select(2) }}

• CPU 的主要任务是执行数据运算和程序控制
• 存储器具有记忆能力，其中信息任何时候都不会丢失
• 两个显示器屏幕尺寸相同，则它们的分辨率必定相同
• 个人用户只能使用 Wifi 的方式连接到 Internet

3. 与二进制小数 0.1 相等的十六进制数是（ ）。 {{ select(3) }}

• 0.8
• 0.4
• 0.2
• 0.1

4. 下面有四个数据组，每个组各有三个数据，其中第一个数据为八进制数，第二个数据为 十进制数，第三个数据为十六进制数。这四个数据组中三个数据相同的是（ ）。 {{ select(4) }}

• 120 82 50
• 144 100 68
• 300 200 C8
• 1762 1010 3F2

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

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

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

• f
• c
• a
• b

7. 前序遍历序列与后序遍历序列相同的二叉树为（ ）。 {{ select(7) }}

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

8. 如果根的高度为 1，具有 61 个结点的完全二叉树的高度为（ ）。 {{ select(8) }}

• 5
• 6
• 7
• 8

9. 66 个顶点的连通图的最小生成树，其边数为（ ）。 {{ select(9) }}

• 6
• 5
• 7
• 4

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

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

11. 具有 n 个顶点，e 条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为（ ）。 {{ select(11) }}

• $Θ(n^2 )$
• $Θ(e^2 )$
• $Θ(ne)$
• $Θ(n+e)$

12. 在数据压缩编码的应用中，哈夫曼（Huffman）算法是一种采用了（ ）思想的算法。 {{ select(12) }}

• 贪心
• 分治
• 递推
• 回溯

13. 双向链表中有两个指针域，llink 和 rlink，分别指回前驱及后继，设 p 指向链表中的一个结点，q 指向一待插入结点，现要求在 p 前插入 q，则正确的插入为（ ）。 {{ select(13) }}

• p->llink = q; q->rlink = p; p->llink->rlink = q;q->llink = p->llink;
• q->llink = p->llink; p->llink->rlink = q; q->rlink = p;p->llink = q->rlink;
• q->rlink = p; p->rlink = q;p->llink->rlink = q; q->rlink = p;
• p->llink->rlink = q; q->rlink = p;q->llink = p->llink; p->llink = q;

14. 对图 G 中各个结点分别指定一种颜色，使相邻结点颜色不同，则称为图 G 的一个正常着色。正常着色图 G 所必需的最少颜色数，称为 G 的色数。那么下图的色数是（ ）。

{{ select(14) }}

• 3
• 4
• 5
• 6

15. 在 NOI 系列赛事中参赛选手必须使用由承办单位统一提供的设备。下列物品中不允许选手自带的是（ ）。 {{ select(15) }}

• 鼠标
• 笔
• 身份证
• 准考证

16. 以下属于操作系统的有（ ）。 {{ multiselect(16) }}

• Windows XP
• UNIX
• Linux
• Mac OS

17. 下列属于视频文件格式的有（ ）。 {{ multiselect(17) }}

• AVI
• MPEG
• WMV
• JPEG

18. 下列选项不是正确的 IP 地址的有（ ）。 {{ multiselect(18) }}

• 202.300.12.4
• 192.168.0.3
• 100:128:35:91
• 111-127-35-21

19. 下列有关树的叙述中，叙述正确的有（ ）。 {{ multiselect(19) }}

• 在含有 n 个结点的树中，边数只能是 (n-1) 条
• 在哈夫曼树中，叶结点的个数比非叶结点个数多 1
• 完全二叉树一定是满二叉树
• 在二叉树的前序序列中，若结点 u 在结点 v 之前，则 u 一定是 v 的祖先

20. 以下图中一定可以进行黑白染色的有（ ）。（黑白染色：为各个结点分别指定黑白两种颜色之一，使相邻结点颜色不同。） {{ multiselect(20) }}

• 二分图
• 完全图
• 树
• 连通图

二、填空题（21、22题每空5分，23-26题每空8分，27题13分，28题14分）

21. 在 1 和 2015 之间（包括 1 和 2015 在内）不能被 4,5,6三个数任意一个数整除的数有_________个。

{{ input(21) }}

22. 结点数为 5 的不同形态的二叉树一共有_________种。（结点数为 2 的二叉树一共有 2 种：一种是根结点和左儿子，另一种是根结点和右儿子。）

{{ input(22) }}

23. 阅读程序写结果：

#include <iostream> 
using namespace std; 
struct point { 
    int x; 
    int y; 
}; 
int main() { 
    struct EX{ 
  int a; 
  int b; 
  point c; 
 } e; 
 e.a = 1; 
 e.b = 2; 
 e.c.x = e.a + e.b; 
 e.c.y = e.a * e.b; 
 cout << e.c.x << ',' << e.c.y << endl; 
    return 0; 
} 

输出：_________

{{ input(23) }}

24. 阅读程序写结果：

#include <iostream> 
using namespace std; 
void fun(char *a, char *b) { 
    a = b; 
    (*a)++; 
} 
int main() { 
    char c1, c2, *p1, *p2; 
    c1 = 'A'; 
    c2 = 'a'; 
    p1 = &c1; 
    p2 = &c2; 
    fun(p1, p2); 
    cout << c1 << c2 << endl; 
    return 0; 
} 
输出：_________

{{ input(24) }}

25. 阅读程序写结果：

#include <iostream> 
#include <string> 
using namespace std; 
int main() { 
 int len, maxlen; 
 string s, ss; 
 maxlen = 0; 
 do { 
     cin >> ss; 
     len = ss.length(); 
     if (ss[0] == '#') 
   break; 
     if (len > maxlen) { 
      s = ss; 
      maxlen = len; 
     } 
 } while (true); 
 cout << s << endl; 
    return 0; 
} 

输入：
I
am
a
citizen
of
China
#

输出：_________

{{ input(25) }}

26. 阅读程序写结果：

#include <iostream> 
using namespace std; 
int fun(int n, int fromPos, int toPos) { 
 int t, tot; 
    if (n == 0) 
     return 0; 
    for (t = 1; t <= 3; t++) 
        if (t != fromPos && t != toPos) 
            break; 
    tot = 0; 
    tot += fun(n - 1, fromPos, t); 
    tot++; 
    tot += fun(n - 1, t, toPos); 
    return tot; 
} 
 
int main() { 
    int n; 
    cin >> n; 
    cout << fun(n, 1, 3) << endl; 
    return 0; 
} 
输入：5
输出：_________

{{ input(26) }}

完善程序

27. （双子序列最大和）给定一个长度为 n(3≤n≤1000) 的整数序列，要求从中选出两个连续子序列，使得这两个连续子序列的序列和之和最大，最终只需输出这个最大和。一个连续子序列的序列和为该连续子序列中所有数之和。要求：每个连续子序列长度至少为 1，且两个连续子序列之间至少间隔 1 个数。（第五空 4 分，其余 2.5 分）

#include <iostream> 
using namespace std;  
const int MAXN = 1000; 
int n, i, ans, sum; 
int x[MAXN]; 
int lmax[MAXN]; // lmax[i]为仅含 x[i]及 x[i]左侧整数的连续子序列的序列和中，最大的序列和 
int rmax[MAXN]; // rmax[i]为仅含 x[i]及 x[i]右侧整数的连续子序列的序列和中，最大的序列和 
int main() { 
    cin >> n; 
    for (i = 0; i < n; i++) 
        cin >> x[i]; 
    lmax[0] = x[0]; 
    for (i = 1; i < n; i++) 
        if (lmax[i - 1] <= 0) 
            lmax[i] = x[i]; 
        else 
            lmax[i] = lmax[i - 1] + x[i]; 
    for (i = 1; i < n; i++) 
        if (lmax[i] < lmax[i - 1]) 
            lmax[i] = lmax[i - 1]; 
        (1)    ; 
    for (i = n - 2; i >= 0; i--) 
        if (rmax[i + 1] <= 0) 
                (2)    ; 
        else 
                (3)    ; 
    for (i = n - 2; i >= 0; i--) 
        if (rmax[i] < rmax[i + 1]) 
                (4)    ; 
    ans = x[0] + x[2]; 
    for (i = 1; i < n - 1; i++) { 
        sum =     (5)    ; 
        if (sum > ans) 
            ans = sum; 
    } 
    cout << ans << endl; 
    return 0; 
}

1.{{ input(27) }}

2.{{ input(28) }}

3.{{ input(29) }}

4.{{ input(30) }}

5.{{ input(31) }}

28. （最短路径问题）无向连通图 G 有 n 个结点，依次编号为 0,1,2,…,(n−1)。用邻接矩阵的形式给出每条边的边长，要求输出以结点 0 为起点出发，到各结点的最短路径长度。

使用 Dijkstra 算法解决该问题：利用 dist 数组记录当前各结点与起点的已找到的最短路径长度；每次从未扩展的结点中选取 dist 值最小的结点 v 进行扩展，更新与 v 相邻的结点的 dist 值；不断进行上述操作直至所有结点均被扩展，此时 dist 数据中记录的值即为各结点与起点的最短路径长度。（第五空 2 分，其余 3 分）

#include <iostream> 
using namespace std; 
const int MAXV = 100; 
int n, i, j, v; int w[MAXV][MAXV]; // 邻接矩阵，记录边长 // 其中 w[i][j]为连接结点 i 和结点 j 的无向边长度，若无边则为-1 
int dist[MAXV]; int used[MAXV]; // 记录结点是否已扩展（0：未扩展；1：已扩展） 
int main() 
{ 
    cin >> n; 
    for (i = 0; i < n; i++) 
        for (j = 0; j < n; j++) 
            cin >> w[i][j]; 
dist[0] = 0;
for (i = 1; i < n; i++) 
        dist[i] = -1; 
    for (i = 0; i < n; i++) 
        used[i] = 0; 
    while (true) { 
            (1)    ; 
        for (i = 0; i < n; i++) 
            if (used[i] != 1 && dist[i] != -1 && (v == -1 ||     (2)    )) 
                    (3)    ; 
        if (v == -1) 
            break; 
            (4)    ; 
        for (i = 0; i < n; i++) 
            if (w[v][i] != -1 && (dist[i] == -1 ||     (5)    )) 
                dist[i] = dist[v] + w[v][i]; 
    } 
    for (i = 0; i < n; i++) 
        cout << dist[i] << endl; 
    return 0; 
}

1.{{ input(32) }}

2.{{ input(33) }}

3.{{ input(34) }}

4.{{ input(35) }}

5.{{ input(36) }}