写出在顺序存储结构下将线性表逆转的算法，要求使用最少的附加空间。

(1)【◆题库问题◆】：[问答题] 写出在顺序存储结构下将线性表逆转的算法，要求使用最少的附加空间。

【◆参考答案◆】：输入：长度为n的线性表数组A（1：n）输出：逆转后的长度为n的线性表数组A（1：n）。C语言描述如下（其中ET为数据元素的类型）：invsl(n,a)int n;ET a[];{int k;ET t;for (k=1; k<=n/2; k++){t=a[k-1]; a[k-1]=a[n-k]; a[n-k]=t;}return; }

(2)【◆题库问题◆】：[判断题] 一个栈的输入序列是12345，则栈的输出序列不可能是12345。
A．正确
B．错误

【◆参考答案◆】：正确

【◆答案解析◆】：有可能。

(3)【◆题库问题◆】：[填空题] 在一棵二叉排序树中，每个分支结点的左子树上所有结点的值一定（）该结点的值，右子树上所有结点的值一定（）该结点的值。

【◆参考答案◆】：小于；大于

(4)【◆题库问题◆】：[单选] 在下列情况中，可称为二叉树的是（）。
A．每个结点至多有两棵子树的树
B．哈夫曼树
C．每个结点至多有两棵子树的有序树
D．每个结点只有一棵子树

【◆参考答案◆】：B

(5)【◆题库问题◆】：[填空题] 在索引查找中，假定查找表（即主表）的长度为96，被等分为8个子表，则进行索引查找的平均查找长度为（）。

【◆参考答案◆】：11

(6)【◆题库问题◆】：[名词解释] 广度遍历

【◆参考答案◆】：
按层次编历方式，从某一点V0开始遍历它的所有邻接点V1，V2……，再依次访问V1，V2..的所有未被访问过的邻接点，直到所有的点均遍历完成。

(7)【◆题库问题◆】：[判断题] 数据的存储结构是数据的逻辑结构的存储映象。
A．正确
B．错误

【◆参考答案◆】：正确

(8)【◆题库问题◆】：[判断题] 一个图的广度优先搜索树是惟一的
A．正确
B．错误

【◆参考答案◆】：正确

(9)【◆题库问题◆】：[问答题] 有一关键字序列（265，301，751，129，937，863，742，694，076，438），写出希尔排序的每趟排序结果。（取增量为5，3，1）

【◆参考答案◆】：初始：265，301，751，129，937，863，742，694，076，438d=5：265，301，694，076，438，863，742，751，129，937d=3：076，301，129，265，438，694，742，751，863，937d=1：076，129，265，301，438，694，742，751，863，937

(10)【◆题库问题◆】：[名词解释] 时间复杂度

【◆参考答案◆】：
一般情况下，算法中基本操作的重复次数是问题规模n的某个函数f（n），算法的时间度量记作T（n）=O（f（n）），表示随着问题规模n的增大，算法执行时间增长率和f（n）的增长率相同，称为时间复杂度。