数据结构-第10章习题(ppt文档)

while (low<high && L.r[high].key>=pivotkey)
_______(___)_______;
L.r[low]=L.r[high]; //将小于枢轴的记录移到低端
while (low<high && L.r[low].key<=pivotkey)
++low;
L.r[high]= __(___)__; 高端
1 [12] 49 32 86 57* 65 57 28
2 [12 28] 32 86 57* 65 57 49 ......
13:30:50
CH.6
9
习题—分析题
已知关键字序列，画出堆排序第一次的建堆过程
i r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8]
28 49 32 86 12 65 77 51
____。 27、 锦标赛排序的时间复杂度T(n) 为____。 28、 后序遍历二叉树算法在最坏情况下的空
间复杂度S(n)为____（设二叉树的结点数为 n）。
13:30:50
CH.6
7
习题—分析题
已知关键字序列，画出快速排序第一次递归划分后的结 果。
i r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8] 57 49 32 86 12 65 57* 28 ^
RcdType temp;
KeyType pivotkey;
temp=L.r[low];
//保存L.r[low]为枢轴记录
pivotkey=L.r[low].key; 的关键字
//取L.r[low].key为枢轴
13:30:50
CH.6
16
习题—编程题
while (_______(___)_______<high) {
20、 堆排序的时间复杂度T(n)为____。 21、 堆排序的空间复杂度S(n) 为____。 22、 二路归并的时间复杂度T(n) 为
____。
13:30:50
CH.6
6
习题—填空题
23、 二路归并的空间复杂度S(n) 为____。 24、 冒泡排序的时间复杂度T(n)为____。 25、 起泡排序的空间复杂度S(n) 为____。 26、 树形选择排序的时间复杂度T(n) 为
//直接插入排序
int i,j;
for(i=2;i<=L.length;i++)
//==比较
if(LT(L.r[i].key,L.r[i-1].key)) {

L.r[0]= L.r[i];

L.r[i]= _______(___)_______;
//==后移

for(j=i-2;LT(L.r[0].key,L.r[j].key);--j)
1
86 51 77 49 12 65 32 28
28
86
49
86
12
32
65
77
51
49
12
77
65
32
51
13:30:50
28
CH.6
10
习题—分析题
已知关键字序列，画出堆排序第二次的建堆过程
i r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8] 28 49 32 86 12 65 77 51
34.已知某排序基本操作的头文件，试写出堆排序函数中建堆 函数HeapAdjust(HeapType &H,int s,int m) 实现的算法。
void HeapAdjust(HeapType &H,int s,int m){//对H.r[s..m]建堆
int j;
RcdType rc;
rc=H.r[s];
int pivotloc;
if (low<_______(___)_______){
pivotloc=Partition(L,low,high);
Output_Data_List1(L,pivotloc);//==输出中间结果
QSort(_______(___)_______);
_______(___)_______ (L,pivotloc+1,high);
H.r[s]=H.r[j];
_______(___)_______;
N
13:30:50
CH.6
4
习题—填空题
11、 有n个关键字的序列K1,K2,……Kn 称为小根堆，当且仅当Ki≤K2i 且 ___。
12、 有n个关键字的序列K1,K2,……Kn 称为大根堆，当且仅当Ki≥K2i 且 ___。
13、 顺序查找的平均时间复杂度T(n)为 ____。
14、 二分查找的平均时间复杂度T(n)为 ____。
void HeapSort(HeapType &H) {
//堆排序
int i;
for (i=_______(___)_______;i>0;--i)
HeapAdjust(H,i,H.length);//把H.r[1..H.length]建成大顶堆
for (i=_______(___)_______;i>1;--i) {
void SelectSort(SqList &L) {//简单选择排序
int i,j;
for(i=1; _______(___)_______;i++) { j=SelectMinKey(L,i);//在L.r[i..L.length]中找最小的记录
if (i!= _______(___)_______) { Swap_record(____(___)____); //交换 Output_Data_List1(L,i);//==输出中间结果
int length;
//顺序表长度
}SqList;
//顺序表类型
//== 2.2 采用顺序表存储表示的堆
typedef SqList HeapType;
13:30:50
CH.6
13
习题—编程题
//== 3. 定义基本操作
//== 3.1 插入排序
void InsertSort(SqList &L) {
15、 直接插入排序的空间复杂度S(n)为 ____。
16、 快速排序的时间复杂度T(n)为 ____。
13:30:50
CH.6
5
习题—填空题
17、 快速排序的空间复杂度S(n) 为 ____。。
18、 直接选择排序的时间复杂度T(n)为 ____。
19、 直接选择排序的空间复杂度S(n) 为____。
}
}//QSort
CH.6
15
习题—编程题
31.已知某排序基本操作的头文件，试写出快速排序函 数中的分区函数 Partition(SqList &L,int low,int high) 实现的算法。
int Partition(SqList &L,int low,int high) {//快速排序中的 分区
//将大于枢轴的记录移到
}
L.r[low]=temp;
//定位枢轴记录
return low;
}//Partition
13:30:50
CH.6
17
习题—编程题
32.已知某排序基本操作的头文件如下，试写出简单选择排序 函数 SelectSort(SqList &L)实现的算法，可以调用 SelectMinKey(SqList L,int i)和Swap_record(RcdType &x,RcdType &y)函数。
2、 快速排序属于_____。
[A]: 插入排序 [B]: 交换排序 [C]: 选择排序 [D]: 归并排序
3、 堆排序属于_____。
[A]: 插入排序 [B]: 交换排序 [C]: 选择排序 [D]: 归并排序
CH.6
2
习题—选择题
4、 _____是稳定的。
//保存当前堆顶记录
for (j=2*s; _______(___)_______;j*=2) {
if (j<m && LT(H.r[j].key,H.r[j+1].key))
___(___)___; // j 为两个孩子中key较大者
if (!LT(rc.key,H.r[j].key)) break;
#define MAXSIZE 20 //数据表的最大长度
typedef struct {
KeyType key;
//关键字
InfoType otherinfo;
//其他数据项
}RcdType;
//记录类型
typedef struct {
RcdType r[MAXSIZE+1]; //r[0]闲置或用作哨兵单元
}
}
}//SelectSort
13:30:50
CH.6
18
习题—编程题
33.已知某排序基本操作的头文件如下，试写出堆排序函数 HeapSort(HeapType &H)实现的算法，可以调用 HeapAdjust(HeapType &H,int s,int m)和 Swap_record(RcdType &x,RcdType &y)函数。
13:30:50
CH.6
3
习题—判断题
7、排序算法的稳定性是指：是否允许出现关 键字相同的数据元素。