考试题目：单项选择题 15 道，4 分/题，编程题 2 道，20 分/题
考试时长：180分钟
单项选择题（4 分/题）
数组相关
- 将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（C）
A. 100
B. 40
C. 55
D. 80
难度：3星（总5星）
【参考解析】主对角线都存：10个，剩下的90个只存一半45个，共55个。
链表相关
- 下面哪项不是链表优于数组的特点?（D）
A. 方便删除
B. 方便插入
C. 长度可变
D. 存储空间小
难度：2星（总5星）
【参考解析】链表方便删除和插入，只需知道结点和要插入的信息即可；长度可变，一般链表是动态分配内存空间；链表的结点信息至少包含数据域和指针域，相同数据下：数组的大小是链表大小的子集，所以选D。
链表、复杂度相关
- 对于长度为n的线性表，建立其对应的单链表的时间复杂度为（C）。
A. O(1)
B. O(log2n)
C. O(n)
D. O(n^2)
难度：2星（总5星）
【参考解析】本题主要考查的知识点是单链表的建立。无论采用什么方式建立单链表，都需要扫描这n个元素，边扫描边创建单链表中的结点并链接起来，其时间复杂度为O(n)。
链表相关
- 需要频繁的插入删除操作使用什么结构比较合适?(C)
A. 数组
B. 队列
C. 链表
D. 栈
难度：2星（总5星）
【参考解析】数组和链表方式实现顺序表，各有其优缺点。数组的优点是较高的存储效率和快速的随机存取，缺点是数组不能动态的增长，并且在插入和删除时，平均会移动n/2的数据，不适用于随机位置插入和删除很频繁的操作。而链表家恰好具备此优点，一般来说链表的插入和删除基本是固定时间的，链表的缺点是不太适合于随机访问，而在连续访问时，链表也具有很好的表现。
队列(queue)和栈是一种操作受限的线性表。栈的操作受限表现在插入和删除只能对栈顶元素进行，删除的元素永远是最新插入的，即操作遵循后入先出（LIFO）原则。队列中的操作原则与栈的相反。删除的元素是最早插入到队列中的，就像排队一样，排在最前面的人将最先从队伍中出列。这样的操作原则常常称作先入先出。所以对于栈和队列的频繁随机插入删除不合适。
队列相关
已知循环队列存储在一维数组A[0..n-1]中，且队列非空时 front 和 rear 分别指向队头和队尾元素。若初始时队列为空，且要求第 1 个进入队列的元素存储在 A[0]处，则初始时 front和 rear 的值分别是（B ）。
A. 0， 0
B. 0， n-1
C. n-1， 0
D. n-1， n-1
难度：4星（总5星）
【参考解析】插入时，队头指针不变，队尾指针后移一位。该题约定队列非空时 front 和 rear 分别指向队头和队尾元素，即插入第一个元素在下标为0的位置后，队头队尾指针皆指向A[0]，此时可以反推出插入前，队头指针仍旧指向下标0，而队尾指针应指向前一位，也就是下标n-1的位置。注意，这道题的约定与大多数题约定队列为空时front=rear=0是不一样的约定，都是根据题意解题。
数组相关
- 在一个长度为n的顺序表中删除第i个元素，要移动_个元素。如果要在第i个元素前插入一个元素，要后移_个元素。(A)
A. n-i，n-i+1
B. n-i+1，n-i
C. n-i，n-i
D. n-i+1，n-i+1
难度：2星（总5星）
【参考解析】：删除第i个元素，要移动后面n-i个元素。在第i个元素之前插入，要移动包括i在内的n-i+1个元素。（注：一般约定俗成的第几个元素，没有特别指明，我们是从1开始计数的。如果从0开始计数，长度为n的数组，那么它最后一个元素对应的索引是n-1，对应的删除和插入则分别为n-i-1和n-i。故答案为A）
二叉树相关
- 二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK;中序遍历：HFIEJKG.则二叉树根结点为（A）
A. E
B. F
C. G
D. H
难度：1星（总5星）
【参考解析】先序遍历是先遍历二叉树的根结点，由先序遍历为：EFHIGJK则知根结点为：E
二叉树相关
- 在一棵二叉树上第四层的结点数最多是（A）
A. 8
B. 9
C. 10
D. 11
难度：1星（总5星）
【参考解析】二叉树第1层最多1个结点，第二层最多2个结点，第三层最多4个结点，第n层最多2^(n-1)个结点，因此第4层最多2^(4-1)=8个结点。
DFS相关
- 下列关于树的深度优先搜索算法描述错误的是？(B)
A. 按照某种条件往前试探搜索，如果前进中遭到失败，则退回头另选通路继续搜索，直到找到条件的目标为止。
B. 先访问该节点所有的子节点，遍历完毕后选取它未访问过的子节点重复上述过程，直到找到条件的目标为止。
C. 假设树的顶点数为V，则算法的空间复杂度为O(V)
D. 深度优先算法非常适合使用递归来实现
难度：3星（总5星）
【参考解析】B选项描述的是广度优先遍历（BFS）。
贪心相关
- 有关贪心法叙述正确的是（A）
A. 采用局部最优策略
B. 采用全局最优策略
C. 在贪心法中采用逐步构造最优解的方法
D. 把问题分解为简单的问题求解
难度：3星（总5星）
【参考解析】贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。
二分查找相关
- 二分查找的时间复杂度（C）
A. O(N*log(N))
B. O(N)
C. O(log(N))
D. O(N^2)
难度：4星（总5星）
【参考解析】二分法每次比较会去掉一半的数据，也就是说比较次数为n,数据为m个则2^n>=m,m=log(N),时间复杂度为O(log(N))
- 对有序数组{2、11、15、19、30、32、61、72、88、90、96}进行二分查找，则成功找到15需比较（C）次
A. 3
B. 4
C. 2
D. 5
难度：3星（总5星）
【参考解析】
0 1 2 3 4 5 6 7 8 9 10
2、11、15、19、30、32、61、72、88、90、96
第一次 index=（0+10）/2=5 对应32 ； 比15大 所以下次范围是 0到4
第二次 index=（0+4）/2=2 对应15 找到
哈希相关
- 以下哪个不属于单向哈希表的特征（假设没有冲突）（B）
A. 它把任意长度的信息转换成固定的长度输出
B. 它把固定的信息转换成任意长度信息输出
C. 根据特定的哈希值，它可以找到对应的原信息值
D. 不同的信息很难产生一样的哈希值
难度：3行（总5星）
【参考解析】哈希表（Hash Table）是一种根据关键字直接访问内存存储位置的数据结构。通过哈希表，数据元素的存放位置和数据元素的关键字之间建立起某种对应关系。
A，hash函数可以把字符串等任意长度的输入映射成固定长度的整数，也就是哈希值
B，与A说法相反，错误
C，哈希表建立了哈希值与原值信息存储之间的联系，可以通过哈希值查找到原值信息
D，不同的信息产生相同的哈希值叫哈希冲突。设计哈希函数应尽量避免哈希冲突。因此一般很难冲突。
分治相关
- 下面哪个不是使用分治法的特征（ C ）
A. 该问题可以分解为若干个规模较小的相同问题
B. 子问题的解可以合并为该问题的解
C. 子问题必须是一样的
D. 子问题之间不包含公共的子问题
难度：3星（总5星）
【参考解析】分治法是建基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
回溯、复杂度相关
- n皇后最坏情况下的时间复杂度为：（C）
A. O(n)
B. O(n^2)
C. O(n^n)
D. O(n^3)
难度：4星（总5星）
【参考解析】一个n*n的棋盘，要在上面放n个皇后。规则：两个皇后之间如果是同列、同行、同对角线它们会互相攻击。也就是说：棋盘上的任意两个皇后皇后
不能为同列、同行、同对角线。
对于这个问题、当n不大的时候，可以用穷举法实现。对于n皇后，每一行有n个位置可以放，一共n行。就会有n的n次方种情况。对于这些情况、再一一判断是不是满足情况。
编程题（20 分/题）
- 四数之和（力扣第 18 题）
难度：中等
【参考答案】
- C++ 解法：
自动检测
class Solution{
public:
vector
sort(nums.begin(),nums.end());
vector
if(nums.size()<4)
return res;
int a,b,c,d,_size=nums.size();
for(a=0;a<=_size-4;a++){
if(a>0&&nums[a]==nums[a-1]) continue; //确保nums[a] 改变了
for(b=a+1;b<=_size-3;b++){
if(b>a+1&&nums[b]==nums[b-1])continue; //确保nums[b] 改变了
c=b+1,d=_size-1;
while(c
else if(nums[a]+nums[b]+nums[c]+nums[d]>target)
d—;
else{
res.push_back({nums[a],nums[b],nums[c],nums[d]});
while(c
while(c
c++;
d—;
}
}
}
}
return res;
}
};
作者：misakasagiri-2
链接：https://leetcode-cn.com/problems/4sum/solution/shuang-zhi-zhen-jie-fa-can-zhao-san-shu-zhi-he-ge-/
来源：力扣（LeetCode）
- Python 解法（国际版力扣高票答案）：
The core is to implement a fast 2-pointer to solve 2-sum, and recursion to reduce the N-sum to 2-sum. Some optimization was be made knowing the list is sorted.
自动检测
def fourSum(self, nums, target):
nums.sort()
results = []
self.findNsum(nums, target, 4, [], results)
return results
def findNsum(self, nums, target, N, result, results):
if len(nums) < N or N < 2: return
# solve 2-sum
if N == 2:
l,r = 0,len(nums)-1
while l < r:
if nums[l] + nums[r] == target:
results.append(result + [nums[l], nums[r]])
l += 1
r -= 1
while l < r and nums[l] == nums[l - 1]:
l += 1
while r > l and nums[r] == nums[r + 1]:
r -= 1
elif nums[l] + nums[r] < target:
l += 1
else:
r -= 1
else:
for i in range(0, len(nums)-N+1): # careful about range
if target < nums[i]N or target > nums[-1]N: # take advantages of sorted list
break
if i == 0 or i > 0 and nums[i-1] != nums[i]: # recursively reduce N
self.findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results)
return
Just revisited and clean the code
自动检测
def fourSum(self, nums, target):
def findNsum(nums, target, N, result, results):
if len(nums) < N or N < 2 or target < nums[0]N or target > nums[-1]N: # early termination
return
if N == 2: # two pointers solve sorted 2-sum problem
l,r = 0,len(nums)-1
while l < r:
s = nums[l] + nums[r]
if s == target:
results.append(result + [nums[l], nums[r]])
l += 1
while l < r and nums[l] == nums[l-1]:
l += 1
elif s < target:
l += 1
else:
r -= 1
else: # recursively reduce N
for i in range(len(nums)-N+1):
if i == 0 or (i > 0 and nums[i-1] != nums[i]):
findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results)
results = []
findNsum(sorted(nums), target, 4, [], results)
return results
passing pointers, not sliced list
自动检测
def fourSum(self, nums, target):
def findNsum(l, r, target, N, result, results):
if r-l+1 < N or N < 2 or target < nums[l]N or target > nums[r]N: # early termination
return
if N == 2: # two pointers solve sorted 2-sum problem
while l < r:
s = nums[l] + nums[r]
if s == target:
results.append(result + [nums[l], nums[r]])
l += 1
while l < r and nums[l] == nums[l-1]:
l += 1
elif s < target:
l += 1
else:
r -= 1
else: # recursively reduce N
for i in range(l, r+1):
if i == l or (i > l and nums[i-1] != nums[i]):
findNsum(i+1, r, target-nums[i], N-1, result+[nums[i]], results)
nums.sort()
results = []
findNsum(0, len(nums)-1, target, 4, [], results)
return results
- 跳跃游戏 II（力扣第45题）
难度：困难
【参考答案】
- Java 解法：
自动检测
public int jump(int[] nums) {
int end = 0;
int maxPosition = 0;
int steps = 0;
for(int i = 0; i < nums.length - 1; i++){
//找能跳的最远的
maxPosition = Math.max(maxPosition, nums[i] + i);
if( i == end){ //遇到边界，就更新边界，并且步数加一
end = maxPosition;
steps++;
}
}
return steps;
}
- Python解法（国际版力扣答案）：
自动检测
class Solution(object):
# @param {integer[]} nums
# @return {integer}
def jump(self, nums):
n, start, end, step = len(nums), 0, 0, 0
while end < n - 1:
step += 1
maxend = end + 1
for i in range(start, end + 1):
if i + nums[i] >= n - 1:
return step
maxend = max(maxend, i + nums[i])
start, end = end + 1, maxend
return step
This problem has a nice BFS structure. Let’s illustrate it using the example nums = [2, 3, 1, 1, 4] in the problem statement. We are initially at position 0. Then we can move at most nums[0] steps from it. So, after one move, we may reach nums[1] = 3 or nums[2] = 1. So these nodes are reachable in 1 move. From these nodes, we can further move to nums[3] = 1 and nums[4] = 4. Now you can see that the target nums[4] = 4 is reachable in 2 moves.
Putting these into codes, we keep two pointers start and end that record the current range of the starting nodes. Each time after we make a move, update start to be end + 1 and end to be the farthest index that can be reached in 1 move from the current [start, end].
To get an accepted solution, it is important to handle all the edge cases. And the following codes handle all of them in a unified way without using the unclean if statements :-)
若有收获，就点个赞吧
0 人点赞
