2018年北京语言大学软件工程825数据结构与程序设计[专业硕士]之数据结构考研核心题库
● 摘要
一、算法设计题
1． 设有顺序放置的n 个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红、白、蓝之一。要求重新安排这些砾石，使得所有红色砾石在前，所有白色砾石居中，所有蓝色砾石居后。重新安排时，对每粒砾石的颜色只能察看一次，并且只允许交换操作来调整砾石的位置。
【答案】算法如下:
r 为含有n 个元素的线性表，元素是具有红、白和蓝色的砾石，用顺序存储结构存储
本算法对其排序，使所有红色栎石在前，白色居中，蓝色在最后
当前元素是红色
当前元素是白色
当前元素是蓝色
2． 已知顺序表中有m 个记录，表中记录不依关键字有序排列，编写算法为该顺序表建立一个有序的索引表，索引表中的每一项含记录的关键字和该记录在顺序表中的序号，要求算法的时间复杂度在最好的情况下能达到O(m)。
【答案】算法如下:
顺序表中记录个数
关键字
该关键字在顺序表中的下标
索引表的一项
关键字
记录中的其他数据
给有m 个记录的顺序表seq 建立索引表
index
监视哨
关键字放入正确位置
第i 个记录的下标
3． 对给定关键字序号j(1 中找到关键字从小到大排在第j 位上的记 录，写一个算法利用快速排序的划分思想实现上述查找(要求用最少的时间和最少的空间) 。 例如:给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。 【答案】算法如下； 在后半部分继续进行划分 在前半部分继续进行划分 4． 写一算法找出n 个数的最大值和最小值，要求最坏条件下的元素比较次数为 。 【答案】算法如下: 用最多3n/2－2次比较在n 个元素r 中选出最大值和最小值 n 为偶数时 r 最小值 ("最大值) ； 5． 编写程序，统计在输入字符串中各个不同字符出现的频度并将结果存入文件(字符串中的合法字符为A 〜Z 这26个字母和0〜9这10个数字) 。 【答案】算法如下: （ ） //统计输入字符串中数字字符和字母字符的个数 //初始化 //’#’表示输入字符串结束 '//数字字符 //字母字符 //输出数字字符的个数 ("数字％d 的个数＝ //求出字母字符的个数 ("字母字符％c 的个数＝ //算法结束。 ) ； ) ； 二、应用题 6． 设某文件经内排序后得到100个初始归并段(初始顺串) ，若使用多路归并排序算法，并要求三趟归并完成排序，问归并路数最少为多少？ 【答案】设归并路数为k ，归并趟数为s ，则 ，因 ，且k 为整数，故k=5， 即最少5-路归并可以完成排序。 7． 设依以下次序给出关键字:34，16，19，21，5，49，24，62，3，17，45，8，构造3阶B-树。要求从空树开始，每插入一个关键字，画出一棵树。 【答案】如图所示: