数据结构与算法-等级考试试题(二级考试 2006年4月内部排序)

填空题（2006年4月二级考试）

对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为__________。

答案解析

45

【解析】

在最坏的情况下，冒泡排序要经过n/2遍的从前往后的扫描和n/2的从后往前的扫描，需要的比较次数为n(n-1)/2，所以比较的次数为10×(10-1)/2=45。

讨论

数据结构与算法

在深度为7的满二叉树中，叶子结点的个数为【】

下列描述中，正确的是【】

按照“后进先出”原则组织数据的数据结构是【】

某二叉树中度为2的结点有18个，则该二叉树中有__________个叶子结点。

有n个数顺序（依次）进栈，则出栈顺序有Cn种。Cn=×

设栈的输入序列是（1，2，3，4），则【】不可能是其出栈序列。

栈的输入序列为1,2,3,...,n，输出序列为a1,a2,a3,...,an，若ai=n(1≤i≤n)，则有 ak>ak+1>an。

设栈的输入序列为1,2,3,...,n，输出序列为a1,a2,a3,...,an，若存在1≤k≤n使得 ak=n，则当k≤i≤n时，ai 为【】

没有提供指针类型的语言，无法构造链式结构，该说法【】

如果入栈序列为ABCD，不可能出现的出栈序列是【】

内部排序

下列排序算法中，哪些时间复杂度不会超过nlogn【】。

初始序列为1 8 6 2 5 4 7 3一组数采用堆排序，当建堆（小根堆）完毕时，堆所对应的二叉树中序遍历序列为【】。

下列排序算法中，不稳定的是【】。Ⅰ. 希尔排序Ⅱ. 归并排序Ⅲ. 快速排序Ⅳ. 堆排序Ⅴ. 基数排序

使用快速排序算法对数据进行升序排序，若经过一次划分后得到的数据序列是 68, 11, 70, 23, 80, 77, 48, 81, 93, 88，则该次划分的轴枢【】。

下述排序算法中，所需辅助存储量最多的是__________，所需辅助存储量最少的是__________，平均速度最快的是__________。A. 快速排序 B. 归并排序 C. 堆排序

若有n个元素已构成一个小根堆，那么如果增加一个元素Kn+1，请用文字简要说明如何在log2n的时间内将其重新调整为一个堆。

序列【】可能是第一趟冒泡排序后的结果。

若待排序记录按关键字基本有序，则宜采用的排序方法是【】。

在待排序的一组关键码序列k1，k2，…，kn中，若ki和kj相同，且在排序前ki领先于kj，那么排序后，如果ki和kj的相对次序保持不变，ki仍领先于kj，则称此类排序为稳定的。若在排序后的序列中有可能出现kj领先于ki的情形，则称此类排序为不稳定的。【】是稳定的排序方法。

对n个记录进行非递减排序，在第一趟排序之后，一定能把关键码序列中的最大或最小元素放在其最终排序位置上的排序算法是【】。

#tts_2#

#tis_2#