网易2013校园招聘笔试题

时间:2021-03-10 18:53:28

第一部分(必做):计算机基础类(25分)

(所有选择题都是多项选择)

1.(2分)假设进栈次序是e1,e2, e3, e4,那可能的出栈次序是()

Ae2, e4, e3, e1  Be2, e3, e4, e1  Ce3, e2, e4, e1   De1, e2, e4, e3

2.2分)表达式X=A+B*(C-D)/E的后缀表示形式可以是()

AXAB+CDE/-*=   BXA+BC-DE/*=  C、XABCD-*E/+=  DXABCDE+*/=

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   B16   C17   D18

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
DREPEATABLE READ
11.5分)如果F(n)为该数列的第n项,那么这句话可以写成如下形式:
F(1)=1F(2)=1F(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下有些文件被删除后还能通过一些数据恢复软件将其数据恢复?