微軟暑期實習筆試題和面試題答案及答案(二)

　　(A) y ^ ((x ^ y) & ~(x < y))

　　(B) y ^(x ^ y)

　　(C) x ^ (x ^ y)

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

　　(E) None of the above

　　11. The Orchid Pavilion (蘭亭集序) is well known as the top of "行書" in history of Chinese literature. The most fascinating sentence "Well I know it is a lie to say that life and death is the same thing, and that longevity and early death make no difference! Alas!" ("周知一死生為虛誕， 齊彭殤為妄作。") By counting the characters of the whole content (in Chinese version), the result should be 391 (including punctuation). For these characters written to a text file, please select the possible file size without any data corrupt.

　　(A) 782 bytes 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 the above

　　12. Fill the blanks inside class definition

　　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);

　　}

　　Running result: 0 20 1 20

　　(A) static/const

　　(B) const/static

　　(C) --/static

　　(D) const static/static

　　(E) None of the above

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

　　(A) 11 (B) 12 (C) 13 (D) 14

　　14. In C++, which of the following keyword(s) can be used on both a variable and a function?

　　(A) static (B) virtual (C) extern (D) inline (E) const

　　15. What is the result of the following program?

　　char f(char str, char ch)

　　{

　　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 << f(a, 'c');

　　}

　　(A) abdcccd (B) abdd (C) abcc (D) abddcccd (E) Access Violation

　　16. Consider the following definition of a recursive function, power, that will perform exponentiation.

　　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);

　　}

　　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 (C) quadratic (D) exponential

　　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 (B) 25/102, 12/50 (C) 50/51, 24/25 (D) 25/51, 12/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 be 1, 2 or 2, 1, so we get 2 different sequences.

　　(A) C_2n^n

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

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

　　(D) n!

　　(E) None of the above

　　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

　　(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?

　　#include

　　using namespace std;

　　struct Item

　　{

　　char c;

　　Item next;

　　};

　　Item Routine1(Item x)

　　{

　　Item Pv = NULL, curr = x;

　　while (curr) {

　　Item next = curr->next;

　　curr->next = Pv;

　　Pv = curr;

　　curr = next;

　　}

　　return Pv;

　　}

　　void Routine2(Item x)

　　{

　　Item curr = x;

　　while (curr) {

　　cout << curr->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);

　　}

　　(A) cbad (B) badc (C) dbca (D) abcd (E) dcba