2012微软暑期实习生笔试题
2012微软暑期实习生笔试题
IT笔试面试题整理
2012 Microsoft Intern Hiring Written Test
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<int> f()
{
vector<int> 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?
(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 <iostream>
using namespace std;
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 << 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
[解决办法]
挑个最容易的翻译下：
下楼再接着翻译...
6. 下面的C++代码哪个是错误的？
(A) int f()
{
int *a = new int(3);
return *a;
}
(B) int *f()
{
int a[3] = {1, 2, 3};
return a;
}
(C) vector<int> f()
{
vector<int> v(3);
return v;
}
(D) void f(int *ret)
{
int a[3] = {1, 2, 3};
ret = a;
return;
}
[解决办法]
12.填写类定义在空白处
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);
}
运行结果: 0 20 1 20
(A) static/const
(B) const/static
(C) /static
(D) const static/static
(E) 以上都不是
[解决办法]
就看了前三道，第三题好像不太对吧。第二个选项错了。栈容量是5，不可能先弹出7的。
[解决办法]
中文版的题目出来了，你们大家要好好感谢我啊，哈哈，还有谷歌
2012年微软实习生招聘笔试
1。假设选择排序的80项已完成32个主循环迭代。多少个项目，现保证在其最终点（永远不会被再次感动）？
（一）16（二）31（三）32（四）39（五）40
2。其中同步机制（S）/用于避免操作系统的进程/线程之间的竞争条件？
（一）互斥（二）邮箱（c）信号灯（四）本地过程调用
3。有n个数字1，2，3，...，n和堆栈可以保持至多m数字序列。推入堆栈后n个数的顺序和随机弹出。假设n是2和m 3，输出序列可能是1,2或2，1，所以我们得到2个不同的序列。假设n是7和m是5，请选择栈的输出序列：
（一）1，2，3，4，5，6，7
（二）7 6 5 4 3 2 1
（三）5，6，4，3，7，2，1
（四）1，7，6，5，4，3，2
（五）3，2，1，7，5，6，4
4。什么是结果后的二进制数01011001乘以0111001和增加1101110？
（一）0001 0100 0011 1111
（二）0101 0111 0111 0011
（三）0011 0100 0011 0101
5。什么是输出，如果你编译并执行下面的代码吗？
void main()
{
int i = 11;
int const *p = &i;
p++;
printf(“%d”, *p);
}
（一）11（二）12（三）垃圾值—）编译错误（五）没有以上
6。后C + +代码是正确的吗？
(A) int f()
{
int *a = new int(3);
return *a;
}
(B) int *f()
{
int a[3] = {1, 2, 3};
return a;
}
(C) vector<int> f()
{
vector<int> v(3);
return v;
}
(D) void f(int *ret)
{
int a[3] = {1, 2, 3};
ret = a;
return;
}
7。鉴于一个5位数字图像的180度旋转，另5位数字和数字之间的差异是78633，什么是原来的5位数字？
（一）60918（二）91086（三）18609 10968（四）（五）86901
8。下列哪项是真的吗？
（一）我们可以从定序和序遍历序列创建二叉树。
（二）我们可以从定序和后序遍历序列创建二叉树。
（三）对于一个几乎排序的数组，插入排序，可以更有效地比快速排序。
（d）假设T（N）是n个元素，T（N）=Θ（1）如果解决问题的运行N = 1; T（N）= 2T（n / 2个）+Θ（N） > 1，所以T（n）是Θ（n日志n）。
（五）以上皆非。
9。下列哪项是真的吗？
（一）插入排序，冒泡排序是不effcient大型数据集。
（二）快速排序为O（n ^ 2），在最坏的情况进行比较。
（三）有一个数组：7，6，5，4，3，2，1。如果使用选择排序（升序），交换操作数为6。
（四）堆排序使用两种堆操作：插入和根删除。
（五）没有以上。
10。假设X和Y都是整数，其中有下列情形之一的，返回两个整数的最低？
（一）Y ^（（X ^ Y）＆?（X <Y））
（二）Y ^（X ^ Y）
（三）X ^（X ^ Y）
（四）（X ^ Y）^（Y ^ X）
（五）以上皆非
11。兰亭（兰亭集序）以及被称为“行书”在中国文学史上的顶部最迷人的一句“嗯，我知道这是一个谎言说，生死是一回事，是长寿和过早死亡没有什么区别！唉！“（”周知一死生为虚诞，齐彭殇为妄作。“），通过计算的全部内容（中国版）的人物，其结果应该是391（包括标点符号）。对于这些字符写入到一个文本文件，请选择没有任何损坏的数据可能的文件大小。
（一）782字节的UTF-16编码
（二）784字节的UTF-16编码
（三）1173字节的UTF-8编码
（四）1176字节的UTF-8编码
（五）以上皆非
12。填充类定义内的空白
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);
}
运行结果：0 20 1 20
（一）静态/常??量
（二）常量/静态
（三）-/static
（四）const的静态/静态
（五）以上皆非
13。一个3阶B-树有2047关键词，该树的最大高度是什么？
（一）11（二）12（三）13（四）14
14。在C +（S）上可以使用的变量和函数，下面的关键字？
（一）静态（二）虚拟（三）外部（四）内联常量（五）
15。以下程序的结果是什么呢？
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’);
}
（一）abdcccd（二）abdd（三）ABCC（e）abddcccd“（五）访问冲突
16。考虑下面的递归函数的定义，电源，将执行幂。
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);
}
渐近（指数e的渐进地），电话，通话功率发生电源（B，E）
（一）对数（二）线性（三）二次（四）指数
17。假设一个完整的卡甲板上有52张牌，2黑色西服（铁锹和俱乐部）和2（钻石和心脏）红色西装。
如果你给出了一个完整的甲板上，和一个半甲板（1红色西装和1个黑色西装），是每一个得到2张红牌2张卡的可能性？
（一）1/2，1/2（二）25/102，12/50（三）50/51，24/25（四）25/51，12/25（五）25/51，1/2
18。有一个栈和一个n个数的序列（即1，2，3，...，N）。推入堆栈后n个数的顺序和随机弹出。我们可能得到的数量很多不同的序列如何？假设n为2，输出序列可能是1,2或2，1，所以我们得到2个不同的序列。
（一）C_2n ^ N
（二）C_2n ^ N - C_2n ^（N + 1）
（三）（（2N））/（N + 1）N！N！
（四）N！
（五）以上皆非
19。最长递增子序列（LIS）是指由同一顺序的序列包含另一个序列中的某些元素，元素的值不断增加。
例如，图书情报学{2，1，4，2，3，7，4，6} {1，2，3，4，6}，其图书情报学的长度为5。
考虑N个元素的数组，什么是最低的时间和空间的复杂性，以获取图书情报学的长度？
（一）时间：^ 2，空间：^ 2
（二）时间：^ 2，空间：
（三）时间：NlogN，空间：
（四）时间：N，空间：
（五）时间：N，空间：C
20。下面这段C + +代码的输出是什么？
#include <iostream>
using namespace std;
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 << 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);
}
（一）cbad（二）BADC（三）DBCA（四）ABCD（五）DCBA