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

一、填空题

1． 在进行入栈运算时应先判别栈是否_____:在进行出栈运算时应先判别栈是否_____:当栈中元素为n 个，进行入栈运算时发生上溢，则说明该栈的最大容量为_____。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_____分别设在内存空间的两端，这样只有当_____时才产生溢出。

【答案】满；空；n ；栈底；两栈顶指针相邻(即值之差的绝对值为1)

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

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

3． n 个顶点的有向图用邻接矩阵array 表示，下面是其拓扑排序算法，试补充完整。

注:(1)图的顶点号从0开始计；

(2)indegree是有n 个分量的一维数组，放顶点的入度， (3)函数crein 用于记算顶点入度； (4)有三个函数回1，否则0) 。

("图有回路") ;

【答案】

其含义为数据data 入栈，出栈和测试栈是否空(不空返

【解析】有向图用邻接矩阵表示时，顶点i 的入度等于第i 列的所有元素之和。拓扑排序过程:首先将入度为0的顶点全部进栈。然后弹出栈顶结点，并将与弹出的顶点相连的其它顶点的入度

减一，然后判断这些顶点的入度是否为零，如果为零，继续进栈，重复这些操作，完成拓扑排序。

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

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

5．

线性表

【答案】(n﹣1)/2

【解析】删除第一个元素需要移动n ﹣1次，以此类推，删除最后一个元素需要移动0次。平均次数为(n﹣l)*n/n/2＝(n﹣l)/2。

6． 在基于关键字比较且时间为

【答案】归并；堆

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

【答案】左子树；右子树

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

8． 一个算法具有5个特性: _____、_____、_____、有零个或多个输入、有一个或多个输出。

【答案】有穷性；确定性；可行性

9． 若用n 表示图中顶点数目，则有_____条边的无向图成为完全图。

【答案】

【解析】无向完全图中任意一个顶点都和其他n －1个顶点都有一条边，即为n(n－1) 。又因. 。 为每条边重复出现两次，所有无向完全图的边数为

10．已知链队列的头尾指针分别是f 和r ，则将值x 入队的操作序列是_____。

【答案】S ＝(LinkedList*)malloc(sizeof (LNode))；s ﹣＞data ＝x ；s ﹣＞next ＝r ﹣＞next ；r ﹣

；2；k

用数组表示，假定删除表中任一元素的概率相同，则删除一个元

素平均需要移动元素的个数是_____。

_ 的排序中，若要求排序是稳定的，则可选用_____

排序；若要求就地排序(及辅助空间为O(1))，则可选用_____排序。

＞next ＝s ；r ＝s ；

【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。

11．在循环队列中，队列长度为n ，存储位置从0到，n ﹣1编号，以rear 指示实际的队尾元素，现要在此队列中插入一个新元素，新元素的位置是_____。

【答案】

12．索引顺序文件既可以顺序存取，也可以 _____存取。

【答案】随机

13．设T 是一棵结点值为整数的二叉排序树，A 是一个任意给定的整数。在下面的算法中，free_tree(T)在对二叉排序树丁进行后序遍历时释放二又排序树T 的所有结点

；

，首先在二叉排序树T 中查找值为A 的结点，根据查找情况分别进行如下

处理:(1)若找不到值为A 的结点，则返回根结点的地址(2)若找到值为A 的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A 的结点是查找树的根结点，删除后变成空的二叉树，则返NULL ; 否则返回根结点的地址。

【答案】

14．起始地址为480，大小为8的块，其伙伴块的起始地址是_____；若块大小为32, 则其伙伴块的起始地址为_____; 。

【答案】480+8=488，480－32=448

【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下:

根据上述公式起始地址就为488。