2. 专升本
  3. 将下面折半查找算法补充完整。 算法说明：已知r[1…n]是n个记录的递增有序表，用折半查找法查找关键字为k的记录，若查找失败返回零；否则返回该记录的序号值。查找表顺序存储结构定义如下： #define MAXSIZE 100 typedef struct

将下面折半查找算法补充完整。 算法说明：已知r[1…n]是n个记录的递增有序表，用折半查找法查找关键字为k的记录，若查找失败返回零；否则返回该记录的序号值。查找表顺序存储结构定义如下： #define MAXSIZE 100 typedef struct

admin2014-08-29  121
问题 将下面折半查找算法补充完整。
算法说明：已知r[1…n]是n个记录的递增有序表，用折半查找法查找关键字为k的记录，若查找失败返回零；否则返回该记录的序号值。查找表顺序存储结构定义如下：
#define MAXSIZE 100
typedef struct
{
keytype key；
}Nodetype；
typedef Nodetype Sqlist[MAXSIZE]；
算法(C函数)：
int binsearch(Sqlist r，datatype k，int n)
{
int low=1，high=
选项
答案10w<=high mid=(10w+high)／2；return mid；high=mid一1；low=mid+1；
解析 折半查找的基本思想是：首先以整个查找表作为查找范围，用查找条件中给定值k与中间位置结点的关键字比较，若相等，则查找成功；否则，根据比较结果缩小查找范围，如果k的值小于关键字的值，根据查找表的有序性可知查找的数据元素只有可能在表的前半部分，即在左半部分子表中，所以继续对左子表进行折半查找；若k的值大于中间结点的关键字值，则可以判定查找的数据元素只有可能在表的后半部分，即在半部分子表中，所以应该继续对右子表进行折半查找。每进行一次折半查找，要么查成功，结束查找，要么将查找范围缩小一半，如此重复，直到查找成功或查找范围缩小空即查找失败为止。
转载请注明原文地址:https://www.kaotiyun.com/show/yyvR777K
本试题收录于： 计算机科学与技术题库普高专升本分类
0

计算机科学与技术

普高专升本

相关试题推荐
随机试题
最新回复(0)