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

一、单项选择题

1． 栈和队的共同点是（ ）。

A. 都是先进后出

B. 都是后进先出

C. 只允许在端点处插入和删除元素

D. 没有共同点

【答案】C

【解析】栈和队列的区别是栈是先进后出的数据结构，队列是先进先出的数据结构，栈和队列的共同点是都只能在端点处插入和删除元素。

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

A.n*n

B.n(n+1)

C.n/2

D.n*(n－1)

【答案】D

【解析】在有向图中，如果任意两个顶点之间都存在边，则称为有向完全图。顶点个数为n 的无向图，最多有条边。如是有向图，需要在无向图的最多边的基础上乘以2，则为n(n－1) 。

3． 有关二叉树下列说法正确的是（ ）。

A. 二叉树的度为2

B. 一棵二叉树的度可以小于2

C. 二叉树中至少有一个结点的度为2

D. 二叉树中任何一个结点的度都为2

【答案】B

【解析】树的度＝MAX(结点1的度，结点2的度，结点3的度

以称为二叉树，是因为二叉树中节点的度最大是2，也可以小于2。

4． 数组通常具有的两种基本操作是（ ）。

A. 查找和修改

结点n 的度) 。二叉树之所

B. 查找和索引

C. 索引和修改

D. 建立和删除

【答案】A

【解析】数组中的元素是顺序存放的，通过下标可以很好地查找数组元素，同时通过对应的指针可以修改数组元素的值，因此数组通常具有的两种基本操作是查找和修改。根据数组的性质，数组通常具有的两种基本运算是排序和查找。

5． 若某文件系统索引结点(inode)中有直接地址项和间接地址项, 则下列选项中, 与单个文件长度无关的因素是（ ）

A. 索引结点的总数

B. 间接地址索引的级数

C. 地址项的个数

D. 文件块大小

【答案】A

【解析】根据文件长度与索引结构的关系可知, 只有选项A 是与单个文件长度无关的。

6． 下列各类存储器中, 不采用随机存取方式的是（ ）。

A.EPROM

B.CDR0M

C.DRAM

D.SRAM

【答案】B

【解析】随机存取方式是指存储器的任何一个存储单元的内容都可以存取, 而且存取时间与存

储单元的物理位置无关。CDROM 是只读的光盘存储器, 采用串行存取方式而不是随机存取方式。

7． 某系统有n 台互斥使用的同类设备, 3个并发进程需要3, 4, 5台设备, 可确保系统不发生死锁的设备数n 最小为（ ）

A.9

B.10

C.11

D.12

【答案】B 【解析】

8． 若某单处理器多进程系统中有多个就绪态进程, 则下列关于处理机调度的叙述中, 错误的是（ ）。

A. 在进程结束时能进行处理机调度

B. 创建新进程后能进行处理机调度

C. 在进程处于临界区时不能进行处理机调度

D. 在系统调用完成并返回用户态时能进行处理机调度

【答案】C 。

【解析】对于A 、B 、D 显然是可以进行处理机调度的, 对于C , 当进程处于临界区时, 只要不破坏临界资源的使用规则, 是不会影响处理机调度的, 比如, 通常访问临界资源可能是慢速的外设(如打印机) , 如果在进程访问打印机时, 不能处理机调度, 那么系统的性能将是非常低的。几种不进行处理机调度的情况如下:

①在处理机中断的过程中;

②进程在操作系统内核程序临界区中;

③其他需要完全屏蔽中断的原子操作过程中。

9． 一个C 语言程序在一台32位机器上运行. 程序中定义了3个变量x 、Y 和z ，其中x 和z 为int

Y 为short 型. 当x ＝127，Y ＝-9时，x 、Y 和z 的值分别是. 型，执行赋值语句z ＝x ＋Y 后，（ ）

A.x ＝0000007FH ， Y ＝FFF9H ， z ＝00000076H

B.x ＝0000007FH ， Y ＝FFF9H ， z ＝FFFF0076H

C.x ＝0000007FH ， Y ＝FFF7H ， z ＝FFFF0076H

D.x ＝0000007FH ， Y ＝FFF7H ， z ＝00000076H

【答案】D

【解析】当两个不同长度的数据，要想通过算术运算得到正确的结果，必须将短字长数据转换成长字长数据，这被称为“符号扩展”.例如，x 和z 为int 型，数据长32位，Y 为short 型，数据长16位，因此首先应将y 转换成32位的数据，然后再进行加法运算.

运算采用补码的形式，而x 的补码是0000007FH ，Y 的补码是FFFFFFF7H ，所以x ＋Y ＝00000076H.

10．对有2个顶点e 条边且使用邻接表存储的有向图进行广度优先遍历, 其算法时间复杂度是（ ）。 A. B. C. D.

【答案】C 。

【解析】遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。当用二维数组表示邻接矩阵图的存储结构时,

查找每个顶点的邻接点所需时间为

, 其中n 为图中顶点数。而当以邻接表作图的存储结构时, 找邻接点所需时间为0(e), 其中e 为无向图中边的数或有向图中弧的数。由此, 当以邻接表作存储结构时, 深度优先搜索遍历图的时间复杂度为

。即可得出正确答案。