下面的算法实现的是带附加头结点的单链表数据结点逆序连接，空缺处应当填入( )。 void reverse(pointer h){ ／／h为附加头结点指针pointer p，q； P=h一＞next；h一＞next=NULL； while(P|=null){ q=P： P=P一＞next： q一＞next=h一＞next； h一＞next=(_____)； } }
假定图G=(V，E)是有向图，V={1，2，…，N}，N≥1，G以邻接矩阵方式存储，G的邻接矩阵为A，即A是一个二维数组。如果i到j有边，则A[i，j]=1，否则A[i，j]=0。请给出一个算法思想，该算法能判断G是否是非循环图(即G中是否存在回路)，要求算法的时间复杂性为O(n
2
)。
某二叉树的先序遍历序列为IJKLMNO，中序遍历序列为JLKINMO，则后序遍历序列是( )。
写一个HeapInsert(R，key)算法，将关键字插入到堆R中，并保证插入后R仍是堆。请分析算法的时间复杂度。提示：将key先插入R中已有元素的尾部(即原堆的长度加1的位置，插入后堆的长度加1)，然后自下往上调整，使插入的关键字满足堆性质。
判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用的是( )。
B单项选择题1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。/B
有一种简单的排序算法，叫做计数排序(Count sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键字互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键字比该记录的关键字小。假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。 设计实现计数排序的算法。对于有n个记录的表，关键字的比较次数是多少?与简单选择排序相比较，这种方法是否更好?为什么?
算法的时间复杂度取决于( )。
有n个结点的二又树，已知叶结点个数为n
0
。
(1)写出求度为1的结点的个数的n
1
的计算公式。
(2)若此树是深度为k的完全二叉树，写出n为最小的公式。
(3)若二叉树中仅有度为0和度为2的结点，写出求该二叉树结点个数n的公式。
已知有一整数序列{a
1
，a
2
，a
3
，…，a
n
}。栈A中只保存整数，即序列中元素为整数时允许其入栈。设计一个算法实现如下功能；用栈结构存储入栈的整数，当a
i
≠一1时，将a
i
进栈；当a
i
=-1时，输出栈顶整数并出栈。
最小最大堆(minmaxHeap)是一种特定的堆，其最小层和最大层交替出现，根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最大堆。(1)画出在图中插入关键字为5的结点后的最小最大堆。(2)画出在图中插入关键字为80的结点后的最小最大堆。(3)编写一算法实现最小最大堆的插入功能。假定最小最大堆存放在数组中，关键字为整数。
一棵二叉树如下图所示，其中序遍历序列为()。
分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是( )。
归并排序中，归并的趟数是( )。
在一棵表示有序集S的二叉搜索树(binary search tree)中，任意一条从根到叶结点的路径将S分为3部分：在该路径左边结点中的元素组成的集合S
1
；在该路径上的结点中的元素组成的集合S
2
：：在该路径右边结点中的元素组成的集合S
3
。S=S
1
∪S
2
∪S
3
。若对于任意的a∈S
1
，b∈S
2
，c∈S
3
，是否总有a≤b≤c?为什么?
设计一个算法求图的中心点。设v是有向图G的一个顶点，把v的偏心度定义为： MAx{从ω到v的最短距离|ω属于V(G)} 如果v是有向图G中具有最小偏心度的顶点，则称顶点v是G的中心点。
以下排序方法中，稳定的排序方法是( )。
已知下列各种初始状态(长度为n)元素，试问当利用直接插入法进行排序时，至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)?
假设K
1
,…，K
n
是n个关键词，试解答：
(1)试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为K
1
，K
2
，…，K
n
时，用算法建立一棵以LLINK—RLINK链接表示的二叉查找树。
(2)设计一个算法，打印出该二叉查找树的嵌套括号表示结构。假定该二叉查找树的嵌套括号表示结构为B(A，D(C，E))。
在一棵表示有序集S的二叉搜索树(binary search tree)中，任意一条从根到叶结点的路径将S分为3部分：在该路径左边结点中的元素组成的集合S
1
；在该路径上的结点中的元素组成的集合S
2
；在该路径右边结点中的元素组成的集合S
3
。S=S
1
∪S
2
∪S
3
。若对于任意的a∈S
1
，b∈S
2
，c∈S
3
，是否总有a≤b≤c?为什么?