慕开复之名，一个小时的笔试，十一道题目，不算多，时间还算充裕。

选择题/填空题

1. 关于c union type，求下列程序的输出结果（具体程序既不清楚了，考点在于union type的内存分布）：
   

   		#include <stdio.h>
   
   union u
   {
       int i;
       char x[2];
   }a;
   
   int main()
   {
       a.x[0] = '1';
       a.x[1] = '2';
       printf("%d\n", a.i);
       return 0;
   }
   

2. 关于什么叫数据库主键。

3. 关于路由器和交换机的区别，哪个用来连接不同网段、分隔子网或者是分隔不同网段、连接子网。

4. 进程和线程的区别（调度、控制、共享内存、通讯方式）。

5. 排序复杂度哪个不是[tex]O(n\lg n)[/tex]（二分插入排序、快速排序、归并排序、堆排序）。

6. kmp算法填空（略微记得一点原理，忘差不多了……）。

7. 有5道工序，其中有一道工序不能放在最后，问有多少种排列方法（[tex]5!-4! = 96[/tex])。

8. 内存分页算法的缺页次数（先进先出、最近最少、理想页面置换算法，完全不会……）。

9. tcp和udp的区别

10. 递归函数：

    		int f(int n)
    {
        if (n == 0)
            return 3;
        else
            return f(n-2) + f(n-1);
    }

    求f(10)（我的答案是没结果，应该是唬人的题目）

编程题

给定一个字符串，字符串中可能含有包含'(', ')', '[', ']'，判定条件如下：

• '('和')'、'['和']'个数相等
• '('和')'，'['和']'完全配对，不能出现嵌套情况。

如符合以上两条，则返回True，否则返回False。

Example：

a(ab)[aa(ba)[aa]b]为True，而a((a)、ab(a[bbb)]c为False。

解决方案：

如果熟悉stack表达式求值算法，这道题目应该不在话下。设定两个计数器m和n，m记录'('和')'的个数的差值，'n'记录'['和']'个数的差值，再设定一个STL stack<char> par。

每当读到'('或'['，就执行push操作par.push('(')，par.push('[')，同时m++, n++；每当读到')'或']'，就判断下栈顶元素和当前元素是否配对，如果配对，则par.pop()，否则直接返回False，同时m--，n--。

最后判断m和n是否为零即可。代码略去。

• Relative Posts