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

一、填空题

1． 对于一个具有n 个结点的二叉树，当它为一棵_____二叉树时具有最小高度, 当它为一棵_____时，具有最大高度。

【答案】完全；只有一个叶结点的二叉树

2． 在单链表L 中，指针P 所指结点有后继结点的条件是_____

【答案】P ﹣＞next! ＝NULL

【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。

3． 当广义表中的每个元素都是原子时，广义表便成了_____。

【答案】线性表

【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。

4． 已知二叉排序树的左右子树均不为空，则_____上所有结点的值均小于它的根结点值，_____上所有结点的值均大于它的根结点的值。

【答案】左子树；右子树

【解析】二叉排序树(binary sort tree)或者是一棵空树，或者是具有下列性质的二叉树:①若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；③它的左、右子树也分别为二叉排序树。

5． 在拓扑分类中，拓扑序列的最后一个顶点必定是_____的顶点。

【答案】出度为0

【解析】如果最后一个顶点的出度不为0, 则必定还有顶点存在，与题目所说的最后一个顶点矛盾，所有最后一个顶点的出度必定为零。

6． 建立索引文件的目的是_____。

【答案】提高查找速度

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

【答案】O(1)；O(n)

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

8． 从用户的观点看，文件的逻辑结构通常可以区分为两类:一类是如NdBASE 中数据库文件那样的文件组织结构，称为_____文件; 另一种是诸如用各种文字处理软件编辑成的文本文件，称为_____文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_____， _____和_____。B+树适用于组织_____的索引结构，m 阶B+树毎个结点至多有_____个儿子，除根结点外每个结点至少有_____个儿子，根结点至少有_____个儿子，有k 个儿子的结点必有_____个关键码。

【答案】数据库；文本；顺序组织；随机组织；链组织；随机组织；m ; ；2；k

9． 执行顺序查找时，存储方式可以是_____，折半查找时，要求线性表_____，分块查找时要求线性表_____，而哈希表的查找，要求线性表的存储方式是_____。

【答案】顺序存储或链式存储；顺序存储且有序；块内顺序存储，块间有序；散列存储

10．G 是一个非连通无向图，共有28条边，则该图至少有_____个顶点。

【答案】9

【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。

二、单项选择题

11．处理外部中断时, 应该由操作系统保存的是（ ）。

A. 程序计数器(PC)的内容

B. 通用寄存器的内容

C. 快表(TLB)的内容

D.Cache 中的内容

【答案】B

【解析】外部中断处理过程首先要保护现场, 使得中断处理完后能够恢复程序的状态继续执行。保护现场有两个含义:

①由中断隐指令保存程序的断点(程序计数器) ;

②由中断服务程序保存通用寄存器和状态寄存器的内容。中断服务程序是操作系统的一部分。

12．将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度为（ ）。

A.4

B.5

C.6

D.7

【答案】C

【解析】若二叉树中最多只有最下面两层的结点的度数可以小于2，并且最下面一层的叶结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树。具有n 个(n＞0) 结点的完全二叉树的高度为或由完全二叉树类推到完全三叉树可知，n 个结点的完全三叉树的高度为

或》

13．在下图所示的采用“存储一转发”方式的分组交换网络中，所有链路的数据传输速率为100Mbps ，分组大小为1000B ，其中分组头大小20B ，若主机H1向主机H2发送一个大小为980000B 的文件，则在不考虑分组拆装时间和传播延迟的情况下，从H1发送开始到H2接收完为止，需要的时间至少是（ ）

.

A.80ms B.

C.

D.

【答案】c

【解析】由题设可知，分组携带的数据长度为980B ，文件长度为980000B ，需拆分为1000个分组，加上头部后，每个分组大小为1000B ，总共需要传送的数据量大小为IMB. 由于所有链路的数据传输速度相同，因此文件传输经过最短路径时所需时间最少，最短路径经过分组交换机. 当t ＝lM ×8/100Mbps＝80ms 时，HI 发送完最后一个比特；到达目的地，最后一个分组，需经过两个分组交换机的转发，每次转发的时间为t 0＝lK ×8/100Mbps＝，所以，在不考虑分组拆装时间和传播延时的情况下，当时，H2接受完文件，

即所需的时间至少为

14．若一棵二叉树的前序遍历序列为a , e , b , d , c , 后序遍历序列为b , c , d , e , a , 则根结点的孩子结点（ ）。

A. 只有e

B. 有e 、b

C. 有e 、c

D. 无法确定

【答案】A 。

【解析】由题目可知, 若一棵二叉树的前序遍历序列为a , e , b , d , c , 后序遍历序列为b , c , d , e , a , 其中a 为这棵二叉树的根结点, 接下来, 在前序遍历的第二个结点为e , 而后序遍历的倒数第二个结点为e , 说明a 的孩子结点只有e 。