百度2017招聘RD_C_2笔试题

第一题（30分）

1.
定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素，push和pop的时间复杂度都是O（1），请简要叙述你的思想

2.
阅读下面代码，说明输出的含义并挑错

问题1：写出下列代码的运行结果的前7行，并说明程序的含义

问题2：代码中是否有不安全隐患？原因是？

1. #include <stdio.h>
    
2. #include <string.h>
    
3. 
    
4. const int MAX_LEN = 128;
    
5. const int MAX_LINE = 20;
    
6. int main(int argc, char* argv[])
    
7. {
    
8.        char str[MAX_LEN] = "1";
    
9.        char tmp_str[MAX_LEN] = "";
    
10.        char buf[MAX_LEN] = "";
     
11.        printf("%s\n",str);
     
12.        for (int line = 1; line <= MAX_LEN; ++line )
     
13.        {
     
14.               strcpy(tmp_str,str);
     
15.               str[0] = '\0';
     
16.               for (int i=0;tmp_str[i]!=0; ++i)
     
17.               {
     
18.                      char ch = tmp_str[i];
     
19.                      int count = 1;
     
20.                      for (;tmp_str[i+1]==tmp_str[i]; ++i)
     
21.                      {
     
22.                             ++count;
     
23.                      }
     
24.                      sprintf(buf,"%d%c",count,ch);
     
25.                      strcat(str,buf);
     
26.               }
     
27.               printf("%s\n",str);
     
28.        }
     
29.        return 0;
     
30. }

3.
分别采用线性表，二叉平衡树，哈希表存储数据，请分析它们的优劣

第二题 算法与程序设计（40分）

1 一串首尾相连的珠子,总共m颗,每颗珠子都有自己的颜色，全部颜色有n种（n<10），现在要在里面截取一段，要求包含所有不同的颜色，并且长度越短越好，请详细描述你的算法思路（如需要，可用伪代码辅助描述），并分析算法的时间复杂度和空间复杂度

[1] [2]  下一页