一、笔试题
1、假设在n进制下，下面的等式成立，n值是（）
567*456=150216
a、 9 b、 10 c、 12 d、 18
2、文法G:S->uvSvu|w所识别的语言是：（）
a、uvw*vu b、（uvwvu）* c、uv(uv)*wvu(vu)* d、(uv)*w(vu)*
3、如下程序段输出是：（）
char str[][10]={"Hello","Google"};
char *p=str[0];
count<<strlen(p 10);
a、0 b、5 c、6 d、10
4、cnt=0
while(x!=1){
cnt=cnt 1;
if(x&1==0)
x=x/2;
else
x=3*x 1;
}
count<<cnt<<end1;
当n=11时，输出：（）
a、12 b、13 c、14 d、15
5、下面哪项不是链表优于数组的特点？（）
a、方便删除 b、方便插入 c、长度可变 d、存储空间小
6、如何减少换页错误？（）
a、进程倾向于占用CPU b、访问局部性（locality of reference）满足进程要求 )
c、进程倾向于占用I/O d、使用基于最短剩余时间（shortest remaining time）的调度机制
e、减少页大小
7、80x86中，十进制数-3用16位二进制数表示为？（）
8、假定符号-、*、$分别代表减法、乘法和指数运算，且
1)三个运算符优先级顺序是：-最高，*其次，$最低；
2)运算符运算时为左结合。请计算3-2*4$1*2$3的值：（）
a、4096 b、-61 c、64 d、-80 e、512
9、下列伪代码中，参数是引用传递，结果是？（）
calc(double p, double q, double r)
{q=q-1.0;r=r+p}
main(){
double a = 2.5, b = 9.0;
calc(b-a, a, a);
print(a);
}
a、1.5 b、2.5 c、10.5 d、8 e、6.5
10、求输出结果：（）
int foo(int x, int y){
if(x <=0 || y <= 0) return 1;
return 3 * foo(x - 1, y / 2);
}
printf("%d ", foo(3, 5));
a、81 b、27 c、9 d、3 e、1
11、下列哪个数据结构在优先队列中被最广泛使用？（）
a、堆 b、数组 c、双向链表 d、图 e、向量
12、以下算法描述了一个在n国元素的双向链表中找到第k个元素的
方法（k >= 1且k <= n）：
如果k <= n - k，从链表开始往前进k-1个元素。
否则，从终点出发，往回走n - k个元素。
这个算法的时间代价是？（）
a、θ(nlogn) b、θ(max{k, n - k}) c、θ(k + (n - k)) d、θ(max{k, k - n}) e、θ(min{k, n - k})
13、有一个由10个顶点组成的图，每个顶点有6个度，那么这个图有几条边？（）
a、60 b、30 c、20 d、80 e、90
14、正则表达式L = x*(x|yx+)。下列哪个字符串不符号L（）
a、x b、xyxyx c、xyx d、yxx e、yx8
15、为读取一块数据而准备磁盘驱动器的总时间包括（）
a、等待时间 b、寻道时间 c、传输时间 d、等待时间加寻道时间 e、等待时间加寻道时间加传输时间
16、Fibonacci,求f(4）使用递归调用f(1)的次数（）
f(n) = f(n-1)+f(n-2), f(0)=0, f(1)=1
a、5 b、4 c、3 d、4以上
17、有关哈希表正确的说法（不定项）（）
a、哈希表的效率和哈希函数。。。。相关
b、哈希表的解决冲突方法慢，回影响哈希表效率
c、使用链表哈希可使内存紧凑
18、下列排序方法最差情况时间复杂度为O(n^2)的是：（）
a、插入 b、归并 c、冒泡 d、快速
567*456=150216
a、 9 b、 10 c、 12 d、 18
2、文法G:S->uvSvu|w所识别的语言是：（）
a、uvw*vu b、（uvwvu）* c、uv(uv)*wvu(vu)* d、(uv)*w(vu)*
3、如下程序段输出是：（）
char str[][10]={"Hello","Google"};
char *p=str[0];
count<<strlen(p 10);
a、0 b、5 c、6 d、10
4、cnt=0
while(x!=1){
cnt=cnt 1;
if(x&1==0)
x=x/2;
else
x=3*x 1;
}
count<<cnt<<end1;
当n=11时，输出：（）
a、12 b、13 c、14 d、15
5、下面哪项不是链表优于数组的特点？（）
a、方便删除 b、方便插入 c、长度可变 d、存储空间小
6、如何减少换页错误？（）
a、进程倾向于占用CPU b、访问局部性（locality of reference）满足进程要求 )
c、进程倾向于占用I/O d、使用基于最短剩余时间（shortest remaining time）的调度机制
e、减少页大小
7、80x86中，十进制数-3用16位二进制数表示为？（）
8、假定符号-、*、$分别代表减法、乘法和指数运算，且
1)三个运算符优先级顺序是：-最高，*其次，$最低；
2)运算符运算时为左结合。请计算3-2*4$1*2$3的值：（）
a、4096 b、-61 c、64 d、-80 e、512
9、下列伪代码中，参数是引用传递，结果是？（）
calc(double p, double q, double r)
{q=q-1.0;r=r+p}
main(){
double a = 2.5, b = 9.0;
calc(b-a, a, a);
print(a);
}
a、1.5 b、2.5 c、10.5 d、8 e、6.5
10、求输出结果：（）
int foo(int x, int y){
if(x <=0 || y <= 0) return 1;
return 3 * foo(x - 1, y / 2);
}
printf("%d ", foo(3, 5));
a、81 b、27 c、9 d、3 e、1
11、下列哪个数据结构在优先队列中被最广泛使用？（）
a、堆 b、数组 c、双向链表 d、图 e、向量
12、以下算法描述了一个在n国元素的双向链表中找到第k个元素的
方法（k >= 1且k <= n）：
如果k <= n - k，从链表开始往前进k-1个元素。
否则，从终点出发，往回走n - k个元素。
这个算法的时间代价是？（）
a、θ(nlogn) b、θ(max{k, n - k}) c、θ(k + (n - k)) d、θ(max{k, k - n}) e、θ(min{k, n - k})
13、有一个由10个顶点组成的图，每个顶点有6个度，那么这个图有几条边？（）
a、60 b、30 c、20 d、80 e、90
14、正则表达式L = x*(x|yx+)。下列哪个字符串不符号L（）
a、x b、xyxyx c、xyx d、yxx e、yx8
15、为读取一块数据而准备磁盘驱动器的总时间包括（）
a、等待时间 b、寻道时间 c、传输时间 d、等待时间加寻道时间 e、等待时间加寻道时间加传输时间
16、Fibonacci,求f(4）使用递归调用f(1)的次数（）
f(n) = f(n-1)+f(n-2), f(0)=0, f(1)=1
a、5 b、4 c、3 d、4以上
17、有关哈希表正确的说法（不定项）（）
a、哈希表的效率和哈希函数。。。。相关
b、哈希表的解决冲突方法慢，回影响哈希表效率
c、使用链表哈希可使内存紧凑
18、下列排序方法最差情况时间复杂度为O(n^2)的是：（）
a、插入 b、归并 c、冒泡 d、快速
19、写一段程序判定一个有向图G中节点w是否从节点v可达。（假如G中存在一条从v至w的路径就说节点w是从v可达的）。以下算法是用C 写成的，在bool Reachable函数中，你可以写出自己的算法。
class Graph{
public:
int NumberOfNodes();//返回节点的总数
bool HasEdge(int u,int v);//u,v是节点个数，从零开始依次递增，当有一条从u到v的边时，返回true
}；
bool Reachable(Graph&G, int v, int w){
//请写入你的算法
}
20、给定一棵所有边的长度均为整数的树，现要求延长其中某些边，使得从根到任意节点的路径长度相等。问满足要求的树的边长度之和最小是多少?请写出你的算法，并分析时间复杂度。
21、以下函数的结果？
int cal(int x)
{
if(x==0)
return 0;
else
return x+cal(x-1);
}
22、以下程序的结果？
void foo(int*a, int* b)
{
*a = *a+*b;
*b = *a-*b;
*a = *a-*b;
}
void main()
{
int a=1, b=2, c=3;
foo(&a,&b);
foo(&b,&c);
foo(&c,&a);
printf("%d, %d, %d", a,b,c);
}
23、T(n) = 25T(n/5)+n^2的时间复杂度？
24、n个顶点，m条边的全连通图，至少去掉几条边才能构成一棵树？
25、正则表达式(01|10|1001|0110)*与下列哪个表达式一样？
26、实现两个N*N矩阵的乘法，矩阵由一维数组表示。
27、长度为n的整数数组，找出其中任意(n-1)个乘积最大的那一组，只能用乘法，不可以用除法。要求对算法的时间复杂度和空间复杂度作出分析，不要求写程序。
28、打印出一个二叉树的内容。
29、在一个字符串中找到第一个只出现一次的字符。如abaccdeff，输出b。
30、求一个二叉树的高度，如果只有root结点，高度为0。
31、将稀疏疏组中的非零元素提取出来，用链表表示。
32、两个n维数组，已排序，为升序。设计算法求2n的数中第n大的数。要求分析时间和空间复杂度。不用给出代码。
33、给定一个长度为N的整数数组（元素有正有负），求所有元素之和。最大的一个子数组。分析算法时空复杂度。不必写代码。
答：最大子序列
问题：
给定一整数序列A1， A2，... An （可能有负数），求A1~An的一个子序列Ai~Aj，使得Ai到Aj的和最大
例如： 整数序列-2, 11, -4, 13, -5, 2, -5, -3, 12, -9的最大子序列的和为20。 对于这个问题，最简单也是最容易想到的那就是穷举所有子序列的方法。利用三重循环，依次求出所有子序列的和然后取最大的那个。当然算法复杂度会达到O(n^3)。显然这种方法不是最优的，下面给出一个算法复杂度为O(n)的线性算法实现，算法的来源于Programming Pearls一书。 在给出线性算法之前，先来看一个对穷举算法进行优化的算法，它的算法复杂度为O(n^2)。其实这个算法只是对对穷举算法稍微做了一些修改：其实子序列的和我们并不需要每次都重新计算一遍。假设Sum(i, j)是A[i] ... A[j]的和，那么Sum(i, j+1) = Sum(i, j) + A[j+1]。利用这一个递推，我们就可以得到下面这个算法：
int max_sub(int a[],int size)
{
int i,j,v,max=a[0];
for(i=0;i<size;i++)
{
v=0;
for(j=i;j<size;j++)
{
v=v+a[j];//Sum(i, j+1) = Sum(i, j) + A[j+1]
if(v>max)
max=v;
}
}
return max;
}那怎样才能达到线性复杂度呢？这里运用动态规划的思想。先看一下源代码实现：
int max_sub2(int a[], int size)
{
int i,max=0,temp_sum=0;
for(i=0;i<size;i++)
{
temp_sum+=a[i];
if(temp_sum>max)
max=temp_sum;
else if(temp_sum<0)
temp_sum=0;
}
return max;
}
class Graph{
public:
int NumberOfNodes();//返回节点的总数
bool HasEdge(int u,int v);//u,v是节点个数，从零开始依次递增，当有一条从u到v的边时，返回true
}；
bool Reachable(Graph&G, int v, int w){
//请写入你的算法
}
20、给定一棵所有边的长度均为整数的树，现要求延长其中某些边，使得从根到任意节点的路径长度相等。问满足要求的树的边长度之和最小是多少?请写出你的算法，并分析时间复杂度。
21、以下函数的结果？
int cal(int x)
{
if(x==0)
return 0;
else
return x+cal(x-1);
}
22、以下程序的结果？
void foo(int*a, int* b)
{
*a = *a+*b;
*b = *a-*b;
*a = *a-*b;
}
void main()
{
int a=1, b=2, c=3;
foo(&a,&b);
foo(&b,&c);
foo(&c,&a);
printf("%d, %d, %d", a,b,c);
}
23、T(n) = 25T(n/5)+n^2的时间复杂度？
24、n个顶点，m条边的全连通图，至少去掉几条边才能构成一棵树？
25、正则表达式(01|10|1001|0110)*与下列哪个表达式一样？
26、实现两个N*N矩阵的乘法，矩阵由一维数组表示。
27、长度为n的整数数组，找出其中任意(n-1)个乘积最大的那一组，只能用乘法，不可以用除法。要求对算法的时间复杂度和空间复杂度作出分析，不要求写程序。
28、打印出一个二叉树的内容。
29、在一个字符串中找到第一个只出现一次的字符。如abaccdeff，输出b。
30、求一个二叉树的高度，如果只有root结点，高度为0。
31、将稀疏疏组中的非零元素提取出来，用链表表示。
32、两个n维数组，已排序，为升序。设计算法求2n的数中第n大的数。要求分析时间和空间复杂度。不用给出代码。
33、给定一个长度为N的整数数组（元素有正有负），求所有元素之和。最大的一个子数组。分析算法时空复杂度。不必写代码。
答：最大子序列
问题：
给定一整数序列A1， A2，... An （可能有负数），求A1~An的一个子序列Ai~Aj，使得Ai到Aj的和最大
例如： 整数序列-2, 11, -4, 13, -5, 2, -5, -3, 12, -9的最大子序列的和为20。 对于这个问题，最简单也是最容易想到的那就是穷举所有子序列的方法。利用三重循环，依次求出所有子序列的和然后取最大的那个。当然算法复杂度会达到O(n^3)。显然这种方法不是最优的，下面给出一个算法复杂度为O(n)的线性算法实现，算法的来源于Programming Pearls一书。 在给出线性算法之前，先来看一个对穷举算法进行优化的算法，它的算法复杂度为O(n^2)。其实这个算法只是对对穷举算法稍微做了一些修改：其实子序列的和我们并不需要每次都重新计算一遍。假设Sum(i, j)是A[i] ... A[j]的和，那么Sum(i, j+1) = Sum(i, j) + A[j+1]。利用这一个递推，我们就可以得到下面这个算法：
int max_sub(int a[],int size)
{
int i,j,v,max=a[0];
for(i=0;i<size;i++)
{
v=0;
for(j=i;j<size;j++)
{
v=v+a[j];//Sum(i, j+1) = Sum(i, j) + A[j+1]
if(v>max)
max=v;
}
}
return max;
}那怎样才能达到线性复杂度呢？这里运用动态规划的思想。先看一下源代码实现：
int max_sub2(int a[], int size)
{
int i,max=0,temp_sum=0;
for(i=0;i<size;i++)
{
temp_sum+=a[i];
if(temp_sum>max)
max=temp_sum;
else if(temp_sum<0)
temp_sum=0;
}
return max;
}
在这一遍扫描数组当中，从左到右记录当前子序列的和temp_sum，若这个和不断增加，那么最大子序列的和max也不断增加(不断更新max)。如果往前扫描中遇到负数，那么当前子序列的和将会减小。此时temp_sum 将会小于max，当然max也就不更新。如果temp_sum降到0时，说明前面已经扫描的那一段就可以抛弃了，这时将temp_sum置为0。然后，temp_sum将从后面开始将这个子段进行分析，若有比当前max大的子段，继续更新max。这样一趟扫描结果也就出来了。
二、面试题
1、求直方图的最大内接矩形，假设每个细条的宽度为1，这个题很hot，两个人来问。我没想出什么好的算法。
2、NxN行列有序的矩阵查找一个数。以前有人遇到过。O(N)的时间复杂度。
3、给定一篇文章，求包含所有单词的最短摘要。O(N)的时间复杂度。
4、将MxN的矩阵转秩，要求O(1)的空间复杂度。参考群论中cyclic group,group generator
5、开放式问题，怎么避免重复抓取网页。
6、开放式问题，有些网站每天只允许有限次访问，怎么抓取网页使得索引尽量全面和新鲜。
7、写一个singleton pattern的例子。
8、vector vs. arraylist, growth strategy & complexity。
9、在C++文件中只declare class A, 但不以任何方式define class A, 是做什么用。
10、virtual function。
11、讨论html vs. xhtml vs. xml。
12、描述在浏览器中敲入一个网址后所发生的事情.dns,cache等。
13、给一个长度为n的整数数组，只允许用乘法不允许用除法，计算任意(n-1)个数的组合乘积中最大的一组。。。写出算法的时空复杂度。
转至http://www.sibowen.com/show_news.php?dh_class=&id=70