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
解析：选择排序每次能确定一个元素的最终位置，所以迭代32次能确定32个元素的位置。
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
答案：AC
解析：进程同步和互斥同样使用Mutex和Semaphore，这是OS的基本知识。
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 int 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
答案：AC
解析：考查栈的基本操作。A中进一个出一个，可以。B中7个元素全部进完，再依次出栈，栈空间只有5，实现不了这种序列。C可以。D需要6个存储空间，超过栈的容量了。E出栈顺序非法。
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
答案： A
解析：考查二进制的乘法，由于是选择题，我们可以通过排除法来快速的得到答案，只看后三位，相乘再相加，后三位为111，所以答案为A。
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
答案： C
解析：这里考查const关键字的用法。const *p = &i；const用来修饰指针所指向的变量，这时指针可变，变量是常量不能再被改变。p++后p指针指向未知的内存空间，所以打印的是垃圾数据。
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;
}
答案：C
解析：A中内存泄露。B中由于a是局部变量，在函数执行完后即被释放，所以不能被传递。D中同样也是局部变量。
7. Given that the 180-degree rotated image of a 5-digit number is another 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
答案： E
解析：89601 - 10968 = 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 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.
答案：ACD
解析：从树的遍历序列建树，必须要知道中序，再加上前序或者后序。所以A对B错。对于已经排好序的数组，用快速排序的效率会达到最差O(n^2)，而插入排序在此时有很多的优势，需要移动的元素个数会很少，所以C对。D是一个简单的算法复杂度的计算，根据主定理T(n) = a*T(n/b) + f(n)，比较f(n)和n^(log以a为底b的对数)的大小，这里是相等，所以T(n) = O(n*log n).所以D对。D也可以一步一步的递推，同样能很快的得到结果。
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.
答案：ABD
解析：对于大规模的数据，一般采用归并排序较好，时间复杂度为O(n*log n)，插入排序和冒泡排序在最坏情况下的时间复杂度为O(n^2)。不适合处理大规模的数据。A对。当数据基本有序的情况下，快速排序达到最坏效率，为O(n^2)，B对。C中用选择排序只需要进行3次数据交换，7和1，6和2，的5和3，之后数组就有序了。所以C错。D是堆排序的基本操作过程，正确。
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
答案：E
解析：A中是返回的最大值。B中返回x。C中返回y。D中返回0,。所以选E。
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 isthe 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
答案：BC
解析：不懂中文编码，下面解析来自网上。
中文编码问题。Unicode是定长编码，每个字符都是2字节，但有一个大尾和小尾的识别需要额外的2字节来作码字头（大尾是0xfe 0xff，表示字节的低位在高地址处，小尾是0xff 0xfe，表示字节的低位在低地址处，微机原理学的“低对低，高对高”说的是小尾系统），这样一样，A错B对。UTF-8是变长字节编码，但大部分中文用三字节完成，且没有大小尾的区别，所以C是对的，也有一种称之为带BOM的UTF-8编码方式，它有大小尾的码字头，但这里题目里没有BOM，所以不选D。
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
答案：BC
解析：看运行结果，b的值始终是20，可以判定b是静态的。a的值有变化，所以a不是静态的。用const修饰a是可以的，因为a初始化后并没有改变它的值，C也是可以的，自动默认为auto。所以BC正确。
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
答案：B
解析：考查B树的特性。除根结点以外的非叶子结点的儿子数为[M/2, M]。每个结点存放至少M/2-1（取上整）和至多M-1个关键字。要使树高达到最大，所以使得每个节点的分支尽量的少，关键字也尽量的少，这里分支数取2，关键字取1,。这时候B-树就退化为二叉树了，的2^11 = 2048，所以树高为11 + 1 = 12. 注意B-树的最后一层包含所有的关键字，所以有12层。
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
解析：A明显可以，静态变量和静态函数，变量可以修饰成extern，函数也可以声明extern型，C对。Const能修饰变量，也可以修饰类成员函数。所以E对。
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
答案： D
解析：当遇到c时，it2指针往后移动，遇到不是c的值将值赋给it1，覆盖it1原来的值，注意it2中的‘\0’是不操作的，所以it1后面的值还是会输出。
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(指数的)
答案：A（对数的）
解析：看函数的递归过程，主要是对e进行判断，每次递归e的大小都是减半，所以时间复杂度是自然对数型。
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
答案： B
解析：概率问题，从一整副牌中抽出2张红色的概率为 26/52 * 25/51 = 25/102。从半副牌中抽出2张红色的概率为 13/26 * 12/25 = 12/50。所以B正确。
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
答案：B C
解析：考研考过数据结构的应该都记得那个公式：(C_2n^n)/(n+1) = C_2n^n - C_2n^(n - 1). (或者是C_2n^n - C_2n^(n + 1)) 如果不知道公式，做为一个选择题，可以用特取值的方法来很快求解，但n = 1结果为1，n=2结果为2，n=3,结果为5，n=4结果为14。带入得到答案为B。B化简后就是C
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
答案：C
解析：此题在编程之美一书中出现过，可参照2.16:求数组中最长递增子序列。
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 *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
答案：E
解析：注意，初始链表的顺序是a,b,c,d。Routine1实质就是一个链表的反序过程，再调用Routine2输出就是dcba了。