程序员历年答案分析2005---2011年全部详细答案(16)

散列查找是根据关键码与表项存储位置的映射关系，进行高效、精确的查找，所以也需要采

用顺序存储结构。

二分查找又称为折半查找法，它是一种高效的查找方法，并且要求表按关键字排序，并使用

顺序存储结构。

顺序查找就是从表的一端开始，顺序扫描线性表，一次将扫描得到的节点关键字和给定值k

相比较，如果相等则表示查找成功，如果扫描到最后还没有找到相等的节点，则查找失败。

所以，顺序查找是链式存储结构最合适的查找方法。

●试题答案（32）C

【考查知识点】本题考查的是数据结构中的字符串。

【解析】字符串“computer”长度为3的子串为“com”、“omp”、“mpu”、“put”、“ute”和

“ter”，一共6个。

●试题答案（33）A （34）C

【考查知识点】本题考查的是堆栈。

【解析】根据题意，对于表达式“（a+b*(a+b)/c）+(a+b)”进行检查时，首先是两个“（”

入栈，然后连续三次“）”出栈，这就会导致第3次出现“栈为空却要进行出栈操作的命令”。

选项A为正确答案。

对于表达式“（（a+b/(a+b)-c/a）/b”进行检查时，首先是连续三个“（”入栈，然后是两个

“）”出栈，这样表达式检查结束时，栈中仍有字符“（”，所以选项C为正确答案。

●试题答案（35）C （36）D

【考查知识点】本题考查的是数据结构中排列算法的堆排序。

【解析】堆排序是利用堆这一特殊树形结构进行的选择排序，它有效地改进了直接排序，提

高了算法的效率。堆排序的基本思想是：对一组待排序记录，首先把他们按堆定义排列成一

个序列（称为初始建堆），堆顶元素为最小或最大关键字的记录，将堆顶元素输出；然后对

剩余的记录再建堆，得到次最小或最大关键字记录；如此反复进行，直到全部记录有序为止。

堆是顺序存储的完全二叉树：若从0开始对树的结点按层，同一层再按从左到右的次序进行

编号，则编号为0 ～[n/2]-1的结点为分支结点，编号大于[n/2]-1的结点为叶结点，对于

每个编号为i的分支结点，它的左子女结点的编号为2i+1，它的右子女结点的编号为

[(i-1)/2]。

●试题答案（37）B （38）C

【考查知识点】本题主要考查的是程序语言设计中的循环结构。

【解析】do-while和while-do两者同属于循环结构，但两者却有本质的不同：do-while

循环是先执行循环体后判断循环条件，也就是说至少会执行一次循环体，循环条件的判断次

数与循环体的执行次数是相等的；while-do循环是先判断循环条件再执行循环体，即循环

体可能一次都不执行，循环条件的判断次数比循环体的执行次数多一次。

经过以上分析，在循环体执行次数同为m次的情况下，do-while执行次数为m，while-do

的执行次数为m-1。

●试题答案（39）D

【考查知识点】本题考查的是程序语言的语句分类。

【解析】程序的语句大体可以分为两大类：一是程序语句，是用来实际执行功能的程序；二

是注释语句，用来解释说明程序的功能。

●试题答案（40）A （41）B

【考查知识点】本题考查的是C语言的编译过程。

【解析】在C语言中，表达式x%m要求x和m都是整数，若x是一个浮点型变量，则无法通

过编译，因此会在编译时报错。