2017年大连理工大学电子信息与电气工程学部810数(13)

【解析】当初始数据表有序，此时快速排序所需要比较的次数最多，快速排序算法的时间复杂度为〇（n2）。

三、算法设计题

28．已知顺序表中有m个记录，表中记录不依关键字有序排列，编写算法为该顺序表建立一个有序的索引表，索引表中的每一项含记录的关键字和该记录在顺序表中的序号，要求算法的时间复

杂度在最好的情况下能达到

【答案】算法如下：

29．设T是一棵满二叉树，写一个把T的后序遍历序列转换为前序遍历序列的递归算法。

【答案】算法如下：

//将满二叉树的后序序列转为前序序列，11、hl、12、h2是序列初始和最后结点的下标。

//根结点

//左子树或右子树的结点数

//将左子树前序序列转为

后序序列

后序序列

30．设二叉树用二指针结构存储（可以是动态存储结构），元素值为整数，且元素值无重复，请编写子程序，求出以元素值等于某个给定的整数的结点为根的子树中的各个叶结点。

【答案】算法如下：

//将右子树前序序列转为