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

一、填空题

1． —棵有个结点的满二叉树有_____个度为1的结点、有_____个分支（非终端）结点和_____个叶子，该满二叉树的深度为_____。 【答案】

或

【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。

2． VSAM 系统是由_____、_____、_____构成的。

【答案】索引集；顺序集；数据集

3． 外排序的基本操作过程是_____和_____。

；归并 【答案】生成有序归并段（顺串）

4． 下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n

个顶点

用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。

（1）若是边，则的值等于_____，若不是边，则的值是一个比任何边的权，矩阵的对角线元素全为0。

（2）构造最小生成树过程中，若顶点Vi 已包括进生成树，就把相邻矩阵的对角线元素A （i , i ）置成若

【答案】（1） 已包括进生成树，就把矩阵元素A （i ，j ）置成 边上的权值；都大的数；（2）1; 负值；（3）为负；边 （3）算法结束时，相邻矩阵中。

5． 对n 个记录的表r[l..n]进行简单选择排序，所需进行的关键字间的比较次数为_____。

【答案】n （n-1）/2

【解析】第一次需要n-1次比较，第i 此需要n-i 此比较，所以共需要、n-l+n-2+...+l=n（n-l ）/2。

6． —棵左子树为空的二叉树在前序线索化后，其中的空链域的个数为 _____。

【答案】2

【解析】只有根结点的做指针为空和最右边的叶结点的右指针为空。

7． 对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_____，在给定值为x 的结点后插入一个新结点的时间复杂度为_____。 【答案】

【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。

8． 在有n 个顶点的有向图中，每个顶点的度最大可达。

【答案】2（n-l ）

【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n-1。

9． 循环队列的引入，目的是为了克服_____。

【答案】假溢出时大量移动数据元素

【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。

10．在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_____; 对于有向图来说等于该顶点的_____。

【答案】度；出度

二、选择题

11．某计算机处理器主频为50MHz ，采用定时查询方式控制设备A 的I/0, 查询程序运行一次所用的时钟 周期数至少为500。在设备A 工作期间，为保证数据不丢失，每秒需对其查询至少200次，则CPU 用于设备A 的I/0的时间占整个CPU 时间的百分比至少是（ ）。

A.0.02%

B.0.05%

C.0.20%

D.0.50%

【答案】C

【解析】对于设备A ，每秒中查询至少200次，每次查询至少500个时钟周期，总的时钟周期数为100000, 又因为处理器主频为50MHz 。所以CPU 用于设备A 的I/0的时间占整个CPU 时间的百分比至少为100000/50=0.20%。

12．操作系统的子系统通常由四个层次组成，每一层明确定义了与邻近层次的接口。其合理的层次组织排列顺序是（ ）。

A. 用户级

B. 用户级

C. 用户级

D. 用户级

【答案】A 。

【解析】对于一次设备的调用，操作系统为用户准备了系统调用的接口，当用户使用设备时，首先在用户程序中发起一次系统调用，操作系统的设备无关层软件接到该调用请求后调用处理程

软件、设备无关软件、设备驱动程序、中断处理程序 软件、设备无关软件、中断处理程序、设备驱动程序 软件、设备驱动程序、设备无关软件、中断处理程序 软件、中断处理程序、设备无关软件、设备驱动程序

序进行处理，根据调用格式和形参，再转到相应的设备驱动程序去处理；大部分设备在运行时是需要时间的，所以设备驱动程序会以中断方式驱动设备，即设置好控制寄存器参数和中断向量等参数后阻塞自己；当设备准备好或所需数据到达后设备硬件发出中断，设备驱动程序唤醒，将数据按上述调用顺序逆向回传到用户程序中，或继续驱动设备执行下一条指令。 因此，软件从上到下分为四个层次：用户层、与设备无关的软件层、设备驱动程序以及中断处理程序。

13．假设5个进

程共享三类资

源这些资源总数分别

为

时刻的资源分配情况如题表所示，此时存在的一个安全序列是（ ）。

题表资源分配情况表

【答案】D 。

【解析】典型的死锁避免算法、银行家算法的应用。本题的题型与2011年的27题相似。银行家算法是操作系统中的一个重点知识单元，考生对此应该非常熟悉，本题并无难点。分析一下下表，可以看到

，运行是可以的。

本题也可以排除法，时刻可用资源是分别为2, 3, 3, 此时刻，P0需要

分别为2, 3, 7，故排除A , P1需要Rl ，R2, R3分别为1，3, 3, P2还需要资源Rl ，R2, R3分别为0, 0, 6，故C 排除，P3需要Rl ，R2, R3分别为2, 2, 1。所以正确答案在B ，D 之间。看B 选项，P1之后的可用资源Rl ，R2, R3分别变为6, 3，6，而P0尚需资源2, 3, 7, 故B 方案行不通。因而最终答案只有D 项。

14．数组

A.55

B.45 中含有元素的个数（ ）。