本文: [转寄][转贴][删除][修改][回复][作者: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] |