2007google笔试题-上海交大站

2 views

Skip to first unread message

Bob

unread,

Oct 18, 2006, 2:37:23 AM10/18/06

to 程序员乐园

From：http://bbs.sjtu.edu.cn/bbscon?board=job&file=M.1160541570.A&num=7569

发信人: careercenter(学生就业服务和职业发展中心),
信区: job
标题: 【合集】Google笔经
发信站: 饮水思源 (2006年10月11日12:39:30 星期三),
站内信件

☆──────────────────────────────────────☆
OfferRain (offer的大雨) 于 2006年10月11日03:06:04 星期三
提到：

开章明义，我是个废人，上来积攒rp了。
在宣讲会的时候，听旁边的师姐说上海只招两个职位每个职位只招一个人。
现在后悔只选了北京和上海的SWE了。
不过反正……也不指望了。。。

笔试题目：9道单选+3道问答
时间：100分钟
我做的是B卷。

单选题：
1，求两个二进制数的异或值，基本上学过一点计算机的东西的人都能对的题目。。

2，不记得了。。也是不需要思考的题目。。

3，大概是如下的函数：
int someFunc(int x){
if (x == 0)
return 0;
else
return x + someFunc(x - 1);
}
问这个计算的是什么。。。

4，不记得了。。不需要思考吧。。

5，不记得了。。不需要思考吧。。

6，参见2，4，5。。

7，似乎需要思考一下。。

8，问链表结构和数组相比的优势不包括哪项，
包括：
插入的时间
删除的时间
存储空间
剩下两个不记得了。。

9，如下函数：
T(x) = 1 (x <= 1)
T(n) = 25 T(n/5) + n^2
问T(n)随n的增长。
选项大概是这样的：
O(n^2)，O(n^2logn)等等的。。

问答：
1，写两个N*N的矩阵的乘法，给出了C的格式，你可以选择你喜欢的语言去写。。
int* multi(int* a1, int* a2, int N){
}

2，寻找一个单向链表的中项，如果存在两个则返回前一个。给出了C的格式，同样你可
以选择。。。。
struct {
Node* next;
int value;
} Node;
Node* someFunc(Node* head){
}

3，给一个长度为n的整数数组，只允许用乘法不允许用除法，计算任意(n-1)个数的组合
乘积中最大的一组。。。写出算法的时空复杂度。
ps：怀疑这道题目出错啦。。虽然我也做错了。。。。。。

一些补充：
1，问答的第一题是google上学期 intern的大题原题；
2，google很喜欢考链表，无论intern的面试以及两次的笔试都有这样的题目；
3，google一般大题第三道都是写算法的时空复杂度；
4，选择题基本上偏简单，但是要做得准确率高似乎并不那么容易；
5，根据传言，小道消息，人云亦云以及以讹传讹，google的高速审卷政策来源于审卷时
以选择题为主，如果你全对啦，那么恭喜你pass啦；如果你错了好几道，那么下次努力
吧，如果还有下次。。。大题基本是做参考的。。。
6，选择题很多记不清了，因为一遍做下来的，回去随便扫了两眼。。。加上过了这几个
小时，记不得了。希望大家补充修正以及修改。。。

7，google会在11号开始3天内发面试通知，据小道消息等等，有四轮面试。bless大家~~

☆──────────────────────────────────────☆
Alicelili (aliss) 于 2006年10月11日03:27:46 星期三)
提到：

zan一下
虽然我不是it类的
【在 OfferRain 的大作中提到: 】
: 开章明义，我是个废人，上来积攒rp了。
:
在宣讲会的时候，听旁边的师姐说上海只招两个职位每个职位只招一个人。
: 现在后悔只选了北京和上海的SWE了。
: 不过反正……也不指望了。。。
: 笔试题目：9道单选+3道问答
: 时间：100分钟
: 我做的是B卷。
: 单选题：
:
1，求两个二进制数的异或值，基本上学过一点计算机的东西的人都能对的题目。。
: 2，不记得了。。也是不需要思考的题目。。
: 3，大概是如下的函数：
: int someFunc(int x){
: if (x == 0)
: return 0;
: else
: return x + someFunc(x - 1);
: }
: 问这个计算的是什么。。。
: 4，不记得了。。不需要思考吧。。
: 5，不记得了。。不需要思考吧。。
: (以下引言省略...)

☆──────────────────────────────────────☆
CCIE (快成一个生死未仆的人了) 于
2006年10月11日07:15:21 星期三提到：

我投的ITE
【在 OfferRain (offer的大雨) 的大作中提到: 】
: 开章明义，我是个废人，上来积攒rp了。
:
在宣讲会的时候，听旁边的师姐说上海只招两个职位每个职位只招一个人。
: 现在后悔只选了北京和上海的SWE了。
: 不过反正……也不指望了。。。
: 笔试题目：9道单选+3道问答
: 时间：100分钟
: 我做的是B卷。
: 单选题：
:
1，求两个二进制数的异或值，基本上学过一点计算机的东西的人都能对的题目。。
: 2，不记得了。。也是不需要思考的题目。。
: .................（以下省略）

☆──────────────────────────────────────☆
jefferyshao (一般一般世界第三·泊沽通津) 于
2006年10月11日07:40:12 星期三提到：

2.P是自己钓用自己的函数，如果P一定会结束，那么P一定：
选择
4.void foo(int *a, int*b)
{
*a=*a+*b;
*a=*a-*b;
*a=*a-*b;
}
int a=1;b=2;c=3;
foo(&a,&b);
foo(&b,&c);
foo(&c,&a);
printf("%d,%d,%d\n",a,b,c);结果
5。邮n个顶点和m个边连通图中至少去掉多少条边才可生成一颗生成树
6。降低换冶错误发生频率的问题
7。给出正则表达式，选和它属于同一语言的选项

【在 OfferRain (offer的大雨) 的大作中提到: 】
: 开章明义，我是个废人，上来积攒rp了。
:
在宣讲会的时候，听旁边的师姐说上海只招两个职位每个职位只招一个人。
: 现在后悔只选了北京和上海的SWE了。
: 不过反正……也不指望了。。。
: 笔试题目：9道单选+3道问答
: 时间：100分钟
: 我做的是B卷。
: 单选题：
:
1，求两个二进制数的异或值，基本上学过一点计算机的东西的人都能对的题目。。
: 2，不记得了。。也是不需要思考的题目。。
: .................（以下省略）

☆──────────────────────────────────────☆
lOOOORPM (万转硬盘) 于 2006年10月11日09:24:52 星期三
提到：

只招一个人......
不过昨天挺热闹，好多人堆在一起

☆──────────────────────────────────────☆
acmboy (愛爸爸，愛媽媽，要有責任心) 于
2006年10月11日09:42:39 星期三)
提到：

还有一题选择题是：
下面事实可以减少内存缺页错误的是：
1。局部性较好
2。主要是cpu运算
3。i/o操作多
。。。。下面选项不记得了。。。
应该选 1 把，我想

【在 OfferRain 的大作中提到: 】
: 开章明义，我是个废人，上来积攒rp了。
:
在宣讲会的时候，听旁边的师姐说上海只招两个职位每个职位只招一个人。
: 现在后悔只选了北京和上海的SWE了。
: 不过反正……也不指望了。。。
: 笔试题目：9道单选+3道问答
: 时间：100分钟
: 我做的是B卷。
: 单选题：
:
1，求两个二进制数的异或值，基本上学过一点计算机的东西的人都能对的题目。。
: 2，不记得了。。也是不需要思考的题目。。
: 3，大概是如下的函数：
: int someFunc(int x){
: if (x == 0)
: return 0;
: else
: return x + someFunc(x - 1);
: }
: 问这个计算的是什么。。。
: 4，不记得了。。不需要思考吧。。
: 5，不记得了。。不需要思考吧。。
: (以下引言省略...)

☆──────────────────────────────────────☆
Ilovehlz (Ilovehlz) 于 2006年10月11日10:08:18 星期三
提到：

这个就是 jefferyshao 给出的第六题吧？

【在 acmboy (愛爸爸，愛媽媽，要有責任心)
的大作中提到: 】
: 还有一题选择题是：
: 下面事实可以减少内存缺页错误的是：
: 1。局部性较好
: 2。主要是cpu运算
: 3。i/o操作多
: 。。。。下面选项不记得了。。。
: 应该选 1 把，我想
: .................（以下省略）

☆──────────────────────────────────────☆
solve (...) 于 2006年10月11日10:15:11 星期三提到：

我给个比较全的吧：

Google 2007笔试题（上海交大）
2006.10.10
1、两个二进制数的异或结果
2、
递归函数最终会结束，那么这个函数一定（不定项选择）：
1. 使用了局部变量 2. 有一个分支不调用自身
3. 使用了全局变量或者使用了一个或多个参数
3、以下函数的结果？
int cal(int x)
{
if(x==0)
return 0;
else
return x+cal(x-1);
}
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);
}
5、下面哪项不是链表优于数组的特点？
1. 方便删除 2. 方便插入 3. 长度可变 4. 存储空间小
6、T(n) = 25T(n/5)+n^2的时间复杂度？
7、n个顶点，m条边的全连通图，至少去掉几条边才能构成一棵树？
8、正则表达式(01|10|1001|0110)*与下列哪个表达式一样？
1.(0|1)* 2.(01|01)* 3.(01|10)* 4.(11|01)* 5.(01|1)*
9、如何减少换页错误？
1. 进程倾向于占用CPU 2. 访问局部性（locality of
reference）满足进程要求
3. 进程倾向于占用I/O
4.使用基于最短剩余时间（shortest remaining time）的调度
机制 5. 减少页大小

10、实现两个N*N矩阵的乘法，矩阵由一维数组表示
11、找到单向链表中间那个元素，如果有两个则取前面一个
12、长度为n的整数数组，找出其中任意(n-1)个乘积最大的那一组，只能用乘法，不可
以用除法。要求对算法的时间复杂度和空间复杂度作出分析，不要求写程序。

【在 OfferRain
(offer 的大雨) 的大作中提到: 】:
开章明义，我是个废人，上来积攒rp了。
:
在宣讲会的时候，听旁边的师姐说上海只招两个职位每个职位只招一个人。
: 现在后悔只选了北京和上海的SWE了。
: 不过反正……也不指望了。。。
: 笔试题目：9道单选+3道问答
: 时间：100分钟
: 我做的是B卷。
: 单选题：
:
1，求两个二进制数的异或值，基本上学过一点计算机的东西的人都能对的题目。。
: 2，不记得了。。也是不需要思考的题目。。
: .................（以下省略）

☆──────────────────────────────────────☆
Stratix (天马行空) 于 2006年10月11日10:18:06 星期三)
提到：

niu~~
【在 solve 的大作中提到: 】
: 我给个比较全的吧：
: Google 2007笔试题（上海交大）
: 2006.10.10
: 1、两个二进制数的异或结果
: 2、
递归函数最终会结束，那么这个函数一定（不定项选择）：
: 1. 使用了局部变量 2. 有一个分支不调用自身
: 3. 使用了全局变量或者使用了一个或多个参数
: 3、以下函数的结果？
: int cal(int x)
: {
: if(x==0)
: return 0;
: else
: return x+cal(x-1);
: }
: 4、以下程序的结果？
: void foo(int*a, int* b)
: {
: *a = *a+*b;
: *b = *a-*b;
: (以下引言省略...)

☆──────────────────────────────────────☆
Ilovehlz (Ilovehlz) 于 2006年10月11日10:20:19 星期三
提到：

第七题不是“全连通图”而是“连通图”吧？

【在 solve (...) 的大作中提到: 】
: 标题: Re: Google笔经
: 发信站: 饮水思源 (2006年10月11日10:15:11 星期三),
站内信件
:
: 我给个比较全的吧：
:
: Google 2007笔试题（上海交大）
: 2006.10.10
: 1、两个二进制数的异或结果
: 2、
递归函数最终会结束，那么这个函数一定（不定项选择）：
: 1. 使用了局部变量 2. 有一个分支不调用自身
: 3. 使用了全局变量或者使用了一个或多个参数
: 3、以下函数的结果？
: int cal(int x)
: {
: if(x==0)
: return 0;
: else
: return x+cal(x-1);
: }
: 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);
: }
: 5、下面哪项不是链表优于数组的特点？
: 1. 方便删除 2. 方便插入 3. 长度可变 4.
存储空间小
: 6、T(n) = 25T(n/5)+n^2的时间复杂度？
:
7、n个顶点，m条边的全连通图，至少去掉几条边才能构成一棵树？
:
8、正则表达式(01|10|1001|0110)*与下列哪个表达式一样？
: 1.(0|1)* 2.(01|01)* 3.(01|10)* 4.(11|01)* 5.(01|1)*
: 9、如何减少换页错误？
: 1. 进程倾向于占用CPU 2. 访问局部性（locality of
reference）满足进程要求
: 3. 进程倾向于占用I/O
4.使用基于最短剩余时间（shortest remaining time）的调度
: 机制 5. 减少页大小
:
: 10、实现两个N*N矩阵的乘法，矩阵由一维数组表示
:
11、找到单向链表中间那个元素，如果有两个则取前面一个
:
12、长度为n的整数数组，找出其中任意(n-1)个乘积最大的那一组，只能用乘法，不可
:
以用除法。要求对算法的时间复杂度和空间复杂度作出分析，不要求写程序。
:
: (offer 的大雨) 的大作中提到: 】:
开章明义，我是个废人，上来积攒rp了。
:
: --
: 呜呜，要什么没什么~
:
: ※ 来源:·饮水思源 bbs.sjtu.edu.cn·[FROM: 58.196.132.5]

☆──────────────────────────────────────☆
xeast (哎于 2006年10月11日10:28:39 星期三提到：

......

【在 jefferyshao (一般一般世界第三·泊沽通津)
的大作中提到: 】
:
2.P是自己钓用自己的函数，如果P一定会结束，那么P一定：
: 选择
: 4.void foo(int *a, int*b)
: {
: *a=*a+*b;
: *a=*a-*b;
: *a=*a-*b;
: }
: int a=1;b=2;c=3;
: foo(&a,&b);
: .................（以下省略）

☆──────────────────────────────────────☆
kycs (kaoyancs) 于 2006年10月11日10:35:59 星期三)
提到：

P是自己钓用自己的函数，如果P一定会结束，那么P一定：
这个题目有难度，它列出的条件有
1 有一个不调用自己的分支
2 一定使用乐全局变量
3 要么使用了全局变量，要么带了参数
还有一个忘记了
我回去研究了一下，发现不一定要引用全局变量或者带参数，还有一种可能，函数内使用
了静态变量，也可以成为跳出的条件。

【在 jefferyshao 的大作中提到: 】
:
2.P是自己钓用自己的函数，如果P一定会结束，那么P一定：
: 选择
: 4.void foo(int *a, int*b)
: {
: *a=*a+*b;
: *a=*a-*b;
: *a=*a-*b;
: }
: int a=1;b=2;c=3;
: foo(&a,&b);
: foo(&b,&c);
: foo(&c,&a);
: printf("%d,%d,%d\n",a,b,c);结果
:
5。邮n个顶点和m个边连通图中至少去掉多少条边才可生成一颗生成树
: 6。降低换冶错误发生频率的问题
: 7。给出正则表达式，选和它属于同一语言的选项
: (以下引言省略...)

☆──────────────────────────────────────☆
bullfinch (Refactor) 于 2006年10月11日10:43:08 星期三
提到：

好奇你师姐哪里来的消息

☆──────────────────────────────────────☆
ningliu (蘑菇王子) 于 2006年10月11日10:49:23 星期三
提到：

第九题是 n^2logn吧。

☆──────────────────────────────────────☆
acmboy (愛爸爸，愛媽媽，要有責任心) 于
2006年10月11日10:50:21 星期三)
提到：

恩
用 T(5^n)递推,最笨的方法,呵呵

【在 ningliu 的大作中提到: 】
: 第九题是 n^2logn吧。

☆──────────────────────────────────────☆
gobr (gobr) 于 2006年10月11日10:50:32 星期三提到：

int * mult(int *a1,int *a2, int n)
{
int i,j,k;
int ia =0, ib =0,id =0;
int *d = (int* )malloc(size(int)*n*n);
if (!d)
return NULL;
for (i = 0; i <n;++i) {
for (j =0; j<n;++j) {
int sum = a1[ia]*a2[ib];
for (k = 1; k<n; k++) {
ia++;
ib+=n;
sum += a1[ia]*a2[ib];
}
d[id++] = sum;
ia -= n;
ib = j;
}
ia += n;
ib = 0;
}

return d;
}

Node* someFunc(Node *head)
{
Node* slow = head;
Node* quick= head;

if (head == NULL)
return NULL;

while (quick->next) {
quick = quick->next;
if (quick == NULL)
return slow;
quick = quick->next;
slow = slow->next;
if (!quick)
return slow;
}

return slow;
}

我来贴下代码呵呵
【在 OfferRain (offer的大雨) 的大作中提到: 】
: 开章明义，我是个废人，上来积攒rp了。
:
在宣讲会的时候，听旁边的师姐说上海只招两个职位每个职位只招一个人。
: 现在后悔只选了北京和上海的SWE了。
: 不过反正……也不指望了。。。
: 笔试题目：9道单选+3道问答
: 时间：100分钟
: 我做的是B卷。
: 单选题：
:
1，求两个二进制数的异或值，基本上学过一点计算机的东西的人都能对的题目。。
: 2，不记得了。。也是不需要思考的题目。。
: .................（以下省略）

☆──────────────────────────────────────☆
gobr (gobr) 于 2006年10月11日10:51:48 星期三提到：

直接套用公式就可以了。呵呵 T(N) = af(N/B) +
f(n)有一个公式的。使用了
一个平滑定理可以推出来。

【在 acmboy (愛爸爸，愛媽媽，要有責任心)
的大作中提到: 】
: 恩
: 用 T(5^n)递推,最笨的方法,呵呵

☆──────────────────────────────────────☆
acmboy (愛爸爸，愛媽媽，要有責任心) 于
2006年10月11日10:54:02 星期三)
提到：

是的,前两天还看到这个公式,就是记不住,进了考场就狂后悔
【在 gobr 的大作中提到: 】
: 直接套用公式就可以了。呵呵 T(N) = af(N/B) +
f(n)有一个公式的。使用了
: 一个平滑定理可以推出来。
:

☆──────────────────────────────────────☆
gobr (gobr) 于 2006年10月11日10:56:25 星期三提到：

2、
递归函数最终会结束，那么这个函数一定（不定项选择）：

1. 使用了局部变量 2. 有一个分支不调用自身
3. 使用了全局变量或者使用了一个或多个参数

7、n个顶点，m条边的全连通图，至少去掉几条边才能构成一棵树？
8、正则表达式(01|10|1001|0110)*与下列哪个表达式一样？
1.(0|1)* 2.(01|01)* 3.(01|10)* 4.(11|01)* 5.(01|1)*
9、如何减少换页错误？
1. 进程倾向于占用CPU 2. 访问局部性（locality of
reference）满足进程要求
3. 进程倾向于占用I/O
4.使用基于最短剩余时间（shortest remaining time）的调度
机制 5. 减少页大小

这几个题咋做的。编译,图论，OS都还给老师了。。。
【在 acmboy (愛爸爸，愛媽媽，要有責任心)
的大作中提到: 】

☆──────────────────────────────────────☆
XSLT (雨人) 于 2006年10月11日10:56:32 星期三提到：

介绍一下。。。？
【在 gobr (gobr) 的大作中提到: 】
: 直接套用公式就可以了。呵呵 T(N) = af(N/B) +
f(n)有一个公式的。使用了
: 一个平滑定理可以推出来。

☆──────────────────────────────────────☆
Stratix (天马行空) 于 2006年10月11日10:57:25 星期三)
提到：

第二个函数不是找中间的节点吧？
【在 gobr 的大作中提到: 】
: int * mult(int *a1,int *a2, int n)
: {
: int i,j,k;
: int ia =0, ib =0,id =0;
: int *d = (int* )malloc(size(int)*n*n);
: if (!d)
: return NULL;
: for (i = 0; i <n;++i) {
: for (j =0; j<n;++j) {
: int sum = a1[ia]*a2[ib];
: for (k = 1; k<n; k++) {
: ia++;
: ib+=n;
: sum += a1[ia]*a2[ib];
: }
: d[id++] = sum;
: ia -= n;
: ib = j;
: }
: ia += n;
: (以下引言省略...)

☆──────────────────────────────────────☆
XSLT (雨人) 于 2006年10月11日10:57:33 星期三提到：

我也都忘了。。。观察后随便写的。。。
【在 gobr (gobr) 的大作中提到: 】
: 2、
递归函数最终会结束，那么这个函数一定（不定项选择）：

: 1. 使用了局部变量 2. 有一个分支不调用自身
: 3. 使用了全局变量或者使用了一个或多个参数
:
7、n个顶点，m条边的全连通图，至少去掉几条边才能构成一棵树？
:
8、正则表达式(01|10|1001|0110)*与下列哪个表达式一样？
: 1.(0|1)* 2.(01|01)* 3.(01|10)* 4.(11|01)* 5.(01|1)*
: 9、如何减少换页错误？
: 1. 进程倾向于占用CPU 2. 访问局部性（locality of
reference）满足进程要求
: 3. 进程倾向于占用I/O
4.使用基于最短剩余时间（shortest remaining time）的调度
: 机制 5. 减少页大小
: .................（以下省略）

☆──────────────────────────────────────☆
XSLT (雨人) 于 2006年10月11日10:57:52 星期三提到：

嗯
【在 Stratix (天马行空) 的大作中提到: 】
: 第二个函数不是找中间的节点吧？
: .................（以下省略）

☆──────────────────────────────────────☆
ningliu (蘑菇王子) 于 2006年10月11日10:58:28 星期三
提到：

第二题感觉有问题。

第七题代值排除即可。
第八题 3
第九题 2

【在 gobr (gobr) 的大作中提到: 】

2、
递归函数最终会结束，那么这个函数一定（不定项选择）：

1. 使用了局部变量 2. 有一个分支不调用自身
3. 使用了全局变量或者使用了一个或多个参数

这几个题咋做的。编译,图论，OS都还给老师了。。。
【在 acmboy (愛爸爸，愛媽媽，要有責任心)
的大作中提到: 】

☆──────────────────────────────────────☆
ningliu (蘑菇王子) 于 2006年10月11日10:58:58 星期三
提到：

http://www.comp.nus.edu.sg/~xujia/mirror/algorithm.myrice.com/algorithm/compl
exity/chapter6_3.htm

【在 XSLT (雨人) 的大作中提到: 】
介绍一下。。。？
【在 gobr (gobr) 的大作中提到: 】
: 直接套用公式就可以了。呵呵 T(N) = af(N/B) +
f(n)有一个公式的。使用了
: 一个平滑定理可以推出来。

☆──────────────────────────────────────☆
Ilovehlz (Ilovehlz) 于 2006年10月11日10:59:44 星期三
提到：

嗯，第二题有点含糊。

【在 ningliu (蘑菇王子) 的大作中提到: 】
: 第二题感觉有问题。
: 第七题代值排除即可。
: 第八题 3
: 第九题 2
: 2、
递归函数最终会结束，那么这个函数一定（不定项选择）：

: 1. 使用了局部变量 2. 有一个分支不调用自身
: 3. 使用了全局变量或者使用了一个或多个参数
:
7、n个顶点，m条边的全连通图，至少去掉几条边才能构成一棵树？
:
8、正则表达式(01|10|1001|0110)*与下列哪个表达式一样？
: .................（以下省略）

☆──────────────────────────────────────☆
XSLT (雨人) 于 2006年10月11日11:00:04 星期三提到：

谢谢 :)
【在 ningliu (蘑菇王子) 的大作中提到: 】
:
http://www.comp.nus.edu.sg/~xujia/mirror/algorithm.myrice.com/algorithm/compl
: exity/chapter6_3.htm
: 介绍一下。。。？

☆──────────────────────────────────────☆
gobr (gobr) 于 2006年10月11日11:02:41 星期三提到：

f(n) = n ^d
如果 a = b^d , T(n) = theta(n^d * logn)
a < b^d , T(n) = theta(n^d)
a > b^d , T(n) = theta(n^(logb a))

【在 XSLT (雨人) 的大作中提到: 】
: 介绍一下。。。？

☆──────────────────────────────────────☆
Ilovehlz (Ilovehlz) 于 2006年10月11日11:02:55 星期三
提到：

不止是静态变量的问题，再变态一点可以这样：
（当然这个有点牵强）

void f ()
{
if (random() > .99999) // 假设 random 返回 0-1
之间的伪随机浮点数
f();
}

【在 Stratix (天马行空) 的大作中提到: 】
: 恩，我觉得第二题12和23都可以，
: 但我选得是23，没考虑到静态变量
: .................（以下省略）

☆──────────────────────────────────────☆
XSLT (雨人) 于 2006年10月11日11:03:52 星期三提到：

赞，收藏
【在 gobr (gobr) 的大作中提到: 】
f(n) = n ^d
如果 a = b^d , T(n) = theta(n^d * logn)
a < b^d , T(n) = theta(n^d)
a > b^d , T(n) = theta(n^(logb a))

【在 XSLT (雨人) 的大作中提到: 】
: 介绍一下。。。？

☆──────────────────────────────────────☆
acmboy (愛爸爸，愛媽媽，要有責任心) 于
2006年10月11日11:04:08 星期三)
提到：

拜
【在 Ilovehlz 的大作中提到: 】
: 不止是静态变量的问题，再变态一点可以这样：
: （当然这个有点牵强）
: void f ()
: {
: if (random() > .99999) // 假设 random 返回 0-1
之间的伪随机浮点数
: f();
: }

☆──────────────────────────────────────☆
XSLT (雨人) 于 2006年10月11日11:04:57 星期三提到：

~cong
【在 Ilovehlz (Ilovehlz) 的大作中提到: 】
不止是静态变量的问题，再变态一点可以这样：
（当然这个有点牵强）

void f ()
{
if (random() > .99999) // 假设 random 返回 0-1
之间的伪随机浮点数
f();
}

【在 Stratix (天马行空) 的大作中提到: 】
: 恩，我觉得第二题12和23都可以，
: 但我选得是23，没考虑到静态变量
: .................（以下省略）

☆──────────────────────────────────────☆
acmboy (愛爸爸，愛媽媽，要有責任心) 于
2006年10月11日11:04:59 星期三)
提到：

不过random算不算使用了全局变量了呢?

【在 acmboy 的大作中提到: 】
: 拜

☆──────────────────────────────────────☆
Ilovehlz (Ilovehlz) 于 2006年10月11日11:05:05 星期三
提到：

不过这种代码本身就是 evil
的，可以不放入考虑之列。

【在 acmboy (愛爸爸，愛媽媽，要有責任心)
的大作中提到: 】
: 拜

☆──────────────────────────────────────☆
Ilovehlz (Ilovehlz) 于 2006年10月11日11:06:01 星期三
提到：

关键要看这个“使用”怎么个定义法了，所以我觉得这个题目尤其含糊。
用了随机数种子是肯定的，也是全局的。

【在 acmboy (愛爸爸，愛媽媽，要有責任心)
的大作中提到: 】
: 不过random算不算使用了全局变量了呢?

☆──────────────────────────────────────☆
acmboy (愛爸爸，愛媽媽，要有責任心) 于
2006年10月11日11:06:18 星期三)
提到：

还有一点考虑就是我决的,static
也应该算是全局的,可以这么说么?他的生存期肯定超出
了f()的范围
【在 acmboy 的大作中提到: 】
: 不过random算不算使用了全局变量了呢?

☆──────────────────────────────────────☆
acmboy (愛爸爸，愛媽媽，要有責任心) 于
2006年10月11日11:06:53 星期三)
提到：

...
【在 Ilovehlz 的大作中提到: 】
: 不过这种代码本身就是 evil
的，可以不放入考虑之列。

☆──────────────────────────────────────☆
Ilovehlz (Ilovehlz) 于 2006年10月11日11:08:03 星期三
提到：

是的，这个代码是可能 stack overflow
的，尽管概率足够小。

【在 acmboy (愛爸爸，愛媽媽，要有責任心)
的大作中提到: 】
: ...

☆──────────────────────────────────────☆
Ilovehlz (Ilovehlz) 于 2006年10月11日11:09:34 星期三
提到：

我也这么感觉的。
但是，从严格意义上说，静态局部变量和全局变量在概念上确实不是一个东西。这个是
我觉得这道题目含糊的又一处。

【在 acmboy (愛爸爸，愛媽媽，要有責任心)
的大作中提到: 】
: 还有一点考虑就是我决的,static
也应该算是全局的,可以这么说么?他的生存期肯定超出
: 了f()的范围

☆──────────────────────────────────────☆
Ilovehlz (Ilovehlz) 于 2006年10月11日11:10:27 星期三
提到：

因为，全局和局部指的是scope，静态和非静态只的是生命周期。

【在 Ilovehlz (Ilovehlz) 的大作中提到: 】
: 我也这么感觉的。
:
但是，从严格意义上说，静态局部变量和全局变量在概念上确实不是一个东西。这个是
: 我觉得这道题目含糊的又一处。

☆──────────────────────────────────────☆
gobr (gobr) 于 2006年10月11日11:11:45 星期三提到：

第8题的思路莫非：
(01|10|1001|0110)*
中的1001可以由01和10产生，所以1001可以除去。

0110可以由01和10产生，所以0110也除去。
这样就和C选项一样了。

第9题谁来说说原因

☆──────────────────────────────────────☆
acmboy (愛爸爸，愛媽媽，要有責任心) 于
2006年10月11日11:12:24 星期三)
提到：

恩,有道理,这种题还真是挺难的,考了n多概念
【在 Ilovehlz 的大作中提到: 】
:
因为，全局和局部指的是scope，静态和非静态只的是生命周期。

☆──────────────────────────────────────☆
ningliu (蘑菇王子) 于 2006年10月11日11:15:08 星期三
提到：

第八题选项1，4，5分别可以产生0，1，11但题设不能，故排除。

选项2即（01）*
，不可能产生1开头的串，但题设可以，也排除。

【在 gobr (gobr) 的大作中提到: 】
: 第8题的思路莫非：
: (01|10|1001|0110)*
中的1001可以由01和10产生，所以1001可以除去。
:
0110可以由01和10产生，所以0110也除去。
: 这样就和C选项一样了。
: 第9题谁来说说原因
: .................（以下省略）

☆──────────────────────────────────────☆
gobr (gobr) 于 2006年10月11日11:25:30 星期三提到：

最后一道题目：

从头开始遍历，记录负数的个数，0的个数，整数个数，以及正数最小值，
负数绝对值最小的元素以及负数绝对值最大的元素。

如果0的个数 >=2
则无论怎么选n-1结果都是0
如果0的个数只有一个
则看负数的个数
如果负数的个数为奇数
则随便去掉一个数。结果是0
如果负数的个数为偶数或者0个
则去掉这个0
如果不存在0元素
如果负数的个数为奇数
则去掉绝对值最小的负数
如果负数的个数为偶数
如果正数个数为0
则去掉绝对值最大的负数
如果正数个数不为0
则去掉最小的正整数

算法复杂度O(n) ，空间为O(1)

☆──────────────────────────────────────☆
gobr (gobr) 于 2006年10月11日11:26:30 星期三提到：

吃饭午睡呵呵
【在 gobr (gobr) 的大作中提到: 】
: 最后一道题目：
:
从头开始遍历，记录负数的个数，0的个数，整数个数，以及正数最小值，
: 负数绝对值最小的元素以及负数绝对值最大的元素。
: 如果0的个数 >=2
: 则无论怎么选n-1结果都是0
: 如果0的个数只有一个
: 则看负数的个数
: 如果负数的个数为奇数
: 则随便去掉一个数。结果是0
: 如果负数的个数为偶数或者0个
: .................（以下省略）

☆──────────────────────────────────────☆
ningliu (蘑菇王子) 于 2006年10月11日11:32:56 星期三
提到：

编程第二题，大家帮忙看看。

Node* someFunc(Node* head)
{
int i=0;
Node* temp = head;
if(!head)
{
return NULL;
}
else
{
while(temp)
{
i++;
temp = temp->next;
}

i = ((i%2)==0)?i/2:(i+1)/2;

temp = head;
for(int j = 1;j<i;++j)
{
temp=temp->next;
}
return temp;
}
}
【在 ningliu (蘑菇王子) 的大作中提到: 】

第八题选项1，4，5分别可以产生0，1，11但题设不能，故排除。

选项2即（01）*
，不可能产生1开头的串，但题设可以，也排除。

☆──────────────────────────────────────☆
acmboy (愛爸爸，愛媽媽，要有責任心) 于
2006年10月11日11:43:14 星期三)
提到：

赞
【在 gobr 的大作中提到: 】
: 最后一道题目：
:
:
从头开始遍历，记录负数的个数，0的个数，整数个数，以及正数最小值，
: 负数绝对值最小的元素以及负数绝对值最大的元素。
: 如果0的个数 >=2
: 则无论怎么选n-1结果都是0
: 如果0的个数只有一个
: 则看负数的个数
: 如果负数的个数为奇数
: 则随便去掉一个数。结果是0
: 如果负数的个数为偶数或者0个
: 则去掉这个0
: 如果不存在0元素
: 如果负数的个数为奇数
: 则去掉绝对值最小的负数
: 如果负数的个数为偶数
: 如果正数个数为0
: 则去掉绝对值最大的负数
: 如果正数个数不为0
: 则去掉最小的正整数
: (以下引言省略...)

☆──────────────────────────────────────☆
SEMFirm (Search Engine) 于 2006年10月11日11:50:32 星期三
提到：

和我思路一样；

不过为了求妥，我将空间复杂度随便说成O(n)了，该死

【在 gobr (gobr) 的大作中提到: 】
: 最后一道题目：
:
从头开始遍历，记录负数的个数，0的个数，整数个数，以及正数最小值，
: 负数绝对值最小的元素以及负数绝对值最大的元素。
: 如果0的个数 >=2
: 则无论怎么选n-1结果都是0
: 如果0的个数只有一个
: 则看负数的个数
: 如果负数的个数为奇数
: 则随便去掉一个数。结果是0
: 如果负数的个数为偶数或者0个
: .................（以下省略）

Reply all

Reply to author

Forward

0 new messages