第八章 查找：查找的定义及分类，静态查找表的存储方式及其查找算法，动态查找表定义和存储方式及其查找、插入、删除的算法，哈希表的定义，构造哈希表的方法，处理冲突的算法。8.1查找概述:查找的定义，查找的分类。[单选题] 1. 对线性表进行二分查找时,要求线性表必须（ ）。选项:[以顺序方式存储,且结点按关键字有序排序, 以顺序方式存储 , 以链接方式存储,且结点按关键字有序排序 , 以链接方式存储]
8.2静态查找表:静态查找表的定义及其查找算法，包括顺序表、有序表和索引顺序表的查找算法。
8.3动态查找表:动态查找表的定义，二叉排序树、平衡二叉树、B-树和B+树的定义、存储结构、查找、插入、删除的算法。
8.4哈希表:介绍了哈希表的定义、特点、查找效率等，构造哈希函数的方法，处理冲突的方法。
8.1查找概述:查找的定义，查找的分类。
8.2静态查找表:静态查找表的定义及其查找算法，包括顺序表、有序表和索引顺序表的查找算法。
8.3动态查找表:动态查找表的定义，二叉排序树、平衡二叉树、B-树和B+树的定义、存储结构、查找、插入、删除的算法。
8.4哈希表:介绍了哈希表的定义、特点、查找效率等，构造哈希函数的方法，处理冲突的方法。
[单选题] 4.试将折半查找的算法改写成递归算法。 Int bisearch (sqlist L,int low, int high , elemtype x ) { If (low>high) return( 0 ); else { if (L.data[mid]= =x) return (mid); else if (L.data[mid]>x) bisearch(L,low,mid-1,x); else bisearch(L,mid+1,high,x);
}
}//bisearch
选项:[mid>(low+high)/2;, mid!=(low+high);, mid=(low+high)/2, A. mid< (low+high)/2]
[单选题] 3.设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点： addr (15)=4; addr (38)=5; addr (61)=6; addr (84)=7 如用二次探测再散列处理冲突，关键字为49的结点的地址是( )选项:[3, 8, 9, 5]
[单选题]5.设计算法判定给定二叉树是否为二叉排序树。 void BSTree(BiTree t,int &flag,int &last);//声明
Status IsBSTree(BiTree t)
{
int flag = 1;
int last =0;
BSTree(t,flag,last);
return flag;
}
void BSTree(BiTree t,int &flag,int &last)//取地址不需要返回值
{
if(t->lchild&&flag) BSTree(t->lchild,flag,last);//遍历左子树
if(t->data.key>last&&flag) last = t->data.key;
else flag=0;
//last原为父节点值，但到了树叶节点后被树叶节点的key值覆盖，然后开始向上反馈key
if(t->rchild&&flag)
}
[单选题] 2.下列描述中不符合二叉排序树特点的是 ( )选项:[关键字插入的顺序影响二叉排序树的形态, 根结点的关键字大于左、右子树中所有结点的关键字, 左子树中所有结点的关键字小于根结点的关键字, 右字树中所有结点的关键字大于根节点的关键字C．]
[单选题] m阶B_树中的m是指？选项:[每个结点至少有m棵子树, 非终端结点中关键字的个数, m阶B_树的深度（或高度）, 每个结点至多有m棵子树]
[单选题] 1. 对线性表进行二分查找时,要求线性表必须（ ）。选项:[以链接方式存储,且结点按关键字有序排序 , 以链接方式存储, 以顺序方式存储 , 以顺序方式存储,且结点按关键字有序排序]
[单选题] 2.下列描述中不符合二叉排序树特点的是 ( )选项:[根结点的关键字大于左、右子树中所有结点的关键字, 左子树中所有结点的关键字小于根结点的关键字, 关键字插入的顺序影响二叉排序树的形态, 右字树中所有结点的关键字大于根节点的关键字C．]
[单选题] 3.设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点： addr (15)=4; addr (38)=5; addr (61)=6; addr (84)=7 如用二次探测再散列处理冲突，关键字为49的结点的地址是( )选项:[5, 3, 8, 9]
[单选题] 4.试将折半查找的算法改写成递归算法。 Int bisearch (sqlist L,int low, int high , elemtype x ) { If (low>high) return( 0 ); else { if (L.data[mid]= =x) return (mid); else if (L.data[mid]>x) bisearch(L,low,mid-1,x); else bisearch(L,mid+1,high,x);
}
}//bisearch
选项:[mid=(low+high)/2, mid!=(low+high);, A. mid< (low+high)/2, mid>(low+high)/2;][单选题]5.设计算法判定给定二叉树是否为二叉排序树。 void BSTree(BiTree t,int &flag,int &last);//声明
Status IsBSTree(BiTree t)
{
int flag = 1;
int last =0;
BSTree(t,flag,last);
return flag;
}
void BSTree(BiTree t,int &flag,int &last)//取地址不需要返回值
{
if(t->lchild&&flag) BSTree(t->lchild,flag,last);//遍历左子树
if(t->data.key>last&&flag) last = t->data.key;
else flag=0;
//last原为父节点值，但到了树叶节点后被树叶节点的key值覆盖，然后开始向上反馈key
if(t->rchild&&flag)
}
[单选题] m阶B_树中的m是指？选项:[非终端结点中关键字的个数, 每个结点至少有m棵子树, m阶B_树的深度（或高度）, 每个结点至多有m棵子树]
