数据结构习题11级用(14)

15．对于关键字序列{72,73,71,23,94,16,5,68,76,103}，用筛选法建堆，必须从

关键字为（ ）的结点开始。

A． 103 B 72 C 94 D． 23 16．以下序列中，（ ）不是堆。

A． {15,26,38,49,27,51,39,62} B {15,23,26,72,94,71,68,73} C {15,23,71,94,72,68,26,73} D． {15,23,26,68,94,72,71,73}

二、填空题

1．对于n个记录的序列进行冒泡排序，在最坏情况下的时间复杂度是 ；在

最好情况下的时间复杂度是 。 2．最简单的交换排序方法是 。

3．在插入和选择排序中，若初始数据基本正序或反序，则选用 ；若初始

数据无序，则选用 。

4．在堆和快速排序中，若初始数据基本有序，则选用 ；若初始数据基本

反序，则选用 。

5. 归并排序的时间复杂度为 。

6. 快速排序是一种 类型的排序；对含有n个元素的序列进行排序时，快速

排序的时间复杂度是 。

7．对具有n个记录的序列进行快速排序，在最坏情况下的时间复杂度是 ；

在最好情况下的时间复杂度是 。

8．对具有n个元素的序列采用堆排序法进行排序，排序趟数为 。 9．在时间复杂度为O(logn)的所有排序方法中， 排序方法是稳定的。 10．在时间复杂度为O(n2)的所有排序方法中， 排序方法是不稳定的。

三、基础知识题

1．以关键字序列（25,84,21,47,15,27,68,35,20）为例，手工执行各种排序算法，写出每一趟排序结束时的关键字状态。

2. 对长度为n的记录序列进行快速排序时，所需进行的比较次数依赖于这n个元素的初始排列。

(1) n=7时在最好情况下需进行多少次比较？请说明理由。 (2) 对n=7给出一个最好情况的初始排列实例。

42

3．试按堆的构造方法，写出对应于序列(26,5,77,1,61,11,59,15,48,19)的初始堆（大根堆、小根堆均可，要求给出调整过程）。

4．判别以下序列是否为堆（小根堆或大根堆）。如果不是，则把它调整为堆（要求记录交换次数最少）。

(1) (100,86,48,73,35,39,42,58,66,22); (2) (12,70,33,65,24,56,46,90,86,33)。

5. 对初始关键字序列(E,D,X,K,H,L,M,C,P)，请画出筛选法建堆的过程。 6．请回答下列关于堆的一些问题：

(1) 堆的存储表示是顺序的，还是链式的？

(2) 设有一个小根堆，则具有最大值的元素可能在什么地方？

(3) 对n个元素进行初始建堆的过程中，最多做多少此数据比较（不用大O表示

法）？

7．分别利用折半插入排序法和2-路归并排序法对含4个记录的序列进行排序，画出描述该排序过程的判定树，并比较它们所需进行的关键字间的比较次数的最大值。 8．对一个由n个关键字不同的记录构成的序列，你能否用比2n-3少的次数选出这n个记录中关键字取最大值和关键字取最小值的记录？若能，请说明如何实现？在最坏情况下至少进行多少次比较？

四、算法设计题

1．以带头结点的单链表为存储结构实现简单选择排序，排序的结果是单链表按关键字的值升序排列，试编写此算法。

2．编写算法，对n个关键字去整数值的记录序列进行整理，以使所有关键字为负值的记录排在关键字为非负值的记录之前，要求：

(1) 采用顺序存储结构，至多使用一个记录的辅助存储空间； (2) 算法的时间复杂度为O(n)；

(3) 讨论算法中记录的最大移动次数。

3．编写一个双向冒泡的排序算法，即相邻两遍向相反方向冒泡。

4．输入若干国家名称，请编写算法按字典顺序将这些国家进行排序（设所有的名称均用大写或小写表示）。

5．荷兰国旗问题：设有一个仅有红、白、蓝3种颜色的条块组成的条块序列。请编写一个时间复杂度为O(n)的算法，使得这些条块按红、白、蓝的顺序排列，即排成荷兰国旗图案。

43