微软实习笔试题.doc-资料库

zhijiang_wu2-5217006-4744300845408681304.doc.pdf-第1页.png

第1页 / 共9页

zhijiang_wu2-5217006-4744300845408681304.doc.pdf-第2页.png

第2页 / 共9页

zhijiang_wu2-5217006-4744300845408681304.doc.pdf-第3页.png

第3页 / 共9页

zhijiang_wu2-5217006-4744300845408681304.doc.pdf-第4页.png

第4页 / 共9页

zhijiang_wu2-5217006-4744300845408681304.doc.pdf-第5页.png

第5页 / 共9页

zhijiang_wu2-5217006-4744300845408681304.doc.pdf-第6页.png

第6页 / 共9页

zhijiang_wu2-5217006-4744300845408681304.doc.pdf-第7页.png

第7页 / 共9页

zhijiang_wu2-5217006-4744300845408681304.doc.pdf-第8页.png

第8页 / 共9页

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)? 对 80 个数进行选择排序，执行 32 个循环后，有多少个数已经固定位置？ (A) 16 (B) 31 (C) 32 (D) 39 (E) 40 Ans: C，考虑逆序的情况 2. Which synchronization mechanism(s) processes/threads in operating system? 下列哪些机制可以避免进程（线程）间的竞争条件？ (A) Mutex (B) Mailbox (C) Semaphore (D) Local procedure call Ans: A C,互斥量和信号量 is/are used to avoid race conditions among 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 maybe 1,2 or 2,1, so we get 2 different sequence. Suppose n is 7 and m is 5, please choose the output sequence 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,6,5,4 Ans: A C 4. What is the result of binary number 01011001 after multiplying 0111001 and adding 1101110? (A) 0001010000111111 (B) 0101011101110011 (C) 0011010000110101 Ans: A 5. What is output if you compile and execute the following C code? [cpp] view plaincopy int main() { int i = 11; int const * p = &i; p++; printf("%d", *p); return 0; } [cpp] view plaincopy int main() { int i = 11; int const * p = &i;

p++; printf("%d", *p); return 0; } (A) 11 (B) 12 (C) Garbage value (D) Compile error (E) None of above Ans: C，p 指向 i 后的四字节内存，为任意值。 6. Which of following C++ code is correct? (A) [cpp] view plaincopy int f() { int *a = new int(3); return *a; } [cpp] view plaincopy int f() { int *a = new int(3); return *a; } (B) [cpp] view plaincopy int *f() { int a[3] = [1, 2, 3]; return a; } [cpp] view plaincopy int *f() { int a[3] = [1, 2, 3]; return a; } (C) [cpp] view plaincopy vector f() { vector v[3]; return v; }

[cpp] view plaincopy vector f() { vector v[3]; return v; } (D) [cpp] view plaincopy void f(int * ret) { int a[3] = {1, 2, 3}; ret = a; return; } [cpp] view plaincopy void f(int * ret) { int a[3] = {1, 2, 3}; ret = a; return; } (E) none of above Ans: C，(A)申请内存后没有初始化，返回的是任意值；(B)返回 a 的地址，但数组 a 在栈区，返回后栈就释放了；(C)印象中 vector 是在堆区，可行；(D)的问题同 B 7. Given that the 180-degree rotated image of a 5-digit number is another 5-digit number and the difference between the number is 78633, what is the original 5-digit number? (A) 60918 Ans: D, 89601-10968 = 78633 (D) 10968 (E) 86901 (B) 91086 (C) 18609 8. Which of the following statements are true (A) We can create a binary tree from given inorder and preorder traversal seqences (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)=O(1) if n=1; T(n)=2T(n/2)+O(n) if n>1; so T(n) is O(nlogn) (E) None of the above Ans: A D 9. Which of the following statements are true? (A) Insertion sort and bubble sort are not eficient for large data sets. (B) Quick sort makes O(n2) comparisons in the worst case (C) There is an array: 7,6,5,4,3,2,1. operation is 6 (D) Heap sort uses two heap operations: insertion and root deletion (E) None of above If using selection sort(ascending), the number of swap

Ans: A B， C 只需要 3 次交换 10. Assume both x and y are integers, which one of the following returns the minimun of the two integers? (A) y^((x^y) & -(x

} [cpp] view plaincopy class Test { public: __ int a; __ int b; public: Test::Test(int _a, int _b): a(_a) { b = _b; } }; int Test::b; int _tmain(int argc, _TCHAR * argv[]) { Test t1(0, 0), t2(1, 1); t1.b = 10; t2.b = 20; printf("%u %u %u %u", t1.a, t1.b, t2.a, t2.b); return 0; (B) const/ static } Running result: 0 20 1 20 (A) static/ const above Ans: C 13. A 3-order B-tree has 2047 key words, what is the maximum height of the tree? (A) 11 Ans: 不太了解 B 树，看完书在作答案 (D) const static/ static (C) -/ static (D) 14 (E) None of the (B) 12 (C) 13 (D) inline (C) extern (B) virtual 14. In C++, which of the following keyword(s) can be used on both a variable and a function? (A) static Ans: A C E 15. What is the result of the following program? [cpp] view plaincopy char* f(char* str, char ch) { (E) const char* it1 = str; char* it2 = str; while(*it2 != '\0') { while(*it2 == ch) { it2++;

} *it1++ = *it2++; } return str; } void main(int argc, char* argv[]) { char* a = new char[10]; strcpy(a, "abcdcccd"); cout<

return power(b*b, e/2); return b*power(b*b, e/2); } [cpp] view plaincopy int power(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); (C) quadratic (D) exponential } Asymptotically(渐近地) in terms of the exponent e, the number of calls to power that occur as a result of the call power(b, e) is (A) logarithmic (B) linear Ans: A，以 2 为底的对数 17. Assume a full deck of cards has 52 cards, 2 black suits(spade and club) and 2 red suits(diamond and heart). If you are given a full deck, and a half deck(with 1 red suit and 1 black suit), what's the possibility for each one getting 2 red cards if taking 2 cards? (A) 1/2, 1/2 Ans: B, a full deck: 26*25/(52*51), a half deck: 13*12/(26*25) (B) 25/102, 12/50 (D) 25/51, 12/25 (C) 50/51, 24/25 (E) 25/51, 1/2 18. There is a stack and a sequence of n numbers(i.e. 1, 2, 3, ..., n). Push the n numbers into the stack following the sequence and pop out randomly. How many different sequences of the number we may get? Suppose n is 2, the output sequence may 1, 2 or 2, 1, so we get 2 different sequences. (A) C_2n^n Ans: B C, 特殊值试出来的，B 化简后就是 C (B) C_2n^n-C_2n^(n+1) (E) None of the above (C) ((2n)!)/(n+1)n!n! (D) n! 19. Longest Increasing Subsequence (LIS) means a sequence containing some elements in another sequence by the same order, and the values of elements keeps increasing. For example, LIS of (2, 1, 4, 2, 3, 7, 4, 6) is (1, 2, 3, 4, 6), and its LIS length is 5. 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 N, Space: N Ans: C，见《编程之美》最长上升子序列的讨论 20. What is the output of the following piece of C++ code? [cpp] view plaincopy #include using namespace std; (C) Time: NlogN, Space: N (B) Time: N^2, Space: N (E) Time: N, Space: C (D) Time: 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<c<<" "; curr = curr->next; } } void _tmain(void) { Item *x, d = {'d', NULL}, c = {'c', &d}, b = {'b', &c}, a = {'a', &b}; x = Routine1(&a); Routine2(x); } [cpp] view plaincopy #include using namespace std; struct Item {

资料库

微软实习笔试题.doc

相关推荐

开发技术

热门标签

最新资料