百度2010笔试题答案.docx

百度客户端开发在线笔试题答案第一题：1.广度优先遍历和深度优先遍历a.广度优先遍历会先访问离根节点最近的节点。二叉树的广度优先遍历又称按层次遍历。非递归算法就借助队列实现。b.正如算法名称那样，深度优先搜索所遵循的搜索策略是尽可能“深”地搜索树的结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点， 则选择其中一个作为源结点并重复以上过程，整个进程反复进行直到所有结点都被发现为止。二叉树的深度优先遍历的非递归的通用做法是采用栈。有三种深度遍历的方法：先序遍历、中序遍历、后序遍历2.处理磁盘数据的策略if(nm) /情况一 就将磁盘的数据整体读取到内存，修改处理之后，按顺序写回磁盘。else /情况二 for(i=磁盘数据起始位置;in;i-=m) 将m块磁盘数据读入到内存，修改处理之后，按顺序写回磁盘 如果是情况一则需要2*n次磁盘IO,如果是情况二，则需要2(n/m)*m次磁盘IO.第二题：1.设计一个计算机程序辅助主持人判断两个人是否为队友第一步：为每个人维护一个队友队列，比如，就表示为：小明-小王第二步：然后,等全部用队列表示出来，再遍历队列，如果前面的队列两个人中，有一个出现在后面的队列中，就将后面的队列合并到前面的队列当中，变化队列如下：小明-小王-小军第三步：重复第二步，最后剩下的几个队列就是“朋友队列”，这些队列分别与其他的队列没有交集。第四步：判断两个人是否是队友，就遍历第三步产生的“朋友队列”，看两人是否在同一个队列中第五步：算法结束，输出结果。2.输出以 node 为根的二叉树第 m 层的第 k 个节点值.node_t* foo(node_t *node, unsigned int m, unsigned int k) queue tree; node_t temp=NULL; tree.push(node); int i; while (!tree.empty() if(i=m-2) break; temp=tree.front(); tree.pop(); if (temp.left!=NULL) tree.push(temp.left); if (temp.right!=NULL) tree.push(temp.right); i+; printf(第m层第k个元素的值为：%d,treek-1.value); return treek-1;第三题：1.(a)vote_info表中的visible属性冗余，因为到时显示时需要显示创建者名字，显示时user_info和vote_info连接后即可获得visible值(b)vote_info表中的options属性设计有问题，当前设计下是把;号当作分隔符，如果用户输入的选项中也存在;号，会造成混乱，一种方法是在前台限制用户输入，另一种方法是替换掉;号。2.(a)由于每天可望创建超过1万个投票，并且有约一百万人次参与投票，所以每条记录大约有100人投票，可以在vote_info中新建一个列vote_record记录投票记录,数据格式如1;2;3;45每个投票ID用;号分隔;(b)可以考虑新建一个表，用来存储用户投票记录，用户投票时先判断是存在相应历史记录，如果存在则禁止投票。3.由于每日数据量很大，较长一段时间后，vote_info表会相应变的很大，会大大降低数据检索的速度，可以采用分表策略，比如一个月创建一个表，表命名方式如vote_info_201005,这样一个vote_info表大概有30万条数据。4.未完成4.1.去除vote_info表的visible列ALTER TABLE vote_infoDROP COLUMN visible2.新建一个vote_record记录投票记录ALTER TABLE vote_infoADD COLUMN vote_record VARCHAR(MAX)3.建立一个分表存储过程，没一个月执行一次CREATE PROCEDURE sp_CreateTableDECLARE Now NVARCHAR(255)DECLARE TableName NVARCHAR(255)Now=CONVERT(VARCHAR,GETDATE(),110)TableName =vote_info_+SELECTLEFT(Now,6)CRETATE TABLE TableName (vid int PRIMARY KEYuid int NOT NULLtitle .max int NOT NULL)面试网络.操作系统.数据库1By yanbing网络：1.OSI七层模型：应用层：为应用程序提供服务表示层：处理在两个通信系统中交换信息的表示方式会话层：负责维护两个结点间会话连接的建立、管理和终止，以及数据交换传输层：向用户提供可靠的端到端服务。UDP TCP协议。网络层：通过路由选择算法为分组通过通信子网选择最适当的路径，以及实现拥塞控制、网络互联等功能。数据传输单元是分组。IP地址，路由器，IP协议。数据链路层：在物理层提供的服务基础上，数据链路层在通信的实体间建立数据链路连接，传输一帧为单位的数据包（，并采用差错控制与流量控制方法，使有差错的物理线路变成无差错的数据链路。）物理层：传输比特流。传输单元是比特。调制解调器。2.面向连接服务：数据传输过程必须经过连接建立、连接维护与连接释放的3个过程，（分组不需要携带目的结点的地址，传输可靠性好，协议复杂，通信效率不高。）无连接服务：每个分组携带完整的目的结点地址，各分组独立传送。不需建立连接、连接维护和连接释放3个过程。（通信协议相对简单，通信效率高，可靠性不好）3.单工通信：信号只能向一个方向传输，不能改变方向半双工通信：信号可以双向传送，交替进行，一个时间只能一个方向全双工通信：信号可同时双向传送4.曼彻斯特编码：每比特周期T分前T/2与后T/2，前T/2传输该比特反码，后T/2传输原码差分曼彻斯特编码：一个比特开始处电平跳变传输二进制“0”，不跳变传输“1”。由曼彻斯特编码写差分曼彻斯特编码对应的规则是0变1不变5.IP地址（网络号+主机号）分类：A：1.0.0.0127.255.255.255 (224)-2个主机号（全0全1不使用） (27) 2个网络（全0全1，十进制是0和127）B：128.0.0.0191.255.255.255 (216)-2个主机或路由器（除全0全1） 214 个网络C：192.0.0.0223.255.255.255 (28)-2个主机号（除全0全1） 221 个网络D：224.0.0.0239.255.255.255 E：240.0.0.0255.255.255.2556.IP协议是一种不可靠、无连接的数据报传送服务的协议TCP是种面向连接的、可靠的传输层协议UDP是一种无连接的、不可靠的传输协议7.同步通信：通信双方必须先建立同步，即双方的时钟要调整到同一个频率。收发双方不停地发送和接收连续的同步比特流。异步通信：异步通信在发送字符时，所发送的字符之间的时间间隔可以是任意的。当然，接收端必须时刻做好接收的准备（如果接收端主机的电源都没有加上，那么发送端发送字符就没有意义，因为接收端根本无法接收）。发送端可以在任意时刻开始发送字符，因此必须在每一个字符的开始和结束的地方加上标志，即加上开始位和停止位，以便使接收端能够正确地将每一个字符接收下来。异步通信的好处是通信设备简单、便宜，但传输效率较低（因为开始位和停止位的开销所占比例较大）。 异步通信也可以是以帧作为发送的单位。接收端必须随时做好接收帧的准备。操作系统：1.进程、线程概念进程间通信：信号、信号量、消息队列、共享内存线程间通信：临界区、互斥量、信号量、事件2.死锁死锁就是两个或多个进程无止境地等候着永远不会成立的条件的一种系统状态在两个或多个并发进程中，如果每个过程持有某中资源而又都等待着别的进程释放它或他们现在白吃的资源，否则就不能向前推进。死锁产生原因：系统资源不足进程推进顺序非法产生死锁的4个必要条件：互斥条件不剥夺条件部分分配环路条件解决死锁策略：采用静态分配方法来预防死锁（静态预防）采用有控分配方法来