一、单项选择题

1、在 Linux 系统终端中，用于切换工作目录的命令为（     ）。

2、你同时用 time 命令和秒表为某个程序在单核 CPU 的运行计时。假如 time 命令的输出如下：

real   0m30.721s 
user   0m24.579s 
sys    0m6.123s

以下最接近秒表计时的时长为（ ）。

3、若元素 a、b、c、d、e、f 依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次退栈操作，则不可能得到的出栈序列是（ ）。

4、考虑对 n 个数进行排序，以下最坏时间复杂度低于 O(n^2) 的排序方法是（    ）。

5、假设在基数排序过程中，受宇宙射线的影响，某项数据异变为一个完全不同的值。请问排序算法结束后，可能出现的最坏情况是（ ）。

6、计算机系统用小端（Little Endian）和大端（Big Endian）来描述多字节数据的存储地 址顺序模式，其中小端表示将低位字节数据存储在低地址的模式、大端表示将高位字节数据存储在低地址的模式。在小端模式的系统和大端模式的系统分别编译和运行以下 C++代码段表示的程序，将分别输出什么结果？（ ）

unsigned x = 0xDEADBEEF; 
unsigned char *p = (unsigned char *)&x; 
printf("%X", *p);

7、一个深度为 5（根结点深度为 1）的完全 3 叉树，按前序遍历的顺序给结点从 1 开始编号，则第 100 号结点的父结点是第（ ）号。

8、强连通图的性质不包括（ ）：

9、每个顶点度数均为 2 的无向图称为“2 正规图”。由编号为从 1 到 n 的顶点构成的所有 2 正规图，其中包含欧拉回路的不同 2 正规图的数量为（ ）。

10、共有 8 人选修了程序设计课程，期末大作业要求由 2 人组成的团队完成。假设不区分每个团队内 2 人的角色和作用，请问共有多少种可能的组队方案。（ ）。

小明希望选到形如“省 A·LLDDD ”的车牌号。车牌号在“·”之前的内容固 的 5 位号码中，前 2 位必须是大写英文字母，后 3 位必须是阿拉伯数字（L代表 A 至 Z，DDD 表示 0 至 9，两个L和三个DDD 之间可能相同也可能不同）。请问总共有多少个可供选择的车牌号。（ ）

12、给定地址区间为 0~9 的哈希表，哈希函数为 h(x) = x % 10，采用线性探查的冲突解决策略（对于出现冲突情况，会往后探查第一个空的地址存储；若地址 9 冲突了则从地址 0 重新开始探查）。哈希表初始为空表，依次存储(71, 23, 73, 99, 44, 79, 89)后，请问 89 存储在哈希表哪个地址中。（ ）

13、对于给定的 n，分析以下代码段对应的时间复杂度，其中最为准确的时间复杂度为（ ）。

int i, j, k = 0;
for (i = 0; i < n; i++) {
    for (j = 1; j < n; j*=2) {
        k = k + n / 2;
    }
}

14、以比较为基本运算，在 n 个数的数组中找最大的数，在最坏情况下至少要做（ ）次运算。

15、ack 函数在输入参数“(2,2)”时的返回值为（）。

unsigned ack(unsigned m, unsigned n) {
    if (m == 0) return n + 1;
    if (n == 0) return ack(m - 1, 1);
    return ack(m - 1, ack(m, n - 1));
}