2017年山东师范大学信息科学与工程学院914数据结构B[专业硕士]考研强化模拟题
● 摘要
目录
2017年山东师范大学信息科学与工程学院914数据结构B[专业硕士]考研强化模拟题（一） . 2 2017年山东师范大学信息科学与工程学院914数据结构B[专业硕士]考研强化模拟题（二） . 8 2017年山东师范大学信息科学与工程学院914数据结构B[专业硕士]考研强化模拟题（三） 16 2017年山东师范大学信息科学与工程学院914数据结构B[专业硕士]考研强化模拟题（四） 23 2017年山东师范大学信息科学与工程学院914数据结构B[专业硕士]考研强化模拟题（五） 30
第 1 页，共 35 页
一、填空题
1． 设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称 增量序列）依次是4，2，1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。
【答案】3; （10，7，-9，0，47，23，1，8，98，36）
2． 求图的最小生成树有两种算法，_____算法适合于求稀疏图的最小生成树e
【答案】克鲁斯卡尔
【解析】克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法，这种算法中，采用堆来存放边的集合，适合于边稀疏而顶点较多的图。
3． 若用n 表示图中顶点数目，则有_____条边的无向图成为完全图。
【答案】n （n-l ）/2
【解析】无向完全图中任意一个顶点都和其他n-1个顶点都有一条边，即为n （n-l ）。又因为每条边重复出现两次，所有无向完全图的边数为n （n-l ）/2。
4． —个字符串中_____称为该串的子串。
【答案】任意个连续的字符组成的子序列
5． 在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。
【答案】要加“虚结点”。
设编号为
和
的结点在顺序存储中的下标为
和
。
6． 在一个具有n 个单元的顺序栈中，假定以地址高端（即下标为n 的单元）作为栈底，以top 作为栈顶指针，则当向栈中压入一个元素时，top 的变化是top=_____。
【答案】
【解析】由于栈底在地址高端，栈中压入一个元素时，栈顶向地址底端移动一个单位，
所以
7． 二叉树由_____，_____，_____三个基本单元组成。
【答案】根结点；左子树；右子树
第 2 页，共 35 页
【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，
，
则结点
和
在同一层上的条件是
8． 阅读下列程序，指出其功能，并写出空格处应填上的语句。
【答案】
【解析】本题是在哈希表ht[]中插入值为的元素，如该元素已在哈希表中，报告出错。
9． 遍历图的过程实质上是_____，广度优先遍历图的时间复杂度_____; 深度优先遍历图的时间复杂度_____, 两者不同之处在于_____, 反映在数据结构上的差别是_____。
【答案】查找顶点的邻接点的过程；0（n+e）; 0（n+e）; 访问顶点的顺序不同；队列和栈 【解析】广度优先遍历图使用队列这种数据结构，深度优先遍历图使用栈这种数据结构。
10．设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。
【答案】模式匹配；模式串
二、算法设计题
11．已知两个定长数组，它们分别存放两个非降序有序序列，请编写程序把第二个数组序列中的数逐个插入到前一个数组序列中，完成后两个数组中的数分别有序（非降序）并且第一数组中所有的数都不大于第二个数组中的任意一个数。注意，不能另开辟数组，也不能对任意一个数组进行排序操作。
例如：
第一个数组为：4，12，28 第二个数组为：1，7，9，29，45 输出结果为：
1，4，7……第一个数组
9，12，28，29，45……第二个数组 【答案】算法如下：
第 3 页，共 35 页
12．设求按
是一个记录构成的数组，
13．辅助地址表的排序是不改变结点物理位置的排序。辅助地址表实际上是一组指针，用它来指出结点排序后的逻辑顺序地址。设
用
表示辅助地址表。初始时
非递减序）算法的语句序列。
【答案】算法如下：
中连续的相等元素构成的子序列称为平台。试设计算法，
表示n 个结点的值，
用
在排序中，凡需对结点交换就用它的地址来
是一个整数数组，其值介于1～100之间，现要
时，则要求将
的内容调整到
中
的内容调整A 中记录的次序，比如当
去。规定可使用的附加空间为
【答案】算法如下：
进行。例如当n=3时，对K （31，11，19）则有T （2，3，1）。试编写实现辅助地址表排序（按
14．给定一个整数数组求出b 中最长平台的长度。
【答案】算法如下：
第 4 页，共 35 页