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

一、填空题

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

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

2． 抽象数据类型的定义仅取决于它的一组_____，而与_____无关，即不论其内部结构如何变化，只要它的_____不变，都不影响其外部使用。

【答案】逻辑特性；在计算机内部如何表示和实现；数学特性

3． 有向图G=(V, E) ，其中

权d 。E(G)为

，则从源点0到顶点3的最短路径长度是_____，经过的中间顶点是_____。

【答案】50；4

4． 对于给定的元素，可以构造出的逻辑结构有_____，_____，_____，_____四种。

【答案】集合；线性结构；树形结构；图状结构(网状结构)

5． 对单链表中元素按插入方法排序的C 语言描述算法如下，其中L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。

:_____:

{_____)

(_____、

:_____；_____；p ＝u ；

【答案】(1)L﹣＞next ＝NULL //置空链表，然后将原链表结点逐个插入到有序表中

，用三元组表示弧及弧上的

(2)p!＝NULL //当链表尚未到尾，p 为工作指针

(3)q!＝NULL //查P 结点在链表中的插入位置，这时q 是工作指针

(4)p﹣＞next ＝r ﹣＞next //将P 结点链入链表中

(5)r﹣＞next ＝p //r是q 的前驱，u 是下个待插入结点的指针

6． 在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。 【答案】

要加“虚结点”。

设编号为i 和j 的结点在顺序存储中的下标为s 和t , 则结点i 和j 在同一层上的条件是

。

【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，

二、判断题

7． 若从二叉树的任一结点出发，到根的路径上所经过的结点序列按其关键字有序，则该二叉树一定是哈夫曼树。（ ）

【答案】×

【解析】在含有N 个带权叶子结点的二叉树中，其中带权路径长度最小的二叉树称为哈夫曼树，也叫做最优二叉树。关键字有序，可能叶子结点部分的关键字最大，根结点的关键字部分最小，此时就不是哈夫曼树。

8． 在一个设有头指针和尾指针的单链表中，执行删除该单链表中最后一个元素的操作与链表的长度无关。（ ）

【答案】 ×

【解析】必须从头指针开始，查找到尾指针所指结点的前驱结点的指针。

9． 一棵树中的叶子数一定等于与其对应的二叉树的叶子数。（ ）

【答案】 ×

【解析】一颗树的叶子树与它对一个的二叉树的叶子树没有直接联系。不妨举例:假设一个有三个结点的二叉树，层数为2。则它的叶结点数为2。将其按规则转为对应的二叉树时，则它的叶结点数为1。

10．在待排数据基本有序的情况下，快速排序效果好。（ ）

【答案】×

【解析】在待排数据基本有序的情况下，插入排序效果好。

11．倒排序文件的优点是维护简单。（ ）

【答案】×

【解析】倒排文件的优点是检索记录较快。特别是对某些询问，不用读取记录，就可得到解答。

12．有向图中顶点V 度等于其邻接矩阵中第V 行中的1的个数。（ ）

【答案】×

【解析】有向图顶点V 的出度等于其邻接矩阵第V 行中的1的个数，而有向图中V 的度等于其邻接矩阵中边表出现的V 的个数。

三、单项选择题

13．用数组r 存储静态链表，结点的next 域指向后继，工作指针j 指向链中结点，使j 沿链移动的操作为（ ）。

A.j ＝r[j].next

B.j ＝j ＋l

C.j ＝j ﹣＞next

D.j ＝r[j]﹣＞next

【答案】A

【解析】因为是用数组存储，这里所说的工作指针j 相当于数组的下标，结点是存储一个值域和next 域，next 域就是存放下一个结点的下表，所以只要将next 域中的值赋给j 就可以实现j 沿链移动。

14．在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A ，并已知A 的左孩子的平衡因子为0, 右孩子的平衡因子为1，则应作（ ）型调整以使其平衡

A.LL

B.LR

C.RL

D.RR

【答案】C

【解析】A 的平衡因子此时为-1，要使插入结点不平衡，必须插在右孩子的左子树上，A 平衡因子变成了-2. 则需要进行两次旋转(先右旋后左旋) 。

15．已知程序如下:

{

}

voidmain （ ）

{

>

}

程序运行时使用栈来保存调用过程的信息, 自栈底到桟顶保存的信息依次对应的是（ ）。