2011_google笔试题_完整版.doc
40墨值下载
一、选择题
(1)
以下哪个字符串不能被正则表达式
a(bc)*d*
匹配到？
A. ad
B. abcd
C. abc
D. abccd
(2)
在
x86 cpu
中，下面哪种运算速度最慢？
A.
加
B.
减
C.
乘
D.
除
(3)
下面程序输出的结果是什么？
void main()
{
bool first=true;
int sum =0;
int current_value;
for(unsigned short i=65535;i>=0;--i )
{
if(first)
{
current_value=65535;
sum+=current_value%3;
first=false;
}
else
{
sum+=-current_value%3;
if(current_value<=0)
{
printf("%d,%d",sum,i);
break;
}
}
}
}
A. 65535, 0
B. 65536, 1
C. 65536, 65535
D. 65536, 0
(4)
书架上有编号为
1-19
的
19
本书，从中拿
5
本，问
5
本编号都不相邻的拿法有多
少种？
A. 2002
B. 3003
C. 11628
D.
比
C
大的一个数，具体多少我忘记
了。
(5)
现在有一套房子，价格
200
万，假设房价每年上涨
10%
，一个软件工程师每年
固定能赚
40
万。如果他想买这套房子，不贷款，不涨工资，没有其他收入，那么他需要
几年才能攒够钱买这套房子？
A. 5
年
B. 7
年
C. 8
年
D. 9
年
E.
永远买不起
(6)
一棵满二叉树，一共有
n
个叶子节点，请问该二叉树一共有多少个节点？
A. 2n-1
B. 2n
C. n-1
D. n
(7)
下列哪种排序方法在最坏情况下的时间复杂度是
nlgn
？
A.
归并排序
B.
快速排序
C.
冒泡排序
D.
插入排序
(8)
有两个从小到大排好序的数组，长度分别是
N
和
M
，将这两个数组合并成一个有
序数组的最小比较次数是：？
A min(N,M)
B M+N-1
C N+M
D max(M,N)
(9)
关于
TLB
和
Cache
的说法中，哪个是错的？
A. TLB
与
Cache
中保存的数据是不同的
B. TLB miss
后，有可能直接在
Cache
中找到页表内容
C. TLB miss
后会导致程序出错，但是
Cache miss
不会
D TLB
和
Cache
的命中率都与程序的访存模式有关
(10)
关于数据库的说法，哪个是错误的？
A.
每个表都必须有主键
B.
跨表查询可能非常慢
C.
数据库不支持多个用户对同一个表进行写操作
D.
多维索引可以用
KD
树实现
二、编程算法题
(1)
编程实现多项式求值：
f(n)=a0+ a1*x^1 + a2*x^2 +…+ an*x^n
，
函数声明如下：
double foo(double x, double *A, int N)
。
(2)
现在有
n=2^k
支足球队，编号为
0
，
1
，…，
n-1
，给出
2
维数组
winner[]
[],winner[i][j]
表示当编号
i
和
j
的会胜出的队伍的编号，并且没有平局，输入保证
winner[i][j]==winner[j][i],
现在给出一个单败淘汰赛的签位一维数组
order[],order[i]
表示第
i
个签位上的队伍的编号，
order
保证是
0
到
n-1
的一个排列。返回比赛最后的排
名顺序，同一轮被淘汰的队伍名词并列，并列的队伍之间的顺序任意，要求时间和空间复
杂度尽量的低，将结果写到一维数组
result[]
里面即可。
接口定义：
c++
：
void calculate_result(int n,vector<vector<int>> winner,vector<int>
order,vector<int> result);
例子：
N=4
，
winner={{0,1,2,3},{1,1,2,1},{2,2,2,3},
{3,1,3,3}},order={0,1,2,3}
…
(3) KOF
游戏相关，玩过
KOF
（拳皇）的人都知道，玩的时候如果按照一定的按键
次序就会连招，连招的威力很大。现在题目的意思是：每招用一个大写字母表示，如
ABC
… Z
，现给定
n
个连招公式：
S→T
，每个公式的
S
长度都相同，都为
m
，
T
的长度为
1
。每个公式都代表一个连招规则，表示如果之前的
m
招为
S
，那么可以在后面连出一招
T
， 在前
m
招的时候可以随便连，但
m+1
招后就必须遵循连招公式。现在要写一个算法，
计算最长连招的长度；如果可以无限连招，则返回
def
。（
1≤n, m≤100
）
这里有一个例子：
n=4, m=3
，连招公式为：
ABC→D
，
ABC→C
，
CCA→A
，
BCC→A
。连招公式的意思是：
A
、
B
、
C
可以连出
C
，
of 3
40墨值下载
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文档的来源（墨天轮），文档链接，文档作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
下载排行榜
评论