一、单项选择题

1、在 Linux 系统终端中，以下哪个命令用于创建一个新的目录？

$2、0,1,2,3,4$ 中选取 4个数字，能组成（）个不同四位数（注：最小的四位数是 $1000$ 最大的四位数是 $9999$）。

3、假设 $n$ 是图的顶点的个数，$m$ 是图的边的个数，为求解某一问题有下面四种不同时间复杂度的算法。对于 $m=\Theta (n)$ 的稀疏图而言，下面的四个选项，哪一项的渐近时间复杂度最小（）。

4、假设有 $n$ 根柱子，需要按照以下规则依次放置编号为 $1,2,3,\cdots$ 的圆环：每根柱子的底 部固定，顶部可以放入圆环；每次从柱子顶部放入圆环时，需要保证任何两个相邻圆环的编号之和是一个完全平方数。请计算当有 4 根柱子时，最多可以放置（）个圆环

5、以下对数据结构的表述不恰当的一项是：

6、以下连通无向图中，（ ）一定可以用不超过两种颜色进行染色

7、最长公共子序列长度常常用来衡量两个序列的相似度。其定义如下：给定两个序列 X=x1​,x2​,x3​,⋯,xm​ 和 Y=y1​,y2​,y3​,⋯,yn​，最长公共子序列（LCS）问题的目标是找到一个最长的新序列 Z=z1​,z2​,z3​,⋯,zk​, 使得序列 $Z$ 既是序列 $X$ 的子序列，又是序列 $Y$ 的子序列，且序列 $Z$ 的长度 $k$ 在满足上述条件的序列里是最大的。 （注：序列 $A$ 是序列 $B$ 的子序列，当且仅当在保持序列 $B$ 元素顺序的情况下，从序列 $B$ 中删除若干个元素，可以使得剩余的元素构成序列 $A$。）则序列 ABCAAAABA 和 ABABCBABA 的最长公共子序列长度为（）

8、一位玩家正在玩一个特殊的掷骰子的游戏，游戏要求连续掷两次骰子，收益规则如下：玩家第一次掷出 $x$ 点，得到 $2x$ 元；第二次掷出 $y$ 点，当 $y=x$ 时玩家会失去之前得到的 $2x$ 元而当 $y\ne x$ 时玩家能保住第一次获得的 $2x$ 元。上述 x,y∈1,2,3,4,5,6。 例如：玩家第 一次掷出 $3$ 点得到 $6$ 元后，但第二次再次掷出 $3$ 点，会失去之前得到的 $6$ 元，玩家最终收益为 $0$ 元；如果玩家第一次掷出 $3$ 点、第二次掷出 $4$ 点，则最终收益是 $6$ 元。假设骰子掷出任意一点的概率均为 1/6，玩家连续掷两次般子后，所有可能情形下收益的平均值是多少？

9、假设我们有以下的 C++ 代码：

int a = 5, b = 3, c = 4;
bool res = a & b || c ^ b && a | c; 

请问，res 的值是什么？（）
提示：在 C++ 中，逻辑运算的优先级从高到低依次为：逻辑非（!）、逻辑与（&&）、逻辑或（||）。位运算的优先级从高到低依次为：位非（~）、位与（&）、位异或（^）、位或（|）。同时，双目位运算的优先级高于双目逻辑运算；逻辑非与位非优先级相同，且高于所有双目运算符。

10、假设快速排序算法的输入是一个长度为n 的已排序数组，且该快速排序算法在分治过程总是选择第一个元素作为基准元素。以下哪个选项描述的是在这种情况下的快速排序行为?

11、以下哪个命令，能将一个名为 main.cpp 的 C++ 源文件，编译并生成一个名为 main 的可执行文件？（    ）

12、在图论中，树的重心是树上的一个结点，以该结点为根时，使得其所有的子树中结点数最多的子树的结点数最少。一棵树可能有多个重心。请问下面哪种树一定只有一个重心？

12、如图是一张包含 $6$ 个顶点的有向图，但顶点间不存在拓扑序。如果要删除其中一条边，使这$6$ 个顶点能进行拓扑排序，请问总共有多少条边可以作为候选的被删除边？（）

15、现在用如下代码来计算 ，其时间复杂度为（）。

double quick_power(double x, unsigned n) {
    if (n == 0) return 1;
    if (n == 1) return x;
    return quick_power(x, n/2)* quick_power(x, n/2)* ((n&1)?x:1);
}