2018年中国科学技术大学信息科学技术学院834软件工程基础[专业硕士]之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 写一算法找出n 个数的最大值和最小值，要求最坏条件下的元素比较次数为
。
【答案】算法如下:
用最多3n/2－2次比较在n 个元素r 中选出最大值和最小值
n 为偶数时
r 最小值
("最大值) ；
2． 已知一棵二叉树的前序遍历序列和中序遍历序列分别存于两个一维数组中，试编写算法建立该二叉树的二叉链表。
【答案】算法如下:
根据二叉树前序序列pre 和中序序列in 建立二叉树。元素下标
申请结点
是根
在中序序列中，根结点将树分成左右
子树
无左子树
递归建立左子树
无右子树
递归建立右子树
结束:
第 2 页，共 38 页
和是两个序列首、尾
3． 输入一个字符串，内有数字和非数字字符，如:akl23x4561796073029ef4563。将其中连续的数字作为一个整体，依次存放到一数组a 中，例如123放入a[0]，456放入a[l]，...... 。编程统计其共有多少个整数，并输出这些数。
【答案】算法如下:
（ ）
//从键盘输入字符串，连续的数字字符算作一个整数，统计其中整数的个数
//整数存储到数组a ，i 记整数个数
//从左到右读入字符串
//'#'是字符串结束标记
//是数字字符
//数初始化
//拼数
//若拼数中输入了’#’，则不再输入
//输入非数字且非#时，继续输入字符
("共有
个整数，它们是:
)
//每10个数输出在一行上
//算法结束
4． 已知顺序表中有m 个记录，表中记录不依关键字有序排列，编写算法为该顺序表建立一个有序的索引表，索引表中的每一项含记录的关键字和该记录在顺序表中的序号，要求算法的时间复杂度在最好的情况下能达到O(m)。
【答案】算法如下:
顺序表中记录个数
关键字
该关键字在顺序表中的下标
索引表的一项
关键字
第 3 页，共 38 页
记录中的其他数据
给有m 个记录的顺序表seq 建立索引表
index
监视哨
关键字放入正确位置
第i 个记录的下标
5． 设有顺序放置的n 个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红、白、蓝之一。要求重新安排这些砾石，使得所有红色砾石在前，所有白色砾石居中，所有蓝色砾石居后。重新安排时，对每粒砾石的颜色只能察看一次，并且只允许交换操作来调整砾石的位置。
【答案】算法如下:
r 为含有n 个元素的线性表，元素是具有红、白和蓝色的砾石，用顺序存储结构存储
本算法对其排序，使所有红色栎石在前，白色居中，蓝色在最后
当前元素是红色
当前元素是白色
当前元素是蓝色
二、应用题
6． 一个ISAM 文件除了主索引外，还包括哪两级索引？
【答案】ISAM 文件有三级索引:磁盘组、柱面和磁盘，柱面索引存放在某个柱面上，若柱面索引较大，占多个磁道时，可建立柱面索引的索引——主索引。故还包括的两级索引是盘组和磁道。
7． 试叙述动态存储分配伙伴系统的基本思想，它和边界标识法不同点是什么？
【答案】(1)动态存储分配伙伴系统的基本思想
在伙伴系统中，无论占用块或空闲块，其大小均为(k为大于等于0的正整数) 。若内存容量为
，则空闲块大小只能是
。由同一大块分裂而得的两个小块互称“伙伴空间”，
(
若
) 或
109
如内存大小为2的块分裂成两个大小为2的块。只有两个“伙伴空间”才能合并成一个大空间。
起始地址为P ，
大小为的内存块，其伙伴的起始地址为
:
第 4 页，共 38 页