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

一、选择题

1． n 个结点的完全有向图含有边的数目（ ）。

A.n*n

B.n （n+l） C.n/2

D.n*（n-l ）

【答案】D

【解析】在有向图中，如果任意两个顶点之间都存在边，则称为有向完全图。顶点个数为n 的无向图，最多有

条边。如是有向图，需要在无向图的最多边的基础上乘以2，则

为n （n-l ）。

2． 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。

A. 单链表

B. 仅有头指针的单循环链表 C. 双链表

D. 仅有尾指针的单循环链表 【答案】D

【解析】仅有尾指针的单循环链表，在最后插入元素和删除第一个元素都会用到这个尾指针。

3． 用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（ ）。

A. 仅修改队头指针 B. 仅修改队尾指针

C. 队头、队尾指针都可能要修改 D. 队头、队尾指针都要修改 【答案】C

【解析】用不带头结点的单链表存储队列，一般删除操作仅修改队头指针，但当队列中只有一个结点时，进行删除操作要将队头、队尾指针都修改成NULL 。

4． 若无向图G= （V , E）中含7个顶点，则保证图G 在任何情况下都是连通的，则需要的边数最少是（ ）。

A.6 B.15 C.16 D.21

【答案】C

【解析】要保证无向图G 在任何情况下都是连通的，即任意变动图G 中的边，G 始终保持连通。首先需要图G 的任意6

个结点构成完全连通子图然后再添加一条边将第7个结点与

需

条边，

连接起来，共需16条边。本题非常容易错误地选择选项A ，

主要原因是对“保证图G 在任何情况下都是连通的”的理解，分析选项A ，在图G 中，具有7个顶点6条边并不能保证其一定是连通图，即有n-1 条边的图不一定是连通图。分析选项D ，图G 有7个顶点21条边，那么图G —定是无向完全图，无向完全图能 保证其在任何情况下都是连通的，但是这不符合题目中所需边数最少的要求。

5． 设有向图G= （V ，E ），顶点集能得到的不同遍历序列个数是（ ）。

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

【答案】D

【解析】根据题意知有向图的结构如图所示。深度优先遍历的特点是尽可能先对纵深方向进行搜索，所以可 能得到的不同遍历序列分别是：

6． 若用户1与用户2之间发送和接收电子邮件的过程如图所示，则图中①、②、③阶段分别使用的应用层协议可以是（ ）。

图 电子邮件发送接收示意图

A.SMTP 、SMTP 、SMTP B.POP3、SMTP 、POP3

V={V0, VI ，V2, V3}，边

集

若从顶点V0开始对图进行深度优先遍历，则可

C.POP3、SMTP 、SMTP D.SMTP 、SMTP 、POP3 【答案】D 。

【解析】题中电子邮件的工作过程如下：

①用户1调用用户代理来编辑要发送的邮件，用户代理用SMTP 将邮件传送给用户1的发送端邮件服务器。

②发送端邮件服务器也就是用户1的邮件服务器将邮件放入邮件缓存队列中，等待发送。 ③运行在发送端邮件服务器的SMTP 客户进程，发现在邮件缓存中有待发送的邮件，就向运行在接收端邮件服务器也就是用户2的邮件服务器的SMTP 服务器进程发起TCP 连接建立。当TCP 连接建立后，SMTP 客户进程开始向远程的SMTP 服务器发送邮件。当所有的待发邮件发完了，SMTP 就关闭所建立的TCP 连接。

④运行在接收端邮件服务器中的SMTP 服务器进程收到邮件后，将邮件放人收信人的用户邮箱中，等待收信人在他方便时进行读取。收信人在打算收信时，调用用户代理，使用POP 协议将自己的邮件从接收端邮件服务器的用户邮箱中取回（如果邮箱中有来信的话）。

因此题中1，2, 3阶段分别使用的应用层协议可以是SMTP ，SMTP , POP3, 因此答案是D 。SMTP 采用“推”的通信方式，用于用户代理向邮件服务器发送邮件、以及邮件服务器之间发送邮件。POP3采用“拉”的通信方式，用于用户从目的邮件服务器上读取邮件。

7． 下列有关接口的叙述中错误的是：（ ）

A. 状态端口和控制端口可以合用同一寄存器 B.

接口中CPU 可访问寄存器，称为

端口

端口

指令，

C. 采用独立编址方式时，【答案】D

【解析】采用统一编码方式，存储器和

端口共用统一的地址空间，不需要专用的

任何对存储器数据进行操作的指令都可用于端口的数据操作。所以D 错误

8． 下列选项中，不能构成折半查找中关键字比较序列的是（ ）。

A.500，200，450，180 B.500，450，200，180 C.180，500，200，450 D.180，200，500，450

【答案】A

【解析】折半查找的过程是：先确定待查找记录所在的范围，然后逐步缩小范围直到找到或找不到该记录为止。折半查找的关键字序列满足：对每一个关键字，其后面的所有关键字序列或者都小于等于该关键字或者都大于等于该关键字。A 项错误，第三次比较的关键字为450，说明待查关键字位于200〜450间，所以第四次比较时不会遇到关键字180。

端口地址和主存地址可能相同

D. 采用统一编址方式时，CPU 不能用访存指令访问