百度笔试题四

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

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

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

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

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

6.    上下文无关文法是一种__d__。
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的值为 c
A. -1；         B. 5；       C. 7；       D. 11；

9.    以下IO函数中，哪个是流式IO函数（b）
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的赋值是_c___。
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

请评价该监控程序的敏感性和正确性。
最好情况应该对角线上的值为1，其他为0
敏感性是有异常能够报警的概率，p(报警的概率|有异常发生) = (0.28*0.98 + 0.12*0.91 + 0.32*.0.90) / (0.28+0.12+0.32) = 0.933
正确性是指能够正确报警的概率，0.28*0.90 + 0.12*0.80 + 0.32*0.82 + 0.28*0.95 = 0.876
所以如果以0.9的概率为标准,我觉得敏感性指标高,正确性指标低

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;
         }
1。如果number很大的话，在for循环中就打开了多个文件，而for循环后至关闭了一个文件
2。如果number很大很大的话，i/20的位数加上file_和.txt的位数可能会超过file_name
3. 如果是用C的编译器来编译的话，for(int i=0; i<number; i++) 中的int i不能这样定义。可以用C++编译器编译
4. number很大的话，sum就溢出了
5. fp需要赋初值，如果没有进入for循环的话，fclose出错

三、编程题：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）的状态可以在有限时间内趋于一致
最后，请针对你考虑到的意外情况，说明所采用的避免、解决或恢复方案。

考虑的因素是三方面的，一个是发送端的命令的存储和发送，二是传输过程中有序，无漏，无重复性和数据正确性问题，三是接收者如何接收和保证所有的接收者的状态能在有限时间内趋于一致。

百度招聘在线笔试百度招聘在线笔试百度首页

      一、选择题：15分 共10题
      1.    C语言，下面语句输出的结果是什么？
      假设 test_item_t 结构大小为16.
      test_item_t* pitem = 0;
      int i=1;
      pitem = pitem + i++;
      printf("%d", (int)pitem );
      A) 1       B) 2           C) 16        D) 32

      2.    下面关于算法和数据结构的说法，不正确的是：
      A.存在额外空间复杂度为O(1)的算法，判断一个链表是否存在回路
      B.对hash table而言，桶的数目最佳为一质数
      C.快速排序算法在数组倒序排列的情况下取得最坏时间复杂度
      D.采用栈对二叉树后序周游时，弹出一个子树的根节点的时机是在第二次访问该节点时

      3.    下面为检查一个数组中元素是否唯一的算法，该算法最坏情况，需要作多少次比较？
      For i = 0 to n-2 do
      For j = i+1 to n-1 do
      If A[i] = A[j] 
      return false
      return true;
      A) n*n/2     B) n*n      C)  n*(n-1)/2     D) 没有正确答案

      4.    以下程序输出结果是______。
      #define  M(x,y)   x*y
       printf(“%d”,M(10+1,3));
      A) 33          B)23          C)13                D) 103

      5.    以下操作符优先级最高的是___:
      A) +         B) &&         C) |              D) >>

      6.    下面一段语句的执行结果为： 
      char buffer[16];
      char *pbuffer=buffer;
      printf("%d,%d",sizeof(buffer),sizeof(pbuffer));
      A) 16,4       B) 16,16      C) 4,4           D)4,16

      7.    以下哪个协议是TCP/IP 网络层的协议：
      A) UDP        B) DHCP      C) PPP           D) ARP

      8.    触发器可在表的插入、修改或删除操作时被触发执行特定的操作。触发器主要用于 
      A）数据库恢复        B）完整性控制
      C）并发控制            D）安全性控制

      9.    下面哪个函数调用可能发生阻塞？
      A 在普通文件的描述符上发出read系统调用
      B 在socket的描述符上发出write系统调用
      C 针对一个普通文件执行open系统调用
      D 在一个普通文件上执行seek系统调用

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

      二、简答题：20分，共2题

      1.    （5分）指出下列程序有哪些问题，或者不安全因素。
      toUpperCase(char &c);  
      int copyStr_c(const char* str)
      {
         char * pbuffer[MAX_SIZE];
         strcpy(pbuffer, str);
         for(; pbuffer, pbuffer++)
      {
        toUpperCase(pbuffer);
      }
      return pbuffer;
      }

      2.    （15分）怎样比较有效率地实现具有如下功能的工具：将两个有定长结构的数据文件按指定的字段进行等值连接。
      例如：A文件的结构为 
      struct A{
          int x, y;
      };
      B文件的结构为
      struct B{
          int y;
      };
      并有struct A a1 = {1, 2}, a2 = {2, 2}; struct B b1 = {2}, b2 = { 3};
      则连接后的结果是：
      {{1, 2, 2}, {2, 2, 2}}

          现指定按y字段进行连接 ,提示：先按y值排序，然后找数组中相同的元素

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

      1.    处理大写字母和小写字母混排的字符串（长度小于1K字节），要求大写字母在前、小写字母在后，并尽可能优化算法。 (一趟快速排序法)

int f(char *str,int len)
{
 if(str==NULL || len == 0)
  return -1 ;
 int i=0;
 int j=len-1;
 while(1)
 {
  while(str[i]>='A'&&str[i]<='Z'&& i < len)i++;
  while(str[j]>='a'&&str[j]<='z'&& j >= 0)j--;
  if(i>=j) break;
  char t=str[i];
  str[i]=str[j];
  str[j]=t;
 }
 return 0;
}

void main()
{
 char str[] = "aBsAdsdASDasd";
 f(str, strlen(str));
 cout << str;
}

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

      1.    一个程序一直接收这样数据结构(struct block_t)的网络随机数据：
      typedef struct block_t{
                 int  value;    /*节点值，范围:0-->200,000,000 */
                 int  group;   /*组号，范围:0-->200,000,000 */
                 char data[1024];  /*其他数据为1K大小*/
         }block_t;
      每天接收不超过5千万个这样的数据，并定时将数据生成分组有序的数据（按group分组，各组按value排序）。

      任务：给出基本思路、设计的具体数据文件格式，以及较详细的算法描述。
      要求：计算过程要尽可能高效。

         下面是限制和提示：
           a)系统内存4G，一个进程内存不超过2G，一个文件大小不超过2G
           b)IO时间开销比较大，并且文件的随机读取比顺序读取速度至少慢10倍
           c)一个50G字节、5千万条的数据，要顺序全部读取出来，大约需要20分钟。如果随机将所有数据取出来，大概需要4个小时。