今天北京的Google笔试2006
瀚海星云 - 同主题文章阅读 讨论区：Job 版主: wZhOu wqstar
回复本文 本讨论区
本文: [转寄][转贴][删除][修改][回复][作者: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
: 先从编程说起吧
: 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]
回复本文 本讨论区