1. 数组作为函数参数传递的是（）
- 数组的首地址
- 数组元素个数
- 数组中各元素值
- 数组的大小
题目解析
考察的是数组传递给函数作为参数的原理
传递方式有如下三种：每种方式都会告诉编译器要接收一个指针，及数组的地址（首元素地址）
void myFunction(int *param) { // 形参是一个指针 }
void myFunction(int param[24]) { // 形参是一个已定义大小的数组 }
void myFunction(int param[]) { // 形参是一个未定义大小的数组 }
2. 在一个长度为 n 的顺序表中删除第 i 个元素，要移动（）个元素。如果要在第 i 个元素的之前插入一个元素，要移动（）个元素
- n-i, n-i+1
- n-i+1, n-i
- n-i, n-i
- n-i+1, n-i+1
题目解析
删除第 i 个元素，要移动后面 n-i 个元素
在第 i 个元素之前插入，要移动包括 i 在内的 n-i+1 个元素
3. 带头节点 head 的单向循环链表 L 为空的判断条件是（）
- head == NULL
- head -> next == NULL
- head -> next == head
- head != NULL
题目解析
基础概念，单向循环链表且带有头节点，判断为空，即循环链表只有头节点，自己指向自己
4. 队列和栈有什么区别（）
- 队列先进先出，栈后进先出
- 队列和栈都是先进先出
- 队列和栈都是后进先出
- 栈先进先出，队列后进先出
题目解析
相同点：从“数据结构”的角度看，它们都是线性结构，即数据元素之间的关系相同
不同点：栈（Stack）是限定只能在表的一端进行插入和删除操作的线性表。队列（Queue）是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。
它们是完全不同的数据类型，除了它们各自的基本操作集不同外，主要区别是对插入和删除操作的“限定”栈必须按“后进先出”的规则进行操作：比如说，小学老师批改学生的作业，如果不打乱作业本的顺序的话，那么老师批改的第一份作业一定是最后那名同学交的那份作业。
如果把所有作业看作是一个栈中的元素，那么最后一个同学交的作业本就是栈顶元素，而第一个同学交的，也就是最低端的作业本就是栈低元素，这就是对栈的读取规则队列必须按“先进先出”的规则进行操作：比如说，一些人去银行办理业务，一定是先去排队的最先得到服务，当然他也是第一个走出银行的（假设这些人都在一个窗口排队）。
如果把所有这些等候服务的人看作是队的元素，第一个人就是队头元素，相应的，最后一个人就是队尾元素，这是队列的读取规则
5. 已知某二叉树的前序为（1-2-3-4-5-6-7-8-9），中序为（2-3-1-6-7-8-5-9-4），则它的后续为（）
- 3-2-8-7-6-9-5-4-1
- 1-2-6-5-4-3-8-7-9
- 5-4-2-1-3-7-6-9-8
- 2-3-5-4-6-7-9-8-1
题目解析
根据前序遍历可以确定根节点为 1，再根据中序遍历可以确定该二叉树的左侧为左子树 23，其余为右子树。
再根据前序遍历得到左子树的根节点为 2，右子树的根节点为 4，然后递归下去就能恢复二叉树，然后后续遍历得到结果 3-2-8-7-6-9-5-4-1
6. 在任意一颗二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（）
- 不一定相同
- 都相同
- 都不相同
- 互为逆序
题目解析
前序序列：根节点 –> 左子树 –> 右子树
后序序列：左子树 –> 右子树 –> 根节点
结论：叶子节点位于左右两个分支上，前序和后序的遍历属性均是左子树在右子树之前（相对次序一定相同），和二叉树的样式无关
7. 采用递归方式对顺序表进行快速排序，下面关于递归次数的叙述中，正确的是（）
- 递归次数与初始数据的排序次序无关
- 每次划分后，先处理较长的分区可以减少递归次数
- 每次划分后，先处理较短的分区可以减少递归次数
- 递归次数与每次划分后得到的分区处理顺序无关
题目解析
递归次数取决于递归树，而递归树取决于轴枢的选择。树越平衡，递归次数越少
对分区的长短处理顺序，影响的是递归时对栈的使用内存，而不是递归次数
8. 优化递归程序的一般手段是（）
- 尾递归优化
- 循环优化
- 堆栈优化
- 停止值优化
题目解析
尾递归：指函数返回的时候，调用自身本身，并且 return 语句不能包含表达式。
这样，编译器或者解释器就可以把尾递归做优化，使递归本身无论调用多少次，都只占用一个栈帧，不会出现栈溢出的情况。
尾递归调用时，如果做了优化，栈不会增长。因此，无论多少次调用也不会导致栈溢出举例：斐波那契数列
普通的递归版本：
int fab(int n) {
if (n < 3) {
return 1;
} else {
return fab(n-1) + fab(n-2);
}
}尾递归（具有“线性迭代”特性的递归）版本：
int fab(int n, int b1=1, int b2=1, int c=3) {
if (n < 3) {
return 1;
}if (n==c) { return b1 + b2; } else { return fab(n, b2, b1+b2, c+1); }}
分析：以 fab(4) 为例子
普通递归：fab(4) = fab(3) + fab(2) = fab(2) + fab(1) + fab(2) = 1 + 1 + = 3，共 6 次调用
尾递归：fab(4, 1, 1, 3) = fab(4, 1, 2, 4) = 1 + 2 = 3，只有 2 次调用
9. 在快速排序、归并排序、插入排序、选择排序和冒泡排序中，使用分治思想的算法个数有（）个
- 1
- 2
- 3
- 4
题目解析
分支思想是很多高效算法的基础，如归并排序、快速排序、傅里叶变换（快速傅里叶变换）
10. 图的 DFS(Depth-First Search) 遍历思想实际上是二叉树（）遍历方法的推广
- 先序
- 中序
- 后序
- 层序
题目解析
深度先序，广度层序
11. 图的 BFS 生成树的树高比 DFS 生成树的树高（）
- 小或相等
- 小
- 大或相等
- 大
题目解析
BFS 是广度优先遍历，DFS 是深度优先遍历
对于一些特殊的图，比如只有一个顶点的图，其 BFS 生成树的树高和 DFS 生成树的树高相等
一般的图，根据图的 BFS 生成树和 DFS 树的算法思想，BFS 生成树的树高比 DFS 生成树的树高小
12. 假设现在只有 100M 的内存，需要对 1G 的数据进行排序，最合适的算法是（）
- 归并排序
- 插入排序
- 快速排序
- 冒泡排序
题目解析
归并排序的典型例子
首先内存只有 100M，而数据却有 1G，所以肯定没法一次性放到内存去排序，只能用外部排序
外部排序通常是使用多路归并排序，即将源文件分解成多个能够一次性装入内存的部分（比如这里的 100M）
分别把每一部分调入内存完成排序（根据情况选取适合的内排算法），然后对已经排序的子文件进行多路归并排序（胜者树或败者树）
13. 一个数据表有 51233 个元素，如果仅要求找出其中最大的 12 个元素，采用下列哪种算法比较节省时间（）
- 堆排序
- 希尔排序
- 快速排序
- 直接选择排序
题目解析
本题是比较常见的排序算法，TopK 问题，堆排序
14. 从 n 个数里面找最大的两个数理论上最少需要比较多少次（）
- 2logn
- 2logn-1
- n + logn - 2
- 2n - 3
题目解析
在 n 个数中找到最大的两个数的最少比较次数，可以考虑排序，首先建堆是时间复杂度为 O(n) 或比较 n-1 次，找到最大的一个。
然后调整堆，找到第二大元素，比较 logn-1，所以是 (n - 1) + (logn - 1) = n + logn - 2
15. 下面关于哈希查找的说法正确的是（）
- 哈希函数构造的越复杂越好，因此这样随机性好，冲突小
- 除留余数法是所有哈希函数中最好的
- 不存在特别好与坏的哈希函数，要视情况而定
- 若需在哈希表中删去一个元素，不管用任何方法解决冲突都只要简单地将该元素删去即可
题目解析
考察哈希，关于哈希有 xxx 的构造方法，具体哈希算法的好坏需要看情况而定，没有绝对的好与坏
A. 对于数据结构中的哈希函数有两个特点：简单，均匀性。
所谓简单就是可以很快地产生一个较好的 hash 值，均匀性是指所有的数据可以均匀地映射到各个 hash 值上，避免产生大部分数据映射到少数的 hash 值上B. 不同的 hash 函数有不同的适应场景，各有优缺点。主要的方法有，直接定址法、数字分析法、平方取中法、折叠法、随机数法和除留余数法
D. 对于空域法，还需要把冲突记录去掉
16. 若有序表的关键字序列为 (b,c,d,e,f,g,q,r,s,t)，则在二分查找关键字 b 的过程中，先后进行比较的关键字依次是（）
- f,c,b
- f,d,b
- g,c,d
- g,d,b
题目解析
考察二分查找，对于 (b,c,d,e,f,g,q,r,s,t)
第一次查找，left = 0, right = 9, mid = 0 + (9 - 0)/2 = 4，关键字是 f，f != b && f > b
第二次查找，left = 0, right = 3, mid = 0 + (3 - 0)/2 = 1, 关键字是 c，c != b && c > b
第三次查找，left = 0, right = 0, mid = 0 + (0 - 0)/2 = 0, 关键字是 b，b == b 查找结束
因此关键字依次是 (f,c,b)
17. 在最坏的情况下，下列排序方法中时间复杂度最小的是（）
- 冒泡排序
- 快速排序
- 插入排序
- 堆排序
题目解析
常见排序算法最坏时间复杂度比较，其中冒泡排序和插入排序 O(n^2)，快速排序最坏情况为 O(n^2)，只有堆排序比较稳定其复杂度为 O(nlogn)
18. 下列关于线性表、二叉平衡树、哈希表存储数据的优劣描述错误的是（）
- 哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制，那么可以直接将键作为数组的索引，那么所有的查找时间复杂度为 O(1)
- 线性表实现相对比较简单
- 平衡二叉树的各项操作的时间复杂度为 O(logn)
- 平衡二叉树的插入节点比较快
题目解析
哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制，那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为 O(1)。
如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存在平衡二叉树中插入节点要随时保证插入后整棵二叉树是平衡的，所以可能需要通过一次或多次树旋转来重新平衡这棵树
19. 下面关于动态规划说法正确的是（）
- 它是利用子结构，进行自底而上的算法设计
- 它需要后来多次计算的问题进行缓存，减少重复子问题的计算
- 它所求问题的整体最优解可以通过一系列局部最优的选择
- 它将分解后的子问题看成互相独立的
题目解析
动态规划利用最优子结构，自底向上从子问题的最优解逐步构成整个问题的最优解
用空间换时间只是一种技巧，不是动态规划的本质
贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到
与分治法不同的是，适用于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的，它们可能共享更小的子问题，被称为重叠子问题
20. 字符串 www.qq.com 所有非空子串（两个子串如果内容相同则只算一个）个数是（）
- 1024
- 1018
- 55
- 50
题目解析
非空子串的个数共有 n(n+1)/2 个，n = 10 即 55 个。由于相同子串算一个，其中 w(两次)、ww、q、.、有重复，故 55 - 5 = 50