第一部分(必做):计算机基础类(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下有些文件被删除后还能通过一些数据恢复软件将其数据恢复?