http://blog.csdn.net/lisonglisonglisong/article/details/51051282

一、不定项选择题

1、以下不属于tcp连接断开的状态的是？

• A. TIME_WAIT
• B. FIN_WAIT_1
• C. SYNC_SENT
• D. FIN_WAIT_2

2、关于红黑树跟AVL树，以下哪种说法不正确？

• A. 两者都属于自平衡二叉树
• B. 两者查找、插入、删除的时间复杂度相同
• C. 包含n个内部节点的红黑树的高度是O(logn)
• D. JDK的TreeMap是一个AVL树的实现

【解】红黑树和AVL树都属于自平衡二叉树，它们的查找、插入、删除的时间复杂度相同，都为O(log n)；包含n个内部节点的红黑树的高度是O(logn)，至多为2log(n+1)

3、有一个如下的结构体：

struct A {
    long a1;
    short a2;
    int a3;
    int *a4;
};

请问在64位linux系统下用sizeof(struct A)计算出的大小是多少？

• A. 24
• B. 28
• C. 16
• D. 18

【解】关于内存对齐，见文《C/C++内存对齐》。

4、小明设计了如下的学籍管理系统：

已知关系：学籍（学号，学生姓名） PK=学号；成绩（科目号，成绩，学号） PK=科目代号，FK=学号。已有表记录如上，请给出能够插入的成绩记录。

• A. (1, 99, 2)
• B. (5, 68, 1)
• C. (3, 70, 3)
• D. (7, 45, null)

【解】外键可以为空，所以D选项也是可以的。

5、在一个单CPU的处理机中，有P1、P3、P5三个作业，有两个IO设备IO1、IO2，并且能够实现抢先式多任务并行工作的多道程序环境中，投入运行优先级由高到低P5、P1、P3三个作业，他们使用设备的先后顺序和占用设备的时间分别为：

• P1：IO2（10ms） CPU（10ms） IO1（30ms） CPU（10ms）
• P3：IO1（30ms） CPU（10ms） IO2（30ms） CPU（10ms）
• P5：CPU（20ms） IO1（30ms） CPU（10ms） IO2（15ms）

忽略其他的时间损耗，3个作业投入到全部完成的情况下，请问下列哪些选项为IO2的设备利用率

• A. 0.55
• B. 0.26
• C. 0.48
• D. 0.5
• E. 0.39

【解】本题最好画图求解，但要注意是抢占式的，所以优先级高的作业可以抢夺优先级低的作业的资源 —— P5优先级最高，不用等待任何资源。如图：

6、有如下一个类似跳表的数据结构：

每层都是已经排好序的链表：

Level 1层的链表所有元素；

Level N层的链表只有Level N-1层的一半的元素；

Level N层的结点指向Level N-1层中相同的结点。

请问查找一个元素的时间复杂度是：

• A. O(logn)
• B. O(n)
• C. O(nlogn)
• D. O(n^2)

【解】其实就是个二分查找的过程。

7、某二叉树的先根遍历序列和后根遍历序列正好相反，则该二叉树具有的特征是

• A. 高度等于其节点数
• B. 任一结点无左孩子
• C. 任一结点无右孩子
• D. 空或只有一个结点

【解】先序遍历是 M-L-R，后序遍历是L-R-M。要使它们正好相反，则任意一个分支结点的左孩子或者右孩子有一个没有（先：M-L ；后：L-M 或者 先：M-R ；后：R-M ），也就成了一条链。

8、 若系统中有五台打印机，有多个进程均需要使用两台，规定每个进程一次仅允许申请一台，则在不发生死锁的情况下至多允许多少个线程参与竞争？

• A. 5
• B. 4
• C. 3
• D. 2

【解】死锁的发生需要具备四个条件：①互斥，②保持和申请，③不剥夺，④环路等待；为了避免发生死锁，不能让它们形成环路，则4个进程是极限了。

9、对某二叉树进行先序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果为

• A. DBFEAC
• B. DFEBCA
• C. BDFECA
• D. BDEFAC

10、Internet的网络层含有的协议是？

• A. IP
• B. ICMP
• C. ARP
• D. RARP

【解】注意，虽然ARP/RARP工作在链路层，但它们是网络层协议。

11、以下是C++的不同数据类型值的比较语句，请问这些判断语句中作为条件部分的语句编写有问题的有

• A. 如果变量bVar为布尔类型：if(false == bVar) { doSomeThing(); }
• B. 如果变量nVar为int型：if(0 == nVar) { doSomeThing(); }
• C. 如果变量fVar为浮点型：if(0.02 == fVar) { doSomeThing(); }
• D. 如果变量sVar为字符串型：if(“” == sVar) { doSomeThing(); }

【解】float有精度问题，尾数不精确，比较会出问题；字符串比较一般用strcmp(str1，str2)，直接用==比较两个字符串，应该比较的是字符串的首地址是否相等，并非比较字符串的内容。

12、Win32系统里，下面几个sizeof的运行结果是

int intValue = 1024;
char str[] = "Tencent";
const char* ch = str;
sizeof(intValue) =   a  ;
sizeof(str) =   b   ;
sizeof(ch) =   c   ;

• A. a=1, b=1, c=1
• B. a=4, b=4, c=4
• C. a=4, b=7, c=4
• D. a=4, b=8, c=4

13、以下涉及到内存管理的代码段中，有错误的是：

• A.

  int *a = new int(12);
  //.....
  free(a);
  

• B.

  int *ip = static_cast<int*>(malloc(sizeof(int)));
  *ip = 10;
  //......
  delete ip;
  

• C.

  double *a = new double[1];
  //......
  delete a;
  

• D.

  int *ip = new int(12);
  for(int i=0;i<12;++i) {
      ip[i] = i;
  }
  delete [] ip;
  

【解】new和delete 配套使用，free和malloc配套使用；D选项中 int *ip = new int(12) 申请的是一个元素，初始值是12 —— 要申请一个指针数组应该用 new int[12]

14、我们常说的mvc框架是指的什么的?

• A.模块(module)-视图(view)-组件(component)
• B.模型(model)-视图(view)-组件(component)
• C.模块(module)-视图(view)-控制器(controller)
• D.模型(model)-视图(view)-控制器(controller)

15、某一速率为100M的交换机有20个端口，其一个端口上连着一台笔记本电脑，此电脑从迅雷上下载一部1G的电影需要的时间可能是多久?

• A.10S
• B.20S
• C.40S
• D.100S
• E.200S

【解】已知交换机每个端口的数据通过率为100Mb/s，即 100/8 = 12.5MB/s，所以最短时间为 1024/12.5 = 81.92s，但这是理论上的极限值，实际上肯定比这个时间长，所以D和E都有可能。

16、下面哪些特性可能导致代码体积膨胀:

• A.宏定义
• B.模板
• C.内联函数
• D.递归

【解】宏定义是单纯的替换，会导致代码膨胀；模板根据不同的类型实参，会生成不同的代码，会导致代码膨胀；内联函数在编译时会将函数体嵌入在每一个调用处，类似于宏定义。

17、TCP连接中主动断开链接netstat观察可能出现的状态流转是：

A. ESTABLISHED->CLOSE_WAIT->TIME_WAIT->CLOSED
B. ESTABLISHED->TIME_WAIT->CLOSE_WAIT->CLOSED
C. ESTABLISHED->FIN_WAIT_1->FIN_WAIT_2->TIME_WAIT->CLOSED
D. ESTABLISHED->FIN_WAIT_1->TIME_WAIT->CLOSED

【解】如果在 FIN_WAIT_1 状态下，收到了对方同时带FIN标志和ACK标志的报文时，可以直接进入到TIME_WAIT状态，而无须经过 FIN_WAIT_2 状态。

18、关于epoll和select的区别，哪些说法是正确的?

• A. epoll和select都是I/O多路复用的技术，都可以实现同时监听多个I/O事件的状态
• B. epoll相比select效率更高，主要是基于其操作系统支持的I/O事件通知机制，而select是基于轮询机制
• C. epoll支持水平触发和边沿触发两种模式
• D. select能并行支持I/O比较小，且无法修改

【解】select在默认情况下，单个进程可监视的最大文件描述符个数为1024。当然，可以通过修改linux的socket内核进行修改。关于select/poll/epoll的区别，请自行查阅资料。

19、客户端C和服务器S之间建立一个TCP连接，该连接总是以1KB的最大段长发送TCP段，客户端C有足够的数据要发送。当拥塞窗口为16KB的时候发生超时，如果接下来的4个RTT往返时间内的TCP段的传输是成功的，那么当第4个RTT时间内发送的所有TCP段都得到了ACK时，拥塞窗口大小是：

• A. 7KB
• B. 8KB
• C. 9KB
• D. 16KB

【解】本题考查的是TCP的拥塞处理，见文《TCP 的那些事儿（下）》。

当拥塞发生（超时）时：

• ① sshthresh = cwnd /2；
• ②cwnd 重置为 1；
• ③进入慢启动过程。

所以阈值变为8KB，拥塞窗口重置为1KB，开始慢启动。
当慢启动时，每过一个RTT时间，cwnd = cwnd*2，呈指数让升：

• 1RTT 结束，1KB- > 2KB
• 2RTT 结束，2KB- > 4KB
• 3RTT 结束，4KB- > 8KB（到达阈值，执行拥塞避免算法）

当拥塞避免开始时，每过一个RTT时间，cwnd = cwnd + 1，线性上升，避免增长过快导致网络拥塞：

• 4RTT 结束，8KB- > 9KB

20、在正方体上任取三个顶点连成三角形，则所得的三角形是直角非等腰三角形的概率为？

• A. 1/14
• B. 4/7
• C. 2/7
• D. 3/7

【解】正方体有8个顶点，三角形总数为C(8, 3)=56个，任意一条边都可以与它对角的两个顶点中的一个组成直角非等腰三角形，故有12*2=24个。概率=24/56=3/7。

21、已知关系R(F,G,H,I,J)及其上的函数相关性集合，F=(F->G,J->F,HJ->I),该关系的候选关键字是：

• A. FJ
• B. HJ
• C. HI
• D. IJ

【解】如果一个超关键字去掉其中任何一个字段后不再能唯一地确定记录，则称它为“候选关键字”（Candidate Key）。候选关键字既能唯一地确定记录，它包含的字段又是最精炼的。—— HJ 能确定关系R的所有属性。

22、在linux编程中，以下哪个TCP的套接字选项与nagle算法的开启和关闭有关?

• A. TCP_MAXSEG
• B. TCP_NODELAY
• C. TCP_SYNCNT
• D. TCP_KEEPALIVE

【解】Nagle算法主要是用来避免大量的小数据包在网络中传输，从而降低网络容量利用率。比如一个20字节的TCP首部+20字节的IP首部+1个字节的数据组成的TCP数据报，有效传输通道利用率只有将近1/40。如果网络充斥着这样的小分组数据，则网络资源的利用率是相当低下的。—— 但是对于一些需要小包场景的程序，比如像telnet或ssh这样的交互性比较强的程序，你需要关闭这个算法。可以在Socket设置TCP_NODELAY选项来关闭这个算法。

23、对于移动平均算法，是计算某变量之前n个数值的算术平均，正确的说法是：

• A.空间复杂度是O(1)
• B.空间复杂度是O(n)
• C.空间复杂度是O(logn)
• D.空间复杂度是O(nlogn)

【解】从前往后每计算一次保留一次求和值到一个临时变量，这样下一个变量进来时，直接用前一次的和+当前数，再取平均。时间复杂度为O(1)，空间复杂度也为O(1)。

24、在动态分区分配方案中，某一作业完成后，系统收回其主存空间，并与相邻空闲区合并，为此需要修改空闲区表，造成空闲区数减1的情况是()

• A.无上邻空闲区，也无下邻空闲区
• B.有上邻空闲区，但无下邻空闲区
• C.有下邻空闲区，但上下邻空闲区
• D.有上邻空闲区，也有下邻空闲区

25、如下代码，result变量的输出结果是多少？

#include
<
iostream
>
using
 namespace std;


int
 i=
1
;

class MyCls{

public
:

MyCls
():

m_nFor
(m_nThd),

m_nSec
(i++),

m_nFir
(i++),

m_nThd
(i++)
    {
        m_nThd=i;
    }


void
 echo()
    {
        cout
<
<
"result:"
<
<
m_nFir+m_nSec+m_nThd+m_nFor
<
<
endl;
    }

private
:

int
 m_nFir;

int
 m_nSec;

int
 m_nThd;

int
&
m_nFor;
};


int
 main()
{
    MyCls oCls;
    oCls.echo();

return
0
;
}

• A. 10
• B. 11
• C. 9
• D. 12
• E. 8

【解】构造函数的初始化列表是运行在构造函数体之前的，还有注意 m_nFor 是 m_nThd 的引用。所以最后result = 4+1+2+4 = 11.

26、请问下列代码的输出结果有可能是哪些？

#include
<
stdio.h
>
#include
<
stdint.h
>
union
 X
{
    int32_t a;

struct

    {
        int16_t b;
        int16_t c;
    };
};


int
 main()
{
    X x;
    x.a=
0x20150810
;

printf
(
"%x,%x\n"
,x.b,x.c);

return
0
;
}

• A. 2015,810
• B. 50810,201
• C. 810,2015
• D. 20150,810

【解】union，即联合体，定义方式与结构体一样，但是二者有本质上区别。

• 在 struct 中各成员有各自的内存空间，一个结构变量的总长度是各成员长度之和（当然还要考虑内存对齐）。
• 在 union 中各成员共享一段内存空间，一个联合变量的长度等于各成员中最长的长度（各成员相对于联合体起始地址的偏移量为0）。

所以上述union X中变量a与struct占用同一块内存区域，由于存在大端序和小端序，所以答案为AC。

27、下面关于ICMP协议的描述中，正确的是()

• A. ICMP协议根据MAC地址查找对应的IP地址
• B. ICMP协议把公网的IP地址转换为私网的IP地址
• C. ICMP协议用于控制数据报传送中的差错情况
• D. ICMP协议集中管理网络中的IP地址分配

【解】ICMP本质上可以理解为带差错报告的IP协议，它与IP协议同属于网络层。

28、数据库设计里，视图(View)可以使得我们为一个或多个数据表定义一个特殊的表现形式，视图在行为上与数据表没啥特别区别，可以使用基本的select,insert,update等命令修改数据，但对于update操作，也有一些限制，下面那些是受限的原因()

• A. 初始View定义的Select语句里如果包含了GROUP BY,DISTINCT,LIMIT或HAVING等命令时
• B. 如果视图里数据来自多张字表时
• C. 如果视图里缺少主键索引，唯一索引，外键约束条件锁涉及的全部数据列时
• D. 当Creat View之后又使用Replace View对已存在视图做了更名操作后

29、C语言里i=5，j=7，请问i|j等于多少？

• A. 1
• B. 3
• C. 5
• D. 7

30、请选择下面代码的输出结果：

int
 main(
int
 argc,
char
*argv[])
{

int
 a=
10
;

int
 b=
4
;

int
 c=a/b;

int
 d=c*a*b++;

std
::
cout
<
<
d
<
<
std
::endl;

return
0
;
}

• A. 60
• B. 80
• C. 100
• D. 125

【解】虽然自增运算符的优先级 比 算数运算符高，但后自增并不影响。

31、下面程序中哪几处有错误？

int
 main()
{

int
 i=
10
;

int
 j=
1
;

const
int
 *p1;
//(1)
int
const
 *p2=
&
i; 
//(2)

    p2=
&
j;
//(3)
int
 *
const
 p3=
&
i;
//(4)

    *p3=
20
;
//(5)

    *p2=
30
;
//(6)

    p3=
&
j;
//(7)
return
0
;
}

• A. 1,2,3,4,5,6,7
• B. 1,3,5,6
• C. 6,7
• D. 3,5

【解】本题主要考察const int *a， int const *a，int * const a之间的区别：前两种写法是等同的，均表示指向一个int常量的指针变量，后一种表示指向一个int变量的指针常量。

32、linux下，指定文件 file1 为所有用户可读，可写，可执行，执行命令：____。修改 file1 的拥有者为test，拥有组为user，执行命令:____。

• A. chmod 776,chown test
• B. chmod 777,chown user
• C. chmod 777,chown test
• D. chmod 778,chown user

33、以下代码输出什么？

int
 main()
{

int
 a[
5
]={
1
,
2
,
3
,
4
,
5
};

int
*p
=(
int
*)
(
&
a+
1
);

printf
(
"
%d
"
,
*(
p-
1
));
}

• A. 1
• B. 2
• C. 5
• D. 出现错误

【解】a是一个数组名，对a取址得到的是一个指向数组的指针，即类型为 int (*)[5]。那么 &a+1 后其偏移量为5*sizeof(int)的大小，故p指向数组的尾地址。又p被强转成int型指针，所以 p-1 相当于 p - sizeof(int)，指向了数组中得最后一个元素。

34、ip地址10.1.8.0/24和10.1.9.0/24，下列哪个是正确的汇总网段：

• A. 10.0.0.0/8
• B. 10.1.0.0/16
• C. 10.1.8.0/23
• D. 10.1.10.0/24

【解】对于 10.1.8.0/24，其中的 10.1.8.0 表示IP或子网，24表示掩码中从高位算起1的位数（24就是掩码有24个1，即255.255.255.0）。将各个选项中的IP与子网掩码按位AND，只有C选项可以包含两个网段。

35、以下代码是否完全正确，执行可能得到的结果是？

class
A
 {
int
 i;
};


class
B
 {
 A 
*p;

public
:
    B() { p = 
new
 A; }
    ~B(){ delete p; }
};


void
 sayHello(B b) {

}


int
 main()
{

 B 
b;
    sayHello(b);
}

• A. 程序正常运行
• B. 程序编译错误
• C. 程序崩溃
• D. 程序死循环

【解】这里的问题是：sayHello(b) 在传参时调用了默认拷贝构造函数，没有进行深度拷贝（仅仅拷贝了p指针的值）；当 sayHello 退出时，临时对象析构而导致p指向的内存被释放；继而退出 main 的时候，又对 b 进行析构，而此时 b 对象内 p 指向的内存已经释放 —— delete两次导致程序崩溃！
解决办法就是自定义拷贝构造函数，进行深度拷贝。

二、编程题

1、 在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code）。请编写一个函数，使用递归方法生成N位的格雷码，并且保证这个函数的健壮性。

【解】首先要知道什么是格雷码，请移步《格雷码-百度百科》。题意是要求指定格雷码的位数，生成整个码表 —— 递归规则如下：

• 1位格雷码有两个码字
• n+1位格雷码的集合 = n位格雷码集合(顺序)加前缀0 + n位格雷码集合(逆序)加前缀1

vector
<
string
>
 getGrayCode(
int
 n) {

vector
<
string
>
 gray;

if
(n 
<
1
) 

return
 gray;

else
if
(n == 
1
) {
        gray.push_back(
"0"
);
        gray.push_back(
"1"
);

return
 gray;
    }

else
 {

vector
<
string
>
 preGray = getGrayCode(n-
1
);

for
(
int
 i=
0
; i
<
preGray.size(); ++i) {     
// 顺序加前缀0

            gray.push_back(
"0"
 + preGray[i]);
        }

for
(
int
 i=preGray.size()-
1
; i
>
=
0
; --i) {  
// 逆序加前缀1

            gray.push_back(
"1"
 + preGray[i]);
        }

return
 gray;
    }
}

2、春节期间小明使用微信收到很多个红包，非常开心。在查看领取红包记录时发现，某个红包金额出现的次数超过了红包总数的一半。请帮小明找到该红包金额。写出具体算法思路和代码实现，要求算法尽可能高效。

【解】本题简单点理解就是：从一个数组中找到出现次数超过一半的那个数。—— 可以用一个map记录每个元素及它出现的次数。

int
 getValue(
vector
<
int
>
 gifts) {

map
<
int
,
int
>
 m;

int
 result = 
0
;

for
(
int
 i=
0
; i
<
gifts.size(); ++i) {
        ++m[gifts[i]];

if
(m[gifts[i]] 
>
 gifts.size()/
2
) {
            result = gifts[i];

break
;
        }
    }

return
 result;
}

3、大整数乘法：输入数据有两行，分别是两个非负整数，最多1000位；输出它们的乘积。

样例输入：
213897129837128937123
43502789523572345

样例输出：
9305121819000846375051201723846663435

【解】本题不需要想太多，只要按照乘法规则一位一位进行运算即可。

string
 multiBigNumber(
string
 num1, 
string
 num2) {
    static 
int
 result[
2048
] = {
0
};

    reverse(num1.begin(), num1.end());
    reverse(num2.begin(), num2.end());


int
 val = 
0
;  
// 临时变量  
for
(
int
 i=
0
; i
<
num1.
size
(); ++i) {

int
 add_up = 
0
;    
// 加法进位
int
 multi_up = 
0
;  
// 乘法进位
for
(
int
 j=
0
; j
<
num2.
size
(); ++j) {
            val = (num1[i]-
48
) * (num2[j]-
48
) + multi_up;
            multi_up = val / 
10
;
            val = val % 
10
;


int
 tmp = result[i+j] + val + add_up;
            add_up = tmp / 
10
;
            result[i+j] = tmp % 
10
;
        }
        result[i+num2.
size
()] += multi_up + add_up;
    }


// 将result逆序并转为字符串
string
 output;

for
(
int
 i=num1.
size
()+num2.
size
()-
2
; i
>
=
0
; --i) {
        output.push_back(result[i]+
48
);
    }

return
 output;
}