当前位置：问答库＞考研试题

一、选择题

1． 在一个有N 个元素的有序单链表中查找具有给定关键字的结点，平均情况下的时间复杂性为（ ）。

【答案】B

【解析】二分查找的时间复杂度为在一个用N 个元素的有序单链表中查找具有给定关键字的结点，因为查找是从头结点开始的，需要使用指针顺序往下查找，

因此时间复杂度为

2． 在缺页处理过程中，操作系统执行的操作可能是（ ）。

I. 修改页表

II. 磁盘I/O

III. 分配页框

A. 仅 I 、II

B. 仅II

C. 仅III

D.I 、II 和III

【答案】D

【解析】首先我们要考虑的是，为什么会发生缺页中断? 当然，在一个采用虚拟存储管理技术的系统中，程 序是部分装入的，还有部分是处于外存上的，因此，当需要访问那部分位于外存上的代码或数据时，系统会产生 缺页中断。产生缺页中断的目的是要将位于外存上的代码或数据装入内存，据此，缺页中断接下去所做的工作就是首先要在内存中找到空闲页框并分配给需要访问的页（若没有空闲的页面则要调用页面置换程序找到一处页 面，将该页面的内容处理掉，或回写

，分配妥当以后，缺页中断处理程序调用设备磁盘，或覆盖掉，然后将此页分配给需要访问的页）

驱动程序做磁盘1/0, 将位于外存（一般是磁盘）上的页面调入内存，调入后转身去修改 页表，将

，将物理页表中代表该页是否在内存的标志位（一般称为存在位或有效位、在位位）修改为“真”

页框号填入相应位置，若必要还需修改其它相关表项等。完成上述任务后，缺页中断处理程序返

回，继续程序的执行。 从上述过程可以看出，涉及的相关处理非常多，因此，答案就显而易见了。

3． 下列关于无向连通图特性的叙述中，正确的是（ ）。

I. 所有的顶点的度之和为偶数

II. 边数大于顶点个数减1

III. 至少有一个顶点的度为1

A. 只有I

B. 只有II

C.I 和II

D.I 和III

【答案】A

【解析】在图中，顶点的度TD

点数，

e 为总边数），因此，I 项正确。对于II 、III 项中的特性不是一般无向连通图的特性，可以轻松地举出反例。“至少有一个顶点的度为1”的反例如下图（1）所示，“边数大于顶点个数减1”的反例如下图（2）所示。

之和与边的数目满足关系式：（n 为图的总结

图

4． 某网络拓扑如下图所示，路由器R1只有到达子网192.168.1.0/24的路由。为使R1可以将IP 分组正确地路由到图中所有子网，则在R1中需要増加一条路由（目的网络，子网掩码，下一跳）是（ ）。

A.192.168.2.0, 255.255.255.128, 192.168.1.1

B.192.168.2.0, 255.255.255.0, 192.168.1.1

C.192.168.2.0, 255.255.255.128, 192.168.1.2

D.192.168.2.0, 255.255.255.0, 192.168, 1, 2

【答案】D

【解析】首先从题目给出的路由表项可以确定下一跳肯定是路由器R1直接相连的R2的地址，因此是 192.168.1.2, 此时可以排除A 和B 两个选项了。进而分析路由器R2所连接的网络特点，注意其连接了 2个网络分别是192.168.2.0/25和192.168.2.128/25，但答案选项中只有一条信息，因此这里用到了超网的概念，超网是与子网类似的概念一IP 地址根据子网掩码被分为独立的网络地址

和主机地址。但是，与子网把大网络分成若干小网络相反，它是把一些小网络组合成一个大网络——超网，这里192.168.2.00000000/25和192.168.2.10000000/25 前24位是相同的，因此所构成的超网就是192.168.2.0/24，那么子网掩码就是255.255.255.00000000即 255.255.255.0, 因此答案是 D 。

5． 某二叉树结点的中序序列为BDAECF ，后序序列为DBEFCA ，则该二叉树对应的森林包括（ ）棵树。

A.1

B.2

C.3

D.4

【答案】C

【解析】由两序列可知，A 为根节点，ECF 为右子树，C 为右子树的根，F 为C 的右孩子。再由二叉树和森林的对应关系可知该二叉树对应的森林包括3棵树。根据中序序列和后序序列画出二叉树，根据二叉树得出对应的森林包含的树的棵数。

6． 主机甲向主机乙发送一个的TCP 段，期望与主机乙建立TCP 连接，若主机乙接受该连接请求，则主机乙向主机甲发送的正确的TCP 段可能是（ ）。

A. （SYN=0, ACK=0, seq=11221, ack=11221）

B. （SYN=1, ACK=1, seq=11220, ack=11220）

C. （SYN=1，ACK=1, seq= 11221，ack= 11221）

D. （SYN=0, ACK=0, seq= 11220, ack= 11220）

【答案】C

【解析】TCP 是面向连接的，所谓面向连接，就是当计算机双方通信时必需先建立连接，然后数据传送，最后拆除三个过程，也就是客户主动打开TCP 传输，服务器被动打开。第一次握手：客户发送SYN=1，seq=x 给服务器，即客户的TCP 向服务器发出连接请求报文段，其首部中的同步位SYN=1，并选择序号seq=x，表明传送数据时的第一个数据字节的序号是X 。第二次握手：服务器发送SYN=1, ACK=1, Seq=y, ack=X+l给客户，即服务器的TCP 收到连接请求报文段后，如同意则发回确认。服务器在确认报文段中应使SYN=1，使 ACK=1，其确认号ack=x+l, 自己选择的序号seq=y。第三次握手：客户发送ACK=1, seq=x+l, ack=y+l 给服务器，即客户收到此报文段后向服务器给出确认，其ACK=1, 确认号aCk=y+l。客户的TCP 通知上层应用进程，连接已经建立。服务器的TCP 收到主机客户的确认后，也通知其上层应用进程：TCP 连接已经建立。 因此，本题中x=11220, y是主机乙自动选取的序号，可以与x 相同，也可以不相同，从而主机乙所

ACK=1, seq=y, ack=x+l，ACK=1, seq=y，ack=11221，发出的TCP 段应该是SYN=1，即 SYN=1，

从而答案是 C 。

7． 下列关于SMTP 协议的叙述中，正确的是（ ）

I. 只支持传输7比特ASCII 码内容

II. 支持在邮件服务器之间发送邮件