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

一、单项选择题

1． 用有向无环图描述表达式

A.5

B.6

C.8

D.9

【答案】A ，至少需要顶点的数目为（ ）。

，6条边【解析】一共5个结点。

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

A. 仅修改队头指针

B. 仅修改队尾指针

C. 队头、队尾指针都可能要修改

D. 队头、队尾指针都要修改

【答案】C

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

3． 某基于动态分区存储管理的计算机，，其主存容量为55MB(初始为空闲）采用最佳适配(BestFit)算法，分配和释放的顺序为:分配15MB 、分配30MB 、释放15MB 、分配8MB 、分配6MB ，此时主存中最大空闲分，区的大小是（ ）.

A.7MB

B.9MB

C.10MB

D.15MB

【答案】B

【解析】对于简单分区内存分配，需要将进程的所有代码和数据装入内存. 故55MB 先分配15MB 余40MB ，再分配30MB 后余10MB ，释放15MB 后出现一个15MB 和一个10MB 的空闲空间，分配8MB 时按最佳适配(BestFit)算法应该使用10MB 的空闲块，余2MB 的碎片，分配6MB 时占用15MB 的空间余9MB 的碎片(空闲空间），因此最大空闲区为9MB.

4． 线性表的顺序存储结构是一种（ ）。

A. 随机存取的存储结构

B. 顺序存取的存储结构

C. 索引存取的存储结构

D.Hash 存取的存储结构

【答案】A

【解析】线性表包括顺序存储结构和链式存储结构，顺序存储结构能够随机存取表中的元素，但插入和删除操作较麻烦，链式存储结构不能随机访问表中的元素，但是能够表示元素之间的先后次序，而且插入和删除操作较容易。

5． 某计算机有五级中断, 中断屏蔽字为屏蔽。若中断响应优先级从高到低的顺序是

的顺序为

A.11110

B.01101

C.00011

D.01010

【答案】D , 则表示对级中断进行

, 且要求中断处理优先级从高到低的中断处理程序中设置的中断屏蔽字是（ ）。

B

排除掉。【解析】由于L 2的中断处理优先级下降, 屏蔽字中需要3个0, 所以可以将选项A 、

需要对开放, 所以相应位应该为“0”, 即为01010。

6． 下列关于图的叙述中, 正确的是（ ）。

Ⅰ. 回路是简单路径

Ⅱ. 存储稀疏图, 用邻接矩阵比邻接表更省空间

Ⅲ. 若有向图中存在拓扑序列, 则该图不存在回路

A. 仅Ⅱ

B. 仅Ⅰ、Ⅱ

C. 仅Ⅲ

D. 仅Ⅰ、Ⅲ

【答案】C

【解析】第一个顶点和最后一个顶点相同的路径称为回路; 序列中顶点不重复出现的路径称为简单路径; 回路显然不是简单路径, 所以选项Ⅰ错误。稀疏图用邻接表表示比邻接矩阵节省存储空间, 稠密图适合用邻接矩阵的存储表示, 所以选项Ⅱ错误。利用拓扑排序算法可以判断图中是否存在回路, 即在拓扑排序输出结束后所余下的顶点都有前驱, 则说明了只得到了部分顶点的拓扑有序序列, 图中存在回路。所以选项Ⅲ正确。

7． 使用浏览器访问某大学Web 网站主页时, 不可能使用的协议是（ ）

A.PPP

B.ARP

C.UDP

D.SMTP

【答案】D

【解析】SMTP 是简单邮件传输协议, 访问主页时并不涉及邮件相关协议。

8． 若用邻接矩阵存储有向图, 矩阵中主对角线以下的元素均为零, 则关于该图拓扑序列的结论是（ ）。

A. 存在, 且唯一

B. 存在, 且不唯一不唯一

C. 存在, 可能不唯一

D. 无法确定是否存在

【答案】C 。

【解析】图的基本应用--拓扑排序, 用邻接矩阵存储有向图, 矩阵中主对角线以下的元素均为零, 说明该图为有向无环图, 所以其拓扑序列存在, 但不一定唯一,

如图的邻接矩阵为, 则存在两个拓扑序列。

9． 设栈S 和队列Q 的初始状态均为空，元素a ，b ，c ，d ，e ，f ，g 依次进入栈S. 若每个元素出

d ，c ，f ，e ，a ，g ，. 栈后立即进入队列Q ，且7个元素出队的顺序是b ，则找S 的容量至少是（ ）

A.1

B.2

C.3

D.4

【答案】C

【解析】由于栈具有先进后出的特性，队列具有先进先出的特性，出队顺序即为人队顺序.. 在本题中，每个元素出栈S 后立即进入队列Q ，出栈顺序即为入队顺序，所以本题中队列的作用形同虚设，根据题意出队顺序即为出栈顺序. 根据出桟顺序可以分析各个元素进出栈的过程：第一个出栈元素为b ，表明栈内还有元素a ，b 出栈前的深度为2；第二个出栈元素为d ，栈内元素为a 和c ，d 出栈前的深度为3；c 出栈后，剩余元素为a ，c 出栈前的深度为2；f 出栈后，剩余元素为a 和e ，f 出栈前的深度为3；e 出栈后，剩余元素为a ，e 出栈前的深度为2；a 出栈后，无剩余元素，a 出栈前的深度为1；g 出栈后，无剩余元素，g 出栈前的深度为1. 所以栈容量至少是3.

10．有向带权图如下图图所示, 若采用迪杰斯特拉(Dijkstta)算法求从源点a 到其他各顶点的最短路径, 则得到的第一条最短路径的目标顶点是b , 第二条最短路径的目标顶点是c , 后续得到的其佘各最短路径的目标顶点依次是（ ）。

图 有向带权图