第一部分（必做）：计算机基础类（25分）
（所有选择题都是多项选择）
1.（2分）假设进栈次序是e1,e2, e3, e4，那可能的出栈次序是（）
A、e2, e4, e3, e1 B、e2, e3, e4, e1 C、e3, e2, e4, e1 D、e1, e2, e4, e3
2.（2分）表达式X=A+B*(C-D)/E的后缀表示形式可以是（）
A、XAB+CDE/-*= B、XA+BC-DE/*= C、XABCD-*E/+= D、XABCDE+*/=
3.（2分）以下排序算法是非稳定排序的是（）
A、冒泡排序 B、归并排序 C、快速排序 D、堆排序 E、希尔排序
4.（2分）一个包含n个结点的四叉树，每一个节点都有4个指向孩子节点的指针，这4n个指针有（）个空指针。
5.（2分）int func(unsigned int i)
{
unsigned int temp = i;
temp = (temp & 0x55555555) + ((temp & 0xaaaaaaaa)>>1);
temp = (temp & 0x33333333) + ((temp & 0xcccccccc)>>2);
temp = (temp & 0x0f0f0f0f) + ((temp & 0xf0f0f0f0)>>4);
temp = (temp & 0xff00ff) + ((temp & 0xff00ff00)>>8);
temp = (temp & 0xffff) + ((temp & 0xffff0000)>>16);
return temp;
}请问func（0x7f530829）的返回值是（）
A、15 B、16 C、17 D、18
6.（2分）进程和线程的差别有（）
A、操作系统只调度进程，不调度线程
B、线程共享内存地址空间，进程不共享
C、线程可以共享内存数据，但进程不可以
D、进程间可以通过IPC通信，但线程不可以
7.（2分）关于段页式管理中，地址映像表是（）
A、每个进程一张段表，一张页表 B、进程的每个段一张段表，一张页表
C、每个进程一张段表，每段一张页表 D、每个进程一张页表，每段一张段表
8.（2分）关于TCP协议，下面哪种说法是错误的（）
A、TCP关闭连接过程中，两端的socket都会经过TIME_WAIT状态
B、对一个Established状态的TCP连接，调用shutdown函数可以让主动调用的一方进入半关闭状态
C、TCP协议默认保证了当TCP的一端发生意外崩溃（当机、网线断开或路由器故障），另一端能自动检测到连接失效
D、在成功建立连接的TCP上，只有在Established状态才能收发数据，其他状态都不可以。
9.（2分）关于主键PrimaryKey和索引index的说法哪些是错误的？（）
A、唯一索引的列允许为NULL值
B、一个关系表中的外键必定是另一表中的主键
C、一个表中只能有一个唯一性索引
D、索引主要影响查询过程，对数据的插入影响不大
10.（2分）数据库的事务隔离级别一般分为4个级别，其中可能发生“不可重复读”的事物级别有（）
A、SERIALIZABLE
B、READ COMMITTED
C、READ UNCOMMITTED
D、REPEATABLE READ
11.（5分）如果F(n)为该数列的第n项，那么这句话可以写成如下形式：
F(1)=1，F(2)=1，F(n)=F(n-1)+F(n-2)(n>=3)
请实现该函数F(n)的求解，并给出算法复杂度，要求算法复杂度小于O(n^2)。
第二部分（必做）：程序设计（25分）
1.（2分）下面的程序的输出是什么？
#include<stdio.h>
int main()
{
intn;
chary[10] = “ntse”;
char*x = y;
n= strlen(x);
*x= x[n];
x++;
printf(“x=%s\n”,x);
printf(“y=%s\n”,y);
}
2.（2分）请给出下面程序的输出结果，并说明原因。
#include<vector>
#include<iostream>
using namespace std;
template<class t>
class array{
public:
array(int size);
size_t getVectorSize() {return_data.size();}
size_t getSize() {return_size;}
public:
vector<t> _data;
size_t _size;
}
template<class t>
array<t>::array(intsize):size(size),_data(_size)
{ }
int main()
{
array<int>*arr= new array<int>(3);
cout<<arr->getVectorSize()<<endl;
cout<<arr->getSize()<<endl;
return0;
}
3.（2分）CAS(CompareAndSwap)，是用来实现lock-free编程的重要手段之一，多数处理器都支持这一原子操作，其用伪代码描述如下：
template bool CAS(T* addr, T expected, Tvalue)
{
if(*addr== expected){
*addr= value;
returntrue;
}
returnfalse;
}
请完成下面填空，实现全局计数器的原子递增操作。
int count = 0;
void count_atomic_inc(int *addr)
{
intoldval = 0;
intnewval= 0;
do
{
oldval= *addr;
newval= + 1;
}untilCAS( ， ， )
｝
4.（2分）下面的程序会输出几个“-”？
#include<stdio.h>
#include<sys/types.h>
#include<unistd.h>
int main(void)
{
intI;
for(i=0;i<2;i++){
fork();
printf(“-”);
fflush(stdout);
}
return 0;
}
5.（4分）写程序判断当前CPU是大端CPU还是小端CPU，并做简要说明。
6.（5分）利用位运算实现两个整数的假发运算，请代码实现，并做简要说明。
7.（8分）图深度遍历问题
a) 写出上述图的深度优先遍历的顺序（遍历起点是节点1）
b) 若用邻接矩阵Matrix存储该矩阵，写出该矩阵
c) 若用非递归方式实现深度优先遍历，请叙述大致的实现思想
d) 用你熟悉的任何语言实现非递归深度优先遍历
第三部分（选做）：C++开发工程师必做，其他选做（15分）
1.（6分）给定一个巨大的文本文件，写一个程序随机输出文件任意k行（k不大，k行能放入内存），要求每一行出现概率相等，请给出核心算法，算法复杂度以及简要的算法原理说明。
2.（9分）Spin Lock是一种较为常见与使用的互斥方法，下面是一种其实现方式：
typedef int lock_t
void initlock(void volatile lock_t*lock_status){
*lock_status= 0;
}
void lock(void volatile lock_t* lock_status){
while(test_and_set(lock_status)== 1);
}
void unlock(void volatile lock_t*lock_status){
*lock_status= 0;
}
a) volatile关键字的作用
b) 怎样优化lock函数(提示：多CPU下如何提高CPUCache效率)
c) 上述代码可能存在的问题（内存模型考虑）
第四部分（选做）：客户端安全工程师必做，其他选做
1. 请简述使用互斥量(Mutex)和临界区(CriticalSection)作为同步方法的区别及应用场景。
2. 如何让一个循环执行的线程安全退出，请用C++代码实现相应线程函数及退出机制。
3. 请列举可以用来唯一标识一台机器特征的属性有哪些；在某些机器特征可能被更换的情况下，请设计一套方案用来唯一标识这台机器。
4. 请描述利用CreatProcess注入一个dll到新创建进程的过程，必要部分可以写伪代码。
5. 请列举32位系统下，驱动隐藏进程的常用方法。
6. 如何检测当前程序运行在虚拟机环境下。
说明：虚拟机主要是指目前常见的VMWare，Virtual PC，Virtual Box等；可以对一种虚拟机检测，也可以对多种虚拟机检测进行说明。
第五部分（选做）：客户端开发工程师必做，其他选做
1. WM_QUIT消息的用途是什么？一个普通的windows窗口能收到的最后一条消息是什么？
2. 什么是DLL的延迟加载(DelayLoad)？用延迟加载有什么好处？
3. 并行计算(ParallelComputing)与并发计算(Concurrent Computing)的联系与区别是什么？
4. 堆内存(Heap)和栈内存(Stack)的联系和区别是什么？在编码过程中，何时优先使用堆内存，何时优先使用栈内存？
5. 为什么windows下有些文件被删除后还能通过一些数据恢复软件将其数据恢复？