程序员考试同步辅导（下午科目）（第2版）（全国计算机技术与软件专业技术资格（水平）考试参考用书）

根据人力资源和社会保障部、工业和信息化部文件，计算机技术与软件专业技术资格（水平）考试纳入全国专业技术人员职业资格证书制度的统一规划。通过考试获得证书的人员，表明其已具备从事相应专业岗位工作的水平和能力，用人单位可根据工作需要从获得证书的人员中择优聘任相应专业技术职务（技术员、助理工程师、工程师、高级工程师）。计算机技术与软件专业实施全国统一考试后，不再进行相应专业技术职务任职资格的评审工作。 

本书是按照人事部(现为人力资源和社会保障部)、信息产业部(现为工业和信息化部)*颁布的全国计算机技术与软件专业技术资格(水平)考试大纲和指定教材而编写的考试用书。全书分为6章，内容包括：常用算法和数据结构，程序流程图和N-S图，C语言，C++语言，Java语言程序设计，程序员考试(下午科目)样卷与答案解析等，主要从考试大纲要求、考点辅导、典型例题分析和专项习题训练几个方面对各部分内容加以系统的阐释。
本书具有考点分析透彻、例题典型、习题丰富等特点，非常适合参加程序员考试的考生使用，也可作为高等院校或培训班的教材。

第1章 常用算法和数据结构
1.2 查找算法
1.2.1 考点辅导
1.2.1.1 查找的基本概念
所谓“查找”（检索）就是在一个含有众多数据元素（记录）的查找表中找出某个“特定的”数据元素。查找表是一种非常重要的数据结构，是由同一类型的数据元素（记录）构成的集合。在查找表中，通常通过查找其关键字是否等于给定值来确定查找是否成功。若查到其关键字等于给定值的记录，则称“查找成功”，否则，称“查找失败”。
对查找表而言，除了按关键字查找外，查找表的插入和删除是对查找表进行的另两个基本操作。
关键字是数据元素（记录）中某个数据项的值，可以标识一个记录，若能惟一标识，则称为主关键字，否则，称为次关键字。
考生特别要注意的是：在查找中是和关键字进行比较，而不是和数据元素进行比较，因而在算法描述中要体现关键字比较的特征。同时，考生要特别注意查找在顺序存储结构和链式存储结构上的区别。
查找的效率通过平均检索长度（ASL）和所需的辅助空间来确定。在查找其关键字等于给定值的过程中，需要与给定值进行比较的关键字个数的期望值称为检索成功时的平均检索长度。
……