《北京理工大学-889-2017-真题回忆版》由会员分享,可在线阅读,更多相关《北京理工大学-889-2017-真题回忆版(1页珍藏版)》请在金锄头文库上搜索。
1、2017 年北理年北理 889 数据结构真题(回忆版)数据结构真题(回忆版) 第一题 选择题(20 个题 共 40 分) 都是非常基础的题目,只要认真做下王道后面的选择题应该都会。第二题 填空题(9 道题 20 个空 共 40 分) 只记得有道题,问 b+树和 b-树都可以进行()访问,其中()树可以进行顺序访问。 (我写的是 随机 b+) 。 队列删除和添加后 front() 和 rear()的位置。 希尔排序以 4 2 1 为间隔,需要()趟排序,第一趟排序后序列为() 。还有两道读程序填空的题。反正选择填空都是很基础的题,当然考纲给的分值和范围都不太准。第三题 简答题(4 道题,每题 1
2、0 分,共 40 分) (1)根据“算法优先法”,写出 3*(7-5)/2 的每一个步骤的 运算符栈和操作数栈的变化。(2)哈希,用线性探测再散列处理冲突,写出哈希表并求出查找成功和失败的平均查找长度。(3)在一个有向无环图中,是否能按照拓扑排序的顺序求源点到其他各点的最短路径?如何可以,请说明为什么? 并按照拓扑排序的顺序求出下图中顶点 1 到其他各点的最短路径长度。 (这个题是 2013年 889 数据结构的原题) (4)归并、快排、堆排序、基数排序中,下列问题用什么合适,并说明原因。对非负整数排序用哪种?要求空间为 O(1)用哪种?浮点数,且要求稳定用哪种?第四题 算法题(3 道题,每题
3、 10 分,共 30 分) (1) 给了一个顺序表的定义和要写的函数的定义, 写出有序表 L1 和 L2 合并成有序表 L3 的代码。 函数的定义记得是这样的:void MergeLinklist(Linklist L1, Linklist L2, Linklist &L3); (2)给了八皇后的初始和输出代码,写出八皇后问题的主要代码。(3)写出快速排序的主要思想和代码。各个学校计算机/软件专业考研真题 免费分享 h t t p s :/g i t h u b .co m /cs s e k y /cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研