性表的最后。r
然后，从后到前扫描剩下的线性表，逐次比较相邻两个元素的大小，若后面的元素小于前面的元素，则将它们互换，不断地将两个相邻元素中的小者往前移动，最后最小者到了线性表的最前面。r
对剩下的线性表重复上述过程，直到剩下的线性表变空为止，此时已经排好序。r
在最坏的情况下，冒泡排序需要比较次数为
（
－1）2。r
（2）快速排序法r
它的基本思想是：任取待排序序列中的某个元素作为基准（一般取第一个元素），通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。r
r
疑难解答：冒泡排序和快速排序的平均执行时间分别是多少？r
冒泡排序法的平均执行时间是O（
2），而快速排序法的平均执行时间是O（
log2
）。r
r
17例题详解r
一、选择题r
【例1】算法的时间复杂度取决于_______。（考点2）r
A）问题的规模B）待处理的数据的初态r
C）问题的难度D）A）和B）r
解析：算法的时间复杂度不仅与问题的规模有关，在同一个问题规模下，而且与输入数据有关。即与输入数据所有的可能取值范围、输入各种数据或数据集的概率有关。r
答案：D）r
【例2】在数据结构中，从逻辑上可以把数据结构分成_______。（考点3）r
A）内部结构和外部结构B）线性结构和非线性结构r
C）紧凑结构和非紧凑结构D）动态结构和静态结构r
解析：逻辑结构反映数据元素之间的逻辑关系，线性结构表示数据元素之间为一对一的关系，非线性结构表示数据元素之间为一对多或者多对一的关系，所以答案为B）。r
答案：B）r
【例3】以下_______不是栈的基本运算。（考点5）r
A）判断栈是否为素空B）将栈置为空栈r
C）删除栈顶元素D）删除栈底元素r
解析：栈的基本运算有：入栈，出栈（删除栈顶元素），初始化、置空、判断栈是否为空或满、提取栈顶元素等，对栈的操作都是在栈顶进行的。r
答案：D）r
【例4】链表不具备的特点是_______。（考点6）r
A）可随机访问任意一个结点B）插入和删除不需要移动任何元素r
C）不必事先估计存储空间D）所需空间与其长度成正比r
解析：顺序表可以随机访问任意一个结点，而链表必须从第一个数据结点出发，逐一查找每个结点。所以答案为A）。r
答案：A）r
【例5】已知某二叉树的后序遍历序列是DACBE，中r