还剩16页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
数据结构考试内部题库含答案解析(全考点)、含有个非叶结点的阶树中至少包含元关键字1n m B•A:nm+l•B:n1),Dem B解析除根结点外,阶树中的每个非叶结点至少有厂7n/2,-1个关键字,根结点至少有一个关键字,所以总共包含的关键字最少个数2—l心】)「必」答案D)+lo、已知一棵阶树中共有个关键字,则树的最大高25B53度为(),最小高度为()•B:20•C:32•D:33解析所有非叶结点的平衡因子均为即平衡二叉树满足平1,衡的最少结点情况,如下图所示对于高度为、左右子n树的高度分别为和、所有非叶结点的平衡因子均n-1n-2为的平衡二叉树,计算总结点数的公式1=2+1+1=4,可推出二20为=+=2,+1,=1,画图法:先画出和、;然后新建一个根结点,连接、‘177rri rrirriFTI FTI1构成3;新建一个根结点,连接、构成/13/24TTa A直到画出,可知°的结点数为20答案B、若将关键字依次插入初始为空的平衡二叉31,2,3,45,6,7树,则中平衡因子为的分支结点的个数是()T T0・•A:0・•B:1・•C:2・•D:3解析利用个关键字构建平衡二叉树,平衡因子为的分支7T0结点个数为,构建的平衡二叉树及构造与调整过程如下3图所示请添加图片描述答案D、现有一棵无重复关键字的平衡二叉树(),对其进行4AVL中序遍历可得到一个降序序列下列关于该平衡二叉树的叙述中,正确的是()・:根结点的度一定为•A2・:树中最小元素一定是叶结点•B最后插入的元素一定是叶结点•c:树中最大元素一定是无左子树•D解析只有两个结点的平衡二叉树的根结点的度为错误1,A中序遍历后可以得到一个降序序列,树中最小元素一定无左子树(可能有右子树),因此不一定是叶结点,错误B最后插入的结点可能会导致平衡调整,而不一定是叶结点,错误C答案D、在任意一棵非空平衡二叉树(树)中,删除某5AVL1结点之后形成平衡二叉树、,再将插入’2形成平衡v7v二叉树下列关于与的叙述中,正确的是()7371若是的叶结点,则V71工、可能不相同口、若不是的叶结点,则与一定不相同印、若不v71v是的叶结点,则与一定相同71713仅工•A:仅工、•c n仅工、•D m解析在非空平衡二叉树中插入结点,在失去平衡调整前,一定插入在叶结点的位置若删除的是的叶结点,则删除后平衡二叉树可能不会失“1去平衡,即不会发生调整,再插入此结点得到的二叉平衡树与相同;若删除后平衡二叉树失去平衡而发生调整,71再插入结点得到的二叉平衡树与可能不同正确71I对于比较绝对的说法和,通常只需举出反例即可ii in例如,如下图所示,删除结点平衡二叉树失衡调整,再o,插入结点后,平衡二叉树和以前不同o若删除的是的非叶结点,且删除和插入操作均没有导致11平衡二叉树的调整,则该结点从非叶结点变成了叶结点丁\7与显然不同例如,如下图所示,删除结点,用有孩子32结点填补,再插入结点,平衡二叉树和以前不同32若删除的是的非叶结点,且删除和插入操作后导1致了平衡二叉树的调整,则该结点有可能通过旋转后继续变成非叶结点,乃与相同例如,如下图所示,删除结点用右孩子结点填补,再插入结点平衡二叉树失衡调2,32,整,调整后的平衡二叉树和以前相同答案A、下图所示是一棵()6・阶树•A:4B・阶树•B:4B+・阶树•C:3B・阶树•D:3B+解析关键字数量比子树数量少,所以不是树,而是树1B+B又因为阶树结点关键字数最多为有一个结点关m B m-1,键字个数为所以不可能为阶3,3答案A下列关于阶树的说法中,错误的是()
7.m B・:根结点至多有棵子树•A m・:所有叶结点都在同一层次上•B・:非叶结点至少有(为偶数)或()(.C m/2m m+l/2m为奇数)棵子树・根结点中的数据是有序的•D:解析除根结点外的所有非终端结点至少有/棵子树对于根结点,最多有棵子树,若其不是叶结点,m则至少有棵子树2答案C、以下关于阶树的说法中,正确的是()8m B工、每个结点至少有两棵非空子树口、树中每个结点至多有个关键字、所有叶结点在同一层、插入一个元m-1m IV素引起树结点分裂后,树长高一层Bi n・•Ax・•口、B m・•c mivs•[、口、D IV「馆/、子树,2每个非根的内部结点必须至少有解析而根结点至少要有两棵子树,所以工不正确、显然正n m确对于,插入一个元素引起树结点分裂后,只要从iv B根结点到该元素插入位置的路径上至少有一个结点未满,树就不会长高,如图所示;只有当结点的分裂传到根B1结点,并使根结点也分裂时,才会导致树高增如图所1,2示,因此错误IV答案B、具有个关犍字的阶树,应有()个叶结点9n mB・•A:n+1・•B:n-1・•C:mn・•D:nm/2解析树的叶结点对应查找失败的情况,对有个关键字的查B n找集合进行查找,失败可能性有种n+1答案A、高度为的阶树至少有()个结点,至多有()个1053B结点•A:32・B:31・•C:120・•D:121解析由阶树的性质可知,根结点至少有棵子树;mB2r nm/2根结点外的所有非终端结点至少有/棵子树,结点数最少时,阶树形状至少类似于一棵满3B52二叉树,即高度为的树至少有个结点5B-1=31由于每个结点最多有棵子树,所以当结点数最多m53时,阶树形状类似于满三叉树,结点数为(3B-1/2=121答案B D解析阶树中共有个关键字,由最大高度公式5B53HS log1/2r1)/2)+1((九+得量大,H Slog31(53+1)/2]+1_反―一,即最大高度为由最小高度公式4;hlog545从而最小高度为=
2.5,3bgmS+1)此得最小高度答案C B、已知一棵阶树中有个关键字,则此树的最大33B2047B高度为(),最小高度为()・•A:11・•B:10・•C:8解析logmS+1)八之和最大高利用最小局)度H logrnn+1/2+1度的m/2公式可以算出最大高度H log[2047+1/2]+1=1122048=
6.9,,最小高度叱电从而最小高度取7答案A D、下列关于树和树的叙述中,不正确的是()4B B+・树和树都能有效地支持顺序查找•A:B B+・树和树都能有效地支持随机查找•B:B B+・树和树都是平衡的多叉树•C:B B+・树和树都可以用于文件索引结构•D:B B+解析树和树的差异主要体现在.结点关键字和子树的个B B+1数;树非叶结点仅起索引作用;树叶结点关键字和
2.B+
3.B其他结点包含的关键字是不重复的;树支持顺序查找
4.B+和随机查找而树仅支持随机查找B由于树的所有叶结点中包含了全部的关键字信息,且叶B+结点本身依关键字从小到大顺序链接,因此可以进行顺序查找,而树不支持顺序查找B答案A在一棵高度为的阶树中,所含关键字的个数至少是
5.25BO・•A:5•B:7・•C:8・•D:14解析答案A在一棵有个关键字的阶树中,含关键字的结点的
6.154B个数最多是・•B:6・C:10・•D:15解析关键字数量不变,要求结点数量最多,即要求每个结点中含关键字的数量最少根据阶树的定义,根结点最少含4B1个关键字,非根结点中最少含厂4/21—1=1/个关键字,所以每个结点中关键字数量最少都为个,即每个结点都有个分支,类似12于排序二叉树,而个结点正好可以构造一个层的阶1544B树,使得终端结点全在第四层,符合树的定义,因此选B Do答案D、树不同于树的特点之一是()7B+B能支持顺序查找・•A::节点中含有关键字・•B:根结点至少有两个分支・•C:所有叶结点都在同一层上・•D解析由于树的所有叶结点中包含了全部的关键字信息,B+且叶结点本身依关键字从小到大顺序链接,因此可以进行顺序查找,而树不支持顺序查找(只支持多路查找)B答案A、高度为的阶树含有的关键字个数至少是()853B・•A:15・•B:31・•C:62・•D:242解析阶树的基本性质根结点以外的非叶结点最少r nmB m/2-1含有/个关键字,代入得到每m=3个非叶结点中最少包含个关键字,而根结点含有个关键11字,因此所有非叶结点都有两个孩子此时其树形与h=5的满二叉树相同,可求得关键字最少为个31答案B、依次将关键字插入初始为空的95,6,9,13,8,2,12,154阶树后,根结点包含的关键字是()B・•A:8・•B:6,9・•C:8,13・•D:9,12解析一个阶树的任意非叶结点至多含有个关键4Bm-l=3字,在关键字依次插入的过程中,会导致结点的不断分裂,插入过程如下所示请添加图片描述得到根结点包含的关键字为6,9O答案B下列关于散列表的说法中,正确的是()、若散列表10,i的填装因子,则可避免碰撞的产生口、散列查找中不需a要任何关键字的比较印、散列表在查找成功时平均查找长度与表长有关、若在散列表中删除一个元素,不能简单地IV将该元素删除和・•A:I IV・•Bn和m・•c in・•DIV解析冲突(碰撞)是不可避免的,与装填因子无关,因此需・•要设计处理冲突的方法,工错误散列查找的思想是计算出散列地址来进行查找,然后比较・关键字以确定是否查找成功,口错误散列查找成功的平均查找长度与装填因子有关,与表长无・关,印错误在开放地址的情形下,不能随便删除散列表中的某个元・•素,否则可能会导致搜索路径被中断(因此通常的做法是在要删除的地方做删除标记,而不是直接删除),正确IV答案D在下图所示的平衡二叉树中插入关键字后得到一棵新
1.48平衡二叉树,在新平衡二叉树中,关键字所在结点的左.右37子结点中保存的关键字分别是()-・,--_I・•A:13,48・•B:24,48・•C:24,53・•D:24,90解析插入后该二叉树根结点的平衡因子由变为失去平48-1-2,衡,需要进行两次旋转(先右旋后左旋)操作答案C、若平衡二叉树的高度为,且所有非叶子结点的平衡因子26均为,则该平衡二叉树的结点总数为()1O•A:12。