九乡新闻网黑色锻甲:百度笔试题 - 天道酬勤 - 博客园
来源：百度文库 编辑：九乡新闻网 时间：2024/05/01 02:49:37
百度笔试题
刚下车，错过了考试时间(-_-)b ：
1． 简要说明树的深度优先、广度优先遍历算法，及非递归实现的特点。
2． 在处理磁盘数据时，需要首先将其读入内存才能进行处理。如果要读取的数据已经在内存中，则可以直接访问内存。通常来说内存是有限的，因此要读取新的数据时必须覆盖内存中一部分原有的数据。假设现在有n块同样大小的数据，内存一共可以容纳m块数据。现在给出一系列对这些数据的读取请求，要求它们必须按照给定的顺序被读取，同时要求读取磁盘的次数尽可能地少。请简述一个策略满足这样的要求。
第二题 算法与程序设计题
1．百度全体员工玩分组游戏，前面五分钟大家分头找队友，并将每个人找到的队友信息汇报给主持人，如果A和B是队友，B和C是队友，那么A和C也是队友；接着主持人不断地随机抽取两个人，希望判断二者是否为队友。请设计一个计算机程序辅助主持人判断两个人是否为队友，说明程序的关键算法，不需要代码实现。
例如：
<小明，小王>，<小军，小王>，<小丽，小李>是队友，那么小军和小明是队友，小军和小丽不是队友。
2．给定以下二叉树:
struct node_t
{
node_t *left, *right;
int value;
};
要求编写函数 node_t* foo(node_t *node, unsigned int m, unsigned int k);
输出以 node 为根的二叉树第 m 层的第 k 个节点值.
(level, k 均从 0 开始计数)
注意：
.此树不是完全二叉树；
.所谓的第K个节点，是本层中从左到右的第K个节点
第三题 系统设计题
百度打算开发一个投票系统，它提供创建、查看、参与和管理投票功能。用户创建一个投票时，有如下信息可知：创建者、标题、各选项内容、截止时间、可投票数。另外，该投票是否对所有用户可见继承于创建者的个性设置。查看一个投票时，除了显示上述信息外，还需要显示每个选项的投票数。在截止时间之前，用户可以参与投票。管理投票功能为创建者提供删除一个投票和调整进行中投票截止时间的功能。
预计该投票系统会很受用户欢迎，每天可望创建超过1万个投票。每天浏览次数达数百万，并且有约一百万人次参与投票。经验还表明，用户更喜欢新近的内容。
实习生小A针对上述需求，打算用数据库来实现这个投票系统，他给出了数据库的表设计如下：
user_info：
uid
name
…
visible
1
“Alex Wang”
…
1 (all)
2
“Jeff Li”
…
0 (self)
vote_info：
vid
uid
title
options
counts
close_time
max
visible
1
1
“Do you like Lady Gaga?”
“Yes; No; Who?”
“4; 2; 1”
1339071276
1
1
2
1
“Who’s the best forward?”
“Messi; Ronaldo; Droba; Millito”
“912; 654; 400; 301”
1339076234
1
1
（红色为主键）
问题：
1、小A的设计存在什么问题，如何改善？
2、如果想增加一个功能，即每个用户对每个投票只能投一次。如何设计？
3、系统运行了较长一段时间之后，用户反馈使用中速度变慢。请分析可能的原因，并提出解决办法。
4、请完整给出新系统下各功能的实现流程。涉及数据库查询的，请给出SQL语句。
躲猫猫社团团长 http://t.sina.com.cn/coolria