In the following，at least one correct answer to each question
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
Answer：C
每次从未排序序列中寻找最小值，置于目前已排序序列末尾。迭代32次，前32个数已排序。
2. Which synchronization mechanism(s) is/are used to avoid race conditions among processed/threads in operating systems?
A. Mutex
B. Mailbox
C.Semaphore
D. Local procedure call
Answer：AC
进程/线程间同步机制：
临界区（Critical Section）、互斥量（Mutex）、信号量（Semaphore）、事件（Event）
进程间通信方式：
管道（Pipe）、信号（Signal）、消息队列（Message Queue）、共享内存（Shared memory）、信号量（semaphore）、套接字（Socket）、内存映射文件（memory-mapped file）、广播式通信（Mailslots）、 信箱通信（Mailbox）、远程过程调用(Remote Procedure Calls,即RPC)
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
Answer：AC
4. What is the result of binary number 01011001 after multiplying by0111001 and adding1101110?
A. 0001010000111111
B. 0101011101110011
C. 0011010000110101
Answer：A
算法一：只观察最后三位
001*9=1001 最后三位回归为初始001
与0111001相乘即相当于2的5次+2的4次+2的3次+1 的自相加操作，mod 9余6。
001相加6次为111
算法二：对应1位左移
由于乘数0111001对应1的位数过多，将此数分为两部分0111000和0000001
01011001*0111000===01011001 000*0111===01011001 000*(1000-0001)
等于01011001 000左移三位01011001 000 000减去01011001 000
得数加01011001 *1+1101110即为答案
此过程也可只观察后三位
5. What is output if you compile and execute the following c code?
void main()
{
int i=11;
int const *p=&i;
p++;
printf("%d",*p);
}
A. 11
B. 12
C. Garbage value
D. Compiler error
E. None of above
Answer：C
const修饰指针正指向的对象，指针本身非const，p++后指向&i后一个地址。
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;
}
E、None of above
Answer：E
(A)函数声明中返回 int，实际返回的a是int*。
如果讲函数声明改为：int *f()。new申请的动态空间在堆上，申请和释放由程序员操作，当函数返回时，该空间不会自动释放。若申请的空间在栈上，函数返回时系统自动释放申请的占空间，因而返回的栈空间指针不可用。
(B)int a[3] = {1, 2, 3} 是局部变量，位于栈空间。在函数返回时，我们返回了指针a，为了安全着想，将不使用该指针。(栈空间被覆盖后，获得garbage value)。
(C)同理B
(D) ret是形参，当函数返回时，值不会发生变化。
7. Given that the 180-degree rorated 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
B. 91086
C.18609
D.10968
E. 86901
Answer：D
180 度6变9 ，9变6
8. Which of the following statements are ture?
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)=O(1) if n=1; T(n)=2*T(n/2)+O(n) if n>1; so T(n) is O(n*logn).
E. None of above.
Answer：ACD
(B)a和b,a是根,b是孩子，只知道preorder and postorder ，无法知道是左孩子还是右孩子；
先序：根左右 中序：左根右 后序：左右根
(D)Think of O(n) as being cn for some constant c, so: T(n) <= 2T(n=2) + cn.
we can bound T(n) in terms of T(n=2), then T(n=4), then T(n=8),and so on, at each step getting closer to the value of T() we do know,namely T(1) = O(1):
T(n) <= 2T(n=2) + cn
<= 2[2T(n=4) + cn=2] + cn = 4T(n=4) + 2cn
<= 4[2T(n=8) + cn=4] + 2cn = 8T(n=8) + 3cn
<= 8[2T(n=16) + cn=8] + 3cn = 16T(n=16) + 4cn
A pattern is emerging… the general term is
T(n) <= 2(k次方)T(n=2(k次方)) + kcn
Plugging in k = log2 n (the depth of the recursion) we get T(n)<= nT(1)+cn log2 n = O(n log n).
9. Which of the following statements are true?
A. Insertion sort and bubble sort are not efficient 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.
Answer：BD
(A)情况不定
(C)less than 6,try
(D)from wikipedia
10. Assume both x and y are integers ,which one of the following 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
Answer：A
x^y是按位异或操作，亲
假如x>y,(x<y)=0,-（x<y）=000000，y^((x^y)&(0000000))=y
假如x<y,(x<y)=1, -(x<y) = -1，-1的位表示就是全1，y^((x^y)&(1111111))=y^(x^y)=x
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 charaters written to a text file ,please select the possible 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
Answer：BCD
UTF-16两字节表示一个汉字，有Big Endian和Little Endian两种，必须要加BOM两字节。UTF-8通常三字节一个汉字，有加BOM和不加BOM两种方式。
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 main(void)
{
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;
}
Running result : 0 20 1 20
A. static/const
B. const/static
C. –/static
D.const static/static
E. None of the above
Answer：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
Answer：A
若n≥1，m≥3，则对任意一棵具有n个关键字的m阶B-树，其树高h至多为：logt((n+1)/2)+1
这里t是每个(除根外)内部结点的最小度数，即 
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
Answer：ACE
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;
}
int main(void)
{
char *a = new char[10];
strcpy(a , "abcdcccd");
cout<<f(a,'c');
return 0;
}
A. abdcccd
B. abdd
C. abcc
D. abddcccd
E. Access violation
Answer：D
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);
else
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. exponentical(指数的)
Answer：A
有点类似8的D
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 half deck(with 1 red suit and a black suit), what’s the possiblility 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
Answer：B
C26(2)/C52(2)
C13(2)/C26(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 n 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
B. C_2n^n-C_2n^(n+1)
C. ((2n)!)/(n+1)n!n!
D. n!
E. none of the above
Answer：C
Catalan数
19. Longest Increasing Subsequence(LIS) means a sequence containing some elements in another sequence by the same order, and the values of elements keep increasing.
For example, LIS of (2,1,4,2,3,7,4,6) is (1,2,4,6), and its LIS length is 5.
Considering an array with N element ,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
Answer：C
20.What is the output of the follow 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;
}
}
int main(void)
{
Item *x,
d = {'d' , NULL},
c = {'c' , &d},
b = {'b' , &c},
a = {'a' , &b};
x = Routine1( &a );
Routine2( x );
return 0;
}
A. c b a d B. b a d c C. d b c a D. a b c d E. d c b a
Answer：E
相似链表逆转
6.选C，不同于B，B返回的是指向临时数组的地址；C返回的是对象，复制给返回值了。