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

{{ select(1) }}

• newdir
• mkdir
• create
• mkfolder

---

题目2:从0,1,2,3,4中选取4个数字，能组成多少个不同四位数？（注：最小的四位数是1000，最大的四位数是9999。）

{{ select(2) }}

• 96
• 18
• 120
• 84

---

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

{{ select(3) }}

• $O(m \sqrt{log n \cdot log log n})$
• $O\left(n^{2}+m\right)$
• $O\left(n^{2} / log m+m log n\right)$
• $O(m+n log n)$

---

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

{{ select(4) }}

• 7
• 9
• 11
• 5

---

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

{{ select(5) }}

• 队列是一种先进先出（FIFO）的线性结构
• 哈夫曼树的构造过程主要是为了实现图的深度优先搜索
• 散列表是一种通过散列函数将关键字映射到存储位置的数据结构
• 二叉树是一种每个结点最多有两个子结点的树结构

---

题目6:以下连通无向图中，哪一个一定可以用不超过两种颜色进行染色？

{{ select(6) }}

• 完全三叉树
• 平面图
• 边双连通图
• 欧拉图

---

题目7:最长公共子序列长度常常用来衡量两个序列的相似度。其定义如下：给定两个序列$X = \{x_{1}, x_{2}, x_{3}, \cdots, x_{m}\}$和$Y = \{y_{1}, y_{2}, y_{3}, \cdots, y_{n}\}$，最长公共子序列（LCS）问题的目标是找到一个最长的新序列$Z = \{z_{1}, z_{2}, z_{3}, \cdots, z_{k}\}$，使得序列Z既是序列X的子序列，又是序列Y的子序列，且序列Z的长度k在满足上述条件的序列里是最大的。（注：序列A是序列B的子序列，当且仅当在保持序列B元素顺序的情况下，从序列B中删除若干个元素，可以使得剩余的元素构成序列A。）则序列“ABCAAAABA”和“ABABCBABA”的最长公共子序列长度为？

{{ select(7) }}

• 4
• 5
• 6
• 7

---

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

{{ select(8) }}

• 7元
• $\frac{35}{6}$元
• $\frac{16}{3}$元
• $\frac{19}{3}$元

---

题目9:假设我们有以下的C++代码：

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

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

• true
• false
• 1
• 0

---

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

{{ select(10) }}

• 快速排序对于此类输入的表现最好，因为数组已经排序。
• 快速排序对于此类输入的时间复杂度是$O(n log n)$。
• 快速排序对于此类输入的时间复杂度是$O(n^{2})$。
• 快速排序无法对此类数组进行排序，因为数组已经排序。

---

题目11:以下哪个命令，能将一个名为“main.cpp”的C++源文件，编译并生成一个名为“main”的可执行文件？

{{ select(11) }}

• g++ -o main main.cpp
• g++ -o main.cpp main
• g++ main -o main.cpp
• g++ main.cpp -o main.cpp

---

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

{{ select(12) }}

• 4个结点的树
• 6个结点的树
• 7个结点的树
• 8个结点的树

---

题目13:如图是一张包含6个顶点的有向图，但顶点间不存在拓扑序。如果要删除其中一条边，使这6个顶点能进行拓扑排序，请问总共有多少条边可以作为候选的被删除边？（注：题目中提及的图未在文本中显示，以题目原始图形为准）

{{ select(13) }}

• 1
• 2
• 3
• 4

---

题目14:若$n=\sum_{i=0}^{k} 16^{i} \cdot x_{i}$，定义$f(n)=\sum_{i=0}^{k} x_{i}$；其中$x_{i} \in \{0, 1, \cdots, 15\}$。对于给定自然数$n_{0}$，存在序列$n_{0}, n_{1}, n_{2}, \cdots, n_{m}$，其中对于$1 ≤i ≤m$都有$n_{i}=f(n_{i-1})$，且$n_{m}=n_{m-1}$，称$n_{m}$为$n_{0}$关于f的不动点。问在$100_{16}$至$1A0_{16}$中，关于f的不动点为9的自然数个数为？

{{ select(14) }}

• 10
• 11
• 12
• 13

---

题目15:现在用如下代码来计算$x^n$，其时间复杂度为？

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);
}

{{ select(15) }}

• $O(n)$
• $O(1)$
• $O(log n)$
• $O(n log n)$