2011计算机等考二级公共基础知识讲义：第1章(7)

　　点击进入：2011计算机等考二级公共基础知识讲义汇总>>

　　1.7 查找技术

　　查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。

　　查找结果：(查找成功：找到;查找不成功：没找到。)

　　平均查找长度：查找过程中关键字和给定值比较的平均次数。

　　1、顺序查找

　　基本思想：从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者相符，查到所要找的元素为止。否则就是表中没有要找的元素，查找不成功。

　　在平均情况下，利用顺序查找法在线性表中查找一个元素，大约要与线性表中一半的元素进行比较，最坏情况下需要比较n次。

　　顺序查找一个具有n个元素的线性表，其平均复杂度为O(n)。

　　下列两种情况下只能采用顺序查找：

　　1)如果线性表是无序表(即表中的元素是无序的)，则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。

　　2)即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。

　　2、二分法查找

　　思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。

　　前提：必须在具有顺序存储结构的有序表中进行。

　　查找过程：

　　1)若中间项(中间项mid=(n-1)/2，mid的值四舍五入取整)的值等于x，则说明已查到;

　　2)若x小于中间项的值，则在线性表的前半部分查找;

　　3)若x大于中间项的值，则在线性表的后半部分查找。

　　特点：比顺序查找方法效率高。最坏的情况下，需要比较log2n次。

　　二分法查找只适用于顺序存储的线性表，且表中元素必须按关键字有序(升序)排列[注释1] 。对于无序线性表和线性表的链式存储结构只能用顺序查找。在长度为n的有序线性表中进行二分法查找，其时间复杂度为O(log2n)。（注释1：允许相邻元素值相等。）

　　1.8 排序技术

　　排序是指将一个无序序列整理成按值非递减顺序排列的有序序列，即是将无序的记录序列调整为有序记录序列的一种操作。

　　1、交换类排序法(方法：冒泡排序，快速排序)。

　　2、插入类排序法(方法：简单插入排序，希尔排序)。

　　3、选择类排序法(方法：简单选择排序，堆排序)。

　　总结：各种排序法比较

　　本章应考点拨：本章内容在笔试中会出现5-6个题目，是公共基础知识部分出题量比较多的一章，所占分值也比较大，约10分。

　　相关推荐：

　　2011计算机等考二级公共基础知识要点汇总

　　2010年9月计算机等级考试成绩查询时间汇总

　　2011年上半年计算机等级考试报名时间汇总