2011微软笔试题

2011微软笔试题

2011微软笔试题

　1. 给定一个整形数组，数组的大小为N，数组内的数的范围为-N到N，问最好的排序时间复杂度是多少?

　　A O(logN)

　　B O(N)

　　C O(NlogN)

　　D O(N2) /*(代表平方)*/

　　E 以上都不对

　　应该是B，采用位图排序，google位图排序

　　2. MVC模式是现在开发的一种常用设计模式，请问如下可以充当MVC模式中控制器的是?

　　A CSS

　　B HTML 模板

　　C Javascript

　　D Web Service

　　E 以上都不是

　　我真的不懂，我勉强觉得Web Service可以当作是控制器吧

　　3. 在编译进程中，会产生Parse Tree的是?

　　A 语法分析过程

　　B 语意分析过程

　　C 汇编代码过程

　　D 目标代码过程

　　百度了一下，貌似是在语法分析上，没学过编译原理不懂，后面百度链接http://baike.baidu.com/view/29903.htm

　　4. 寻找最短路径，给定一个还算不是很复杂的图。图不记得了，选项也不记得了。

　　google 普鲁姆算法 克鲁斯卡尔算法

　　5. 一个节点可以生成生成一种二叉树，两个相同的节点可以生成两种二叉树，三个相同的节点可以生成5种二叉树?那5种呢?

　　备选答案忘记了。刚查了一下，42。公式是C(2n, n)/(n+1)

　　6. 对于一个32位的操作系统来说，那些是正确的?

　　A. 操作系统可以访问到的物理内存为4G

　　B. 用户空间可访问的内存为4G

　　C. 碎片会极大的减缓程序的运行速度

　　D. 虚拟内存对应的实际内存不一定要连续

　　我觉得是ACD