百度2010笔试题分析和总结.docx

2010年实习生招聘笔试题RD-混合

试卷说明：

!--[if!supportLists]--1. !--[endif]--本试卷共两套题目，请先用几分钟的时间浏览一遍，选择一套适合你的试卷进行笔试。

!--[if!supportLists]--2. !--[endif]--请在您答案的第一行标注您选择的是A卷还是B卷。

!--[if!supportLists]--3. !--[endif]--两套试卷的成绩不会合并计算，仅计算其中一套的分数。请安排好答题时间，不要两套都做而耽误时间。

A

A卷（共三道大题）

【请先阅读卷首的试卷说明，在A、B卷选择一套试卷作答，同时作答试卷无效】第一题、简答题

!--[if!supportLists]--1．!--[endif]--简要说明树的深度优先、广度优先遍历算法，及非递归实现的特点。

!--[if!supportLists]--2．!--[endif]--在处理磁盘数据时，需要首先将其读入内存才能进行处理。如果要读取的数据已经在内存中，则可以直接访问内存。通常来说内存是有限的，因此要读取新的数据时必须覆盖内存中一部分原有的数据。假设现在有n块同样大小的数据，内存一共可以容纳m块数据。现在给出一系列对这些数据的读取请求，要求它们必须按照给定的顺序被读取，同时要求读取磁盘的次数尽可能地少。请简述一个策略满足这样的要求。

第二题、算法与程序设计

百度全体员工玩分组游戏，前面五分钟大家分头找队友，并将每个人找到的队友信息汇报给主持人，如果A和B是队友，B和C是队友，那么A和C也是队友；接着主持人不断地随机抽取两个人，希望判断二者是否为队友。请设计一个计算机程序辅助主持人判断两个人是否为队友，说明程序的关键算法，不需要代码实现。

例如：

小明，小王，小军，小王，小丽，小李是队友，那么小军和小明是队友，小军和小丽不是队友。

给定以下二叉树:

structnode_t

{

node_t*left,*right;intvalue;

};

要求编写函数node_t*foo(node_t*node,unsignedintm,unsignedintk);

输出以node为根的二叉树第m层的第k个节点值.(level,k均从0开始计数)

注意：

!--[if!supportLists]--1）!--[endif]--此树不是完全二叉树；

!--[if!supportLists]--2）!--[endif]--所谓的第K个节点，是本层中从左到右的第K个节点

第三题、系统设计题

百度打算开发一个投票系统，它提供创建、查看、参与和管理投票功能。用户创建一个投票时，有如下信息可知：创建者、标题、各选项内容、截止时间、可投票数。另外，该投票是否对所有用户可见继承于创建者的个性设置。查看一个投票时，除了显示上述信息外，还需要显示每个选项的投票数。在截止时间之前，用户可以参与投票。管理投票功能为创建者提供删除一个投票和调整进行中投票截止时间的功能。

预计该投票系统会很受用户欢迎，每天可望创建超过1万个投票。每天浏览次数达数百万，并且有约一百万人次参与投票。经验还表明，用户更喜欢新近的内容。

实习生小A针对上述需求，打算用数据库来实现这个投票系统，他给出了数据库的表设计如下：

user_info：

uid

uid

1

name

“AlexWang”

…

…

visible

1(all)

2

2

“JeffLi”

…

0(self)

vote_info：

vid

id

utitle

options

counts

close_time

max

visible

1

1“DoyoulikeLadyGaga?”

“Yes;No;Who?”

“4;2;

1”

1339071276

1

1

2

1“Who’sthebestforward?”

“Messi;

Ronaldo;

“912;

654;

1339076234

1

1

Droba;

Millito”

400;

301”

（红色为主键）问题：

1、小A的设计存在什么问题，如何改善？

2、如果想增加一个功能，即每个用户对每个投票只能投一次。如何设计？

3、系统运行了较长一段时间之后，用户反馈使用中速度变慢。请分析可能的原因，并提出解决办法。

4、请完整给出新系统下各功能的实现流程。涉及数据库查询的，请给出SQL语句。

B

B卷（共三道大题）

【请先阅读卷首的试卷说明，在A、B卷选择一套试卷作答，同时作答试卷无效】第一题、算法和程序设计题

1、请编写函数foo(intx,inty,intn)计