第九章查找表 、名词解释 1.查找表2.集合3.查找长度4.有序表5.平衡化6.平衡二叉排序树7.平衡因子8.散列表 9.散列函数10.散列地址11.同义词12.冲突13.开散列表14.拉链法15.堆积 填空题 1.对任何集合A而言,A的每一个成员a称为A的一个 记为 2.空集是的集合,记为 3.在集合这种逻辑结构中,任何结点之间都不存在 关系,这是集合这种逻辑结构的 基本特点 4.集合中没有相同的 。作为一个数学概念,集合的元素没有 5.数据元素之间的逻辑关系反映的是 6.对于集合这逻辑结构来说,其中的数据元素之间也可以有各种各样的非逻辑关系,但任何 一对数据元素之间没有 关系,即没有关系。 7.查找表按其所包括的运算的不同分为 查找表和 找 8.查找表中主关键字指的是 ,次关键字指的是 9.静态查找表包括 三种基本运算。 10.动态查找表包括 五种基本运算 11.假定key为主关键字,若顺序表中第n个元素的键值为K,则顺序查找算法的查找长度为 1:若第1个元素的键值为K,则查找长度为 若表中无键值等于K的元素,则查找 长度为 12.以下算法在有序表R中用二分査找法查找键值等于K的元素,请分析程序,并在 上填充合适的语句。 int binsearch (stable R, keytype k) {low=l;hig=R.n;/*置査找区间初值。low,hig分别标记查找区间的下、上界*/ hile(low<=hig Imid=(lowthig)/2 switch case K==R.item[mid].key: return(mid);/*找到,返回位置mid*/ case K<R item[mid]. key: break;/缩小区间*/ case K>R item[mid].ki break;/*缩小区间*/ return(0);/*若区间长度已为0但仍不成功,则返回0,表示查找不成功* 13.二分查找在查找成功时的查找长度不超过 其平均查找长度为 较大时约等于 4一个 表由一个顺序表和一个索引表两部分组成。其中的顺序表在组织形式与普通 表完全相同:而索引表本身在组织形式上也是一个 15.索引顺序表的特点表现为以下两个方面:a.顺序表中的数据元素 ":b.索引表反 映了这些 的有关特性 16.在索引顺序表上,对于顺序表中的每一块,索引表中有相应的一个”索引项"。每个索引项 有两个域:块内最大 _值和块_位置 17.索引顺序表上的查找分两个阶段: 。该查找方法称为 查找1 第九章 查找表 一、名词解释 1.查找表 2.集合 3.查找长度 4.有序表 5.平衡化 6.平衡二叉排序树 7.平衡因子 8.散列表 9.散列函数 10.散列地址 11.同义词 12.冲突 13.开散列表 14.拉链法 15.堆积 二、填空题 1.对任何集合 A 而言，A 的每一个成员 a 称为 A 的一个________，记为________。 2.空集是________的集合，记为________。 3.在集合这种逻辑结构中，任何结点之间都不存在________关系，这是集合这种逻辑结构的 基本特点。 4.集合中没有相同的________。作为一个数学概念，集合的元素没有________。 5.数据元素之间的逻辑关系反映的是________。 6.对于集合这逻辑结构来说，其中的数据元素之间也可以有各种各样的非逻辑关系，但任何 一对数据元素之间没有________关系，即没有________关系。 7.查找表按其所包括的运算的不同分为________查找表和________查找表。 8.查找表中主关键字指的是________，次关键字指的是________。 9.静态查找表包括________、________、________三种基本运算。 10.动态查找表包括________、________、________、________、________五种基本运算。 11.假定 key 为主关键字，若顺序表中第 n 个元素的键值为 K，则顺序查找算法的查找长度为 1；若第 1 个元素的键值为 K，则查找长度为________；若表中无键值等于 K 的元素，则查找 长度为________。 12.以下算法在有序表 R 中用二分查找法查找键值等于 K 的元素，请分析程序，并在________ 上填充合适的语句。 int binsearch(sqtable R,keytype K) {low=1;hig=R.n;/*置查找区间初值。low,hig 分别标记查找区间的下、上界*/ while(low<=hig) {mid=（low+hig)/2; switch {case K==R.item[mid].key:return(mid);/*找到，返回位置 mid*/ case K<R.item[mid].key:________;break;/*缩小区间*/ case K>R.item[mid].kiy:________;break;/*缩小区间*/ } } return(0);/*若区间长度已为 0 但仍不成功，则返回 0，表示查找不成功*/ } 13.二分查找在查找成功时的查找长度不超过________，其平均查找长度为________，当 n 较大时约等于________。 14.一个________表由一个顺序表和一个索引表两部分组成。其中的顺序表在组织形式与普通 的________表完全相同；而索引表本身在组织形式上也是一个________表。 15.索引顺序表的特点表现为以下两个方面：a.顺序表中的数据元素"________"；b.索引表反 映了这些"________"的有关特性。 16.在索引顺序表上，对于顺序表中的每一块，索引表中有相应的一个"索引项"。每个索引项 有两个域：块内最大________值和块________位置。 17.索引顺序表上的查找分两个阶段：一、________；二、________。该查找方法称为________ 查找