发信人: whqnju (男儿何不带吴钩，收取关山五十州 ), 信区: Algorithm. 本篇人气: 1401标

题: Google公司预选笔试试题发信站: 南京大学小百合站 (Sat May 12 18:00:07 2007)大家有兴趣看看吧，5/10 sjtu的考卷。选择题3、8我蒙的，大牛给解答一下。1.单项选择题1.

下面一段代码的输出是[

]void fn( int* b){

(*b)++;}int main(){

int a=7;

fn(&a);cout}A.0

B.7

C.8

D.undefined2.

定义int i,j,*p=&i; 那么下面哪条语句可以完成i=j的赋值[

]A.i=*p;

B. *p=*&j;

C.i=&j;

D.I=**p;3.

用二叉搜索树和哈希表存储相同的数据集,对于以下何种操作,二叉搜索树比哈希表速度更快?[

]A.检索

B. 插入

C.删除

D.更新

E.排序4.

包含N个几点和M条边的有向带权图G, 边的权为正, 以下操作中不可以在O(N+M)的时间复杂度内完成的操作是:[

]A.

求结点s到结点t之间的最短距离B.

求距离结点s最近的结点C.

已知起始结点, 对图G中的结点进行拓扑排序D.

求图G的最大强连通子图5.

有如下递归函数f(n),其时间复杂度为[

]int f(int n){

if(n==0)

return 0;

if(n==1)

return 1;

return ( 5*f(n-1) - 6*f(n-2));}A.O(n)

B. O(n^2)

C. O(n^3)

D. O(2^n)6.

下面所述步骤中,哪一个不是创建经常所必需有的[

]A.由调度程序为进程分配CPU

B.建立一个进程控制块C.为进程分配内存

D.将进程控制块链入就绪队列7.

在多进程的系统中,为了保证公区变量的完整性,各进程应互斥进入临界区。所谓临界区是[

]A.一个缓冲区

B.一个数据区

C.一个同步机构

D.一段程序8.

能产生满足如下条件语言的正则表达式是：1.每一个a后至少紧跟两个c; 2.每一个b后至少紧跟一个c [

]A.(acc|bc|c)*

B.(acc|bc)* C.(ac|bc)*

D.不是正则语言9.

以下哪项不是RPC（远程过程调用）的特点[

]A.速度快

B.降低系统耦合度

C.可以实现异构系统间的协作10. 有三个桶，容量分别是3升，5升，7升，你只能进行下面的操作：把一个桶中所有的水倒掉；把一个桶A中的水倒入桶B，直到桶A空了或者桶B满了；假设一开始容量为3升和5升的桶是满的，7升的桶是空的，希望通过一系列操作使3个桶中任意一个中正好有4升水，那么至少需要[

]次操作。A.3

B.5

C.7

D.不可能2.

程序设计与算法2.1 实现如下编码算法，对于重复2-9次数的字符，用两个数字表示，即NX（其中N为重复的次数，X为重复的字符，下同），超过九个则先输出9X，然后处理剩下的字符。对于连续的不重复的字符，则两边加1来封字符串。如果被封的字符串其中有数字为1，则用1来转义。

示例： AAAAAABCCCC -> 6A1B14C,

12344 -> 11123124。。。（下面的框架是用C++语言写的。你可以用你熟悉的语言。）void encode (const char* text, char* dest)text 为需要编码的字符串，dest表示编码输出的目标空间，而空间足够大2.2给定一颗有n个结点的二叉树。求它的所有结点数为m的连通子图数目。m<=n分析你的算法的时间复杂度，解释算法即可，不必写代码。