数据结构及算法第9章 学生基本信息排序

第九章查找一、选择题1•若查找每个记录的概率均等，则在具有n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL 为()。

A ．(n-1)/2B.n/2C.(n+1)/2D.n 2. 下面关于二分查找的叙述正确的是()A. 表必须有序，表可以顺序方式存储，也可以链表方式存储C.表必须有序，而且只能从小到大排列B. 表必须有序且表中数据必须是整型，实型或字符型D.表必须有序，且表只 能以顺序方式存储3. 用二分(对半)查找表的元素的速度比用顺序法() A. 必然快B.必然慢C.相等D.不能确定4. 具有12个关键字的有序表，折半查找的平均查找长度()A.3.1B.4C.2.5D.55．当采用分块查找时，数据的组织方式为()A. 数据分成若干块，每块内数据有序B. 数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块C. 数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块D. 数据分成若干块，每块(除最后一块外)中数据个数需相同6. 二叉查找树的查找效率与二叉树的((1))有关,在((2))时其查找效率最低(1) ：A.高度B.结点的多少C.树型D.结点的位置(2) :A.结点太多B.完全二叉树C.呈单枝树D.结点太复杂。

7. 对大小均为n 的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找失败,它们的平均查找长度是((1)),对于查找成功,他们的平均查找长度是((2))供选择的答案:A.相同的B.不同的9．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是()A ．(100，80，90，60，120，110，130)B.(100，120，110，130，80，60，90) C. (100，60，80，90，120，110，130)D.(100，80，60，90，120，130，110)10. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A 的左孩子的平衡因子为0右孩子的平衡因子为1，则应作()型调整以使其平衡。

KCN i n(n 1) / 2 n 2 / 2, RMN (i 2) (n 4)(n 1) / 2 n 2 / 2
i 1 i 1 n 1 n 1
140-14


平均情况下排序的时间复杂度为 o(n2)。 直接插入排序是一种稳定的排序方法。
折半插入排序 (Binary Insertsort)

基本思想是 : 设在顺序表中有一 个元素序列 V[0], V[1], …, V[n-1]。其中, V[0], V[1], …, V[i-1] 是已经排好序的元素。在插入V[i] 时, 利 用折半搜索法寻找V[i] 的插入位置。
折半插入排序的算法
#include "dataList.h"
140-15
插入排序 (Insert Sorting)

基本方法是：每步将一个待排序的元素，按其 排序码大小，插入到前面已经排好序的一组元 素的适当位置上, 直到元素全部插入为止。
直接插入排序 (Insert Sort)

基本思想是 : 当插入第i (i≥1) 个元素时，前面 的V[0], V[1], …, V[i-1]已经排好序。这时，用 V[i]的排序码与V[i-1], V[i-2], …的排序码顺序 进行比较，插入位置即将V[i]插入，原来位置 上的元素向后顺移。
140-11
直接插入排序的算法
#include "dataList.h" template <class T> void InsertSort (dataList<T>& L, int left, int right) { //依次将元素L.Vector[i]按其排序码插入到有序表 //L.Vector[left],…,L.Vector[i-1]中,使得 //L.Vector[left]到L.Vector[i]有序。 Element<T> temp; int i, j; for (i = left+1; i <= right; i++) if (L[i] < L[i-1]) { temp = L[i]; j = i-1;

2 插入排序


9.2.3 希尔排序
3.算法



void ShellSort() { gap=n/2;//初次增量取序列元素个数n的一半为步长 while(gap>0) { for(i=gap+1;i<=n;i++) { j=i-gap; while(j>0) { if(r[j]>r[j+gap]) { x=r[j];r[j]=r[j+gap];r[j+gap]=x; j=j-gap; }//对子序列作直接插入排序 else j=0; } } gap=gap/2;}//每次减半，直至步长为1 上一页 }
上一页
下一页
9.3 快速排序法


9.3.2 快速排序
3【例9-5】对数据序列:70, 75, 69, 32, 88, 18, 16, 58进行快速排序如图9-3所示。 4.算法


void QuickSort(int low, int high)//递归形式的快速排序 { int pivotpos; if(low<high) { pivotpos=Partition(low,high); QuickSort(low,pivotpos-1);//对低子表递归排序 QucikSort(pivotpos+1,high);//对高子表递归排序 } }
9.2 插入排序


9.2.2 二分插入排序
3.算法



void BinsSort() { for(i=2;i<=n;i++) { r[0]=r[i];low=1;high=i-1;//将r[i]暂存到r[0] while(low<=high) //在r[low..high]中折半查找有序插入的位置 { m=(low+high)/2;//折半 if(r[0].key<r[m].key) high=m-1;//插入点在低半区 else low=m+1;//插入点在高半区 } for(j=i-1;j>high+1;--j) r[j+1]=r[j];//记录后移 r[high+1]r[0];//插入 } 上一页 下一页

R[3] 10
R[4] 60
R[5] 25
R[6] 30
R[7] 18 18 18 18
18 36 20

10 10 36
60 60 60
25 25 25
30 30 30
【算法】直接插入排序 void D_InsertSort(datatype R[ ], int n) { /*对排序表R[1]..R[n]进行直接插入排序，n是记录的 个数*/ for(i=2; i<=n; i++) if (R[i].key<R[i-1].key) {R[0]=R[i]; /*将R[i]插入R[1].. R[i-1]中， R[0]为监测哨*/ for(j=i-1; R[0].key<R[j].key; j--) R[j+1]=R[j]; /*后移记录*/ R[j+1]=R[0]; /*插入到合适位置*/ } }
空间性能：除排序表以外的内存占用情况。 时间性能：比较关键码的次数，数据移动的次数。 它们往往是排序表规模（n）的函数
6. 记录和排序表的数据结构
一般采用顺序结构存储排序表。 记录和排序表的类型定义如下： #define MAXNUM … /* MAXNUM 为足够大的数 typedef struct { keytype key; …… } datatype; datatype R[MAXNUM]; /*关键码字段*/ /*其它信息*/ /*记录类型*/ /*定义排序表的存储
第一趟排序结果，使得间隔为5的字表有序： P=3
29 7 41 30 11 39 50 76 41 13 10 0 80 78 86
子序列分别为:{29,30,50,13,78}，{7,11,76,100,86}， {41,39,41,80}。第二趟排序结果： P=1