谷歌 2006 上海交大笔试题

---------------------------------------------------------------------------

1. 两个二进制数的异或结果。

按位异或即可。

---------------------------------------------------------------------------

2. 递归函数最终会结束，那么这个函数一定(不定项选择)：
1) 使用了局部变量
2) 有一个分支不调用自身
3) 使用了全局变量或者使用了一个或多个参数

2, 3

---------------------------------------------------------------------------

3. 以下函数的结果？
int cal(int x)
{
if(x==0)
return 0;
else
return x+cal(x-1);
}

x*(x+1)/2 (自然数求和)

---------------------------------------------------------------------------

4. 以下程序的结果是什么？

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);
}

1, 3, 2

---------------------------------------------------------------------------

5. 下面哪项不是链表优于数组的特点？
1. 方便删除 2. 方便插入 3. 长度可变 4. 存储空间小

4

---------------------------------------------------------------------------

6. T(n) = 25T(n/5)+n^2 的时间复杂度？

O((n^2)*log(n))
注：主定理。

---------------------------------------------------------------------------

7. n 个顶点，m 条边的全连通图，至少去掉几条边才能构成一棵树？

m-(n-1) (n 个顶点的树边的条数为 n-1)

---------------------------------------------------------------------------

8. 正则表达式(01|10|1001|0110)*与下列哪个表达式一样？
1) (0|1)* 2) (01|01)* 3) (01|10)* 4) (11|01)* 5) (01|1)*

3

---------------------------------------------------------------------------

9. 如何减少换页错误？
1) 进程倾向于占用CPU 2) 访问局部性(locality of reference)满足进程要求
3) 进程倾向于占用I/O 4) 使用基于最短剩余时间(shortest remaining time)的调度机制
5) 减少页大小

2 (?)

---------------------------------------------------------------------------

10. 实现两个N*N矩阵的乘法，矩阵由一维数组表示。

void matrix_multiply(int A[], int B[], int result[], int N)
{
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
result[i*N+j] = 0;
}
}
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
for (int k = 0; k < N; ++k)
{
result[i*N+j] += A[i*N+k] * B[k*N+j];
}
}
}
}

/* 略微优化 */
void matrix_multiply(int A[], int B[], int result[], int N)
{
for (int i = 0; i < N * N; i += N)
{
for (int j = 0; j < N; ++j)
{
result[i+j] = 0;
}
}
for (i = 0; i < N * N; i += N)
{
for (j = 0; j < N; ++j)
{
int t = 0;
for (ia = i, ib = j; ib < N * N; ++ia, ib += N)
{
t += a[ia] * b[ib];
}
result[i+j] = t;
}
}
}

---------------------------------------------------------------------------

11. 找到单向链表中间那个元素，如果有两个则取前面一个。

#include <stddef.h>

struct listtype
{
int data;
struct listtype * next;
};

typedef struct listtype * list;

/* Find the middle element of the singly linked list sll. */
list find_middle(list sll)
{
list slow = sll;
list fast = sll;

if (NULL == fast)
{
return NULL;
}

while (1)
{
if (NULL == fast->next || NULL == fast->next->next)
{
return slow;
}

slow = slow->next;
fast = fast->next->next;

/* Prevent that there is a loop in the linked list. */
if (fast == slow)
{
return NULL;
}
}
}

---------------------------------------------------------------------------

12. 长度为 N 的整数数组，找出其中任意(N-1)个乘积最大的那一组，只能用乘法，不可以用除法。要求对算法的时间复杂度和空间复杂度作出分析，不要求写程序。

令这 N 个数的乘积为 P，
1) 如果 P<0，则剔除其中最大的负整数即可；
2) 如果 P=0，
2.1) 若这 N 个数中有且仅有一个为“0”。若其他数之积为正，则剔除“0”；否则剔除任意一个非零数；
2.2) 若这 N 个数中至少有两个为“0”，则随便剔除一个数均可；
3) 如果 P>0，如果有正数，则剔除其中最小的正整数即可；否则，剔除最小的负整数。

时间复杂度：遍历数组，获得正整数个数 cp，负整数个数 cn，0 的个数 cz，需要 O(N) 时间；找被剔除的数最坏情况下需要 O(N) 时间。输出结果需要 O(N) 时间。因此，时间复杂度为 O(N)。

空间复杂度：数组存储需要 O(N) 空间，cp, cn, cz 和被剔除的数的下标各需要 O(1) 空间。因此，空间复杂度为 O(N)。

---------------------------------------------------------------------------