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

文章作者 100test 发表时间 2007:05:13 21:48: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)，此方法是不稳定的。