冒泡排序法的平均执行时间是O（n2），而快速排序法的平均执行时间是O（nlog2n）。

1.7例题详解

一、选择题

【例1】算法的时间复杂度取决于。（考点2）

A）问题的规模

C）问题的难度

B）待处理的数据的初态

D）A）和B）

解析：算法的时间复杂度不仅与问题的规模有关，在同一个问题规模下，而且与输入数据有关。即与输入数据所有的可能取值范围、输入各种数据或数据集的概率有关。

答案：D）

【例2】在数据结构中，从逻辑上可以把数据结构分成。（考点3）

A）内部结构和外部结构C）紧凑结构和非紧凑结构

B）线性结构和非线性结构

D）动态结构和静态结构

解析：逻辑结构反映数据元素之间的逻辑关系，线性结构表示数据元素之间为一对一的关系，非线性结构表示数据元素之间为一对多或者多对一的关系，所以答案为B）。

答案：B）

【例3】以下不是栈的基本运算。（考点5）

A）判断栈是否为素空B）将栈置为空栈

C）删除栈顶元素D）删除栈底元素

解析：栈的基本运算有：入栈，出栈（删除栈顶元素），初始化、置空、判断栈是否为空或满、提取栈顶元素等，对栈的操作都是在栈顶进行的。

答案：D）

【例4】链表不具备的特点是。（考点6）A）可随机访问任意一个结点

C）不必事先估计存储空间

B）插入和删除不需要移动任何元素D）所需空间与其长度成正比

解析：顺序表可以随机访问任意一个结点，而链表必须从第一个数据结点出发，逐一查找

每个结点。所以答案为A）。

答案：A）

【例5】已知某二叉树的后序遍历序列是DACBE，中序遍历序列是DEBAC，则它的前序遍

历序列是。（考点8）

A）ACBED

C）DECAB

B）DEABC

D）EDBAC

解析：后序遍历的顺序是"左子树－右子树－根结点"；中序遍历顺序是"左子树－根结点－右子树"；前序遍历顺序是"根结点－左子树－右子树"。根据各种遍历算法，不难得出前序遍历

序列是EDBAC。所以答案为D）。

答案：D）

【例6】设有一个已按各元素的值排好序的线性表（长度大于2），对给定的值k，分别用顺序查找法和二分查找法查找一个与k相等的元素，比较的次数分别是s和b，在查找不成功的情况下，s和b的关系是。（考点9）

A）s=b B）s>b C）s

解析：对于顺序查找，查找不成功时和给定关键字比较的次数为n+1。二分查找查找不成功的关键字比较次数为［log2n］+1。当n≥2时，显然n+1>［log2n］+1。

答案：B）