微软校园招聘笔试题

1、Supposethataselectionsortof80itemshaspleted32iterationsofthemainloop.Howmanyitemsarenowguaranteedtobeintheirfinalspot(nevertobemovedagain)?

A、16B、31C、32D、39E、40

2、Whichsynchronizationmechanism(s)is/areusedtoavoidraceconditionsamongprocesses/threadsinoperatingsystem?

A、MutexB、MailboxC、SemaphoreD、Localprocedurecall

3、Thereisasequenceofnnumbers1,2,3,...,nandastackwhichcankeepmnumbersatmost.Pushthennumbersintothestackfollowingthesequenceandpopoutrandomly.Supposenis2andmis3,theoutputsequencemaybe1,2or2,1,soweget2differentsequences.Supposenis7,andmis5,pleasechoosetheoutputsequenceofthestack.

A、1,2,3,4,5,6,7

B、7,6,5,4,3,2,1

C、5,6,4,3,7,2,1

D、1,7,6,5,4,3,2

E、3,2,1,7,5,6,4

4、Whichistheresultofbinarynumber01011001aftermultiplyingby0111001andadding1101110?

A、0001010000111111

B、0101011101110011

C、0011010000110101

转化为10进制*作以后，再转化为二进制就可以了。

5、Whatisoutputifyoupileandexecutethefollowingccode?

[cpp]viewplaincopyprint?voidmain()

{

inti=11;

intconst*p=&i;

p++;

printf("%d",*p);

}

voidmain()

{

inti=11;

intconst*p=&i;

p++;

printf("%d",*p);

}A、11

B、12

C、Garbagevalue

D、Compileerror

E、Noneofabove

6、WhichoffollowingC++codeiscorrect?C

A、

[cpp]viewplaincopyprint?intf()

{

int*a=newint(3);

return*a;

}

intf()

{

int*a=newint(3);

return*a;

}B、[cpp]viewplaincopyprint?int*f()

{

inta[3]={1,2,3};

returna;

}

int*f()

{

inta[3]={1,2,3};

returna;

}C、[cpp]viewplaincopyprint?vectorf()

{

vectorv(3);

returnv;

}

vectorf()

{

vectorv(3);

returnv;

}D、[cpp]viewplaincopyprint?voidf(int*ret)

{

inta[3]={1,2,3};

ret=a;

return;

}

voidf(int*ret)

{

inta[3]={1,2,3};

ret=a;

return;

}E、Noneofabove

7、Giventhatthe180-degreerotatedimageofa5-digitnumberisanother5-digitnumberandthedifferencebetweenthenumbersis78633,whatistheoriginal5-digitnumber?

A、60918B、91086C、18609D、10968E、86901

8、Whichofthefollowingstatementsaretrue

A、Wecancreateabinarytreefromgiveninorderandpreordertraversalsequences.

B、Wecancreateabinarytreefromgivenpreorderandpostordertraversalsequences.

C、Foranalmostsortedarray,InsertionsortcanbemoreeffectivethanQuciksort.

D、SupposeT(n)istheruntimeofresolvingaproblemwithnelements,T(n)=O(1)ifn=1;

T(n)=2*T(n/2)+O(n)ifn>1;soT(n)isO(nlgn)

E、Noneofabove

9、Whichofthefollowingstatementsaretrue?

A、Insertionsortandbubblesortarenotefficientforlargedatasets.

B、QuciksortmakesO(n^2)parisonsintheworstcase.

C、Thereisanarray:7,6,5,4,3,2,1.Ifusingselectionsort(ascending),thenumberofswapoperationsis6

D、Heapsortusestwoheapoperations:insertionandrootdeletion(*入、堆调整)

E、Noneofabove

10、Assumebothxandyareintegers,whichoneofthefollowingsreturnstheminimumofthetwointegers?

A、y^((x^y)&-(x

B、y^(x^y)

C、x^(x^y)

D、(x^y)^(y^x)

E、Noneofabove

x

11、TheOrchidPavilion(兰亭集序)iswellknownasthetopof“行书”inhistoryofChineseliterature.Themostfascinatingsentenceis"WellIknowitisalietosaythatlifeanddeathisthesamething,andthatlongevityandearlydeathmakenodifferenceAlas!"(固知一死生为虚诞，齐彭殇为妄作).Bycountingthecharactersofthewholecontent(inChineseversion),theresultshouldbe391(includingpunctuation).Forthesecharacterswrittentoatextfile,pleaseselectthepossiblefilesizewithoutanydatacorrupt.

A、782bytesinUTF-16encoding

B、784bytesinUTF-16encoding

C、1173bytesinUTF-8encoding

D、1176bytesinUTF-8encoding

E、Noneofabove

12、Filltheblanksinsideclassdefinition

[cpp]viewplaincopyprint?classTest

{

public:

____inta;

____intb;

public:

Test::Test(int_a,int_b):a(_a)

{

b=_b;

}

};

intTest::b;

intmain(void)

{

Testt1(0,0),t2(1,1);

t1.b=10;

t2.b=20;

printf("%u%u%u%u",t1.a,t1.b,t2.a,t2.b);

return0;

}

classTest

{

public:

____inta;

____intb;

public:

Test::Test(int_a,int_b):a(_a)

{

b=_b;

}

};

intTest::b;

intmain(void)

{

Testt1(0,0),t2(1,1);

t1.b=10;

t2.b=20;

printf("%u%u%u%u",t1.a,t1.b,t2.a,t2.b);

return0;

}Runningresult:020120

A、static/const

B、const/static

C、--/static

D、conststatic/static

E、Noneofabove

13、A3-orderB-treehas2047keywords,whatisthemaximumheightofthetree?

A、11B、12C、13D、14

解析：m阶B-树的根节点至少有两棵子树，其他除根之外的所有非终端节点至少含有m/2(向上取整)棵子树，即至少含有m/2-1个关键字。根据题意，3阶的B-树若想要达到最大的高度，那么每个节点含有一个关键字，即每个节点含有2棵子树，也就是所谓的完全二叉树了，这样达到的高度是最大的。即含有2047个关键字的完全二叉树的高度是多少，这也是为什么这种题只出3阶的原因吧，就是为了转化成求完全二叉树的深度。很明显求得高度是11，但是由于B-树还有一层所谓的叶子节点，可以看作是外部结点或查找失败的结点，实际上这些结点不存在的，指向这些结点的指针为空。所以不考虑叶子节点信息的时候，最大高度是11，考虑叶子节点信息的时候，最大高度就是12了。

14、InC++,whichofthefollowingkeyword(s)canbeusedonbothavariableandafunction?

A、staticB、virtualC、externD、inlineE、const

15、Whatistheresultofthefollowingprogram?

[cpp]viewplaincopyprint?char*f(char*str,charch)

{

char*it1=str;

char*it2=str;

while(*it2!='\0')

{

while(*it2==ch)

{

it2++;

}

*it1++=*it2++;

}

returnstr;

}

intmain(void)

{

char*a=newchar[10];

strcpy(a,"abcdcccd");

cout<

return0;

}

char*f(char*str,charch)

{

char*it1=str;

char*it2=str;

while(*it2!='\0')

{

while(*it2==ch)

{

it2++;

}

*it1++=*it2++;

}

returnstr;

}

intmain(void)

{

char*a=newchar[10];

strcpy(a,"abcdcccd");

cout<

return0;

}A、abdcccd

B、abdd

C、abcc

D、abddcccd

E、Accessviolation

16、Considerthefollowingdefinitionofarecursivefunction,power,thatwillperformexponentiation.

[cpp]viewplaincopyprint?intpower(intb,inte)

{

if(e==0)

return1;

if(e%2==0)

returnpower(b*b,e/2);

else

returnb*power(b*b,e/2);

}

intpower(intb,inte)

{

if(e==0)

return1;

if(e%2==0)

returnpower(b*b,e/2);

else

returnb*power(b*b,e/2);

}Asymptotically(渐进地)intermsoftheexponente,thenumberofcallstopowerthatoccurasaresultofthecallpower(b,e)is

A、logarithmic

B、linear

C、quadratic

D、exponential

17、Assumeafulldeckofcardshas52cards,2blackssuits(spadeandclub)and2redsuits(diamondandheart).Ifyouaregivenafulldeck,andahalfdeck(with1redsuitand1blacksuit),whatisthepossibilityforeachonegetting2redcardsiftaking2cards?

A、1/21/2

B、25/10212/50

C、50/5124/25

D、25/5112/25

E、25/511/2

18、Thereisastackandasequenceofnnumbers(i.e.1,2,3,...,n),Pushthennumbersintothestackfollowingthesequenceandpopoutrandomly.Howmanydifferentsequencesofthennumberswemayget?Supposenis2,theoutputsequencemay1,2or2,1,sowoget2differentsequences.

A、C_2n^n

B、C_2n^n-C_2n^(n+1)

C、((2n)!)/(n+1)n!n!

D、n!

E、Noneofabove

19、LongestIncreasingSubsequence(LIS)meansasequencecontainingsomeelementsinanothersequencebythesameorder,andthevaluesofelementskeepsincreasing.

Forexample,LISof{2,1,4,2,3,7,4,6}is{1,2,3,4,6},anditsLISlengthis5.

ConsideringanarraywithNelements,whatisthelowesttimeandspaceplexitytogetthelengthofLIS?

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、WhatistheoutputofthefollowingpieceofC++code?

[cpp]viewplaincopyprint?#include

usingnamespacestd;

structItem

{

charc;

Item*next;

};

Item*Routine1(Item*x)

{

Item*prev=NULL,

*curr=x;

while(curr)

{

Item*next=curr->next;

curr->next=prev;

prev=curr;

curr=next;

}

returnprev;

}

voidRoutine2(Item*x)

{

Item*curr=x;

while(curr)

{

cout<

curr=curr->next;

}

}

intmain(void)

{

Item*x,

d={'d',NULL},

c={'c',&d},

b={'b',&c},

a={'a',&b};

x=Routine1(&a);

Routine2(x);

return0;

}

#include

usingnamespacestd;

structItem

{

charc;

Item*next;

};

Item*Routine1(Item*x)

{

Item*prev=NULL,

*curr=x;

while(curr)

{

Item*next=curr->next;

curr->next=prev;

prev=curr;

curr=next;

}

returnprev;

}

voidRoutine2(Item*x)

{

Item*curr=x;

while(curr)

{

cout<

curr=curr->next;

}

}

intmain(void)

{

Item*x,

d={'d',NULL},

c={'c',&d},

b={'b',&c},

a={'a',&b};

x=Routine1(&a);

Routine2(x);

return0;

}

A、cbad

B、badc

C、dbca

D、abcd

E、dcba

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

1、数据库

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

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

A、Namedevent

B、Namedpipe

C、Criticalsection

D、Sharedmemory

3、shallowcopying(浅拷贝)的特征

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

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

完全不了解functionalprograming

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

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

A、Dijkstra

B、Prim

C、Kruskal

D、Floyd-Warshall

E、KMPstringmatch

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、下列属于设计模式中”creationalpattern”(创建型)的是?

A、Facade

B、Singleton

C、Bridge

D、Composite

Facadepositebridge都属于Structural(结构型)

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

三次握手baike.baidu/view/1003841.htm

*中好像没有SYN，SYN+ACK，ACK，于是我就选了E、Noneofabove

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

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、Noneofabove

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

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

只比较第一个元素。

StuctA{

Intkey1;

Intkey2;

};

比较函数为intcmp(Ax,Ay){returnx.key1-y.key1;)

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

冒泡排序其条件是cmp<0,显然(3,4)不可能会与(3,1)交换，因此不符合题目要求

快速排序是不稳定的排序，不能保*谁在谁前面，快排的条件是cmp<=0且其哨兵都是选择序列中的第一个作为哨兵，结合本题所给的数组a，结果是与题目相符。

13、继承、虚函数

下面程序输出结果

[cpp]viewplaincopyprint?#include

usingnamespacestd;

classBase

{

public:

charValue(){return'A';}

virtualcharVirtualValue(){return'X';}

};

classDerived:publicBase

{

public:

charValue(){return'U';}

};

classVirtualDerived:virtualpublicBase

{

public:

charValue(){return'Z';}

charVirtualValue(){return'V';}

};

voidmain()

{

Base*p1=newDerived();

Base*p2=newVirtualDerived();

cout<

p1->VirtualValue()<<""<<

p2->Value()<<""<<

p2->VirtualValue()<

}

#include

usingnamespacestd;

classBase

{

public:

charValue(){return'A';}

virtualcharVirtualValue(){return'X';}

};

classDerived:publicBase

{

public:

charValue(){return'U';}

};

classVirtualDerived:virtualpublicBase

{

public:

charValue(){return'Z';}

charVirtualValue(){return'V';}

};

voidmain()

{

Base*p1=newDerived();

Base*p2=newVirtualDerived();

cout<

p1->VirtualValue()<<""<<

p2->Value()<<""<<

p2->VirtualValue()<

}输出：AXAV

14、两个线程thread1:x=1;r1=y;thread2:y=1;r2=x;x和y初始值为0，两者皆为全局变量，程序运行过后r1和r2的值可能是

A、r1=1,r2=1

B、r1=1,r2=0

C、r1=0,r2=1

D、r1=0,r2=0

15、A，B，C，D都为32位整型，基于以下给定的C，D能否得出A，B

A、C=A+B,D=A-B

B、C=A+2*B,D=A+B

C、C=A+B,D=B

D、C=A-B,D=(A+B)>>1

E、C=A*B,D=A/B

该题主要是考虑越界问题

对于A选项假设A>0,B>0;C可能越界使得C=A+B-2^32举个反例：A=B=2^31-1C=-2,D=0;

A=B=-1,C=-2,D=0

对于C选项不管C是否越界总能得到A=C-D,B=D

对于B选项我们可以考虑Q=A+B,C=Q+B,D=Q跟C的那个一样，就能求出Q与BQ=A+B，B又已知A可求

D选项：A=B=-1A=B=2^31-1

E选项：A=B=2^15,A=B=2^31

16、BNF

很简单的一个题目

17、http协议

18、不属于栈的基本*作

A、pop

B、push

C、ifempty

D、sort

19.一颗完全二叉树有n个节点，求深度

A、lg(n)/lg2

B、1+lg(n)/lg2

• 腾讯校园招聘软件测试部分笔试题

  1、计算机系统中cpu中的base寄存器和limit寄存器的作用是()2、*作系统不执行以下哪个*作()a分配内存b输出/输入c资源回收d用户访问数据库资源3、以下哪个是用于用户拨号认*的()apptpbipseccl2pdchap4、下列...

• 微软公司IBM社会招聘笔试题

  小编整理了微软公司ibm社会招聘笔试题，欢迎阅读!微软公司ibm社会招聘笔试题1.一个粗细均匀的长直管子，两端开口，里面有4个白球和4个黑球，球的直径、两端开口的直径等于管子的内径，现在白球和黑球的排列是wbbbb，要求不取出任何一个球，使...

• 淘宝校园招聘会笔试题

  一、单选题1、我们有很多瓶无*的液体，其中有一瓶是毒*，其它都是蒸馏水，实验的小白鼠喝了以后会在5分钟后死亡，而喝到蒸馏水的小白鼠则一切正常。现在有5只小白鼠，请问一下，我们用这五只小白鼠，5分钟的时间，能够检测多少瓶液体的成分(c)a、5...

• 网易校园招聘笔试题目

  1、假设进栈次序是e1,e2,e3,e4，那可能的出栈次序是()a、e2,e4,e3,e1b、e2,e3,e4,e1c、e3,e2,e4,e1d、e1,e2,e4,e3给定入栈顺序，求出可能的出栈顺序。(点评：老得掉渣得题目了，只要小心点都...

• 腾讯技术类校园招聘笔试试题

  一.单选题(每题4分,15题,共60分)1.考虑函数原型voidhello(inta,intb=7,char*pszc=”*”),下面的函数调用钟,属于不合法调用的是:ahello(5)b.hello(5,8)c.hello(6,”#”)d...