2018年中国科学技术大学计算机科学与技术学院834软件工程基础[专业硕士]之数据结构考研核心题库
● 摘要
一、算法设计题
1． 试将下列递归过程改写为非递归过程。
【答案】算法如下:
2． 写出一个递归算法来实现字符串逆序存储。
【答案】算法如下:
//字符串逆序存储的递归算法
r
//需要使用静态变量
//
规定
是字符串输入结束标志
//字符串逆序存储
//字符串结尾标记
//结束算法InvertStore
3． (1)试分别找出满足下列条件的所有二叉树:(a)前序序列和中序序列相同:(b)前序序列和后序序列相同；(c)中序序列和后序序列相同。
(2)已知非空二叉树的结点结构为(lchild，data , rchild) ，设计算法:从右向左依次将所有叶子的数据值放到向量(假定向量的空间大于叶子的总个数) 中。
【答案】(1)满足条件的二叉树如下:
(a)若前序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。 (b)若前序序列与后序序列相同，则或为空树，或为只有根结点的二叉树。
(c)若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树。 (2)算法如下:
全局变量
从右向左依次将二叉树bt 的所有叶子的数据值放到a 向量中 .
中序遍历右子树
叶结点
中序遍历左子树
4． 已知L 为没有头结点的的单链表中第一个结点的指针，每个结点数据域存放一个字符，该字符可能是英文字母字符、数字字符或其他字符，编写算法构造三个以带头结点的单循环链表表示的线性表，使每个表中只含同一类字符(要求用最少的时间和最少的空间) 。
【答案】算法如下:
L 是不带头结点的单链表第一个结点的指针，链表中的数据域存放字符
//本算法将链表L 分解成含有英文字母字符、数字字符和其他幸符的带头结点的三个循环链表
//建立三个链表的头结点
//置三个循环链表为空表
//分解原链表
//L指向待处理结点的后继
//处理字母字符
//处理数字字符
//处理其他符号
//结束while(L!＝null)
//算法结束
5． 线性表中元素存放在向量A(1，... ，，1) 中，元素是整型数。试写出递归算法求出A 中的最大和最小元素。
【答案】算法如下:
//一维数组A 中存放有n 个整型数，本算法递归的求出其中的最小数和最大数
//算法结束
二、应用题
6． 已知一个大小为512个字长的存储，假设先后有6个用户申请大小分别为23, 45, 52, 100, 11 和19的存储空间，然后再顺序释放大小为45, 52, 11的占用块。假设以伙伴系统实现态存储管理。
(1)画出可利用空间表的初始状态。
(2)画出为6个用户分配所需要的存储空间后可利用空间表的状态以及每个用户所得到的存储块的起始地址。
(3)画出在回收3个占用块之后可利用空间表的状态。 【答案】(1)因为
，可利用空间表的初始状态图如图1所示:
图1可利用空间表的初始状态
(2)当用户申请大小为23的内存块时，因
9
8
7
7
，但没有大小为2的块，只有大小为2的
5
9
6
块，故将2的块分裂成两个大小为2的块，其中一块挂到可利用空间表上，另一块再分裂成两个大小为2的块。又将其中大小为2的一块挂到可利用空间表上，另一块再分裂成两个大小为2
6
5
的块。其中一块2的块挂到可利用空间表上，另一块分裂成两个大小为2的块，其中一块挂到可利用空间表上，另一块分给用户(地址0〜31) 。如此下去，最后每个用户得到的存储空间的起始地