全国计算机等级考试三级数据库考点分析之数据结构算法[4]

文章作者 100test 发表时间 2007:05:10 08:44:27
来源 100Test.Com百考试题网

计算机等级考试训练软件《百宝箱》

　　考点21散列表的存储和查找

散列存储中使用的函数称为散列(Hash)函数散列表(又称哈希表)是线性表的一种重要的存储方式 和检索方法。实现散列技术检索必须解决两个问题：一个是构造一个好的散列函数，尽可能避免冲突现象的发生；另一个是设计有效的解决冲突的方法。

1.散列函数

常用的散列函数有以下几种。

(l)除余法。选择一个适当的正整数川通常选p为不大于散列表存储区域大刁、的最大素数)，用p去除 关键码值，取其余数作为地址，即h(key)二key mod p。

(2)数字分析法。当关键码的位数比存储区域地址码位数多时，可以对关键码的各位进行分析，去掉分 布不均匀的位，留下分布均匀的位作为地址。

(3)折叠法。将关键码值从某些地方断开，分为几段，折叠相加，作为地址。

(4)中平方法。对关键码值求平方，取中间的几位数作为地址。

2.处理冲突的方法

发生冲突是指由关键字求得的散列地址为i(O-i-m一l)的位置上已存有记录，处理冲突就是为该关健字找到另一个“空”的散列地址。常用的处理冲突的方法有开地址法、拉链法等。

3.负载因子(装填因子)和平均检索长度

装填因子表示散列表的装满程度，定义为散列表中节点的数目除以基本区域能容纳的节点数所得的商，用a表示a越小，冲突的可能性越小，a越大，冲突的可能性越大，检索时需要比较的次数就越多。平均检索长度依赖于散列表的装填因子。

2.6排序

排序是数据处理领域经常要使用的一种运算，就是将一组元素按照关键码的递增或递减的顺序来排列为过程

按照排序过程中的存储器不同，可将排序方法分为内部排序和外部排序两类。一厂面将介绍插人排序、选择排序、交换排序和归并排序等几种常用的内部排序方法。

考点22插入排序

插人排序的基本思想：每一步将一个待排序的记录按其关键字值的大小插人到一个有序的文件中，插人后该文件仍然是有序文件。

l.直接插入排序

直接插人排序是一种最简单的排序方法它的基木思想是将一个记录插人到已排好序的有序表中，从而得到一个新的、记录数增I的有序表整个排序过程为：先将第一个记录看成是一个有序的子序列，然后从第2个记录起依次逐个地插人到这个有序的子序列中去。

直接插人排序的时间复杂度为0(n )。

直接插人排序方法不仅适用于顺序表，而且适用于单链表

2.二分法插入排序

在直接插人排序｝｝，，若采用二分法查找而不是顺序查找待插入元素的插人位置，则称为二分法插入排序这种插人排序可减少比较次数，使排序速度有所提高，但提高不会太多，因为移动记录的总次数不受改变，其时间复杂度仍为0(n2)。

直接插人和二分法插入排序方法都是稳定的，因为它们不会改变原序列中具有相同关键字记录的相对次序。

3.希尔排序

希尔排序又称缩小增量排序，它是对直接插人排序的一种改进方法希尔排序的基本思路：对相隔较大距离的记录进行比较，就能使记录在比较后移动较大的距离这样能使较小的记录尽快往前移，较大的记录尽快往后移，从而提高排序的速度

希尔排序是一种不稳定的排序过程

考点23选择排序

选择排序的基木思想是每次从待排序的记录中选出关键码值最小或最大的记录放在已排好序的记录序列后面，直至排序完毕。

1.直接选择排序

直接选择排序也是一种简单的排序方法。选择排序的基本方法是：每次从待排序的区间中选择出具有最小排序码的元素。把该元素与该区间的第一个元素交换位置。第一次待排序区间为A[1] ～A[n]，经过选择和交换后，A［1］为最小排序码的元素。第二次待排序区间为A[2]~A[n]，经过选择和交换后，A[2]为仅次于A［1］的具有最小排序码的元素，依次类推，经过n-1次选择和交换后，排序完毕。

直接选择排序方法的时间复杂度为O(n2)，此方法是不稳定的。

2.堆排序

堆的定义如下：n个元素序列{k¬.1,k2，…，kn}，当且仅当满足下列关系时，称之为堆。

人毛人Ki≤K2i, Ki≤K2i＋1，i＝1，2，…，n/2

堆排序的基本思想：对一组待排序的关键码，首先把它们按堆的定义排列成一个序列，找到其中最小的关键码．接着将最小的关键码取出，然后将剩下的关键码再建堆排序，依次进行，直到将全部关键码排好为止。建堆的基本方法是将大的元素下沉，小的元素上浮，即所谓的筛选法。

在最坏的情况下，堆排序时间复杂度为O(nlog2 n )。堆排序仅需一个记录大小的辅助存储空间。堆排序是不稳定的。

考点24交换排序

交换排序的基本思想：两两比较待排序记录的关键字值，并交换不满足顺序要求的那些记录，直到全部记录满足关键字值排序要求为止。

1.起泡排序

起泡排序又称为冒泡排序，其基本思想是通过相邻记录之间关键字的比较和交换，使关键字值较小的记录逐渐从底部移向顶部，即从下标较大的单元移向下标较小的单元，关键字较大的记录从顶部移向底部。从起泡排序算法可以看出，若初始序列为“正序”序列，则只需进行一趟排序；反之，若初始序列为“逆序”序列，则需进行。一I趟排序。因此，总的时间复杂度为。(矿)。

起泡排序是一种稳定的排序过程。

2.快速排序

快速排序是口前内部排序中速度最快的一种排序算法，其实质是对起泡排序的改进在快速排序中，记录的比较和交换是从两端向中间进行的，排序码较大的记录一次就能够从前面交换到后面单元，排序码较小的记录一次就能够从后面交换到前面单元，记录每次移动的距离较远，总比较和移动次数较少。

快速排序是不稳定的排序。排序速度最快时，其时间复杂度为0 ( nlog, n )；排序速度最慢时，其时间复杂度为。(n`)快速排序的平均时间复杂度为0 (nlog2 n )。快速排序除了需要一个记录的辅助空间来存放每次选取的基准记录外，还需要一个栈空间来实现递归。

考点25归并排序

归并是将两个或者多个有序表合并成一个有序表归井排序要求待排序文件已经部分排序。归并排序的基本思想是将这些已排过序的文件进行合并，得到完全排序的文件。

假设初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或I的有序子序列，再两两归并，如此重复，直到得到一个长度为n的有序序列为止。这种排序方法称为二路归并排序。

归并排序平均时间复杂度为0(n1092 n )，辅助空间为0(n)。