前 75 题

题目 1

下列数据结构不是多型数据类型的是（）

堆
栈
字符串
有向图

正确答案

答案：C

多型就是数据元素的类型不确定，字符串的每个元素始终都是字符(char)，而不会是别的类型

题目 2

稀疏矩阵压缩存储后,必会失去随机存取功能()

正确答案及解析

答案：对的

稀疏矩阵在采用压缩存储后将会失去随机存储的功能。因为在这种矩阵中，非零元素的分布是没有规律的，为了压缩存储，就将每一个非零元素的值和它所在的行、列号做为一个结点存放在一起，这样的结点组成的线性表中叫三元组表，它已不是简单的向量，所以无法用下标直接存取矩阵中的元素。

题目 3

某二叉树的前序遍历序列为-+a*b-cd/ef，后序遍历序列为abcd-*+ef/-，问其中序遍历序列是()。

正确答案及解析

答案：a+b*c-d-e/f

可以根据后缀表达式求出中缀表达式，中缀表达式是直观的表达式。

这里要注意理解，不能理解为树只给前序遍历和后序遍历就无法确定树的结构。

题目 4

一棵3阶B-树中含有2047个关键字,包含叶结点层,该树的最大深度为()

正确答案及解析

答案：12

M阶B-树中含有N个关键字，最大深度为

题目 5

设某种二叉树有如下特点：每个结点要么是叶子结点，要么有2棵子树。假如一棵这样的二叉树中有m（m>0）个叶子结点，那么该二叉树上的结点总数为（）。

2m+1
2m-1
2(m-1)
2m

正确答案及解析

答案：B

出度为0的结点为m

出度为2的结点 = 出度为0的结点 - 1 = m - 1

题目中说：每个结点要么是叶子结点，要么有2棵子树

所以没有出度为1的结点

总结点数为：2m - 1

题目 6

若用数组S[0. .n-1]做为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（）。

S1的栈底位置为0，S2的栈底位置为n-1
S1的栈底位置为0，S2的栈底位置为n/2
S1的栈底位置为1，S2的栈底位置为n/2

正确答案及解析

答案：A

题目 7

下面关于二分查找的叙述中正确的是：

表必须有序,表可以顺序方式存储,也可以链表方式存储
表必须有序且表中数据必须是整型,实型或字符型
表必须有序,而且只能从小到大排列
表必须有序,且表只能以顺序方式存储

正确答案及解析

答案：D

折半查找方法适用于不经常变动而查找频繁的有序列表。

它的算法要求是必须是顺序存储结构，必须有序排列

题目 8

假设某段通信电文仅由 6 个字母 ABCDEF 组成，字母在电文中出现的频率分别为2，3，7，15，4，6。根据这些频率作为权值构造哈夫曼编码，最终构造出的哈夫曼树带权路径长度与字母 B 的哈夫曼编码分别为______。(这里假定左节点的值小于右节点的值)

正确答案及解析

答案：86、1011

长度计算为 （2+3）*4+（4+6+7）*3+15*1=86

题目 9

一个长度为99的循环链表，指针A和指针B都指向了链表中的同一个节点，A以步长为1向前移动，B以步长为3向前移动，一共需要同时移动多少步A和B才能再次指向同一个节点____。

正确答案及解析

答案：99

设需要走x步A、B才能重新相遇，那么x%99 = (3x)%99;

令x%99 = r,则可得x = 99k1 + r, 3x = 99k2 + r，整理两个式子可得 x = 99 * (k2 - k1)/2，因为均为正整数，所以x最小为99

题目 10

有一个数组（53,83,18,59,38,35），依次将其存储在hash表中，其中哈希函数为h(k)=k%7,如采用线性探测（每次向后查找1位）的方式解决冲突，则该hash表上查找38,35,53访问hash表的表项次数分别为 ?, ?, ?。

正确答案及解析

5, 2, 1

表的顺序:

索引值	表项
0	38
1	35
2
3	59
4	53
5	18
6	83

附带求模结果：

53 % 7 = 4, 83 % 7 = 6, 18 % 7 = 4

59 % 7 = 3, 38 % 7 = 3, 35 % 7 = 0

题目 11

对于某个函数调用，可以不给出被调用函数的原形的情况是（）。

被调用函数式无参函数
被调用函数式无返回值的函数
函数的定义在调用处之前
函数的定义在别的程序文件中

正确答案及解析

如果被调用函数的定义出现在主调函数之前，可以不必加以声明。因为编译系统已经事先知道了已定义的函数类型，会根据函数首部提供的信息对函数的调用作正确性检查。

题目 12

To speed up data access , we build cache system. In one system , The L1 cache access time is 5 ns , the L2 cache access time is 50 ns and the memory access time is 400 ns. The L1 cache miss rate is 50% , the L2 cache miss rate is 10%. The average data access time of this system is:

正确答案及解析

0.5*5+0.5*0.9*（50+5）+0.5*0.1*（400+50+5）=50

题目 13

某二叉树结点的中序序列为BDAECF,后序序列为DBEFCA,则该二叉树对应的森林包括()棵树

正确答案及解析

答案：3

构建后的二叉树的右下节点都是由对应的森林里不同的树相连而成的，可以想象二叉往树右侧的先序遍历依次经过A-C-F到达树的底端，这三个结点在对应的森林中都必定分属不同的树。所以一共有三棵树。

题目 14

某表达式的前缀形式为"+-*^ABCD/E/F+GH",它的中缀形式为()

A^B*C-D+E/F/G+H
A^B*(C-D)+(E/F)/G+H
A^B*C-D+E/(F/(G+H))
A^B*(C-D)+E/(F/(G+H))

正确答案及解析

答案：C

前缀表达式的计算机求值特点：从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 op 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果。

根据从右至左扫描计算过程如下:
题目中的前缀形式为：+-*^ABCD/E/F+GH
1) 首先扫描 H,是数字 入栈 ，栈中为: H
2) 扫描 G 为数字 入栈 ,栈中为:G,H
3)扫描+ 为运算符 ,依次弹出G ,H ,得到 G+H 的结果 入栈，栈中为： G+H(在这里方便讲解 标记为  G+H)
4)扫描 F 为数字 ,入栈 ，栈中为  F, G+H
5)扫描 / 为运算符, 依次弹出 F,G+H ，计算F/(G+H) 的结果入栈 ，栈中为 F/(G+H)
6)扫描 E 为数字,入栈，栈中为 E,  F/(G+H)
7) 扫描 / 为运算符, 依次弹出E, F/(G+H) ，计算 E/(F/(G+H))
8)扫描 D 为数字,入栈 栈中为:D, E/(F/(G+H))
9) 扫描 C 为数字,入栈 栈中为:C,D, E/(F/(G+H))
10) 扫描 B 为数字,入栈 栈中为:B,C,D, E/(F/(G+H))
11) 扫描 A 为数字,入栈 栈中为:A,B,C,D, E/(F/(G+H))
12) 扫描^ 为数字,依次弹出 A,B 计算 A^B的结果入栈, 栈中为：A^B ,C,D, E/(F/(G+H))
13) 扫描*为数字,依次弹出 A^B,C 计算 A^B*C的结果入栈, 栈中为：A^B* C,D, E/(F/(G+H))
14) 扫描-为数字,依次弹出 A^B*C,D 计算 A^B*C-D的结果入栈, 栈中为：A^B* C-D, E/(F/(G+H))
15) 扫描+为数字,依次弹出 A^B*C-D, E/(F/(G+H))   计算 A^B*C-D+  E/(F/(G+H)) 的到结果
最后得到的表达式为：  A^B* C-D+ E/(F/(G+H))

题目 15

下面有关 ibatis 中的#与$的区别，描述错误的是？

#将传入的数据都当成一个字符串，会对自动传入的数据加一个双引号
$ 方式能够很大程度防止 sql 注入。
$ 方式一般用于传入数据库对象，例如传入表名
$ 将传入的数据直接显示生成在 sql 中

正确答案及解析

答案：B

1. # 是把传入的数据当作字符串，如#user_id_list#传入的是1,2,则sql语句生成是这样，in ('1,2') ,
2. $ 传入的数据直接生成在sql里，如$user_id_list$传入的是1,2,则sql语句生成是这样，in(1,2)． 
3. # 方式能够很大程度防止sql注入． 
4. $ 方式无法方式sql注入． 
5. $ 方式一般用于传入数据库对象．例如传入表名. 
6. 一般能用#的就别用$.

举例：
#str# 出来的效果是  'str' 
$str$ 出来的效果是   str

题目 16

下面关于B和B+树的描述中，不正确的是()

B树和B+树都是平衡的多叉树
B树和B+树都可用于文件的索引结构
B树和B+树都能有效的支持顺序检索
B树和B+树都能有效的支持随机检索

正确答案及解析

答案：C

B树只适用于随机检索，不适用于顺序检索；而B+树把所有关键码都存在叶结点上，这就为顺序检索也提供了方便。

B 树和 B+ 树用于组织文件的动态索引结构。
B 树和 B+ 树都是平衡的多分支树。
B 树只适用于随机检索, 不适用于顺序检索, 而 B+ 树适用于顺序检索和随机检索

题目 17

求解最短路径的Floyd算法的时间复杂度为()

O(n)
O(n+c)
O(n*n)
O(n*n*n)

正确答案及解析

答案：D

int n;//n为节点个数
for(int i=0; i<n; ++i )
{
    for (int j=0; j<n; ++j )
    {
        for ( int k=0; k<n; ++k )
        {
            if ( Dis[i][k] + Dis[k][j] < Dis[i][j] )
            {
                // 找到更短路径
                Dis[i][j] = Dis[i][k] + Dis[k][j];
            }
        }
    }
}

题目 18

关于进程和线程，下列说法正确的是___

线程是资源分配和拥有的单位
线程和进程都可并发执行
在 linux 系统中，线程是处理器调度的基本单位
线程的粒度小于进程，通常多线程比多进程并发性更高
不同的线程共享相同的栈空间

正确答案及解析

答案：BCD

A：进程是资源分配和拥有的单位
C：线程是处理机调度和分配的单位
B：进程之间可以并发执行，同一个进程的多个线程之间也可并发执行
E：每个线程拥有自己的堆栈，和自己的寄存器上下文

题目 19

每个进程在操作系统中用进程控制块（process control block，PCB）来表示，请找出以下不属于进程控制块中的信息______。

进程PID
进程优先级
进程间通信方式
进程的执行时间

正确答案及解析

答案：D

通常 PCB 应包含如下一些信息：

进程标识符 name
进程当前状态 status
进程相应的程序和数据地址，以便把 PCB 与其程序和数据联系起来
进程资源清单。列出所拥有的除 CPU 外的资源记录
进程优先级 priority
CPU 现场保护区 cpustatus
进程同步与通信机制, 用于实现进程间互斥、同步和通信所需的信号量等
进程所在队列 PCB 的链接字
与进程有关的其他信息, 如进程记账信息, 进程占用 CPU 的时间等

题目 20

设计实时操作系统时，首先应该考虑系统的优良性和分配性。

正确答案及解析

答案：错的

设计实时操作系统时，首先应该考虑系统的实时性和可靠性。

题目 21

Inter-process communication (IPC) is the transfer of data among processes. Which of the following is NOT a typical programming technique for IPC?

mutex
pipe
socket
message queue

正确答案及解析

答案：A

题目问哪一个不是进程间通信的方式。其中进程间通信的方式有管道（pipe）、共享存储器系统、消息传递系统（message queue）以及信号量。而mutex是互斥锁，在锁机制中通过原语保证资源状态的检查和修改作为一个整体来执行，以保证共享数据操作的完整性，并不能在两个进程间传递消息。网络上的两个程序通过一个双向的通信连接实现数据的交换，这个连接的一端称为一个socket，也就是说socket也是两个进程间的通信方式。

题目 22

TCP 协议中的 ESTABLEISHED 状态是什么状况？

服务器端处于监听状态
服务器接受 SYN 报文，建立 TCP 连接时的三次握手会话过程中的一个中间状态
连接已经建立状态
初始状态

正确答案及解析

答案：C

CLOSED: 表示初始状态。
LISTEN: 表示服务器端的某个 SOCKET 处于监听状态，可以接受连接。
SYN_RCVD: 这个状态表示接受到了SYN报文，在正常情况下，这个状态是服务器端的SOCKET在建立TCP连接时的三次握手会话过程中的一个中间状态，很短暂，基本上用 netstat 你是很难看到这种状态的，除非你特意写了一个客户端测试程序，故意将三次 TCP 握手过程中最后一个 ACK 报文不予发送。因此这种状态时，当收到客户端的 ACK 报文后，它会进入到 ESTABLISHED 状态。
SYN_SENT: 这个状态与 SYN_RCVD 遥相呼应，当客户端 SOCKET 执行 CONNECT 连接时，它首先发送 SYN 报文，因此也随即它会进入到了 SYN_SENT 状态，并等待服务端的发送三次握手中的第2个报文。SYN_SENT 状态表示客户端已发送SYN报文。
ESTABLISHED：表示连接已经建立。
FIN_WAIT_1: FIN_WAIT_1 和 FIN_WAIT_2 状态的真正含义都是表示等待对方的 FIN 报文。而这两种状态的区别是：FIN_WAIT_1 状态实际上是当 SOCKET 在 ESTABLISHED 状态时，它想主动关闭连接，向对方发送了 FIN 报文，此时该 SOCKET 即进入到 FIN_WAIT_1 状态。而当对方回应 ACK 报文后，则进入到 FIN_WAIT_2 状态，当然在实际的正常情况下，无论对方何种情况下，都应该马上回应 ACK 报文，所以 FIN_WAIT_1 状态一般是比较难见到的，而 FIN_WAIT_2 状态还有时常常可以用netstat看到。
FIN_WAIT_2：FIN_WAIT_2 状态下的 SOCKET，表示半连接，也即有一方要求 close 连接，但另外还告诉对方，还有数据需要传送，稍后再关闭连接。
TIME_WAIT: 表示收到了对方的 FIN 报文，并发送出了 ACK 报文，就等 2MSL 后即可回到 CLOSED 可用状态了。如果 FIN_WAIT_1 状态下，收到了对方同时带 FIN 标志和 ACK 标志的报文时，可以直接进入到 TIME_WAIT 状态，而无须经过 FIN_WAIT_2 状态。
CLOSING: 属于一种比较罕见的例外状态。正常情况下，当你发送 FIN 报文后，按理来说是应该先收到（或同时收到）对方的 ACK 报文，再收到对方的 FIN 报文。但是 CLOSING 状态表示你发送 FIN 报文后，并没有收到对方的 ACK 报文，反而却也收到了对方的 FIN 报文。
CLOSE_WAIT: 这种状态的含义表示在等待关闭。当对方 close 一个 SOCKET 后发送 FIN 报文，你系统毫无疑问地会回应一个 ACK 报文给对方，此时则进入到 CLOSE_WAIT 状态。
LAST_ACK: 它是被动关闭一方在发送 FIN 报文后，最后等待对方的 ACK 报文。当收到 ACK 报文后，也即可以进入到 CLOSED 可用状态了。

题目 23

在下列存储形式中,哪一个不是树的存储形式?()

双亲表示法
孩子链表表示法
孩子兄弟表示法
顺序存储表示法

正确答案及解析

答案：D

二叉树可以，不过要补充很多 ##### 这个东东，很浪费空间，二叉树已经很浪费了，如果是 N 叉树呢......所以 D 不行

双亲表示法

以一组连续的空间存储数的节点，同时在每个元素中，附带一个用于指示其双亲节点在数组中的下标的指示器。

孩子表示法

与双亲表示法相反，每个节点在保存数据的同时记录了其左右孩子的下标

孩子兄弟表示法

在存储结点信息的同时，附加两个分别指向该结点最左孩子和右邻兄弟的指针域leftmostchild和rightsibling，即可得树的孩子兄弟链表表示

题目 24

中断响应时间是指（）。

从中断处理开始到中断处理结束所用的时间
从发出中断请求到中断处理结束所用的时间
从发出中断请求到进进中断处理所用的时间
从中断处理结束到再次中断请求的时间

正确答案及解析

答案：C

题目 25

IP 地址中网络号的作用有哪些？

指定了主机所属的网络
指定了网络上主机的标识
指定了设备能够进行通信的网络
指定被寻址的网中的某个节点

正确答案及解析

答案：A

网络号代表主机所在的网络区域所以 A 对

但是有网络号并不能确定到某一台机器上，所以不是一个节点，是一片区域所以BD错,也并不是指能够通信的网络，要能够通信要达到很多条件才行。

题目 26

下面哪种内存管理方法有利于程序的动态链接？（）

分段存储管理
分页存储管理
可变分区分配
固定分区分配

正确答案及解析

答案：A

动态链接是指在作业运行之前，并不把几个目标程序段链接起来。要运行时，先将主程序所对应的目标程序装入内存并启动运行，当运行过程中又需要调用某段时，才将该段(目标程序)调入内存并进行链接。可见，动态链接也要求以段作为管理的单位。

题目 27

下列有关图的遍历说法中，不正确的是

有向图和无向图都可以进行遍历操作
基本遍历算法两种：深度遍历和广度遍历
图的遍历必须用递归实现
图的遍历算法可以执行在有回路的图中

正确答案及解析

答案：C

图的遍历分为递归和非递归实现，即为深度遍历和广度遍历

其实所有的递归都可以变成非递归，通过使用栈来实现。

题目 28

下面有关多核CPU和单核CPU的描述，说法错误的是？

双核2.4GHZ，那么其中每单个核心的频率也是2.4GHZ
多核CPU功耗低，体积小
多核cpu共用一组内存，数据共享
所有程序在多核CPU上运行速度都快

正确答案及解析

答案：D

多核cpu的主要优势在于处理多任务，处理多任务时性能才能充分发挥出来
如果程序是单进程单线程的，多核cpu的处理速度核单核cpu的处理速度理论上是相同的
在多核cpu上为了充分利用其性能，程序最好采用多进程多线程异步非阻塞的方式运行

题目 29

一台主机要实现通过局域网与另一个局域网通信，需要做的工作是？

配置域名服务器
定义一条本机指向所在网络的路由
定义一条本机指向所在网络网关的路由
定义一条本机指向目标网络网关的路由

正确答案及解析

答案：D

如果主机想访问本地局域网外的某一网络，需要做两件事：

1、设置本机的默认网关 。
2、本地局域网默认网关上需要设置一条路由，用以完成本地局域网内的任一主机到目标局域网主机的路由工作。

题目 30

三个程序a,b,c,它们使用同一个设备进行I/O操作，并按a,b,c的优先级执行(a优先级最高，c最低).这三个程序的计算和I/O时间如下图所示。假设调度的时间可忽略。则在单道程序环境和多道程序环境下(假设内存中可同时装入这三个程序，系统采用不可抢占的调度策略).运行总时间分别为()

计算 I/O 计算

a 30 40 10

b 60 30 10

c 20 40 20

正确答案及解析

260， 180

单道时运行时间为 80+100+80=260

黄色是计算时间，绿色是 I/O 输出时间，多道程序环境下运行时间如图所示为30+40+10+20+80=180

题目 31

下面关于求关键路径的说法不正确的是()

一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
求关键路径是以拓扑排序为基础的
一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
关键活动一定位于关键路径上

正确答案及解析

答案：A

节点代表事件, 边代表活动
边, 都是从左 -> 右, 即 a3 对应的是 <B, D>, B -> D 这个方向

该 AOE 网络的源点为 A, 汇点为 F

事件 D 的最早发生时间：从源点 A 开始到达 D 的所有路径加和的最大值 max{<a1,a3>,<a2,a5>} = 6

事件 D 的最迟发生时间：

首先求出汇点 F 的最早发生时间:
max{<a1,a4,a8>,<a1,a3,a7>,<a2,a5,a7>,<a2,a6>} = 8
汇点 F 的最早发生时间 - max{汇点逆向到事件 D 的路径累加之和} = 
8 - max{<a7>} = 5

活动 a3 <B,D>
- 最早发生时间:
  以 a3 该活动为出发点的事件 B ---a3---> D, 即 B 事件的最早发生时间；
- 最迟发生时间：
  以 a3 该活动对应的箭头所指向的事件的最迟发生时间 - a3 活动持续时间 B---a3--->D, 即, D 事件的最迟发生时间 - a3 活动的持续时间
  = 5 - 2 = 3

综上所述，
最早发生时间，事件=活动，是从前往后计算
最迟发生时间，都是从后往前计算，
事件最迟发生时间与汇点和路径累加有关，
事件的时间计算要先于活动的时间计算
活动最迟发生时间与活动持续时间有关

题目 32

若某线性表最常用得操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用哪种存储方式最节省时间？

顺序表
双链表
带头结点的双循环链表
单循环链表

正确答案及解析

答案：A

线性表最常用得操作是存取任一指定序号的元素和在最后进行插入和删除运算；

进行任意位置存取，这个最省时省力的就是数组了，也就是顺序表。

而且元素是在最后的位置进行插入和删除运算，也就不涉及其他元素进行位移的额外操作，最多涉及的就是去扩展空间了。

所以答案选择 A 顺序表

题目 33

已知一棵二叉树，如果先序遍历的节点顺序是：ADCEFGHB，中序遍历是：CDFEGHAB，则后序遍历结果为：（）

正确答案及解析

CFHGEDBA

题目 34

设有数组A[i,j],数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5,8]的存储首地址为()。

正确答案及解析

答案：BA + 180

注意是列为主, ((7 * 8 + 5) - 1) * 3 = 180

题目 35

对进程和线程的描述，一下哪个是正确的？

父进程的所有线程共享相同的地址空间，父进程的所有子进程共享相同的地址空间
改变进程里面主线程的状态会影响其他线程的行为，改变父进程的状态不会影响其他子进程
多线程会引发死锁，而多进程不会
以上都不对

正确答案及解析

答案：D

A 错, 进程拥有独立的地址空间
B 错, 主线程和子线程是并行关系的时候, 并没有依赖关系. 父进程和子进程中, 子进程是父进程的一个副本, 创建子进程后, 子进程会有自己的空间, 然后把父进程的数据拷贝到子进程的空间里. 运行时, 谁先运行是不确定的, 这由系统决定
C 错, 多线程和多进程都会引起死锁, 一般说的死锁指的是进程间的死锁

进程和线程的主要差别在于它们是不同的操作系统资源管理方式。进程有独立的地址空间，一个进程崩溃后，在保护模式下不会对其它进程产生影响，而线程只是一个进程中的不同执行路径。线程有自己的堆栈和局部变量，但线程之间没有单独的地址空间，一个线程死掉就等于整个进程死掉，所以多进程的程序要比多线程的程序健壮，但在进程切换时，耗费资源较大，效率要差一些。但对于一些要求同时进行并且又要共享某些变量的并发操作，只能用线程，不能用进程。

题目 36

下述有关hash冲突时候的解决方法的说法，错误的有？

通常有两类方法处理冲突：开放定址(Open Addressing)法和拉链(Chaining)法。
开放定址更适合于造表前无法确定表长的情况
在用拉链法构造的散列表中，删除结点的操作易于实现
拉链法的缺点是：指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间

正确答案及解析

答案：B

由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况

题目 37

如果关系模式R=(A,B,C,D,E)中的函数依赖集F={A→B,B→C,CE→D},这是第几范式？

正确答案及解析

答案：第一范式

F={A→B,B→C,CE→D}，主键为(A,E)，非主属性B,C却并不是完全依赖于码(A,E)，只依赖于主键的部分属性 A，因此不符合2NF, 只1NF。

* 第一范式（ 1NF ）：属性不可分；
* 第二范式（2NF）：符合 1NF，并且，非主属性完全依赖于主键，而不是依赖于部分主键属性；
* 第三范式（3NF）：符合 2NF，并且，消除传递依赖；
* BC 范式（BCNF）：符合 3NF，并且，主属性不依赖于主属性（若一个关系达到了第三范式，并且它只有一个候选码，或者它的每个候选码都是单属性，则该关系自然达到 BC 范式）；
* 第四范式：要求把同一表内的多对多关系删除；
* 第五范式：从最终结构重新建立原始结构。

题目 38

完全二叉树共有700结点，该二叉树有多少个叶子结点？

正确答案及解析

答案：350

因为 12/2 等于 6, 等于父节点值, 所以是最后一个带子节点的, 拿总数减去 6, 即为叶子节点数, 同理, 所以 700 作为最后一个节点, 他的父节点是 350, 所以序号 350 是最后一个非叶子节点, 以下的都没有子节点, 700 -350 = 350 所以答案选 B

题目 39

下面 Transact-SQL 语句中可以用于创建主键的是（）

alter table table1 with notcheck add constraint [PK_table1] primary key nonclustered (column1) on primary;
alter table table1 column1 primary key;
alter table table1 column1;
create table table1 (column1 char(13) not null primary,column2 int not) on primary;

正确答案及解析

答案：A

表中删除主键为：
alter table table_test drop primary key;
表中增加主键为：
alter table table_test add primary key(id);

题目 40

字符串 www.qq.com 所有非空子串（两个子串如果内容相同则只算一个）个数是（）

正确答案及解析

答案：50

要求的是子串, 从左到右一次截取, 10 个字符的子串, 1 个;

9 个字符的子串, 2个;

8, 3个;

7, 4 个;

.........

1, 10 个

共有: 1 + 2 + 3 + ... + 10 = 10 * (10 + 1) / 2 = 55

减去重复的: 1 个字符时有 3 个 w, 2 个 q, 2 个 ., 2 个字符时有 2 个 ww, 故应减去:(2+1+1+1)=5

答案: 55-5=50

题目 41

从浏览器打开 http://www.nowcoder.com, TCP/IP 协议族中不会被使用到的协议是()

SMTP
HTTP
TCP
IP

正确答案及解析

答案：A

题目 42

一进程刚获得3个主存块的使用权，若该进程访问页面的次序是{1,2,3,4,1,2,5,1,2,3,4,5}。当采用先进先出调度算法时，发生缺页次数是()次

正确答案及解析

答案：9

1被访问，第1次缺页，队列为1
2被访问，第2次缺页，队列为1,2
3被访问，第3次缺页，队列为1,2,3
4被访问，第4次缺页，队列为2,3,4。1出队列，4入队列。
1被访问，第5次缺页，队列为3,4,1。2出队列，1入队列。
2被访问，第6次缺页，队列为4,1,2。3出队列，2入队列。
5被访问，第7次缺页，队列为1,2,5。4出队列，5入队列。
1被访问，此时不缺页，队列不变，即队列为1,2,5。
2被访问，此时不缺页，队列不变，即队列为1,2,5。
3 被访问，第8次缺页，队列为 2,5,3。1出队列，3入队列。
4 被访问，第9次缺页，队列为 5,3,4。2出队列，4入队列。
5被访问，此时不缺页，队列不变，即队列为5,3,4。
所以共9次缺页。

题目 42

以下对 CSMA/CD 描述正确的是？

在数据发送前对网络是否空闲进行检测
在数据发送时对网络是否空闲进行检测
在数据发送时对发送数据进行冲突检测
发生碰撞后 MAC 地址小的主机拥有发送优先权

正确答案及解析

答案：AC

CSMA/CD 协议即带冲突检测的载波监听多路访问协议。

A，发送前空闲检测，只有信道空闲才发送数据
B，发送时当前信号占据信道，信道必定不为空闲，检测空闲没意义
C，发送过程中冲突检测，如果发生冲突，立即停止发送，随机避让。
D，冲突发送后，两个发送端都随机避让一段时间，避让的时间是随机的，优先级相等，没有哪个优先权高的说法。

题目 43

内存管理中的 LRU 方法是用来管理什么的？

虚拟内存的分配
虚拟内存的释放
物理内存的分配
物理内存的释放

正确答案及解析

答案：AD

页面调入：是给页面调入内存中，给它分配物理内存。
页面置换，就是将内存中的页面置换出来，放到虚拟内存中，让物理内存空闲出来，让给需要使用的页面。
LRU：全称是：Least Recently Used（最近最久未使用）置换算法，所以这个算法涉及到了虚拟内存的分配和物理内存的释放。所以答案是 AD。

题目 44

http, telnet, ftp的端口是 ?, ?, ?(FTP写最常用的那一个端口就好)

正确答案及解析

80, 23, 21

FTP 端口号有两个 20 和 21, 一个为控制端口, 一个为数据端口

题目 45

VLAN的主要作用有？

保证网络安全
抑制广播风暴
简化网络管理
提高网络设计灵活性

正确答案及解析

答案：B

VLAN（virtual local area network）虚拟局域网，把大的局域网划分为几个单独的互不相通的虚拟局域网，隔离广播风暴。

题目 46

在公有派生情况下，有关派生类对象和基类对象的关系，下列叙述不正确的是( )

派生类的对象可以赋给基类的对象
派生类的对象可以初始化基类的引用
派生类的对象可以直接访问基类中的成员
派生类的对象的地址可以赋给指向基类的指针

正确答案及解析

答案：C

A，B 和 D 说法是相同的，都是说可以用派生类对象初试化基类对象或者指针，是正确的

C，派生类对象只有在基类成员未被派生类覆盖的情况下才能访问基类中的成员

题目 47

国标规定交换机中具备CID功能的用户电路的配置比例暂定为

5％～10％
10％～20％
10％～30％
10％～40％

正确答案及解析

答案：C

题目 48

一棵非空的二叉树的前序序列和后序序列正好相反,则该二叉树一定满足()

其中任意一个结点均无左孩子
其中任意一个结点均无右孩子
其中只有一个叶结点
其中度为2的结点最多为一个

正确答案及解析

答案：C

一棵非空的二叉树的前序序列和后序序列正好相反,则该二叉树一定满足只有左子树或只有右子树。

A,B 明显不对，举最简单的例子，1为根节点，2分别为1的左右孩子，都满足前序序列和后序序列正好相反。

D 不可能出现一个度为2的节点。

题目 49

判断一个单向链表中是否存在环的最佳方法是（）

两重遍历
快慢指针
路径记录
哈希表辅助

正确答案及解析

答案：B

让快慢指针都从链表表头开始，快指针一次向前移动连个位置，慢指针每次向前移动一个位置。如果快指针到达了NULL，说明不存在环，但如果快指针追上了慢指针，说明存在环。

题目 50

把逻辑地址转变为内存的物理地址的过程称作（）。

编译
连接
运行
重定位或地址映射

正确答案及解析

答案：D

重定位对应的也是虚拟内存的地址，不是真正的物理地址

题目 51

对于IP地址130.63.160.2，MASK为255.255.255.0，子网号为（）

160.2
160
63.160
130.63.160

正确答案及解析

答案：B

130.63.160.2是B类IP地址

B类IP地址前16位（两个字节）为网络号，后16位是主机号

划分子网就是将主机号中的一部分拿出来当做子网号

这里子网掩码为255.255.255.0也就是把前三个字节当成了网络号

与B类IP默认的前两个字节作为网络号相比，第三个字节就是子网号，就是160

所以这个ip的网络号是130.63 子网号是 160 主机号是2

题目 52

关于进程的正确说法是()。

进程就是程序，或者说进程是程序的另一叫法
一个被创建了的进程，在它被消灭之前，处于进程的三种基本状态之一
多个不同的进程不可以包含相同的程序
一个处于等待队列中的进程，即使进入其他状态，仍然放在等待队列中

正确答案及解析

答案：B

进程的三种基本状态包括有就绪状态，执行状态，阻塞状态。

多个不同的进程可以包含相同的程序段，

题目 53

下列关于网络编程错误的是______。

UDP 是不可靠服务
主动关闭的一端会出现 TIME_WAIT 状态
服务端编程会调用 listen(),客户端也可以调用 bind()
TCP 建立和关闭连接都只需要三次握手
Linux 通过提供提供 socket 接口来进行网络编程
长连接相对短连接可以节省建立连接的时间

正确答案及解析

答案：D

TCP建立连接3次握手,断开链接需要4次

题目 54

单链表的每个结点中包括一个指针link，它指向该结点的后继结点。现要将指针q指向的新结点插入到指针p指向的单链表结点之后，下面的操作系列中哪一个是正确的？

q=p->link;p->link=q->link
p=p->link=q->link;p->link
q->link=p->link;p->link=q;
p->link=1;q->link=p->link

正确答案及解析

答案：C

首先应该让新结点q的link指向p的link也就是q->link = p->link;

然后再让p的link指向q即可.也就是p->link = p;

题目 55

有n(n>0)个分支结点的满二叉树的深度是()

正确答案及解析

答案：log2(n+1)+1

假设树有K层，所有的分枝节点都在 1 - (k - 1) 层，每层都是满的，对有 1 - (k - 1) 层，有 2^(k-1)-1=n 变形后得：k=log(n+1)+1。

题目 56

有订单表orders，包含字段用户信息userid，字段产品信息productid，以下语句能够返回至少被订购过两会的productid？

select productid from orders where count（productid）>1
select productid from orders where max（productid）>1
select productid from orders where having count（productid）>1 group by productid
select productid from orders group by productid having count（productid）>1

正确答案及解析

答案：D

顺序为：select, from, where, group by, having, order by, limit

题目 57

银行家算法中的数据结构包括有可利用资源向量Available、最大需求矩阵Max、分配矩阵Allocation、需求矩阵Need，下列选项中表述正确的是（）。

Allocation[i,j]=Max[i,j] +Need[i,j]
Need[i,j]= Max[i,j]- Allocation[i,j]
Max[i,j]= Allocation[i,j]*Need[i,j]
Need[i,j]= Max[i,j]+Allocation[i,j]

正确答案及解析

答案：B

题目 58

进行数据库提交操作时使用事务（Transaction）是为了?

提高效率
保证数据一致性
网络安全
归档数据文件

正确答案及解析

答案：B

数据库事务(Database Transaction) ，是指作为单个逻辑工作单元执行的一系列操作。事务处理可以确保除非事务性单元内的所有操作都成功完成，否则不会永久更新面向数据的资源。通过将一组相关操作组合为一个要么全部成功要么全部失败的单元，可以简化错误恢复并使应用程序更加可靠。一个逻辑工作单元要成为事务，必须满足所谓的ACID(原子性、一致性、隔离性和持久性)属性。

题目 59

以下代码的输出结果是?

#define a 10

void foo(); 
main(){

  printf("%d..",a);
   foo();
   printf("%d",a);
}
void foo(){
   #undef a
   #define a 50
}

正确答案及解析

答案：10..10

宏定义是在编译器预处理阶段中就进行替换了，替换成什么只与define和undefine的位置有关系，与它们在哪个函数中无关。

以本题为例：#define a 10 到 #undef

a之间的代码在预处理阶段就将a全部换为10，#define a 50后面的代码会将a替换为50。

如果没有#define a 50后面再使用a，编译器就会报错了。

题目 60

采用可重定位分区分配方式，（）。

使用户程序占用若干不连续的内存空间
解决了碎片问题
为用户编写程序提供方便
扩充了内存容量，提供了虚拟存储器

正确答案及解析

答案：B

可重定位分区分配方式也是属于连续分配方式的，只是它在内存碎片很多而导致的程序不能放入内存时，进行“紧凑”（可能会移动原来的数据的，所以此时就需要重定位啦~紧凑完了，就能放进去啦~~），所以A是不对的哦

题目 61

mysql数据库有选课表 learn(student_id int,course_id int),字段分别表示学号和课程编号，现在想获取每个学生所选课程的个数信息，请问如下的sql语句正确的是

select student_id,sum(course_id)from learn
select student_id,count(course_id)from learn group by student_id
select student_id,count(course_id)from learn
select student_id,sum(course_id)from learn group by student_id

正确答案及解析

答案：B

group by student_id 是按学生号分组，每个编号的学生可能有多门课程，但不可能课程编号会重复，所以直接使用 count(course_id)，否则就要使用 count(disctinct(course_id))

题目 62

若度为m的哈夫曼树中,其叶结点个数为n,则非叶结点的个数为()

正确答案及解析

答案：[(n-1)/(m-1)]

首先说明一点,我们平时一般所说的哈夫曼树是指最优二叉树,也叫做严格二叉树（注意不是完全二叉树）,但是哈夫曼树完全不局限于二叉树,也存在于多叉树中,即度为m的哈夫曼树,也叫最优m叉树,严格m叉树（注意不是完全m叉树）

这题表示哈夫曼树的节点的度要么是0要么是m

设度不为0（即非叶结点）的个数为X

则总的结点数为：X+n

除根结点外，其余的每一个结点都有一个分支连向一个结点，对于度为m的每个结点都有m个分支，而度为0的结点是没有分支的，所以从分支的情况来看

总的结点数位：X*m + 1（这里的1为根结点）

两者相等，所以答案是（n-1) / （m-1）

题目 63

计算斐波那契数列第n项的函数定义如下：

正确答案及解析

答案：D

若C(n) 表示计算次数，则 
C(0) = 1; 
C(1) = 1; 
C(n) = C(n-1) + C(n-2) + 1; n>=2; 

故： 
C(0) = 1; 
C(1) = 1; 
C(2) = 1 + 1 + 1 = 3; 
C(3) = 3 + 1 + 1 = 5; 
C(4) = 5 + 3 + 1 = 9; 
C(5) = 9 + 5 + 1 = 15;
 ……

题目 64

给定下列程序，那么执行 printf("%d\n", foo(20, 13)); 的输出结果是 ________。

int foo(int x, int y){
    if (x <= 0 || y <= 0)
        return 1;
    return 3 * foo( x-6, y/2 );
}

正确答案及解析

答案：81

分析： 3*6 < 20 < 4*6,递归 4层。

log13 < log16 = 4;

所以结果为 3^4 = 81.

题目 65

设图 G 的相邻矩阵如下图:则 G 的顶点数和边数分别为()

正确答案及解析

答案：5, 8

总共有5行，所以有5个顶点。

在无向图里，矩阵里任意两个1为两个顶点的连线，总共有8对。所以边数为8。

题目 66

（）操作不是P操作可完成的。

为进程分配处理机
使信号量的值变小
可用于进程的同步
*使进程进入阻塞状态

正确答案及解析

答案：A

P操作分配的是我们申请的资源，并不是处理机

题目 67

关于下列操作哪个复杂度为O(1)?

vector<> 中插入元素(动态数组)
set 中查找元素
hasp_map 中查找元素
deque尾部删除元素

正确答案及解析

答案：CD

双端队列，尾部插入一个应该是O(1)吧

题目 68

同一进程下的线程可以共享以下？

stack
data section
register set
file fd

正确答案及解析

答案：BD

线程共享的内容包括： 1. 进程代码段 2. 进程的公有数据(利用这些共享的数据，线程很容易的实现相互之间的通讯) 3. 进程打开的文件描述符 4. 信号的处理器 5. 进程的当前目录 6. 进程用户ID与进程组ID

线程独有的内容包括： 1. 线程ID 2. 寄存器组的值 3. 线程的堆栈 4. 错误返回码 5. 线程的信号屏蔽码

题目 69

下面描述中正确的为：

线性表的逻辑顺序与物理顺序总是一致的。
线性表的顺序存储表示优于链式存储表示。
线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。
二维数组是其数组元素为线性表的线性表。

正确答案及解析

答案：CD

题目 70

在下列说法中，哪个是错误的（）

若进程A和进程B在临界段上互斥，那么当进程A处于该临界段时，它不能被进程B中断
虚拟存储管理中采用对换(swapping)策略后，用户进程可使用的存储空间似乎增加了
虚拟存储管理中的抖动(thrashing)现象是指页面置换(page replacement)时用于换页的时间远多于执行程序的时间
进程可以由程序、数据和进程控制块(PCB)描述

正确答案及解析

答案：AC

注意A选项，A进程是可以被B进程中断的，只是B不能进入临界区。

c选项中：是请求分页虚拟存储管理。

当需要执行否条的指令或使用某个数据而发现他们不再内存中时候，会产生缺页异常。

系统从磁盘中把此指令或数据所在的页面装入。缺页异常是由硬件所产生的一种特殊终端信号，其中当中断率较高时，整个系统的页面调度非常频繁造成大部分时间都花费在来回调度上，而不是执行任务，这种现象叫做“抖动”。——《操作系统》

题目 71

数组不适合作为任何二叉树的存储结构()

正确答案及解析

答案：错的

二叉树的顺序存储就是利用数组实现的。也就是用一组连续的存储单元存放二叉树中的结点。依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系，这样既能够最大可能地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。

题目 72

程序出错在什么阶段（）?

int main(void)
{
    http://www.taobao.com
    cout << "welcome to taobao" << endl;
    return 0;
}

预处理阶段出错
编译阶段出错
汇编阶段出错
链接阶段出错
运行阶段出错
程序运行正常

正确答案及解析

答案：Ｆ

"http:"是goto语句的标记，＂//＂是注释，注释内容为"www.taobao.com"

题目 73

下列哪一个不属于关系数据库的特点？

数据冗余度小
数据独立性高
数据共享性好
多用户访问

正确答案及解析

答案：D

关系数据库的特点：

数据库存在的一个目的就是统一管理数据，减少数据冗余度，A正确；
数据独立性，指数据和其管理软件独立，以及数据及其结构的独立，B正确；
数据库就是为了方便用户之间共享数据，C正确；
数据库中存在锁机制，如果多用户访问可能导致数据不一致等，D不正确。

题目 74

通道能够完成（）之间数据的传输。

CPU与外设
内存与外设
CPU与主存
外设与外设

正确答案及解析

答案：B

CPU正在工作，突然想到要与外设通信，于是发命令给通道，然后接着做自己的工作。通道接到命令后，接通外设与内存，并在他们之间传递数据，等数据传递完成后，通知CPU进行处理。

题目 75

某IP地址192.168.48.10，掩码为255.255.255.128，其所在的子网为()，广播地址为()，有效的主机IP地址范围从()到().

正确答案及解析

答案：192.168.48.0/192.168.48.127/192.168.48.1 到 192.168.48.126

255转换为2进制是 11111111

128转换为2进制是 10000000

对地址 192.168.48.10和掩码255.255.255.128 进行 and操作得到子网 192.168.48.0

ip地址和掩码做and操作后，得到这个子网地址的都属于这个ip段， 192.168.48.0 ... 192.168.48.127和 255.255.255.128进行and操作后都是 192.168.48.0

其中， 192.168.48.127为广播地址， 192.168.48.0 ... 192.168.48.126为有效地址