当前位置:首页 >> 研究生入学考试 >>

北京理工大学数据结构考研例题解析9


理硕教育—专注于北理工考研辅导 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

因为专一所以专业 理硕教育全力助您圆北理之梦


相关文章:
北京理工大学数据结构考研例题解析9.doc
北京理工大学数据结构考研例题解析9_研究生入学考试_高等教育_教育专区。本资料由
北京理工大学数据结构考研例题解析7.doc
北京理工大学数据结构考研例题解析7_研究生入学考试_高等教育_教育专区。本资料由
北京理工大学数据结构考研例题解析6.doc
北京理工大学数据结构考研例题解析6_研究生入学考试_高等教育_教育专区。本资料由
北京理工大学数据结构考研例题解析3.doc
北京理工大学数据结构考研例题解析3 - 本资料由理硕教育整理,理硕教育是全国唯一专注于北理工考研辅导的学校,相对于其它机构理硕教育有得天独厚的优势。丰富的理工...
北京理工大学数据结构试题及答案.doc
北京理工大学数据结构试题及答案 - 北京理工大学期末测试题 北京理工大学数据结构 10 年期末试题 数据结构试卷(一) 一、单选题(每题 2 分,共 20 分) 1. 栈...
北京理工大学数据结构十年期末试题及答案_图文.pdf
北京理工大学数据结构十年期末试题及答案_研究生入学考试_高等教育_教育专区。 您的评论 发布评论 用户评价 北京理工大学数据结构十年期末试题及答案,如何下载 2018...
北京理工大学数据结构历年真题汇编考研真题_图文.pdf
北京理工大学数据结构历年真题汇编考研真题 - 华研考试网www.eduky.net考研专业课辅导视频;考研专业课全套资料(笔记讲义复习题期末试题);考研专业课冲刺三套模拟题;...
北京理工大学2013级数据结构B试题(B卷)_答案.doc
北京理工大学2013级数据结构B试题(B卷)_答案_研究生入学考试_高等教育_教
2003-2016年北京理工大学889数据结构考研真题及答案解....doc
2003-2016年北京理工大学889数据结构考研真题及答案解析 汇编_研究生入学考试_...四、北理工《数据结构》考研复习提纲。 五、北理工《数据结构》考研题库及答案...
2017年北京理工大学数据结构889模拟试题.pdf
2017年北京理工大学数据结构889模拟试题 - 2017 年北京理工大学数据结构 889 模拟试题 说明:考纲上的分值分布是填空题 20 分、选择题 30 分、问答题 70 分、...
数据结构考研真题及其答案_图文.pdf
数据结构考研真题及其答案 - 一、选择题 1. 算法的计算量的大小称为计算的( B )。 【北京邮电大学 2000 二、3 (20/8 分) 】 A.效率 B. 复杂性 C. ...
2016年北京理工大学考研889数据结构考试大纲解析_图文.pdf
2016年北京理工大学考研889数据结构考试大纲解析 - 考研大纲,考研参考书,考研招生目录,考研招生简章,考研招生人数
计算机数据结构考研真题及其答案_图文.pdf
计算机数据结构考研真题及其答案 - 第1章 绪论 一、选择题 1. 算法的计算量的大小称为计算的( )。 【北京邮电大学 2000 二、3 (20/8 分) 】 A.效率 B...
最新版数据结构1800题含完整答案详解.doc
最新版数据结构1800题含完整答案详解_研究生入学考试...栈 9.以下数据结构中,哪一个是线性结构( D )?...【北京理工大学 2001 六、1(2 分) 】 A.栈 B...
北京理工大学考研889数据结构参考书真题资料.doc
北京理工大学考研889数据结构参考书真题资料 - 考研就要一次考上 889 数据结构 考试内容: 数据结构主要考查考生以下几个方面: 1.理解数据结构的基本概念;掌握数据...
2018年北京理工大学计算机学院889数据结构[专业硕士]考....pdf
2018年北京理工大学计算机学院889数据结构[专业硕士]考研核心题库 - 专注考研专业课 13 年,提供海量考研优质文档! 目录 2018 年北京理工大学计算机学院 889 数据...
北京理工大学数据结构编程练习答案.doc
北京理工大学数据结构编程练习答案 - 1.一元多项式相加(10 分) 成绩: 10 / 折扣: 0.8 题目说明: 编写一元多项式加法运算程序。要求用线性链表存储一元多项式(...
2015年北京理工大学889数据结构考研大纲,考研参考书,考....pdf
才思教育考研考博全心全意 北京理工大学 889 数据结构考研大纲 889 数据结构 ...九) 基数排序 (十) 各种内部排序算法的比较 (十一) 内部排序算法的应用 题型...
数据结构考研复习题--第三章--栈和梯队(带答案).doc
数据结构考研复习题--第三章--栈和梯队(带答案)_研究生入学考试_高等教育_...大学 2001 二、4 (1 分)】 【北京理工大学 2000 一、2 (2 分) 】 9....
2018年北京理工大学软件学院885软件工程专业基础综合之....pdf
2018年北京理工大学软件学院885软件工程专业基础综合之数据结构考研仿真模拟五套题 - 专注考研专业课 13 年,提供海量考研优质文档! 目录 2018 年北京理工大学软件...
更多相关文章: