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

一、选择题

1． 链表不具有的特点是（ ）。

A. 插入、删除不需要移动元素 B. 可随机访问任一元素 C. 不必事先估计存储空间 D. 所需空间与线性长度成正比 【答案】B

【解析】B 项是顺序表的特点。只要确定了顺序线性表的起始位置，线性表中的任一数据元素都可随机存取。

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

A. 顺序表 B. 双链表

C. 带头结点的双循环链表 D. 单循环链表 【答案】A

【解析】线性表采用顺序表，便于进行存取任一指定序号的元素；线性表采用链表，便于进 行插入和删除操作。但该题是在最后进行插入和删除运算，所以利用顺序表存储方式最节省时间。

3． 已知有向图G=（V ，E ），其中

G 的拓扑序列是

（ ）。

【答案】A

【解析】设G=（V ，E ）是一个具有n 个顶点的有向图，V 中顶点序列

能被称

，则在序列中顶点Vi 为拓扑序列的条件：若是图中的边（即从顶点V i 到V j 有一条路径）

必须排在顶点Vj 之前。根据上面拓扑序列的定义，就可以得出G 的拓扑序列

是

4． 若一棵二叉树的前序遍历序列和后序遍历序列分别为1，2, 3, 4和4, 3, 2, 1，则该二叉树的中序遍历序列不会是（ ）。

A.1, 2.3.4

B.2，3, 4.1 C.3, 2, 4, 1 D.4, 3, 2, 1 【答案】C

【解析】题目中的二叉树的先序序列和后序序列正好相反，这样的二叉树每层只有一个结点。该二叉树的形态如下图所示。

从左至右，这8棵二叉树的中序序列分别为： （1）4. 3. 2. 1， （2）3, 4, 2, 1 （3）2, 4, 3, 1 （4）2, 3, 4，1 （5）1，4，3, 2 （6）1, 3, 4, 2 （7）1，2, 4, 3 （8）1, 2, 3, 4

显然选项C 的中序序列不会出现。 5．

协议对

A.011111000011111010

B.011111000111110101111110 C.01111100011111010

D.011111000111111001111101 【答案】A

组帧后对应的比特串为（ ）

HDLC 协议对比特串进行组帧时，HDLC 数据帧以位模式0111 1110标识每一个帧的【解析】

开始和结束，因此在帧数据中凡是出现了 5个连续的位“1”的时候，就会在输出的位流中填充一个“0”。所以答案为A 。

6． 下列关于管道（Pipe ）通信的叙述中，正确的是（ ）

A. —个管道可实现双向数据传输 B. 管道的容量仅受磁盘容量大小限制

C. 进程对管道进行读操作和写操作都可以被阻塞 D. —个管道只能有一个读写进程或一个写进程对其操作

【答案】C

【解析】只有写进程才能对管道写入数据，读进程对管道进行读取数据，只能半双工通信，即某一时刻只能单向传输。管道为空，则读操作被堵塞，而如果有写操作对管道进行写的话那就要堵塞了。那么C 正确

7． 以太网的MAC 协议提供的是（ ）。

A. 无连接不可靠服务 B. 无连接可靠服务 C. 有连接不可靠服务 D. 有连接可靠服务 【答案】A 。

【解析】考查以太网MAC 协议，考虑到局域网信道质量好，以太网采取了两项重要的措施以使通信更简洁：①采用无连接的工作方式；②不对发送的数据帧进行编号，也不要求对方发回确认。因此，以太网提供的服务是不可靠的服务，即尽最大努力交付，差错的纠正由高层完成。

8． 采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是（ ）。

A. 递归次数与初始数据的排列次序无关

B. 每次划分后，先处理较长的分区可以减少递归次数 C. 每次划分后，先处理较短的分区可以减少递归次数 D. 递归次数与每次划分后得到的分区的处理顺序无关 【答案】D

【解析】快速排序是递归的，递归过程可用一棵二叉树给出，递归调用层次数与二叉树的深，采用快速排序方法，其对应递归调用度一致。例如：待排序列{48, 62，35, 77, 55, 14, 35, 98）过程的二叉树如下图所示。

在最坏情况下，若初始序列按关键码有序或基本有序时，快速排序反而蜕化为冒泡排序。即其对应递归调用过程的二叉树是一棵单支树。因此快速排序的递归次数与初始数据的排列次序有关。但快速排序的递归次数与每次划分后得到的分区处理顺序无关，即先处理较长的分区或先处理较短的分区都不影响递归次数。

9． 已知程序如下：

{