《北京理工大学-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获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研
