《(全)数据结构考试内部题库含答案解析2023.docx》由会员分享，可在线阅读，更多相关《(全)数据结构考试内部题库含答案解析2023.docx（18页珍藏版）》请在课桌文档上搜索。
1、数据结构考试内部题库含答案解析(全考点)1、含有11个非叶结点的m阶B树中至少包含用关键字。.A:n(m+l)B:rm2l1C:n(/)rm2l1D:(n-l)(/)+1解析除根结点外，m阶B树中的每个非叶结点至少有rm2,1/个关键字，根结点至少有一个关键字，所以总共包含的关键字最少个数rm2l1=(n-l)(/)+o答案：D2、已知一棵5阶B树中共有53个关键字，则树的最大高度为()，最小高度为()。解析5阶B树中共有53个关键字，由最大高度公式H1gm2(n+1)/2)+1得最大二ilog3(53+l)2+l34Bp最大高度为4;由最小高度公式九Iog7Q+1)得最小高度hl0g554=
2、25,从而最小高度为30答案：UB3、已知一棵3阶B树中有2047个关键字，则此B树的最大高度为()，最小高度为()。 A:11 B:10 C:8解析利用最小高度九NlSm(n+1)和最大高Hlog.5+1)/2)+1公式。可以算出最大高度HIog32048=6.9ll,最小局度&3,从而最小高度取7o答案：A。D4、下列关于B树和B+树的叙述中，不正确的是()。A:B树和B+树都能有效地支持顺序查找.B:B树和B+树都能有效地支持随机查找.C:B树和B+树都是平衡的多叉树.D:B树和B+树都可以用于文件索引结构解析B树和B+树的差异主要体现在：L结点关键字和子树的个数；2.B+树非叶结点仅起
3、索引作用；3.B树叶结点关键字和其他结点包含的关键字是不重复的；4.B+树支持顺序蛰找和随机蛰找。而B树仅支持随机查找。由于B+树的所有叶结点中包含了全部的关键字信息，且叶结点本身依关键字从小到大顺序链接，因此可以进行顺序查找，而B树不支持顺序查找。答案：A5、在一棵高度为2的5阶B树中，所含关键字的个数至少是（）。 A:5 B:7 C:8 D:14解析答案：A6、在一棵有15个关键字的4阶B树中，含关键字的结点的个数最多是（）。.A:5 B:6.C:10 D:15解析关键字数量不变，要求结点数量最多，即要求每个结点中含关键字的数量最少。根据4阶B树的定义，根结点最少含1个关键字，非根结点中最
4、少含r421-1=1/个关键字，所以每个结点中关键字数量最少都为1个，即每个结点都有2个分支,类似于排序二叉树，而15个结点正好可以构造一个4层的4阶B树，使得终端结点全在第四层，符合B树的定义，因此选Do答案：D7, B+树不同于B树的特点之一是（）。 A:能支持JliM蛰找 B:节点中含有关键字 C:根结点至少有两个分支 D:所有叶结点都在同一层上解析由于B+树的所有叶结点中包含了全部的关键字信息，且叶结点本身依关键字从小到大顺序链接，因此可以进行顺序查找，而B树不支持顺序查找（只支持多路查找）。答案：A8、高度为5的3阶B树含有的关键字个数至少是（）0 A:15 B:31 C:62 D:
5、242解析m阶B树的基本性质：根结点以外的非叶结点最少rm2l1含有/个关键字，代入m=3得到每个非叶结点中最少包含1个关键字，而根结点含有1个关键字，因此所有非叶结点都有两个孩子。此时其树形与h=5的满二叉树相同，可求得关键字最少为31个。答案：B9、依次将关键字5,6,9,13,8,2,12,15插入初始为空的4阶B树后，根结点包含的关键字是（）。.A:8.B:6,9.C:8,13.D:9,12解析一个4阶B树的任意非叶结点至多含有m-l=3个关键字，在关键字依次插入的过程中，会导致结点的不断分裂，插入过程如下所示。请添加图片描述得到根结点包含的关键字为6,9o答案：B10、下列关于散列表
6、的说法中，正确的是（）。I、若散列表的填装因子1,则可避免碰撞的产生口、散列查找中不需要任何关键字的比较印、散列表在蛰找成功时平均查找长度与表长有关IV、若在散列表中删除一个元素，不能简单地将该元素删除A:I和IV.B:II和In.c：m.D:IV解析.冲突（碰撞）是不可避免的，与装填因子无关，因此需要设计处理冲突的方法，工错误。散列查找的思想是计算出散列地址来进行蛰找，然后比较关键字以确定是否查找成功，口错误。散列查找成功的平均蛰找长度与装填因子有关，与表长无关，11I错误。在开放地址的情形下，不能随便删除散列表中的某个元素，否则可能会导致搜索路径被中断（因此通常的做法是在要删除的地方做删除
7、标记，而不是直接删除），IV正确。答案：D1、在下图所示的平衡二叉树中插入关键字48后得到一棵新平衡二叉树,在新平衡二叉树中,关键字37所在结点的左、右子结点中保存的关键字分别是（）。 A:13,48.B:24,48 C:24,53.D:24,90解析插入48后该二叉树根结点的平衡因子由-1变为-2,失去平衡，需要进行两次旋转（先右旋后左旋）操作。答案：C2、若平衡二叉树的高度为6,且所有非叶子结点的平衡因子均为1,则该平衡二叉树的结点总数为（）。 A:12 B:20 C:32 D:33解析所有非叶结点的平衡因子均为1,即平衡二叉树满足平衡的最少结点情况，如下图所示。对于高度为n、左右子树的高
8、度分别为n-1和n-2、所有非叶结点的平衡因子均为1的平衡二叉树，计算总结点数的公式Cn=Cn_1+Cn_2+iC1=102=2=2+1+1=4,可推出6=20。画图法:先画出TI和7、；然后新建一个根结点,连接7、T1T1T1FTlFJTl11构成,3;新建一个根结点，连接3、/2构成4TUrc直到画出,可知。的结点数为20。答案：B3、若将关键字1,2,3,4,5,6,7依次插入初始为空的平衡二叉树T,则T中平衡因子为O的分支结点的个数是（）。.A:O.B:1.C:2.D:3解析利用7个关键字构建平衡二叉树T,平衡因子为O的分支结点个数为3,构建的平衡二叉树及构造与调整过程如下图所示。请添
9、加图片描述答案：D4、现有一棵无重复关键字的平衡二叉树（AVL）,对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是（）OA:根结点的度一定为2B:树中最小兀素-一定是叶结点c：最后插入的元素一定是叶结点D:树中最大元素一定是无左子树解析只有两个结点的平衡二叉树的根结点的度为1,A错误。中序遍历后可以得到一个降序序列，树中最小元素一定无左子树（可能有右子树），因此不一定是叶结点，B错误。最后插入的结点可能会导致平衡调整，而不一定是叶结点，C错误。答案：D5.在任意一棵非空平衡二叉树（AVL树）中，删除某结点V之后形成平衡二叉树4,再将V插入儿形成平衡二叉树N下列关于TI
10、与33的叙述中，正确的是（）。I、若V是TI的叶结点，则Tl与&可能不相同口、若V不是TI的叶结点，则71与7%一定不相同田、若V不是TI的叶结点，则71与7、一定相同.a：仅I.B：仅口.c：仅I、.D:仅I、In解析在非空平衡二叉树中插入结点，在失去平衡调整前,一定插入在叶结点的位置。若删除的是TI的叶结点，则删除后平衡二叉树可能不会失去平衡，即不会发生调整，再插入此结点得到的二叉平衡树Tl与73相同；若删除后平衡二叉树失去平衡而发生调整，再插入结点得到的二叉平衡树羽与TI可能不同。工正确。对于比较绝对的说法II和11I,通常只需举出反例即可。例如，如下图所示，删除结点O,平衡二叉树失衡调
11、整，再插入结点O后，平衡二叉树和以前不同。Tl若删除的是TI的非叶结点，且删除和插入操作均没有导致平衡二叉树的调整,则该结点从非叶结点变成了叶结点,显然不同。例如，如下图所示，删除结点2,用有孩子结点3填补，再插入结点2,平衡二叉树和以前不同。若删除的是TI的非叶结点，且删除和插入操作后导致了平衡二叉树的调整，则该结点有可能通过旋转后继续变成非叶结点，相同。例如，如下图所示，删除结点2,用右孩子结点3填补，再插入结点2,平衡二叉树失衡调整，调整后的平衡二叉树和以前相同。答案：A6、下图所示是一棵（）。.A:4阶B树.B:4阶B+树.C:3阶B树.D:3阶B+树解析关键字数量比子树数量少1,所以
12、不是B+树，而是B树。又因为m阶B树结点关键字数最多为m-1,有一个结点关键字个数为3,所以不可能为3阶。答案：A7、下列关于m阶B树的说法中，错误的是（）。 A:根结点至多有m棵子树.B:所有叶结点都在同一层次上 C:非叶结点至少有m/2（m为偶数）或（m+1）/2（m为奇数）棵子树 D:根结点中的数据是有序的解析除根结点外的所有非终端结点至少有/棵子树。对于根结点，最多有m棵子树，若其不是叶结点，则至少有2棵子树。答案：C8、以下关于m阶B树的说法中，正确的是（）。I、每个结点至少有两棵非空子树口、树中每个结点至多有m-1个关键字印、所有叶结点在同一层IV、插入一个元素引起B树结点分裂后，
13、树长高一层.A:Ix11.B:口、HIC:m、IV.D:I、口、IV解析每个非根的内部结点必须至少有必2、子树,而根结点至少要有两棵子树，所以I不正确。口、m显然正确。对于IV,插入一个元素引起B树结点分裂后，只要从根结点到该元素插入位置的路径上至少有一个结点未满，B树就不会长高，如图1所示；只有当结点的分裂传到根结点，并使根结点也分裂时，才会导致树高增1,如图2所示，因此IV错误。答案：B9、具有n个关键字的m阶B树，应有（）个叶结点。.A:n+1 B:n-1.C:mn D:nm/2解析B树的叶结点对应查找失败的情况，对有n个关键字的查找集合进行查找，失败可能性有n+1种。答案：A10、高度为5的3阶B树至少有（）个结点，至多有（）个结点。 A:32 B:31 C:120 D:121解析由m阶B树的性质可知，根结点至少有2棵子树;根结点外的所有非终端结点至少有LZn/2棵子树，结点数最少时，3阶B树形状至少类似于一棵满二叉树，即高度为5的B树至少有小个结点。由于每个结点最多有m棵子树，所以当结点数最多35时，3阶B树形状类似于满三叉树，结点数为（-1)/2=121。答案：B。D
