1. 在Linux系统终端中,以下那个命令用于创建一个新的目录?( )
- A.newdir
- B.mkdir
- C.create
- D.mkfold
2. 由0,1,2,3,4中选取4个数字,能组成( )个不同四位数注:最小的四位数是1000最大的四位数是9999)
3. 假设n 是图的顶点的个数,m 是图的边的个数,为求解某一问题有下面四种不同时间复杂度的算法对于m=O(n)的稀疏图而言下面的四个选项,哪一项的渐近时间复杂度最小。( )
- A.O(m*sqrt(logn)*loglogn)
- B.O(n^2+m)
- C.O(n^2/logm+mlogn)
- D.O(m+nlogn)
4. 假设有n 根柱子,需要按照以下规则依次放置编号为1、2、3、...的圆环:每根柱子的底部固定,顶部可以放入圆环,每次从柱子顶部放入圆环时,需要保证任何两个相邻圆环的编号之和是一个完全平方数。请计算当有4根柱子时,最多可以放置( )个圆环。
5. 以下对数据结构的表述不恰当的一项是:( )
- A.队列是一种先进先出(FIFO)的线性结构
- B.哈夫曼树的构造过程主要是为了实现图的深度优先搜索
- C.散列表是一种通过散列函数将关键字映射到存储位置的数据结构
- D.二又树是一种每个结点最多有两个子结点的树结构
6. 以下连通无向图中,( )一定可以用不超过两种颜色进行染色
7. 最长公共子序列长度常常用来衡量两个序列的相似度。其定义如下:给定两个序列X={x1,x2,x3,...xm}和Y={y1,y2,y3...yn},最长公共子序列(LCS)问题的目标是找到一个最长的新序列Z= {z1,z2,z3...zk},使得序列 既是序列X 的子序列,又是序列Y的子序列,且序列Z的长度k 在满足上述条件的序列里是最大的。(注:序列A 是序列B 的子序列,当且仅当在保持序列B 元素顺序的情况下,从序列B中删除若千个元素,可以使得剩余的元素构成序列A。测序列“ABCAAAABA”和“ABABCBABA”的最长公共子序列长度为( )
8. 一位玩家正在玩一个特殊的掷骰子的游戏,游戏要求连续掷两次骰子,收益规则如下:玩家第一次掷出x点,得到2x元;第二次掷出y点,当y=x 时玩家会失去之前得到的2x元而当y!=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的已排序数组,且该快速排序算法在分治过程总是选择第1个元素作为基准元素。以下哪个选项描述的是在这种情况下的快速排序行为?( )
- A.快速排序对于此类输入的表现最好因为数组已经排序
- B.快速排序对于此类输入的时间复杂度是O(nlogn)。
- C.快速排序对于此类输入的时间复杂度是O(n^2)
- D.快速排序无法对此类数组进行排序因为数组已经排序
11. 以下哪个命令,能将一个名为“main.cpp”的 C++源文件,编译并生成一个名为"main“的可执行文件? ( )
- A.g++ -o main main.cpp
- B.g++ -o main.cpp main
- C.g++ main -o main.cpp
- D.g++ main.cpp -o main.cpp
12. 在图论中,树的重心是树上的一个结点,以该结点为根时,使得其所有的子树中结点数最多的子树的结点数最少。一棵树可能有多个重心。请问下面哪种树一定只有一个重心( )
- A.4个结点的树
- B.6个结点的树
- C.7个结点的树
- D.8个结点的树
13. 如图是一张包含6个顶点的有向图,但顶点间不存在拓扑序。如果要删除其中一条边,使这6个顶点能进行拓扑排序,请问总共有多少条边可以作为候选的被删除边?
14. 若$n=\sum_{i=0}^k 16^i*X_i$,定义$f(n)=\sum_{i=1}^k x_i$;其中$x_i\to{0,1,...,15}$。对于给定自然数$n_0$,存在序列$n_0,n_1,..., 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的自然数个数为( )。
15. 现在用如下代码来计算x^n,其时间复杂度为( )
double quick_power(double x,unsigned int 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);
}
- A.O(n)
- B.O(1)
- C.O(logn)
- D.O(nlogn)