2020-爱奇艺测开第一场
- 求递归方程T(n)=4T(n/2)+n 的解 ( )
答案：O(n^2)
题解：
主定理提供了分治方法带来的递归表达式的渐进复杂度分析.
将规模为n的问题通过分治,得到a个规模为n/b的问题,每次递归带来的额外计算为c(n^d)
即T(n)=a(n/b)+c(n^d)
若 a=b^d , T(n)=O(n^dlog(n))
若 a<b^d , T(n)=O(n^d)
若a>b^d , T(n)=O(n^logb(a))
该题 a=4,b=2,d=1,a>2 T(n)=O(n^logb(a))=O(n^2) - 下列关于动态规划算法说法错误的是（）
答案：当某阶段的状态确定后，当前的状态是对以往决策的总结并且直接影响未来的决策
题解
动态规划:
1.递推关系式.
2.子问题重叠.
3.最优子结构.
无后效性。即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。
3. 使用shell脚本比较2个数字，这2个数字由用户运行脚本时通过参数传入，下面哪项所示代码能够正确实现此功能？（）
答案
#!/bin/bash
x=2
if [ y ]
then
echo “x is greater than y”
else
echo “y is greater than x”
fi
题解
shell 获取命令行输入的参数：$1-9表示第1到9参数
./a.sh 1 2 3 4 5
则1是 1，后面类推。
shell比较数值：
运算符 含义
-gt 是否大于
-ge 是否大于等于
-ne 是否不等于
-lt 是否小于
-le 是否小于等于
4. 哪种模式下提供一种简单的单任务环境（ ）
答案
实模式
题解
80386开始，CPU有三种工作方式：实模式，保护模式和虚拟8086模式。只有在刚刚启动的时候是real-mode，等到操作系统运行起来以后就切换到protected-mode。实模式只能访问地址在1M以下的内存称为常规内存，我们把地址在1M 以上的内存称为扩展内存。在保护模式下，全部32条地址线有效，可寻址高达4G字节的物理地址空间; 扩充的存储器分段管理机制和可选的存储器分页管理机制，不仅为存储器共享和保护提供了硬件支持，而且为实现虚拟存储器提供了硬件支持; 支持多任务，能够快速地进行任务切换(switch)和保护任务环境(context); 4个特权级和完善的特权检查机制，既能实现资源共享又能保证代码和数据的安全和保密及任务的隔离; 支持虚拟8086方式，便于执行8086程序。
5. 下列哪些属于软件测试的基本过程（ ）
答案
单元测试 集成测试 确认测试
题解
软件测试的过程：单元测试、集成测试、系统测试、验收测试
6. 假设有一个函数中有三个变量，其中1980<=a<=2016,1<=b<=12,1<=c<=31,若采用边界值分析法设计测试用例，至少需要（ ）个测试用例
答案
13
题解
边界值分析方法的归纳：通过变量数量和通过值域的种类，归纳变量数量很容易，如果有一个n变量函数，使除一个以外的所欲变量取正常值，使剩余的那个变量取最小值、略高于虽小值、正常值、略低于最大值和最大值，对每个变量都重复进行。如此，对于一个n变量函数，采用边界值分析会产生4N+1个测试用例。
