数据结构第五章-查找-答案.docx

数据结构与算法上机作业第五章查找一、选择题1、若构造一棵具有n个结点的二叉排序树,在最坏情况下,其高度不超过B。 C.(n+1)/2 +12、分别以下列序列构造二叉排序数(二叉查找树),与用其他3个序列所构造的结果不同的是C: A.(100,80,90,60,120,110,130) B.(100,120,110,130,80,60,90) C.(100,60,80,90,120,110,130) D.(100,80,60,90,120,130,110)3、不可能生成下图所示的二叉排序树的关键字的序列是A。 、在二叉平衡树中插入一个结点造成了不平衡,设最低的不平衡点为A,并已知A的左孩子的平衡因子为0,右孩子的平衡因子为1,则应作C型调整使其平衡。 、一棵高度为k的二叉平衡树,其每个非叶结点的平衡因子均为0,则该树共有C个结点。 -1-1 -1+1 -1 +16、具有5层结点的平衡二叉树至少有A个结点。 、下面关于B-和B+树的叙述中,不正确的是C。 -树和B+树都是平衡的多叉树 -树和B+树都可用于文件的索引结构 -树和B+树都能有效地支持顺序检索 -树和B+树都能有效地支持随机检索8、下列关于m阶B-树的说法错误的是D。 (m为偶数)或m/2+1(m为奇数)棵子树 、下面关于哈希查找的说法正确的是C。 ,因为这样随机性好,冲突小 ,要视情况而定 ,不管用何种方法解决冲突都只要简单地将该元素删去即可10、与其他查找方法相比,散列查找法的特点是C。 、有一组关键字{8,24,16,3,12,32,51},采用除留余数法构造散列函数:H(key)=keymod12,则将发生次冲突。 、有一个结点的关键字为3276012483,采用移位叠加法生成4位散列地址,则生成的地址为B。 、填空题1、在查找过程中有插入或删除元素操作的,称为动态查找。2、一个无序序列可以通过构造一棵二叉排序树而变为一个有序序列,构造树的过程即为对无序序列进行排序的过程。3、对于一棵二叉排序树,按中根方法遍历得出的结点序列是从小到大排列的。4、对二叉排序树进行查找的方法是用待查找的值与根结点的键值进行比较,若比根结点的值小,则继续在左子树中查找。5、AVL树为在构造二叉排序树时,为确保搜索的性能而保持树的平衡,保持平衡的方法为在构建AVL树时根据特定条件而进行LL,RR,LR,RL四种旋转操作,如对于下图的树,应该进行RLRR旋转。6、在m阶一棵B-树中,若在某个结点中插入一个新关键字而引起该结点分裂