2018年辽宁石油化工大学计算机与通信工程学院408计算机学科专业基础综合之数据结构考研强化五套模拟题
● 摘要
一、算法设计题
1． 设有两个栈S 1，S 2都采用顺序栈方式，并且共享一个存储区的操作算法。
【答案】找的定乂:
两栈共享顺序存储空间所能达到的最多元素数
//假设元素类型为整型
； //栈空间
//top为两个栈顶指针
//S是如上定义的结构类型变量，为全局变量
(1)入栈操作:
//入栈操作。i 为栈号，i ＝〇表示左栈Sl ，i ＝l 表示右栈s2，x 是入栈元素。入栈成功返回1，否则返回
(2)出栈操作
//出栈算法。i 代表栈号，i ＝0时为s1栈，i ＝l 时为s2栈。出栈成功返回出栈元素，否则返﹣
1
为了尽量利用
空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S 1，S 2有关入栈和出找
//算法结束
2． 叙述基数排序算法，并对下列整数序列图示其基数排序的全过程。(179，208，93，306，55，859，984，9，271，33)
【答案】算法如下:
待排序记录的个数
关键字由d 个分量组成
静态链域
记录的其他数据域
存放n 个记录
.
用队列表示桶，共m 个
进行基数排序，返回收集用的链头指针
将
进行d 趟排序
初始化桶
按关键字的第j 个分量进行分配
k 为桶的序号
将将
链到桶头
链到桶尾
链成一个静态链表
将初始链表的终端结点指针置空，P 指向链表的第一个结点
队列的头、尾指针
对
修改桶的尾指针
扫描下一个记录
找第一个非空的桶
为收集链表的头指针，t 为尾指针
连接非空桶
本趟收集完毕，将链表的终端结点指针置空
3． 已知一具有n
个结点的二叉树的中序遍历序列与后序遍历序列分别存放于数组
和
中(设该二叉树各结点的数据值均不相同) 。请写一建立该二叉树的二叉链表结构的非递
归算法。该二叉链表的链结点结构为(lchild, data , rchild) ，其中data 为数据域，lchild 与rhild 分别为指向该结点左、右孩子的指针域(当孩子结点不存在时，相应指针域为空，用nil 表示) 。
【答案】算法如下:
由二叉树的中序序列IN[ ]和后序序列POST[ ]建立二叉树
和
为栈，容量足够大
初始化
取出栈顶数据
在中序序列中査等于
.
根结点的值
无左子树
将建立左子树的数据入栈
无右子树
右子树数据入
结束
:
中找到关键字从小到大排在第j 位上的记
的结点
分別是中序序列和后序序列第一和最后元素的下标，初始调用时
，
4． 对给定关键字序号j(1 录，写一个算法利用快速排序的划分思想实现上述查找(要求用最少的时间和最少的空间) 。 例如:给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。 【答案】算法如下；