今天北京的Google笔试2006

瀚海星云 - 同主题文章阅读 讨论区：Job 版主:wZhOuwqstar
本讨论区
本文: [转寄][转贴][删除][修改][回复][作者:ustcbbs][人气:57] 发信人: ustcbbs (自动发信系统), 信区: Job                                       标  题: 【合集】今天北京的Google笔试 发信站: 瀚海星云自动发信系统(2006年10月19日01:41:40 星期四) ☆──────────────────────────────────────☆      Weitz (魏氏春秋:小硕～) 于 2006年10月17日22:16:24 星期二 提到： 9道选择，3道编程，都考得是基本知识，看来数据结构真的很重要！ 先从编程说起吧 1.已知一二叉树，给一个值，搜索二叉树，如果有匹配的节点，返回其地址指针， 如果没有，返回NULL 2.求tribonacci数列，t(0)=1,t(1)=1,t(2)=2,t>2时,t(n)=t(n-1)+t(n-2)+t(n-3) 不考虑溢出,写出尽可能高效的代码 3.在一个有n个定点的有向图中任意两点间判断K步路径的存在性，不需要写代码， 给出尽可能优化的算法和说明，时间和空间复杂度 选择题若干，我挑记起来的说吧： 1.已知一二叉树中序遍历123456，5为右子树父节点，求可能的一个节点插入顺序 a，123456 b，123546 c，321546 d，321456 e，321465 2.一个有n个节点的完全图有多少条边？ a，n b，n^2 c，n*(n-1)/2 d，n^3 e，忘了... 3.有个函数为： int a(int x,int y){   if(x<=0||y<=0) return 1;   return(a(x,y-1)+a(y,x-1)); } 求a(3,2)的结果 a，9 b，10 c，11 d，12 e，13 4.操作系统中线程的作用集指的是： a，线程访问的内存地址集 b，cpu给线程分配的资源 c，线程分配的I/O资源 d，线程收回的空内存 e，忘了... 这个是操作系统的，我给忘得一干二净... 5.有个程序 main(){    const char *p,*q;    p="abcde";    q=p;    q="12345";    const char *s=++p;    p="ABCDE"；    printf("%c",*++s); } 问结果是什么？ a，c b，b c，3 d，A e，B 6.已知有如下正则表达式 S=AB|AS A=a|aA B=b 则下列哪个答案满足上述规则 a，aab*+ b，aab* c，a(ab)*b d，(aab)*b e，忘了... 这个是编译原理得题，答案记不太清了，反正我是没搞清楚-_-b，早知到当初 上课不睡觉了 7.两个长度分别为m和n得有序线性链表，合并为一个链表的最大时间复杂度 a，m b，n c，m+n d，m+n+1 e，m+n-1 还有两道题我很痛快得答过去了，没记住，攒个rp先～ 今天顺便看了一下清华得就业中心日历，投行和四大什么的都去宣讲，唉 啥时候科大也有这么好待遇就好了 不说了，去洗澡了，今天因为堵车我从青年公寓裸走到清华，累 ☆──────────────────────────────────────☆      zzqu (人间有冷无暖) 于 2006年10月17日22:19:42 星期二 提到： 编程早忘记了，怎么办啊．哎 【 在 Weitz 的大作中提到: 】 : 9道选择，3道编程，都考得是基本知识，看来数据结构真的很重要！
: 先从编程说起吧
: 1.已知一二叉树，给一个值，搜索二叉树，如果有匹配的节点，返回其地址指针，
: 如果没有，返回NULL
: 2.求tribonacci数列，t(0)=1,t(1)=1,t(2)=2,t>2时,t(n)=t(n-1)+t(n-2)+t(n-3)
: 不考虑溢出
: 3.在一个有n个定点的有向图中任意两点间判断K步路径的存在性，不需要写代码，
: 给出尽可能优化的算法和说明，时间和空间复杂度
: 选择题若干，我挑记起来的说吧：
: 1.已知一二叉树中序遍历123456，5为右子树父节点，求可能的一个节点插入顺序
: a，123456
: b，123546
: c，321546
: d，321456
: e，321465
: 2.一个有n个节点的完全图有多少条边？
: a，n
: b，n^2
: c，n*(n-1)/2
: d，n^3
: (以下引言省略...)
☆──────────────────────────────────────☆      wqstar (心有所愿) 于 2006年10月17日22:22:39 星期二 提到： google好爱考二叉树啊 【 在 Weitz (魏氏春秋:小硕～) 的大作中提到: 】 : 9道选择，3道编程，都考得是基本知识，看来数据结构真的很重要！
: 先从编程说起吧
: 1.已知一二叉树，给一个值，搜索二叉树，如果有匹配的节点，返回其地址指针，
: 如果没有，返回NULL
: 2.求tribonacci数列，t(0)=1,t(1)=1,t(2)=2,t>2时,t(n)=t(n-1)+t(n-2)+t(n-3)
: 不考虑溢出
: 3.在一个有n个定点的有向图中任意两点间判断K步路径的存在性，不需要写代码，
: 给出尽可能优化的算法和说明，时间和空间复杂度
: 选择题若干，我挑记起来的说吧：
: 1.已知一二叉树中序遍历123456，5为右子树父节点，求可能的一个节点插入顺序
: .................（以下省略）
☆──────────────────────────────────────☆      pmzqonxw (笑狐狸·德国伪球迷) 于 2006年10月17日22:31:20 星期二 提到： 第5题那个程序....编译通不过。 【 在 Weitz (魏氏春秋:小硕～) 的大作中提到: 】 : 9道选择，3道编程，都考得是基本知识，看来数据结构真的很重要！
: 先从编程说起吧
: 1.已知一二叉树，给一个值，搜索二叉树，如果有匹配的节点，返回其地址指针，
: 如果没有，返回NULL
: 2.求tribonacci数列，t(0)=1,t(1)=1,t(2)=2,t>2时,t(n)=t(n-1)+t(n-2)+t(n-3)
: 不考虑溢出
: 3.在一个有n个定点的有向图中任意两点间判断K步路径的存在性，不需要写代码，
: 给出尽可能优化的算法和说明，时间和空间复杂度
: 选择题若干，我挑记起来的说吧：
: 1.已知一二叉树中序遍历123456，5为右子树父节点，求可能的一个节点插入顺序
: .................（以下省略）
☆──────────────────────────────────────☆      Weitz (魏氏春秋:小硕～) 于 2006年10月17日22:36:16 星期二 提到： 改了一下 q=p； 不过记得原题不是这样的，但是好像对结果没影响吧 【 在 pmzqonxw (笑狐狸·德国伪球迷) 的大作中提到: 】 : 第5题那个程序....编译通不过。
: .................（以下省略）
☆──────────────────────────────────────☆      ipx (穆尔如云-白日无梦) 于 2006年10月17日23:16:55 星期二 提到： 第三个编程怎么搞啊？ 【 在 Weitz (魏氏春秋:小硕～) 的大作中提到: 】 : 9道选择，3道编程，都考得是基本知识，看来数据结构真的很重要！
: 先从编程说起吧
: 1.已知一二叉树，给一个值，搜索二叉树，如果有匹配的节点，返回其地址指针，
: 如果没有，返回NULL
: 2.求tribonacci数列，t(0)=1,t(1)=1,t(2)=2,t>2时,t(n)=t(n-1)+t(n-2)+t(n-3)
: 不考虑溢出
: 3.在一个有n个定点的有向图中任意两点间判断K步路径的存在性，不需要写代码，
: 给出尽可能优化的算法和说明，时间和空间复杂度
: 选择题若干，我挑记起来的说吧：
: 1.已知一二叉树中序遍历123456，5为右子树父节点，求可能的一个节点插入顺序
: .................（以下省略）
☆──────────────────────────────────────☆      dudu (9700~嘟嘟) 于 2006年10月17日23:18:24 星期二 提到： 其实好像有个简单的办法，就是做矩阵相乘 【 在 ipx (穆尔如云-白日无梦) 的大作中提到: 】 : 第三个编程怎么搞啊？
: .................（以下省略）
☆──────────────────────────────────────☆      ipx (穆尔如云-白日无梦) 于 2006年10月17日23:21:15 星期二 提到： 一个数组，记录第N步可以到达的地方，然后根据这个数组算N+1可以到达的地方， 一直到第K步， 不知道效率如何 【 在 dudu (9700~嘟嘟) 的大作中提到: 】 : 其实好像有个简单的办法，就是做矩阵相乘
☆──────────────────────────────────────☆      Murphoenix (---) 于 2006年10月17日23:26:47 星期二 提到： BFS? 最直接的想法 【 在 dudu (9700~嘟嘟) 的大作中提到: 】 : 其实好像有个简单的办法，就是做矩阵相乘
☆──────────────────────────────────────☆      Weitz (魏氏春秋:小硕～) 于 2006年10月17日23:46:16 星期二 提到： 今天听google的工程师说这第三道题答得很好的话，google会对你很重视的... 【 在 ipx (穆尔如云-白日无梦) 的大作中提到: 】 : 第三个编程怎么搞啊？
: .................（以下省略）
☆──────────────────────────────────────☆      ipx (穆尔如云-白日无梦) 于 2006年10月17日23:48:01 星期二 提到： 那有没有说到底怎么搞呢？ 【 在 Weitz (魏氏春秋:小硕～) 的大作中提到: 】 : 今天听google的工程师说这第三道题答得很好的话，google会对你很重视的...
☆──────────────────────────────────────☆      HooK (...) 于 2006年10月17日23:48:10 星期二 提到： 自己想啊…… 【 在 ipx (穆尔如云-白日无梦) 的大作中提到: 】 : 那有没有说到底怎么搞呢？
☆──────────────────────────────────────☆      CoffeeOrTea (泡面的幸福) 于 2006年10月18日10:51:28 星期三 提到： 很容易吧,那本经典的算法导论里面全部都有讲 我按路由那种思想做的,恩 【 在 ipx 的大作中提到: 】 : 那有没有说到底怎么搞呢？
☆──────────────────────────────────────☆      CoffeeOrTea (泡面的幸福) 于 2006年10月18日10:53:36 星期三 提到： 第5题我记得开始是const char* p = "xxxxx"之类,大体意思没错 【 在 pmzqonxw 的大作中提到: 】 : 第5题那个程序....编译通不过。
☆──────────────────────────────────────☆      skyguide (skyguide) 于 2006年10月18日11:53:35 星期三 提到： 【 在 CoffeeOrTea 的大作中提到: 】 : 很容易吧,那本经典的算法导论里面全部都有讲
:
: 我按路由那种思想做的,恩
:
哪本经典的算法导论啊，该不会是那个很厚的英文版的吧 ☆──────────────────────────────────────☆      wqstar (心有所愿) 于 2006年10月18日11:59:09 星期三 提到： 读者服务部有中文的 【 在 skyguide (skyguide) 的大作中提到: 】 :
:
: 哪本经典的算法导论啊，该不会是那个很厚的英文版的吧
☆──────────────────────────────────────☆      ncs (never can stop) 于 2006年10月18日12:02:37 星期三 提到： 现在还有吗 似乎 N年前就没有了 【 在 wqstar 的大作中提到: 】 : 读者服务部有中文的
☆──────────────────────────────────────☆      sunboy (阳光男孩) 于 2006年10月18日14:56:06 星期三 提到： 第3题的 const char c定义应该在最上端，不然语法错误的，估计题目应该是~~~~ main(){    const *p,*q;    p="abcde";    q=p;    q="12345";    const *s=++p;    p="ABCDE"；    printf("%c",*++s); } 当然，这到题裸考指针没什么说头 【 在 Weitz 的大作中提到: 】 : 9道选择，3道编程，都考得是基本知识，看来数据结构真的很重要！
: 先从编程说起吧
: 1.已知一二叉树，给一个值，搜索二叉树，如果有匹配的节点，返回其地址指针，
: 如果没有，返回NULL
: 2.求tribonacci数列，t(0)=1,t(1)=1,t(2)=2,t>2时,t(n)=t(n-1)+t(n-2)+t(n-3)
: 不考虑溢出,写出尽可能高效的代码
: 3.在一个有n个定点的有向图中任意两点间判断K步路径的存在性，不需要写代码，
: 给出尽可能优化的算法和说明，时间和空间复杂度
: 选择题若干，我挑记起来的说吧：
: 1.已知一二叉树中序遍历123456，5为右子树父节点，求可能的一个节点插入顺序
: a，123456
: b，123546
: c，321546
: d，321456
: e，321465
: 2.一个有n个节点的完全图有多少条边？
: a，n
: b，n^2
: c，n*(n-1)/2
: d，n^3
: (以下引言省略...)
☆──────────────────────────────────────☆      Saleen (bottle--9802er) 于 2006年10月18日14:58:51 星期三 提到： C++中变量可以随处定义 【 在 sunboy (阳光男孩) 的大作中提到: 】 : 第3题的 const char c定义应该在最上端，不然语法错误的，估计题目应该是~~~~
:
: main(){
:    const *p,*q;
:    p="abcde";
:    q=p;
:    q="12345";
:    const *s=++p;
:    p="ABCDE"；
:    printf("%c",*++s);
: }
: 当然，这到题裸考指针没什么说头
:
☆──────────────────────────────────────☆      ipx (穆尔如云-白日无梦) 于 2006年10月18日15:05:08 星期三 提到： 发现下面两个程序的结果不同，哪位解释一下？ ///aa.c: #include  int main(){    const *p,*q;    p="abcde";    q=p;    q="12345";    const *s=++p; p="ABCDE";    printf("%c",*++s);   return 0; } $gcc aa.c $./a.out ///输出3 ///aa.cpp #include  int main(){    const char *p,*q;    p="abcde";    q=p;    q="12345";    const char *s=++p; p="ABCDE";    printf("%c",*++s);   return 0; } $g++ aa.cpp $./a.out  //输出c 【 在 Saleen (bottle--9802er) 的大作中提到: 】 : C++中变量可以随处定义
: .................（以下省略）
☆──────────────────────────────────────☆      longport (happyboy) 于 2006年10月18日15:11:07 星期三 提到： 考const，呵呵 【 在 sunboy 的大作中提到: 】 : 第3题的 const char c定义应该在最上端，不然语法错误的，估计题目应该是~~~~
:
: main(){
:    const *p,*q;
:    p="abcde";
:    q=p;
:    q="12345";
:    const *s=++p;
:    p="ABCDE"；
:    printf("%c",*++s);
: }
: 当然，这到题裸考指针没什么说头
:
: (以下引言省略...)
☆──────────────────────────────────────☆      duduzhu (我是廷娜的老公，阿根) 于 2006年10月18日15:12:12 星期三 提到： const *p;默认int型指针，++的时候跳过4个字节 【 在 ipx 的大作中提到: 】 : 发现下面两个程序的结果不同，哪位解释一下？
: ///aa.c:
: #include 
: int main(){
:    const *p,*q;
:    p="abcde";
:    q=p;
:    q="12345";
:    const *s=++p;
: p="ABCDE";
:    printf("%c",*++s);
:   return 0;
: }
: $gcc aa.c
: $./a.out ///输出3
: ///aa.cpp
: #include 
: int main(){
:    const char *p,*q;
:    p="abcde";
: (以下引言省略...)
☆──────────────────────────────────────☆      PointGuard (♀0111♂~土人) 于 2006年10月18日16:28:01 星期三 提到： 【 在 ipx 的大作中提到: 】 : 发现下面两个程序的结果不同，哪位解释一下？
: ///aa.c:
: #include 
: int main(){
:    const *p,*q;
:    p="abcde";
:    q=p;
:    q="12345";
:    const *s=++p;
: p="ABCDE";
:    printf("%c",*++s);
:   return 0;
: }
: $gcc aa.c
: $./a.out ///输出3
~~~~~~~~~~~~~~~~~~~~~输出是e吧 : ///aa.cpp
: #include 
: int main(){
:    const char *p,*q;
:    p="abcde";
: (以下引言省略...)
☆──────────────────────────────────────☆      ipx (穆尔如云-白日无梦) 于 2006年10月18日16:44:47 星期三 提到： 呵呵，就是3，前面有人说原因了 【 在 PointGuard (♀0111♂~土人) 的大作中提到: 】 :
: .................（以下省略）
☆──────────────────────────────────────☆      rLuoY (★~Do Something Really) 于 2006年10月18日17:06:04 星期三 提到： china-pub今年刚新出的 【 在 ncs (never can stop) 的大作中提到: 】 : 现在还有吗
: 似乎 N年前就没有了
☆──────────────────────────────────────☆      xhacker (泡泡龙) 于 2006年10月18日17:08:03 星期三 提到： ms读者服务部的那个是偷偷翻译的 【 在 rLuoY (★~Do Something Really Cool~★) 的大作中提到: 】 : china-pub今年刚新出的
☆──────────────────────────────────────☆      sinrohu (Or-------------z) 于 2006年10月18日17:08:20 星期三 提到： 为什么等于3？ 是不是因为给12345分配的内存紧跟着abcde 【 在 ipx (穆尔如云-白日无梦) 的大作中提到: 】 : 发现下面两个程序的结果不同，哪位解释一下？
: ///aa.c:
: #include 
: int main(){
:    const *p,*q;
:    p="abcde";
:    q=p;
:    q="12345";
:    const *s=++p;
: p="ABCDE";
: .................（以下省略）
☆──────────────────────────────────────☆      wqstar (心有所愿) 于 2006年10月18日17:09:29 星期三 提到： 版权问题? 【 在 xhacker (泡泡龙) 的大作中提到: 】 : ms读者服务部的那个是偷偷翻译的
☆──────────────────────────────────────☆      xhacker (泡泡龙) 于 2006年10月18日17:09:37 星期三 提到： 欢迎来ansic版 嘻嘻 【 在 sinrohu (Or-------------z) 的大作中提到: 】 : 为什么等于3？
: 是不是因为给12345分配的内存紧跟着abcde
: .................（以下省略）
☆──────────────────────────────────────☆      Voldemort (飘在阴间的小路上|0) 于 2006年10月18日17:11:36 星期三 提到： 那是南大翻译的吧 没出版 【 在 xhacker (泡泡龙) 的大作中提到: 】 : ms读者服务部的那个是偷偷翻译的
-- ※ 来源:·瀚海星云 bbs.ustc.edu.cn·[FROM: ::1]
本讨论区