百度面试题目大揭秘：函数编程、数据结构、排序等考点汇总

BAT面试题目

百度一面

给定一个像“abcdef”这样的字符串，要求编写出一个函数，将其编程为“defabc”，此函数所处理的字符串位数是能够发生变化的，这事相当比较简单，我选用的是strcpy以及memcpy，随后接着他询问是否存在任何优化的途经，这样一来我就全然不知道了。

2、将socket的server和client的整个流程写下来，这便是socket过程，做到这点还是没什么问题的。

3、针对数据结构二叉树，给出了一个二叉树，要求写出前序遍历，写完前序遍历再写中序遍历，写完中序遍历最后写后序遍历，做这件事在正常学习中是没有太大困难程度的。

4、对于树的层次遍历，起初这确实被遗忘了，经过一番思索才回想起运用队列，而后他又要求我详尽地书写入队以及出队的过程，总而言之最终还是成功解决了。

5、关于两圆相切转圈的问题，有一个小圆，其半径是 1 厘米，还有一个大圆，其半径是 5 厘米，小圆凭借自身的滚动沿着大圆的圆周转动，那么我们要思考，小圆需转几圈才能够完整地转完更大圆的一圈呢？这个问题曾经在行政职业能力倾向测验的题目中出现过，它所涉及的实际上就是公转与自转类型的问题，无论大圆和小圆的半径具体数值是多少，当两圆处于外切状态并进行转圈运动时，需要转动的圈数是 R/r + 1 圈，而当两圆处于内切状态并进行转圈运动时，需要转动的圈数是 R/r - 1 圈。

百度二面

1、二叉树的前序遍历的递归和非递归的可执行程序

写出快速排序的实现代码，有一个是字符串拼接函数strcat()的实现，另外还有大数相乘，全都是基本题。

3、归并排序的实现。

4、文件按照从a到z依次编号，先是aa到az，随后是ba到bz，依此类推，直到za，然后是zz，接着是aaa以及后续一系列，像aaz，aba到abz等等这样的方式来进行编号。当给定任意一个编号时，输出该编号对应的文件是第几个文件。并且要写出测试方法。此方法比较简单，只需把编号看成26进制，那么这道题就变成了一个十进制和26进制的进制转换问题了。

有两个链表，需要将它们按照升序的方式进行排序，在合并之后依旧要保持按升序排列，而且不准使用递归法，还要弄清楚其复杂度是多少。

百度笔试题

1、数组的优点与缺点，链表的优点与缺点：这个问题相对而言较为简单，但我常常会忽视的一点在于，数组所占据的空间是固定不变的，而链表所占用的空间则是可以改变的。

2、将a输入N个字符串，这些字符串的长度都不超过20，要比较这些字符串之中是不是存在完全一样的字母，并且相同字母的数量是不是相等。那么该如何对这个算法进行改进呢，从而把复杂度降低呢。

3、猜扑克牌——给定一些牌，把花色告诉，把点数告诉乙

甲：我不知道 乙：我知道你不知道

甲：现在我知道了 乙：我也知道了

求是哪张牌。

对于给定的那些牌，我没能记住，不管怎样，这个题目是很容易的，是行政职业能力测验里的容易题目，在网络上到处都有。

4、A：一个由M乘以M所构成的矩阵，探寻字符串S是不是存在于A的连续对角线上，（关于这道题目，应该是有涉及到某一个之字二维矩阵范畴内的知识的）。

A若为内存装不下的大矩阵该如何处理？

5、系统会接收数据包，该数据包是32字节，其中第1字节是优先级，其余的字节是数据，要设计出一个调度算法。

（1）优先级高的先处理

（2）同等条件下，请求次数多的先处理

（3）优先级高的一定比优先级低的先处理

写出所用的数据结构的定义，计算空间容量。

百度电面：

1、谈谈你对数据库中索引的理解

2、现在普通关系数据库用得数据结构是什么类型的数据结构

3、索引的优点和缺点

4、session、cookie和cache的区别是什么

5、如果有几千个session，怎么提高效率？

6、session是存储在什么地方，以什么形式存储的？