一、单项选择题(共15题，每题2分，共计30分；每题有且仅有一个正确选项)
1. 在Linux系统终端中，以下哪个命令用于创建一个新的目录?（ ）
A. newdir
B. mkdir
C. create
D. mkfolder
答案：B，计算机基础，Linux的基础操作知识。
2. 0,1,2,3,4中选取4个数字，能组成（ ）个不同四位数。(注：最小的四位数是1000,最大的四位数是9999。)
A. 96
B. 18
C. 120
D. 84
答案：A，组合计数，分步，千位有4种选择，百位4种，十位3种，个位2种，乘法原理，4*4*3*2=96。
3. 假设n是图的顶点的个数，m是图的边的个数，为求解某一问题有下面四种不同时间复杂度的算法。对于m=θ(n)的稀疏图而言，下面的四个选项，哪一项的渐近时间复杂度最小。
A. O(m√logn·loglogn )
B. O(n²+m)
C. O(n²/logm+mlogn)
D. O(m+nlogn)
答案：A，图论，m和n同一级别，可以把所有的m换成n来比较，loglogn”替换为“>=”,那么原输出与现输出的大小关系为（ ）
A. 一定小于
B. 一定小于等于且不一定小于
C. 一定大于等于且不一定大于
D. 以上三种情况都不对
答案：B，变成了差值小于x的数对个数，相当于判断条件变严格了，答案可能会变大或者不变。
33. 当输入为“5 8 2 -5 3 8 -12”时，输出为（ ）
A.“13”
B.“14”
C.“8”
D.“15”
答案：B，排序后是-12 -5 2 3 8，差值不超过14的数对是8，差值不超过13的数对是7。
阅读程序题（3）整体解析：
读f函数可知，f0中的a数组是从小到大排序的，a[j]＜a[i]-m，j是小于a[i]-m的最后一个位置（或者0），所以s是计算序列a中差值不超过m的数对的个数。
f0判断满足这个条件的数对个数是否>=k。本题需要看懂题目才方便做题。
f函数是一个二分查找，g=0，h=a.back()-a[0]，分别是条件最紧和条件最宽松，返回值是最小的x，满足a中差值不超过x的数对个数>=k。
三、完善程序(单选题，每小题3分，共计30分)
1、(第k小路径)给定一张n个点m条边的有向无环图，顶点编号从0到n-1。对于一条路径，我们定义"路径序列"为该路径从起点出发依次经过的顶点编号构成的序列。
求所有至少包含一个点的简单路径中，“路径序列"字典序第k小的路径。保证存在至少k条路径，上述参数满足1≤n,m≤105和1≤k≤1018。
在程序中，我们求出从每个点出发的路径数量。超过1018的数都用1018表示。然后我们根据k的值和每个顶点的路径数量，确定路径的起点，然后可以类似地依次求出路径中的每个点。
试补全程序：
34. ①处应填（ ）
A. k >= f[u]
B. k f[u]
D. k< f[u]
答案：B，next函数是在cand队列中查找第k条在哪个结点为起点的路径中，所以如果k1
D. deg[v]>o
答案：A，入度为0的点入队列，--deg[v]在入队列的后面执行，所以这里判断deg[v]==1；题目保证了是DAG，所以整个队列中一定会有n个结点。
36. ③处应填（ ）
A. std::min(f[u]+ f[v],LIM)
B. std::min(f[u]+ f[v]+ 1,LIM)
C. std::min(f[u]* f[v],LIM)
D. std::min(f[u]*(f[v]+ 1),LIM)
答案：A，动态规划，计算u为起点的路径树，f[u]=1是只有自身的一条路，枚举所有子结点的路径数，累加。先把Q逆序是因为要拓扑序靠前的结点计算依赖拓扑序靠后的结点。
37. ④处应填（ ）
A. u!=-1
B. !E[u].empty()
C. k >0
D. k >1
答案：D，next函数执行后我们知道了第k小的路径在u开头的路径中，当k==1时，这条路径就只有u一个结点，如果k>1，则需要从u的子结点中继续找。
38. ⑤处应填（ ）
A. k += f[u]
B. k -= f[u]
C. --k
D. ++k
答案：C，--k表示减去u为唯一结点的那条路径。后两空相对比较难。
完善程序题1 整体解析：
拓扑排序+动态规划，基本思路是先拓扑排序，然后按从后往前的顺序计算每个结点为起点的路径数，然后按编号排序找第k小路径的起点。
2、(最大值之和)给定整数序列ao,a₁,a₂……an,求该序列所有非空连续子序列的最大值之和。上述参数满足1≤n≤105和1≤ai≤108。
一个序列的非空连续子序列可以用两个下标I和r(其中0≤l≤r≤n)表示，对应的序列为al,al+1,al+2,……ar。两个非空连续子序列不同，当且仅当下标不同。
例如，当原序列为[1,2,1,2] 时，要计算子序列[1],[2],[1],[2],[1,2],[2,1],[1,2],[1,2,1],[2,1,2],[1,2,1,2]的最大值之和，答案为18。注意[1,1]和[2,2]虽然是原序列的子序列，但不是连续子序列，所以不应该被计算。
另外，注意其中有一些值相同的子序列，但由于他们在原序列中的下标不同，属于不同的非空连续子序列，所以会被分别计算。解决该问题有许多算法，以下程序使用分治算法，时间复杂度O(nlogn).
尝试补全程序：
39. ①处应填（ ）
A. pre[i]=std::max(pre[i-1],a[i-1])
B. pre[i + 1]= std::max(pre[i],pre[i +1])
C. pre[i]= std::max(pre[i - 1],a[i])
D. pre[i]= std::max(pre[i],pre[i - 1])
答案：D，std::vectorpre(a + mid, a+r); 复制从a[mid]到a[r-1]的数组。然后计算这个数组的前缀最大值，即pre[i]是从0到i的数组的最大值。
40. ②处应填（ ）
A. a[j]< max
B. a[j]< a[i]
C. pre[j - mid]< max
D. pre[j - mid]> max
答案：B，找最大值在前半段还是后半段的分界点，比较容易混淆的是C选项，因为此时max还没有更新，所以不能让a[j]或pre[j-mid]跟max来比，只能跟a[i]来比。
41. ③处应填（ ）
A. (long long)(j - mid)* max
B. (long long)(j - mid)*(i - 1)* max
C. sum[j - mid]
D. sum[j - mid]*(i - 1)
答案：A，i为起点，终点在后半段， 且最大值在前半段的个数是(j-mid)个，此时最大值都是max。
42. ④处应填（ ）
A. (long long)(r - j)* max
B. (long long)(r - j)*(mid - i)* max
C. sum[r - mid]- sum[j - mid]
D. (sum[r - mid]- sum[j - mid])*(mid - i)
答案：C，i为起点，终点在后半段，且最大值在后半段的情况，最大值的和通过sum前缀和数组计算。
43. ⑤处应填（ ）
A. solve(0, n)
B. solve(0, n - 1)
C. solve(1,n)
D. solve(1, n - 1)
答案：A，因为line 12-14行，可以看到二分的结束条件是l+1==r，而且此时取l的值，也就是说[l,r)，左闭右开的区间。
完善程序题2 整体解析：
分治算法，分为三部分来计算，1) 起点终点都在前半段；2) 都在后半段；3) 起点在前半段、终点在后半段。前两部分递归解决，难点在于第三部分。预处理后半段的两个数组，pre数组表示前缀数组的最大值（pre数组一定是单调不下降的），sum数组是pre数组前缀和。然后用双指针，前半段从后往前，维护最大值，后半段从前往后。