正文
4
，
-2
，
-5}
，第一个包含
[n/2]
个点的最小区间就是
[-5,-2]
。（
2011
年
4
月实习招聘考题）
分析：这道题目让求解的是前n/2
个数，也就是说，我们找到中位数和最大
(
小
)
元素即可。而求中位数的方法，在数组有序的时候显然是二分，但这里的数组是无序的，恩，要时刻记得快排的
partition
算法，在很多时候很有帮助。代码如下：
[cpp]
view plain
copy
-
int
Partition(
int
* A,
int
begin,
int
end)
-
{
-
-
int
X = A[end];
-
-
int
i=begin;
-
-
int
j=end;
-
-
while
(i
-
{
-
-
while
(A[i]
-
i++;
-
-
if
(i
-
A[j] = A[i];
-
while
(A[j]>=X && i
-
j--;
-
-
if
(i
-
A[i]=A[j];
-
}
-
A[i] = X;
-
return
i;
-
}
-
-
-
-
-
-
-
-
void
FindMiddleElement(
int
* A,
int
begin ,
int
end,
-
int
middle_index,
int
& middle_element)
-
{
-
if
(!A || begin>end)
-
{
-
return
;
-
}
-
int
split_pos = Partition(A,begin,end);
-
if
(split_pos == middle_index)
-
{
-
middle_element = A[split_pos];
-
return
;
-
}
-
FindMiddleElement(A,begin,split_pos-1,middle_index,middle_element);
-
FindMiddleElement(A,split_pos+1,end,middle_index,middle_element);
-
}
8、
N
个数，范围从
-N
到
N,
可能重复，排序时间复杂度最好能到多少？
（
2011
年
9
月招聘考题）
分析：答案是O(n)
，使用
计数排序和位图排序，桶排序都可以达到这个时间复杂度。
9
、
假设一个
长度为
80
的数组
选择排序已完成主循环
32
次迭代。现在
能保证有多少元素
是在他们
最终的位置
？
（
2012
年
4
月实习生招聘考题）
A
、
16 B
、
31
C
、
32
D
、
39 E
、
40
分析：这个不用过多解释吧，对选择排序不了解的详见找工作知识储备
(3)---
从头说
12
种排序算法：原理、图解、动画视频演示、代码以及笔试面试题目中的应用
10
、下列哪项陈述是对的？
（
2012
年
4
月实习招聘考题）
A
、我们能从一颗二叉树的先序遍历序列和中序遍历序列，确定这颗二叉树。
B
、我们能从一颗二叉树的先序遍历序列和后序遍历序列，确定这颗二叉树。
C
、近乎排序的数组，插入排序可以比快排更有效。
D
、假设
T(n)
是解决
n
个元素的问题时候的运行时间，
T(N)= O(1)
如果
n = 1
；
T(n)
＝
2×T(N/2)+ O(n)
当
n
＞
1
；则
T(n)
是
O(nlgn)
E
、上述都不对
11
、下面哪项
(
些
)
陈述是对的？
（
2012
年
4
月实习招聘考题）
A
、插入排序和冒泡排序
在
大型数据集
下效率很低
。
B
、快速排序是在最坏情况
下
比较
了
O
（
N^2
）
次
。
C
、有一
序列
7,6,5,4,3,2,1
。如果使用选择排序（升序），交换操作
次
数是
6
D
、堆排序使用两个堆操作：插入、堆调整
E
、
上述都不对
分析：常规题，对各种排序算法要熟悉
12
、
最长递增子序列（
LIS
）是一个序列
满足
元素的值不断增加
的子序列中最长的序列
。
例如，里
{ 2,1,4,2,3,7,4,6 }
是
{ 1,2,3,4,6 }
，以及
LIS
的长度为
5
。
考虑具有
n
个元素的数组，
则得到
LIS
的长度
的
最低的时间复杂度和空间复杂度
是多少
？（
2012
年
4
月实习招聘考题）
A
、
Time : N^2 , Space : N^2
B
、
Time : N^2 , Space : N
C
、
Time : NlogN , Space : N
D
、
Time : N , Space : N
E
、
Time : N , Space : C
分析：详见找工作知识储备
(2)---
数组字符串那些经典算法：最大子序列和，最长递增子序列，最长公共子串，最长公共子序列，字符串编辑距离，最长不重复子串，最长回文子串
13
、对于以下的定义
（
201
3
年
4
月实习招聘考题）
[cpp]
view plain
copy
-
int
[][] myArray3 =
new
int
[3][]{
-
new
int
[3]{5,6,2},
-
new
int
[5]{6,9,7,8,3},
-
new
int
[2]{3,2}};
则
myArray3[2][2]
返回的是
?
A. 9
B. 2
C. 6
D. overflow
分析：越界导致overflow
14
、以下哪些
排序方法是稳定的？
（
201
3
年
4
月实习招聘考题）
A.
冒泡排序
B. 快速排序
C. 堆排序
D.
归并排序
E. 选择排序
15
、
快速排序的最好时间复杂度是
?
（
2013
年
9
月招聘考题）
A
、
O(lgn)
B
、
O(n)
C
、
O(nlgn)
D
、
O(n*n)
分析：好吧，这一题就不解释了，大家都知道的。
2
、链表相关
1
、下列程序的输出是什么？
（
2012
年
4
月实习招聘考题）
[cpp]
view plain
copy
-
#include
-
using
namespace
std;
-
struct
Item
-
{
-
char
