本文: [转寄][转贴][删除][修改][回复][作者: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 <stdio.h> 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 <stdio.h> 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 <stdio.h> : 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 <stdio.h> : int main(){ : const char *p,*q; : p="abcde"; : (以下引言省略...) ☆──────────────────────────────────────☆ PointGuard (♀0111♂~土人) 于 2006年10月18日16:28:01 星期三 提到： 【 在 ipx 的大作中提到: 】 : 发现下面两个程序的结果不同，哪位解释一下？ : ///aa.c: : #include <stdio.h> : 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 <stdio.h> : 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 <stdio.h> : 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] | 
