北京理工大学数据结构考研例题解析9
更新时间:2024-03-14 19:49:01 阅读量: 综合文库 文档下载
理硕教育—专注于北理工考研辅导www.lishuoedu.com
本资料由理硕教育整理,理硕教育是全国唯一专注于北理工考研辅导的学校,相对于其它机构理硕教育有得天独厚的优势。丰富的理工内部资料资源与人力资源确保每个学员都受益匪浅,确保理硕教育的学员初试通过率89%以上,复试通过率接近100%,理硕教育现开设初试专业课VIP一对一,初试专业课网络小班,假期集训营,复试VIP一对一辅导,复试网络小班,考前专业课网络小班,满足学员不同的需求。因为专一所以专业,理硕教育助您圆北理之梦。详情请查阅理硕教育官网
第 9 章 索引技术
课后习题讲解 1. 填空题
⑴ 在索引表中,每个索引项至少包含( )和( )等信息 【解答】关键码,关键码对应的记录在存储器中的位置 ⑵ 在线性索引中,( )称为稠密索引 【解答】若文件中的每个记录对应一个索引项
⑶ 分块有序是指将文件划分为若干块,( )无序,( )有序。 【解答】块内,块间
⑷ 在分块查找方法中,首先查找( ),然后查找相应的( )。 【解答】索引表,块
⑸ 在10阶B—树中根结点所包含的关键码个数最多为( ),最少为( )。 【解答】9,1
【分析】m阶的B-树中每个结点至多有m棵子树,若根结点不是终端结点,则至少有两棵子树,每个结点中关键码的个数为子树的个数减1。
⑹ 一棵5阶B—树中,除根结点外,每个结点的子树树目最少为( ),最多为( )。 【解答】3,5
【分析】m阶的B-树中每个结点至多有m棵子树,除根结点之外的所有非终端结点至少有?m/2? 棵子树。
⑺ 对于包含n个关键码的m阶B—树,其最小高度是( ),最大高度是( )。 【解答】[logm(n+1)], [logm/2(n+1)/2]
⑻ 在一棵B—树中删除关键码,若最终引起树根结点的合并,则新树比原树的高度( )。 【解答】减少1层
因为专一所以专业 理硕教育全力助您圆北理之梦
理硕教育—专注于北理工考研辅导www.lishuoedu.com
⑼ 在一棵高度为h的B—树中,叶子结点处于第( )层,当向该B—树中插入一个新关键码时,为查找插入位置需读取( )个结点。 【解答】h+1,h
【分析】B-树的叶子结点可以看作是外部结点(即查找失败)的结点,通常称为外结点。实际上这些结点不存在,指向这些结点的指针为空,B-树将记录插入在终端结点中。 ⑽ 对于长度为n的线性表,若采用分块查找(假定总块数和每块长度均接近 ,用顺序查找确定所在块),则时间复杂性为( )。 【解答】O(2. 判断题
⑴ 在索引顺序表上采用分块查找,在等概率情况下,其平均查找长度不仅与子表个数有关,而且与每一个子表中的对象个数有关。
【解答】对。分块查找的平均查找长度不仅和文件中记录的个数n有关,而且和每一块中的记录个数t有关,当t取 时,ASL取最小值 +1。
⑵ B—树是一种动态索引结构,它既适用于随机查找,也适用于顺序查找。 【解答】错。B—树不能进行顺序查找。
⑶ 对于B—树中任何一个非叶结点中的某个关键码k来说,比k大的最小关键码和比k小的最大关键码一定都在叶结点中。 【解答】对。
⑷ 在索引顺序表的查找中,对索引表既可以采取顺序查找,也可以采用折半查找。 【解答】对。因为索引表有序。
⑸ m阶B—树中每个结点的子树个数都大于或等于?m/2?。
【解答】错。m阶的B-树中除根结点之外的所有非终端结点至少有[m/2] 棵子树。若根结点不是终端结点,则至少有两棵子树。
⑹ m阶B—树中任何一个结点的左右子树的高度都相等。 【解答】对。B树都是树高平衡的。
3.对图9-2所示的3阶B—树,分别给出插入关键码为2,12,16,17和18之后的结果。
)
【解答】插入关键码为2,12,16,17,18之后的结果分别如图9-3中(a)、(b)、(c)、(d)、(e)所示。
因为专一所以专业 理硕教育全力助您圆北理之梦
理硕教育—专注于北理工考研辅导www.lishuoedu.com
4.对上题所示的3阶B—树,分别给出删除关键码为4,8,9之后的结果。 【解答】删除关键码为4,8,10之后的结果如图9-4(a),(b),(c)所示:
因为专一所以专业 理硕教育全力助您圆北理之梦
理硕教育—专注于北理工考研辅导www.lishuoedu.com
5.为什么在内存中使用的B—树通常是3阶的,而不使用更高阶的B—树?
【解答】作为外存上的动态查找,B—树比平衡二叉树的性能要好,但若要作为内存中的查找表,B—树却不一定比平衡二叉树性能好,因为查找等操作的时间性能在m阶B—树上是O(mlogtn)=O(log2n*(m/log2t))(n为记录个数),而m/log2t>1,故m较大时,O(mlog2n)比平衡的二叉排序树上相应操作的时间O(log2n)大得多。因此,仅在内存中使用的B—树必须取较小的m,通常取最小值m=3。
6.设有10000个记录,通过分块划分为若干子表并建立索引,那么为了提高查找效率,每一个子表的大小应设计为多大?
【解答】每个子表的大小应为学习自测及答案
1.在索引顺序表中,首先查找( ),然后再查找相应的( ),其平均查找长度等于( )。 【解答】索引表,块,查找索引表的平均长度与检索相应块的平均查找长度的和 2.既希望较快的查找又便于线性表动态变化的查找方法是( )。 A 顺序查找 B折半查找 C散列查找 D 索引顺序查找 【解答】D
3.在一个3阶的B—树上,每个结点所含的子树数目最多为( )。 【解答】3
4.在一棵m阶的B—树中,当将一个关键码插入某结点而引起该结点分裂时,此结点原有( )个关键码;若删去某结点中的一个关键码,而导致结点合并时,该结点原有( )个关键码。
【解答】m-1, ?m/2? -1
。
因为专一所以专业 理硕教育全力助您圆北理之梦
理硕教育—专注于北理工考研辅导www.lishuoedu.com
5.当向B—树中插入关键码时,可能引起结点的( ),最终可能导致整个B-树的高度( ),当从B—树中删除关键码时,可能引起结点( ),最终可能导致整个B—树的高度( )。 【解答】分裂,增加1,合并,减少1
6.在9阶B—树中,除根结点以外其他非叶子结点中的关键码个数不少于( )。 【解答】4
7.当向一棵m阶的B—树做插入操作时,若一个结点中的关键字个数等于( ),则必须分裂为两个结点。 A m B m-1 C m+1 D m/2 【解答】A
8.在一个5阶的B—树上,每个非终端结点所含的子树数最少为( )。 A 2 B 3 C 4 D 5 【解答】B
9. 给定一组记录,其关键码为字母。记录按照下面的顺序插入一棵空的B—树中:C,S,D,T,A,M,P,I,B,W,N,G,V,R,K,E,H,O,L,J。请画出插入这些记录后的3阶B—树。
【解答】最后的B—树如图9-5所示。
10.已知一个B+树有5个叶子结点,每个叶子结点中的关键码如图9-6所示,请画出这棵3阶B+树,然后在此3阶B+树中插入关键码65,再画出插入后的B+树。
【解答】该B+树如图9-7所示,插入关键码65后,B+树如图9-8所示。
因为专一所以专业 理硕教育全力助您圆北理之梦
理硕教育—专注于北理工考研辅导www.lishuoedu.com
因为专一所以专业 理硕教育全力助您圆北理之梦
正在阅读:
北京理工大学数据结构考研例题解析903-14
中考数学总复习第二轮03-11
平刨机安全技术操作规程08-15
船体毕业设计论文格式03-13
改革强军大背景下士官实战化训练教学教材建设之我见-最新资料03-26
农村承包土地经营权转让合同范本02-27
公派访学告知书-北京理工大学12-27
采油工补充题05-13
- 必修一物理寒假作业
- 2019-201X年5月大学生入党积极分子思想汇报-word范文模板(3页)
- 药物分析习题五
- 重拾应用意识 体会数学价值(沈建军)
- 2017全国高校辅导员结构化面试题集及参考答案
- 广东徐闻县实验中学2014届高三第二次月测地理试题
- 今天你共鸣了么?
- 2018-2019正能量读后感1000字-推荐word版(6页)
- 2018年中国截切型盖板针布行业专题研究分析报告目录
- 中国移动业务处理流程大全
- 公文写作常用词汇和句子集锦2016
- ARM课程设计说明书
- 教师资格证教育学论文
- 中考试卷分析
- 环境监测试卷(五)
- 党风廉政建设广播稿1
- 快速制作香香宫煮麻辣烫教程
- 《国际金融学》习题
- 文明施工保障措施方案
- 春兰维修资料故障代码
- 北京理工大学
- 例题
- 数据结构
- 解析
- 考研
- 出血、血栓与止血检测考试试题
- 浅析:中国餐饮业的市场现状分析
- 东营市建设工程施工安全监督交底书
- 小升初数学天天练:模拟题系列(含答案)31
- 鲁建标函〔2017〕23号 山东省住房和城乡建设厅关于调整山东省建
- 无限长单位脉冲响应滤波器设计
- 八年级地理教学案例(贾艳梅)
- 酒店式公寓租赁协议书
- 光明乳业电子商务 - 图文
- 农村骨干教师职业幸福力的研究
- 宝应生态新城高中景观、绿化工程情况说明及新技术、新工艺、新材
- 第二节 影响化学反应速率的因素正式版 - 图文
- 彩色的非洲第二课时
- X6132型万能升降台铣床主轴变速箱设计说明书
- 湖北省襄樊四中2012届高三11月月考(数学文)
- 浅谈中国动画的发展方向
- 应建防空地下室报建程序
- 安徽省安全生产应急救援指挥中心移动应急平台指挥车具体技
- 自我教学情况分析报告
- 七年级文言文古诗大全(原文+译文)