百度面试题集锦

挑战一下！百度面试题！

一、选择题：15 分 共 10 题
1. 任何一个基于“比较”的内部排序的算法，若对 6 个元素进行排序，则在最坏情况下所需的比较次数至少为____。
A. 10 B. 11 C. 21 D. 36

2. 关系模型有三类完整性约束，定义外键实现的是：
A. 实体完整性 B. 参照完整性 C. 用户定义的完整性 D. 实体完整性、参照完整性和用户定义的完整性

3. 64 位 Linux 系统和机器，int 类型、long 类型分别占用多大的空间(字节数)：
A. 4, 4 B. 4, 8 C. 8, 4 D. 8, 8

4. 下面说法正确的是：
A. 根据gprof统计的程序运行时函数调用次数及执行时间，进行程序代码优化，这是 amdahl 定律的应用
B. 计算机网络设备的缓冲区是时间和空间局部性原理的应用
C. 局域网内的计算机发送数据包的数学模型遵循泊松分布
D. 分支预测使用先前运行时得到的配置文件，这是依据正态分布

5. 下列叙述正确的是：
A . #define fun(x,y) (x/y)
Int I = fun(2+4, 3);
I 的值为 2
B. var++ 与 ++var 没有区别
C. C++ 程序，抛出异常时，一定会发生异常对象的拷贝过程
D. quick sort 是一种稳定排序。

6. 上下文无关文法是一种____。
A. 左线性文法 B. 右线性文法 C. 正则文法 D. 以上都不上

7. 关系表达式 !(A&&(B||C)) 和下面哪个表达式表达的意思一致：
A. (!(A&&B))||(!(A&&C)) B. (!(A&&B))&&((!A)||(!B)) C. (!(A||B))&&(!(A&&B)) D. (!A)||((!B)||(!C))

8. 设 int x=4; 则执行以下语句 x+=x-=x-x--; 后，x 的值为：
A. -1 B. 5 C. 7 D. 11

9. 以下 IO 函数中，哪个是流式 IO 函数：
A. read B. fread C. mmap D. recv

10. 已知：
struct st
{
　　int n;
　　struct st *next;
};
static struct st a[3]={1, &a[1], 2, &a[2], 3, &a[0] }, *p;
如果下述语句的显示是 2，则对 p 的赋值是____。
printf( "%d", ++(p->next->n) );
A. p=&a[0]; B. p=&a[1]; C. p=&a[2]; D. p=*a;

二、简答题：20 分，共 2 题
1. （10 分）已知某种线上服务存在 3 种异常 D1, D2, D3，根据每天在固定时间段长期人工监控的统计结果，3 种异常的发生率是：D1 0.28%, D2 0.12%, D3 0.32%。现开发一种监控程序，分别对这三种异常做监控，如果发现某种异常就发出相应报警。记无异常为 D4，无报警为 A4。在各种异常情况下发出报警的溉率如下表：
D1 D2 D3 D4
A1 0.90 0.06 0.02 0.02
A2 0.05 0.80 0.06 0.01
A3 0.03 0.05 0.82 0.02
A4 0.02 0.09 0.10 0.95

请评价该监控程序的敏感性和正确性。

2. （10 分）以下是一个常驻内存的 C 程序，请问程序中有什么问题？
int f( int number )
{
　　FILE * fp;
　　char file_name[20];
　　int sum=0;
　　for( int i = 0; i < number; i++ )
　　{
　　　　if( 0 == i % 30 )
　　　　{
　　　　　　sprintf( file_name, "file_%d.txt", i / 20 );
　　　　　　fp = fopen( file_name, "r" );
　　　　　　if( fp == NULL ) return -1;
　　　　}
　　　　sum += i;
　　}

　　fclose( fp );
　　return sum;
}

三、编程题：30 分 共 1 题
注意：要求提供完整代码，如果可以编译运行酌情加分。

1. 一条 1 百万节点的单向链表，链表所有节点是按 value 字段从小到大的顺序链接；下面是一个节点的结构
typedef struct node_t{
　　int value; /* 节点排序字段 */
　　int group; /* 组号: 0,1,2,3,4,5,6,7,8,9 */

　　struct node_t *pnext; /* 下个节点的指针 */
}node_t;
node_t head; /*该单向链表的头节点，全局变量 */

试设计程序：针对各个 group(0-->9)，根据 value 字段排序，输出各组 top 10 的节点。（top10 是从小到大，取后面的大值 top10）
要求：尽量减少计算复杂度、遍历次数，不允许大量的辅助内存

四、设计题：35 分 共 1 题
注意：请尽可能详细描述你的数据结构、系统架构、设计思路等。建议多写一些伪代码或者流程说明。

1. 设想网络上的一个发送者和 64 个接收者，发送者每秒有不超过 128 条的命令产生，每条命令包含一个 512 字节的头部 command_head_t 和至多 4K 字节的变长内容。command_head_t 的结构如下：
typedef struct {
　　int cmd_no; //该命令的命令号，唯一识别一个命令
　　int version; //产生该命令的程序的版本
　　int detail_len; //变产内容的实际长度
　　char *content; //指向变长内容的指针
　　…
} command_head_t;
发送者根据命令号将这些命令分别发送给接收者去处理，例如：发送者产生 c1，c2，c3，c4 命令，并设定将 c1，c2 命令发送到接收者 r1 和 r2，将 c2、c3，c4 命令发送到 r3。
接收者执行接收到的命令，并相应修改自己的状态。
现在的问题是：在尽可能多的考虑各种可能的意外情况下（包括但不限于网络故障、传输错误、程序崩溃、停电…），如何设计命令的存储、发送、接收的流程，以保证命令的：
1) 传输中的有序、无漏、无重复性
2) 整个过程中命令和数据的正确性
3) 多个同一类型的接收者（例如 r1 与 r2）的状态可以在有限时间内趋于一致
最后，请针对你考虑到的意外情况，说明所采用的避免、解决或恢复方案。