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

一、填空题

1． 高度为4的3阶B-树中，最多有_____个关键字。

【答案】26

【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，关键字最多。

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

【答案】出度为0

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

3． 实现字符串拷贝的函数strcpv 为:

(_____)

【答案】s++＝*t++或(*s++＝*t++)!＝'\0’

4． 设广义表L ＝(（ ），（ ）) ，则head(L)是_____tail(L)是_____L的长度是_____；深度是_____。

【答案】（ ）；(（ ）) ；2；2

【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。

5． 以下是用类C 语言写出的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild 域作为前链域，指向结点的直接前驱，结点的Rchild 域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack , 栈顶指针为top ，P ，t 为辅助指针，head 为双向循环链表的头指针。试填充算法中的空格，使算法完整。

【答案】

6． 在二叉树中，指针p 所指结点为叶结点的条件是_____。

【答案】

【解析】叶子节点的左右孩子都不存在。

二、单项选择题

7． 假定编译器规定int 和short 类型长度分别为32位和16位, 执行下列C 语言语句:

;

A.00007FFAH B.0000FFFAH C.FFFF7FFAH D.FFFFFFFAH 【答案】B 。

X 和y 均为无符号数, 其中X 为16位, y 为32位, 将16位无符号数转化成32位无符【解析】

号数, 前面要补零。因为X=65530=FFFAH, 所以y=0000FFFAH。

8． 有n(n＞0) 个分支结点的满二叉树的深度是（ ）。

A.n 2﹣l

B.log 2(n＋1) ＋1 C.log 2(n＋1) D.log 2(n—1) 【答案】C

【解析】满二叉树的结点总数＝分支的结点总数＋非分支的结点总数。由于此树为满二叉树， 所以非分支的结点总数为1，所以满二叉树共有n ＋1个结点，所以满二叉树的深度为log 2 (n＋1) 。 9． 每个结点的度或者为0或者为2的二叉树称为正则二叉树。n 个结点的正则二叉树中有（ ）个叶子。

A. B.

:得到y 的机器数为（ ）。

C. D.

【答案】D

【解析】二叉树结点总数n ＝n 0＋n 1＋n 2(n0，n 1，n 2分别代表度为0，度为1，度为2的结点数) 。又在非空二叉树中:n 0＝n 2＋l ，且本题所给树为正则二叉树，n 1＝0，所以n ＝2*n0﹣l ，因此n 1＝(n+1)/2。

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

A. 顺序表 B. 双链表

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

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

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

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

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

12．—个多道批处理系统中仅有P1和P2两个作业, P2比P1晚5ms 到达。它们的计算和作顺序如下:P1:计算60ms

,

, 计算20ms ; P2:计算120ms

,

不考虑调度和切换时间, 则完成两个作业需要的时间最少是（ ）。

A.240ms B.260ms C.340ms D.360ms

【答案】B 。

【解析】考查处理系统的性能计算, 由于P2比P1晚5ms 到达, P1先占用CPU , 根据P1和P2的执行过程, 作业运行的甘特图如下所示, 故答案为B 。

操

, 计算40ms 若