微软校园招聘笔试题

概要：Considering an array with N elements , what is the lowest time and space complexity to get the length of LIS?A、Time : N^2 , Space : N^2B、Time : N^2 , Space : NC、Time : NlogN , Space : ND、Time : N , Space : NE、Time : N , Space : C20、What is the output of the following piece of C++ code ?[cpp] view plaincopyprint?#includeusing namespace std;struct Item{char c;Item *next;};Item *Routine1(Item *x){Item *prev = NULL,*curr = x;while(curr){Item *next = curr->next;curr->next = prev;prev

微软校园招聘笔试题,标签：笔试大全,http://www.88haoxue.com

　　Considering an array with N elements , what is the lowest time and space complexity to get the length of LIS?

　　A、Time : N^2 , Space : N^2

　　B、Time : N^2 , Space : N

　　C、Time : NlogN , Space : N

　　D、Time : N , Space : N

　　E、Time : N , Space : C

　　20、What is the output of the following piece of C++ code ?

　　[cpp] view plaincopyprint?#include

　　using namespace std;

　　struct Item

　　{

　　char c;

　　Item *next;

　　};

　　Item *Routine1(Item *x)

　　{

　　Item *prev = NULL,

　　*curr = x;

　　while(curr)

　　{

　　Item *next = curr->next;

　　curr->next = prev;

　　prev = curr;

　　curr = next;

　　}

　　return prev;

　　}

　　void Routine2(Item *x)

　　{

　　Item *curr = x;

　　while(curr)

　　{

　　cout<

　　curr = curr->next;

　　}

　　}

　　int main(void)

　　{

　　Item *x,

　　d = {'d' , NULL},

　　c = {'c' , &d},

　　b = {'b' , &c},

　　a = {'a' , &b};

　　x = Routine1( &a );

　　Routine2( x );

　　return 0;

　　}

　　#include

　　using namespace std;

　　struct Item

　　{

　　char c;

　　Item *next;

　　};

　　Item *Routine1(Item *x)

　　{

　　Item *prev = NULL,

　　*curr = x;

　　while(curr)

　　{

　　Item *next = curr->next;

　　curr->next = prev;

　　prev = curr;

　　curr = next;

　　}

　　return prev;

　　}

　　void Routine2(Item *x)

　　{

　　Item *curr = x;

　　while(curr)

　　{

　　cout<

　　curr = curr->next;

　　}

　　}

　　int main(void)

　　{

　　Item *x,

　　d = {'d' , NULL},

　　c = {'c' , &d},

　　b = {'b' , &c},

　　a = {'a' , &b};

　　x = Routine1( &a );

　　Routine2( x );

　　return 0;

　　}

　　A、 c b a d

　　B、 b a d c

　　C、 d b c a

　　D、 a b c d

　　E、 d c b a

　　微软2012年9月22日校园招聘笔试题

　　1、数据库

　　基于某个条件选出一个订单列表，考的是最基本的数据库语言select * from * where *

　　2、不能用于进程间通信的是

　　A、Named event

　　B、Named pipe

　　C、Critical section

　　D、Shared memory

　　3、shallow copying (浅拷贝)的特征

　　英文太烂不知道shallow copying怎么翻译不敢选

　　4、 Functional programming(函数式编程)的特点

　　完全不了解functional programing

　　考了”没有副作用”，“不修改状态”，“引用透明”引用透明的概念类似于可重入

　　5、以下算法用到贪婪算法的是

　　A、Dijkstra

　　B、Prim

　　C、Kruskal

　　D、Floyd- Warshall

　　E、KMP string match

　　6、1,2,3,…1000 一共出现了多少个0

　　A、189

　　B、191

　　C、193

　　D、195

　　算出来是192个可是没有这个答案估计题目出错了。

　　7、T(x)=1 (x<=1), T(n)=25*T(n/5)+n^2 求T(n)的时间复杂度

　　A、O(n*log(n))

　　B、O(log(n))

　　C、O(n^2*log(n))

　　D、O(n^3*log(n))

　　T(n)=25*(25*T(n/25)+(n/5)^2)+n^2=25^2*T(n/(5^2))+2*n^2=25^(log(n)/log5)+(log(n)/log5)*n^2=n^2+n^2*log(n) =O(n^2*log(n))

　　8、下列属于设计模式中 ”creational pattern” (创建型)的是?

　　A、Facade

　　B、Singleton

　　C、Bridge

　　D、Composite

　　Facade composite bridge 都属于Structural(结构型)

　　9、建立一个TCP连接的过程?

　　三次握手http://baike.baidu.com/view/1003841.htm

　　答案中好像没有SYN，SYN+ACK，ACK，于是我就选了 E、None of above

　　10、二叉树的pre-order traversal为abcdefg，则它的in-order traversal可能是?

　　A、abcdefg

　　B、gfedcba

　　C、efgdcba

　　D、bceadfg

　　E、bcdaefg

　　以前序遍历abc为例，只有三个节点，中序遍历可能是cba, bca, bac, abc, acb

　　11、15个球放在4个袋子中，每个袋子至少有一个球且每个袋子中球的数目不同，总共有多少种放法?

　　A、4

　　B、5

　　C、6

　　D、7

　　E、None of above

　　不知道除了枚举有没有别的更好的办法

　　12、给了4个函数，可以看出其中第一个为选择排序，第二个为冒泡排序第三个感觉代码本身就有些问题第四个为快速排序。问哪一个排序能将数组a={(3,4),(6,5),(2,7),(3,1),(1,2) }变为{(1,2), ,(2,7), (3,1),( 3,4),(6,5)}

　　只比较第一个元素。

　　Stuct A{

　　Int key1;

　　Int key2;

　　};

　　比较函数为 int cmp(A x, A y) {return x.key1-y.key1;)

　　选择排序, 此题代码是选择的最小出列。选出最小的与前面的交换，其条件是cmp<0, 显然第一趟(3,4)与(1,2)交换后到了(3,1)的后面然后是(6,5)与(2,7)交换，其条件是cmp<0,所以(6,5)与(3,1 )交换，最后的输出结果满足题目要求

上一页  [1] [2] [3] [4]  下一页