微软笔试题

根据http://bbs.sjtu.edu.cn/bbscon,board,JobForum,file,M.1333796036.A.html以及自己的记忆进行的修改。下面有些和原话有部分出入，但不影响理解。

不定向选择题，全答对得所有分，部分答对给一个分，答错扣分。越往后题的分值相对增大，做错扣的也越狠。

Choose部分是我自己做的答案,非标准答案.有些题目选项记不起来了,非常抱歉.

1.Selection sort 80 items, after 32 iterations, how many positions of items are inits final position?

A.16 B.31 C32 D39 E40

Choose：C

2.Which is used in sync（synchronization）process//thread to avoid race conditionin operation system?

A.MutexB.mailboxC.SemaphoreD.local procedure call

Choose:AC

3.Size of a stack is 5, input is a sequence 1, 2, …, 7, which is possible output?

A.1234567 B. 76321 C.53721 D. 17632 E.32175

Choose:AC

4.010111001 * 011001 + 1101110 = ?(我的试卷是01011000*0111001+1101110=？)

A.0001010000111111 B.0101011101110011 C.0011010000110101

Choose:A

5.What is the output of the follow code?

voidmain(intargc, char* argv[]) {

int i = 11;

intconst *p = &i; p++;

print(“%d”,*p); }

A. 11 B. 12 C.Garbage value D. Comipler error E. None of above

Choose:C

解析：这个笔者在程序里面运行了，确实得到一个这样的数据-8593460

6.Which code is correct?

A. intf() {

int *a = new int(3);

return *a; }

C.vectorf() {

vector v(3);

return v; }

D. void f(int *ret) {

int a[3] ={1,2,3};

ret=a;

return ; }

E.None of above

Choose:AC

这个题我都在程序里面运行了，下面是我的理解

解析：A中注意newint的后面是（）而不是[],()的返回结果为3，[]对应的返还结果为一个Garbagevalue，按这个说来这个选项也可姑且算为对(可以认为这个函数就是返还一个3)

B 由于在函数内部定义的a，函数结束后空间就释放了，（空间内的值暂时还是1，2，3，但是当别的代码需要分配空间的时候，就可能会用新的值覆盖掉1，2，3）。这属于悬空指针吧.

D.只是变了指针ret的指向，最后指针ret还被释放了。

7.Which number has difference 78633 after 180-degree rotation?

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

Choose:D

8Which statement is true?

A.Inorder and preorder can determine a Binary tree

B.Postorder and preorder can determine a Binary tree

C. Foralmost sorted array, Insertion sort is more efficient than Quicksort

D. n=1,T(n)= ⊖(n) ,whe n>1 T(n)=2T(n/2)+⊖(n), Then T(n)=⊖(nLogn)

E.none of above

Choose:ACD

9. Whichstatement is true?

A.Insertion and buble sort are not effient for large data sets

B. Thecomplexity of Quick Sort is O(n2) in worst case

C. Itis needed 6 swap operations to sort sequence 7,6,5,4,3,2,1(ascending) by Selectionsort

D.Heap sort has two operations: Insertion and root deletion

E.None of above

Choose:AB

10.Which expression return Minimum value of x and y?

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

Cx^(x^y)

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

Choose:A.

11.For 391 characters(including punctuation). select possible file size withoutdata corrupt?

A. 782bytes in UTF-16 encoding B.784 bytes in UTF-16 encoding

C.1173 bytes in UTF-8 encoding D.1176 bytes in UTF-8 encoding

E.None of above

Nochoose

12.The output of the following code is 0 20 1 20, what are the type of a and b?

classTest{

public:

____ int a;

____ int b;

Test(int _a, int _b) {a = _a;b=_b;} }

voidmain() {

Test t1(0, 0), t2(1,1);

t1.b = 10;

t2.b = 20;

cout<A.static/const B. const/static C. __/static D. const static/static

E.None of above

Choose:C

13. A3-order B-tree has 2047 key words, what is the maximum height?

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

nochoose

14.Which can be used both to variable and function?

A.static B. virtual C. extern

Choose:ACE

15.What is the output of the follow code?

char *f(char *str, char ch) {

char *it1 = str;

char *it2 = str;

while(*it2 != '\\0') {

while(*it2 == ch)

{

it2++;

}

D. inline E. const *it1++ = *it2++;

}

returnstr; }

int main(intargc, char* argv[]) {

char *a = new char[10];

strcpy(a, \"abcdcccd\");

cout<return 0; }

A.abdcccd B. abdd C. abccD.abddcccd E. Access violation

Choose:D

16.What is the complexity of the result call of power(b, e) in the follow code?

intpower(int b, int e) {

if(e==0) return 1;

if(e%2 == 0) return power(b*b,e/2);

return b*power(b*b,e/2); }

A.logarithmicB.linear C. quadratic D. exponentical

Choose:A

17.Take 2 cards from one full poker(52 cards, 26 red and 26 black) and half pokereach, what is the probability of the event that two cards are both red?

A.1/2,1/2 B. 25/102,12/50 C. 50/51, 24/25 D. 25/51,12/25 E.25/51,1/2

Choose:B

18.How many kinds of output of stack with the input 1,2,…,n?

B.C_2n^n-C_2n^(n+1) C.((2n)!)/(n+1)n!n! D. n! E. none

Choose:C

19.What is the minimum time and space complexity to compute the Largest IncreasedSubsequence(LIS) of array?

A.N^2,N^2 B. N^2,N C. NlogN,N D. N, N E. N,C

Choose:C

解析：这个《编程之美》里面有

20.What is the output of the follow code?

structItem{

char c;

Item *next; };

Item*f1(Item* x){

Item *prev = NULL;

Item *curr = x;

while(curr) {

Item *next =curr->next;

curr->next =prev;

prev = curr;

curr = next;

}

returnprev; }

voidf2(Item *x){

while(x){

cout<c;

x = x->next;

} }

intmain(intargc, char* argv[]){

Item *x, d = {'d', NULL}, c ={'c', &d}, b = {'b', &c}, a = {'a', &b};

x = f1(&a);

f2(x);

return 0; }

Choose:dcba

解析：链表的逆置