数据结构与算法-等级考试试题(程序员软考 2017年秋有序表查找)

单项选择（2017年秋程序员软考）

对关键码序列(9，12，15，20，24，29，56，69，87)进行二分查找(折半查找)，若要查找关键码15，则需依次与【】进行比较。

A、87、29、15

B、9、12、15

C、24、12、15

D、24、20、15

答案解析

C在该关键码序列中进行二分查找时，首先与中间元素24比较，若相等，则结束;若小于24，则继续在前4个元素中进行二分查找;否则在后4个元素中进行二分查找。查找15 时，需要与24、12和 15 依次进行...

查看完整答案

讨论

查找

在一个线性表上可以进行二分查找(折半查找)的充分必要条件是【】。

【】不符合二叉排序树的定义。

设有二叉排序树如下图所示，根据关键码序列【】可构造出该二叉排序树。

下列哪两个数据结构，同时具有较高的查找和删除性能【】

最优二叉树（哈夫曼树）、最优查找树均为平均查找路径长度wihi最小的树，其中对最优二叉树，n表示__________，对最优查找树，n表示__________，构造这两种树均__________。（1）结点数（2）叶结点数（3）非叶结点数（4）度为2的结点数（5）需要一张n个关键字的有序表（6）需要对n个关键字进行动态插入（7）需要n个关键字的查找概率表（8）不需要任何前提

用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。

若在线性表中采用折半查找元素，该线性表应该【】。

在分块检索中，对256个元素的线性表分成__________块最好，每块的最佳长度是__________；若每块的长度为8，其平均检索长度为__________。

有n个数存放在一维数组A[1..n]中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同。

在n个记录的有序顺序表中进行折半查找，最大的比较次数是__________。

静态查找表

用二分法查找一个线性表时，该线性表必须具有的特点是____________。

分块查找要求将待查找的表均匀地分成若干块，块中诸记录的顺序可以是任意的，但块与块之间____________。

在分块检索中，若索引表和各块内均用顺序查找，则有900个元素的线性表分成__________块最好；若分成25块，其平均查找长度为__________。

在有13个元素构成的有序表data[1..13]中，用折半查找(即二分查找，计算时向下取整)方式查找值等于data[8]的元素时，先后与【】等元素进行了比较。

折半(二分)查找法适用的线性表应该满足【】的要求。

对含有 600 个元素的有序顺序表进行折半查找，关键字之间的比较次数最多是【】

按照逻辑关系的不同可将数据结构分为【】。

若栈采用链式存储且仅设头指针，则【】时入栈和出栈操作最方便。

三个互异的元素a、b、c依次经过一个初始为空的栈后，可以得到【】种出栈序列。

递归函数执行时，其调用和返回控制是利用【】来进行的。

有序表查找

设有初始为空的栈S，对于入栈序列a、b、c、d，经由一个合法的进栈和出栈操作序列后(每个元素进栈、出栈各1次)，以c作为第一个出栈的元素时，不能得到的序列为【】。

队列采用如下图所示的循环单链表表示，左图表示队列为空，右图为e1、e2、e3依次入队列后的状态，其中，rear指针指向队尾元素所在结点，size为队列长度。以下叙述中，正确的是【】。

在单 CPU 计算机系统中，完成相同功能的递归程序比非递归程序【】

设元素a、b、c、d依次进入一个初始为空的栈，则不可能通过合法的栈操作序列得到【】。

表达式可采用后缀形式表示。例如，“a+b”的后缀式为“ab+”。那么，表达式“a*(b-c)+d”的后缀表示为【】

对于一个初始为空的栈，其入栈序列为 1,2,3,...,n(n>3)，若出栈序列的第一个元素是1则出栈序列的第n个元素【】

正规式(ab|c)(0|1|2)表示的正规集合中有【】个元素。

以下关于栈和队列的叙述中，错误的是【】。

设有字符串S和P，串的模式匹配是指确定【】。

对于一个初始为空的栈，其入栈序列为abc时，其出栈序列可以有【】种。