学步园

这是网上找到的一套微软笔试题。本人自己做了一下，题解贴在这里。水平有限，错误之处，欢迎拍砖！

首先说一下这套题的评分标准，微软的标准总是很有意思，对于选择题，他们是一定会设法避免有人瞎蒙的！

1~7 全对3分，少选2分，错选-2分

8~18 全对5分，少选3分，错选-3分

19~20 全对12分，少选5分，错选-5分

所有题目不选均是0分。

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

选C

Selection Sort每迭代一次，确定一个元素的位置，迭代32次，自然是确定32个元素。
2、Which synchronization mechanism(s) is/are used to avoid race conditions among processes/threads in operating system?
A、Mutex B、Mailbox
C、Semaphore D、Local
procedure call

选AC

用互斥和信号量避免竞争的紊乱。
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 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,5,6,4

选AC

A，每入栈一个元素立马拿出即可，由于栈容量为5，所以B不可能，同理，D也不可以，E这种顺序是不可能。C先入栈5个，然后把5出栈，再把6入栈，拿出6，4，3，把7入栈，然后全部出栈。
4、Which is the result of binary number 01011001 after multiplying by 0111001 and adding 1101110?
A、0001010000111111
B、0101011101110011
C、0011010000110101

选A

这种肯定不会直接去算。先看一下乘，乘完之后最后几位正好是0001的形式，所以再加1101110之后最后四位肯定都是1，从而选A。

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

1. void main()

2. {

3. int i = 11;

4. int const *p
= &i;

5. p++;

6. printf("%d",*p);

7. }

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

选C

int const *p表示p指向的对象是不能修改的，但p所指的对象可以变，所以p++之后指向了一个垃圾值。

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

A、

1. int f()

2. {

3. int *a = new int(3);

4. return *a;

5. }

B、

1. int *f()

2. {

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

4. return a;

5. }

C、

1. vector<int>
f()

2. {

3. vector<int>
v(3);

4. return v;

5. }

 D、

1. void f(int *ret)

2. {

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

4. ret = a;

5. return ;

6. }

E、None of above

选ABC

A，返回一个int值自然是可以的。B，这种方式是不安全的，因为a的作用域在函数内，函数返回时会释放a的内存，应该尽力避免这样的使用！但是这里不会有语法或者什么编译的问题，不过在多数编译器里会给出warning，提示返回了一个局部变量的地址。如果用int *p = f()调用，当函数结束时，p指向的是一个已经不存在对象的地址，不过输出p[0],
p[1], p[2]会得到1，2，3的结果，这是因为虽然对象不存在了，但这几个内存单元还是存着原来的结果。总之，这样的调用不会有语法问题，也可以编译连接运行，但是是非常不安全的！C，这个是正确的，返回vector<int>时，应该是会调用拷贝构造函数（是这样吗？）。

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

选D

没什么说的，这个转完之后是89601，正和相差78633

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 Quciksort.
D、Suppose T(n) is the runtime of resolving a problem with n elements, T(n)=O(1) if n=1;
T(n)=2*T(n/2)+O(n) if n>1; so T(n) is O(nlgn)
E、None of above

选ACD

A,给出中序遍历顺序和先序遍历顺序可以确定一颗二叉树，给出中序遍历顺序和后序遍历顺序也可以确定一棵二叉树，但给出后序和先序却是不可以的。C，QuickSort总是希望数据越乱越好，见 http://blog.csdn.net/stormdpzh/article/details/8718760。D，这个是很明显的，2
* (n / 2)log(n / 2) + n = nlogn
9、Which of the following statements are true?
A、Insertion sort and bubble sort are not efficient for large data sets.
B、Qucik 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 operations is 6
D、Heap sort uses two heap operations:ion and root deletion （插入、堆调整）
E、None of above

选B

见 http://blog.csdn.net/stormdpzh/article/details/8718760。Quick Sort在最坏情况下会退化到O(n^2)，不过如果加上随机化等方法，这种退化的可能性是极其小的。
10、Assume both x and y are integers,which one of the followings returns the minimum of the two integers?
A、y^((x^y) & -(x<y))
B、y^(x^y)
C、x^(x^y)
D、(x^y)^(y^x)
E、None of above

选A

B的结果是x，C的结果是y，D的结果是0.对于A，分析如下：

if(x >= y) y ^ ((x ^ y) & -(x ＜ y)) = y ^ ((x ^ y) & -0) = y ^ 0 = y = min(x, y);

if(x < y) y ^ ((x ^ y) & -(x ＜ y)) = y ^ ((x ^ y) & -1) = y ^ ((x ^ y) & oxffffffff) = y ^ (x ^ y) = x = min(x,
y)
11、The Orchid pavilion(兰亭集序)
is well known as the top of “行书”in history of Chinese literature. The most fascinating sentence is "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 above

选BCD

UTF-16：2 bytes存储一个汉字+2 bytes BOM（Byte Order Marker），共784 bytes

UTF-8：3 bytes存储一个汉字+ 3 bytes BOM或者不加BOM，共1176或1173 bytes

12、Fill the blanks inside class definition

1. class Test

2. {

3. public:

4. ____ int a;

5. ____ int b;

6. public:

7. Test::Test(int _a
, int _b) : a( _a )

8. {

9. b = _b;

10. }

11. };

12. int Test::b;

13.

14. int main(void)

15. {

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

17. t1.b = 10;

18. t2.b = 20;

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

20. return 0;

21. }

Running result : 0 20 1 20

A、static/const

B、const/static

C、--/static

D、conststatic/static

E、None of above

选BC

由int Test::b和运行结果中b的值知b为static修饰。对于a，由于初始化用的是a(_a)的形式，所以可以有const修饰，也可以没有。如果构造函数写成Test::Test(int _a,
int _b) {a = _a; b = _b;}，则a不可以有const修饰。

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

选A

要使B-tree最高，则假定每个非叶子节点有两个孩子，而且所有的关键字都在叶子上。这样，12层的树可以有2048个关键字。然后删除一个关键字，从下往上依次合并。一个1个孩子的节点和一个2个孩子的节点合并成一个3个孩子的节点。最后，进行到根时，根只有1个孩子了，这时，删除根，高度-1。从而2047个关键字的B-tree最高应该是11层。
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

选ACE

概念。

15、What is the result of the following program?

1. char *f(char *str
, char ch)

2. {

3. char *it1 = str;

4. char *it2 = str;

5. while(*it2 != '\0')

6. {

7. while(*it2 == ch)

8. {

9. it2++;

10. }

11. *it1++ = *it2++;

12. }

13. return str;

14. }

15.

16. int main(void)

17. {

18. char *a = new char[10];

19. strcpy(a , "abcdcccd");

20. cout<<f(a,\c\);

21. return 0;

22. }

A、abdcccd
B、abdd
C、abcc
D、abddcccd
E、Access violation

选D

读代码。执行时，ab不变，过滤掉c，然后第一个c换成下一个非c字符（d），然后第一个d换成最后一个非c字符（还是d），剩下的字符没有变。从而输出abddcccd。

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

[cpp] view plaincopyprint?

1. int power(int b
, int e)

2. {