数据结构导论2014年10月真题及答案解析（02142）

假设线性表中结点是按键值递增的顺序排列，试编写一个顺序查找算法，将岗哨设在高下标端。并说明等概率情况下查找成功和不成功时的平均查找长度。

单链表的结构定义如下：

typedef struct node

{ int data;

   struct node *next;

}Node, *LinkList;

试编写算法int CountLinklist(LinkList head,int x)实现在带头结点的单链表head中计算值为x的结点数。

判断序列(28，75，33，68，25，56，47，99，86，36)是否为堆?如果不是，则把它调整为堆(最小堆)。

将题32图所示的一棵树转换为二叉树。

分别写出题30图所示二叉树的先序遍历、中序遍历和后序遍历的结点序列。

写出题31图所示有向图顶点的所有拓扑排序序列。

最好情况下，冒泡排序算法的时间复杂度为_______，它是一种稳定的排序方法。

如题29图所示，在栈的输入端元素的输入顺序为A，5，8，试写出在栈的输出端可以得到的以数字开头的所有输出序列，并写出进栈、出栈的操作过程(用push(X)表示X进栈，pop(x)表示x出栈)。

二叉排序树上的平均查找长度介于________和O(n)之间。

二分查找算法的时间复杂度是________。