考研数据结构及程序设计在线题库每日一练（八）

本文提供考研数据结构及程序设计在线题库每日一练，以下为具体内容

1、在一个单链表中，若p所指的结点不是最后一个结点，在p之后插入s所指的结点，则执行（ ）。

A、s→next=p; p→next=s;

B、p→next=s; s→next=p;

C、p=s; s→next=p→next;

D、s→next=p→next; p→next=s;

2、设顺序队列的容量为MaxSize，其头指针为front，尾指针为rear，空队列的条件为（ ）。

A、front=rear

B、front=MaxSize

C、front+1=rear

D、rear=0

3、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（ ）。

A、二叉查找树

B、哈夫曼树

C、AVL树

D、堆

4、设int x=1，y=1；表达式（!x++||y--）的值是（ ）。

A、0

B、1

C、2

D、-1

5、下列关于二叉排序树的说法正确的是（ ）。I.向二叉排序树插入一个结点，所需要的比较次数可能大于此排序树的高度II.二叉排序树一定是平衡二叉树III.删除二叉排序树中的一个结点，再重新插入，一定能得到原来的二叉排序树IV.平衡二叉树是指左、右子树的高度差的绝对值不大于1的二叉树

A、I、II、IV

B、II、III、IV

C、I. IV

D、只有IV

1、试题答案：D

试题解析：

【考点】本题考查单链表的删除操作。
【解析】在一个单链表中，若p所指的结点不是最后一个结点，在p之后插入s所指的结点的示意图如下所示。故本题选D。

2、试题答案：A

试题解析：

【考点】本题考查队列的判断条件。
【解析】为了方便起见，约定初始化建空队时，令front=rear=0。但是，当队空时，front=rear；当队满时，front=rear亦成立。因此只凭等式front=rear无法判断队空还是队满。有两种方法处理上述问题：
（1）另设一个标志位以区别队列是空还是满。
（2）牺牲一个存储空间，约定以“队列头指针front在队尾指针rear的下一个位置上”作为队列“满”状态的标志（front指向队首元素，rear指向队尾元素的下一个元素）。即：
① 队空时：front=rear；
② 队满时：(rear+1)%maxsize=front。
综上所述，本题选A。

3、试题答案：D

试题解析：

【考点】本题考查满二叉树的特点。
【解析】
A：二叉排序树只有中序遍历结果是一个有序序列。
B：在哈夫曼树中，所有关键字只会出现在叶子结点上，其非叶子结点上并没有关键字。
C：AVL树（平衡二叉树）本质上是带了平衡功能的二叉排序树，所以也不满足题干性质。
D：大根堆的特点是任意结点满足“该结点值≥左右孩子结点值”；小根堆的特点是任意结点满足“该结点值≤左右孩子结点值”。因此，在大根堆中，从任一结点出发到根的路径上所经过的结点序列按其关键字有序递减；在小根堆中，从任一结点出发到根的路径上所经过的结点序列按其关键字有序递增。因此对满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序。
综上所述，本题选D。

4、试题答案：B

试题解析：

【考点】本题考查运算符。
【解析】进行运算的两个数据，按二进制位进行“或”运算。运算规则：0|0=0；0|1=1；1|0=1；1|1=1；即：参加运算的两个对象只要有一个为1，其值为1。!和++运算同级，结合性是从右向左，那么!x++等价于!( x++)。表达式!x++运行结果为0，x的值为2，表达式y—的运行结果为1，y的值为0。因此，表达式（!x++||y--）相当于（0||1），结果为1。故本题选B。

5、试题答案：D

试题解析：

【考点】本题考查二叉排序树的特点。
【解析】
I.向二叉排序树中插入新的结点所需要的比较次数最多为该树的高度，所以I说法错误。
II.二叉排序树不一定是平衡叉树，如下所示，该二叉树是一颗二叉排序树，但不是平衡二叉树。

III.删除二叉排序树中的一个结点，再重新插入，不一定能得到原来的二叉排序树，如下所示：

IV.平衡二叉树也叫AVL树，它或者是一颗空树，或者具有以下性质的二叉排序树：它的左子树和左子树的高度之差的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树，所以IV说法正确。
综上所述，本题选D。