爱奇艺2018秋季校招算法工程师（第三场）

若图G采用邻接表存储，邻接表中有奇数个表结点，下列选项正确的是__________。

以下算法属于有监督算法的是

以下哪种排序算法在最坏情况下的时间复杂度最小？

设栈S初始状态为空。元素1,2,3,4,5,6依次通过栈S，若出栈的顺序为4,6,5,3,2,1，则栈S的容量至少应该为？

在Linux系统中，因为某些原因造成了一些进程变成孤儿进程，那么这些孤儿进程会被以下哪一个系统进程接管？

一个完整的括号字符串定义规则如下:
1、空字符串是完整的。
2、如果s是完整的字符串，那么(s)也是完整的。
3、如果s和t是完整的字符串，将它们连接起来形成的st也是完整的。
例如，"(()())", ""和"(())()"是完整的括号字符串，"())(", "()(" 和 ")"是不完整的括号字符串。
牛牛有一个括号字符串s,现在需要在其中任意位置尽量少地添加括号,将其转化为一个完整的括号字符串。请问牛牛至少需要添加多少个括号。 输入描述： 输入包括一行,一个括号序列s,序列长度length(1 ≤ length ≤ 50). s中每个字符都是左括号或者右括号,即'('或者')'.输入样例： (()(() 输出描述： 输出一个整数,表示最少需要添加的括号数输出样例 2

牛牛选择了一个正整数X,然后把它写在黑板上。然后每一天他会擦掉当前数字的最后一位,直到他擦掉所有数位。 在整个过程中,牛牛会把所有在黑板上出现过的数字记录下来,然后求出他们的总和sum.
例如X = 509, 在黑板上出现过的数字依次是509, 50, 5, 他们的和就是564.
牛牛现在给出一个sum,牛牛想让你求出一个正整数X经过上述过程的结果是sum. 输入描述： 输入包括正整数sum(1 &le sum &le 10^18)输入样例： 564 输出描述： 输出一个正整数,即满足条件的X,如果没有这样的X,输出-1。输出样例 509

牛牛学习了冒泡排序,并写下以下冒泡排序的伪代码,注意牛牛排序的数组a是从下标0开始的。

BubbleSort(a):
    Repeat length(a)-1 times:
        For every i from 0 to length(a) - 2:
            If a[i] > a[i+1] then:
                 Swap a[i] and a[i+1]

牛牛现在要使用上述算法对一个数组A排序。
在排序前牛牛允许执行最多k次特定操作(可以不使用完),每次特定操作选择一个连续子数组,然后对其进行翻转,并且k次特定操作选择的子数组不相交。
例如A = {1, 2, 3, 4, 5, 6, 7}, k = 1,如果牛牛选择的子数组是[2,4](注意下标从0开始),那么翻转之后的数组变为A = {1, 2, 5, 4, 3, 6, 7}。
牛牛知道冒泡排序的效率一定程度上取决于Swap操作次数,牛牛想知道对于一个数组A在进行k次特定操作之后,再进行上述冒泡排序最少的Swap操作次数是多少? 输入描述： 输入包括两行,第一行包括两个正整数n和k(2 &le n &le 50, 1 &le k &le 50),表示数组的长度和允许最多的特定操作次数。 第二行n个正整数A[i](1 &le A[i] &le 1000),表示数组内的元素,以空格分割。输入样例： 3 2 2 3 1 输出描述： 输出一个整数,表示在执行最多k次特定操作之后,对数组进行上述冒泡排序需要的Swap操作次数。输出样例 1