18.静态查找表的三种不同实现各有优缺点。其中, 查找效率最低但限制最少。 查找效率最高但限制最强。而 查找则介于上述二者之间 19.二叉排序树是一种特殊的、增加了限制条件的二叉树,其限制条件是任一结点的键值 于其左孩子(及其子孙)的键值且 于其右孩子(及其子孙)的键值 0.在表示一棵二叉排序树的二叉链表上,要找键值比某结点X的键值 的结点,只需 通过结点X的左指针到它的左子树中去找。 1.中根遍历一棵二叉排序树所得的结点访问序列是键值的序列 22.对于一个无序序列,可以通过构造一棵 而使其成为一个有序序列 23.以下算法在指针T所指的二叉排序树上查找键值等于K的结点。成功时回送指向该结点的 指针;否则回送空指针。请分析程序,并在 填充合适的语句。 bitreptr search bst(bitreptr t, keytype K) lif(t==NULL)return (NULL else swith Icase T->key==K: case rerun(search bst(T->lchild, K)) rerun(search bst(T->rchild, K)) 24.二叉排序树上的查找长度不仅与 有关,也与二叉排序树的 有关。 5.在随机情况下,含有n个结点的二叉排序树的平均查找长度为 其时间效率很高。 26.二叉排序的查找效率与树的形态有关。当二叉排序树退化为一条单支时,查找算法退化为 查找,平均查找长度上升为 27.有n个结点的AⅥL树的深度与 是同数量级的,因而在它上面进行查找的平均查找 长度也与 同数量级 28.平衡二叉排序树上任一结点的平衡因子只可能是 29..用散列技术时需要考虑的两个主要问题是 30.按组织形式的不同,通常有 与 两类散列表 31.以下算法在开散列表田P中查找键值等于K的结点,成功时返回指向该结点的指针,不成 功时返回空指针。请分析程序,并在 上填充合适的语句。 pointer research openhash(keytype K, openhash HP i=H(K);/*计算K的散列地址*/ p=HP[i];/*i的同义词子表表头指针传给p*/ while()p=p->next;/未达表尾且未找到时,继续扫描* 32以下算法实现若开散列表田P中无键值为K结点,则插入一个这样的结点。请分析程序并 在 上填充合适的语句 void insert openhash (keytype K, openhash HP) lif (research openhash(K, HP)==NULL) Hi=H(K) g=malloc(size): g->key= /*生成新结点*/ =HPli]: HP[i]= /*前插法链入新结点*/2 18.静态查找表的三种不同实现各有优缺点。其中，________查找效率最低但限制最少。 ________查找效率最高但限制最强。而________查找则介于上述二者之间。 19.二叉排序树是一种特殊的、增加了限制条件的二叉树，其限制条件是任一结点的键值 ________于其左孩子（及其子孙）的键值且________于其右孩子（及其子孙）的键值。 20.在表示一棵二叉排序树的二叉链表上，要找键值比某结点 X 的键值________的结点，只需 通过结点 X 的左指针到它的左子树中去找。 21.中根遍历一棵二叉排序树所得的结点访问序列是键值的________序列。 22.对于一个无序序列，可以通过构造一棵________而使其成为一个有序序列。 23.以下算法在指针 T 所指的二叉排序树上查找键值等于 K 的结点。成功时回送指向该结点的 指针；否则回送空指针。请分析程序，并在________填充合适的语句。 bitreptr search_bst(bitreptr T,keytype K) {if(T==NULL)return(NULL); else swith {case T->key==K:________; case________: rerutn(search_bst(T->lchild,K)); case________: rerutn(search_bst(T->rchild,K)); } } 24.二叉排序树上的查找长度不仅与________有关，也与二叉排序树的________有关。 25.在随机情况下，含有 n 个结点的二叉排序树的平均查找长度为________，其时间效率很高。 26.二叉排序的查找效率与树的形态有关。当二叉排序树退化为一条单支时，查找算法退化为 ________查找，平均查找长度上升为________。 27.有 n 个结点的 AVL 树的深度与________是同数量级的，因而在它上面进行查找的平均查找 长度也与________同数量级。 28.平衡二叉排序树上任一结点的平衡因子只可能是________、________或________。 29.采用散列技术时需要考虑的两个主要问题是：一、________？二、________？ 30.按组织形式的不同，通常有________与________两类散列表。 31.以下算法在开散列表 HP 中查找键值等于 K 的结点，成功时返回指向该结点的指针，不成 功时返回空指针。请分析程序，并在________上填充合适的语句。 pointer research_openhash(keytype K,openhash HP) {i=H(K); /*计算 K 的散列地址*/ p=HP[i]; /*i 的同义词子表表头指针传给 p*/ while(________)p=p->next;/*未达表尾且未找到时，继续扫描*/ ________; } 32 以下算法实现若开散列表 HP 中无键值为 K 结点，则插入一个这样的结点。请分析程序并 在________上填充合适的语句。 void insert_openhash(keytype K,openhash HP) {if(research_openhash(K,HP)==NULL) {i=H(K); q=malloc(size);q->key=________; /*生成新结点*/ ________=HP[i];HP[i]=________; /*前插法链入新结点*/ } }