这份微软暑期实生招聘笔试题来自网上资料,秋季找工作的计算机毕业生建议先自己做一遍，然后再寻找答案。

　　1. Suppose that a Selection Sort of 80 items has completed 32 iterations of the main loop. How many items are now guaranteed to be in their final spot (never to be moved again)?

　　(A) 16 (B) 31 (C) 32 (D) 39 (E) 40

　　2. Which Synchronization mechanism(s) is/are used to avoid race conditions among processes/threads in operating systems?

　　(A) Mutex (B) Mailbox (C) Semaphore (D) Local procedure call

　　3. There is a sequence of n numbers 1, 2, 3,.., n and a stack which can keep m numbers at most. Push the n numbers into the stack following the sequence and pop out randomly. Suppose n is 2 and m is 3, the output sequence may be 1, 2 or 2, 1, so we get 2 different sequences. Suppose n is 7 and m is 5, please choose the output sequences of the stack:

　　(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. What is the result of binary number 01011001 after multiplying by 0111001 and adding 1101110?

　　(A) 0001 0100 0011 1111

　　(B) 0101 0111 0111 0011

　　(C) 0011 0100 0011 0101

　　5. What is output if you compile and execute the following code?

　　void main()

　　{

　　int i = 11;

　　int const p = &i;

　　p++;

　　printf("%d", p);

　　}

　　(A) 11 (B) 12 (C) Garbage value (D) Compile error (E) None of above

　　6. Which of following C++ code is correct?

　　(A) int f()

　　{

　　int a = new int(3);

　　return a;

　　}

　　(B) int f()

　　{

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

　　return a;

　　}

　　(C) vector f()

　　{

　　vector v(3);

　　return v;

　　}

　　(D) void f(int ret)

　　{

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

　　ret = a;

　　return;

　　}

　　7. Given that the 180-degree rotated image of a 5-digit number is another 5-digit number and the difference between the numbers is 78633, what is the original 5-digit number?

　　(A) 60918 (B) 91086 (C) 18609 (D) 10968 (E) 86901

　　8. Which of the following statements are true?

　　(A) We can create a binary tree from given inorder and preorder traversal sequences.

　　(B) We can create a binary tree from given preorder and postorder traversal sequences.

　　(C) For an almost sorted array, insertion sort can be more effective than Quicksort.

　　(D) Suppose T(n) is the runtime of resolving a problem with n elements, T(n) = Θ(1) if n = 1; T(n) = 2T(n/2) + Θ(n) if > 1; so T(n) is Θ(n log n).

　　(E) None of the above.

　　9. Which of the following statements are true?

　　(A) Insertion sort and bubble sort are not effcient for large data sets.

　　(B) Quick sort makes O(n^2) comparisons in the worst case.

　　(C) There is an array: 7, 6, 5, 4, 3, 2, 1. If using selection sort (ascending), the number of swap operation is 6.

　　(D) Heap sort uses two heap operations: insertion and root deletion.

　　(E) None of above.

　　10. Assume both x and y are integers, which one of the followings returns the minimum of the two integers?