算法的稳定性

(1)【◆题库问题◆】：[名词解释] 算法的稳定性

【◆参考答案◆】：
假设Ri=Rj，且在排序之前Ri领先于Rj，若在排序后的序列中Ri仍然领先于Rj，则称所用的排序算法是稳定的，反之则称所用的算法是不稳定的。

(2)【◆题库问题◆】：[判断题] 采用环形队列可以解决队列中假溢出的现象。
A．正确
B．错误

【◆参考答案◆】：正确

(3)【◆题库问题◆】：[单选] 在作退栈运算时应先判别栈是否（）。
A．空
B．满
C．上溢
D．下溢

【◆参考答案◆】：A

(4)【◆题库问题◆】：[名词解释] 选择排序

【◆参考答案◆】：
选择排序是每一趟在n-i+1（i=1，2，3…n-1）个记录中选择关键字最小的记录作为有序序列中第i个记录。其中最简单的是简单选择排序。

(5)【◆题库问题◆】：[单选] 深度为5的二叉树至多有（）个结点。
A．16
B．32
C．31
D．10

【◆参考答案◆】：C

(6)【◆题库问题◆】：[单选] 在无向图中定义顶点Vi域Vj之间的路径为从Vi到达Vj的一个（）。
A．顶点序列
B．边序列
C．权值总和
D．边的条数

【◆参考答案◆】：A

(7)【◆题库问题◆】：[问答题,简答题] 一棵度为2的树与一棵二叉树有何区别？

【◆参考答案◆】：度为2的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序的。即，在一般树中若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即使是一个孩子也有左右之分。

(8)【◆题库问题◆】：[问答题] 具有n个顶点的强连通图至少有多少条边？这样的图应该是什么形状？

【◆参考答案◆】：
具有n个顶点的强连通图至少有n条边，这样的图是一个由n个顶点构成的环。
强连通图是相对于有向图而言的。由于强连通图要求图中任何两个顶点之间能够相互连通，因此每个顶点至少要有一条以该顶点为弧头的弧和一条以该顶点为弧尾的弧，每个顶点的入度和出度至少各为1，即顶点的度至少为2，这样根据图的顶点数、边数以及各项点的度三者之间的关系计算可得：边数=2×n/2=n。

(9)【◆题库问题◆】：[单选] 设单循环链表中结点的结构为（data，link），且first为指向链表表头的指针，current为链表当前指针，在循环链表中检测current是否达到链表表尾的语句是（）。
A．current->link=null
B．first->link=current
C．first=current
D．current->link=first

【◆参考答案◆】：D

(10)【◆题库问题◆】：[单选] 广义表A=（a），则表尾为（）。
A．a
B．（（））
C．空表
D．（a）

【◆参考答案◆】：C