2018年福州大学软件学院408计算机学科专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 元素集合已存入整型数组树T 的非递归算法:CSBT(r，A)
【答案】算法如下:
以存储在数组K 中的n 个关键字，建立一棵初始为空的二叉排序
树
在调用时，
T=null
f 是P 的双亲
申请结点空间
根结点
左子女
右子树根结点的值大于等于根
结点的值
算法结束
2． 设有一个数组中存放了一个无序的关键序列
【答案】算法如下:
。现要求将K n 放在将元素排序后
中，试写出依次取A 中各值
构造一棵二叉排序
的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n(注:用程序实现) 。
3． 给定(已生成) 一个带表头结点的单链表，设head 为头指针，结点的结构为(data，next) ，data 为整型元素，next 为指针，试写出算法:按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间(要求:不允许使用数组作辅助空间) 。
【答案】算法如下:
//head是带头结点的单链表的头指针
//本算法按递增顺序输出单链表各结点的值，并释放结点所占的存储空间
//循环到仅剩头结点
//pre为元素最小值结点的前驱结点的指针
//P为工作指针
//记住当前最小值结点的前驱
//输出元素最小值结点的数据
//删除元素值最小的结点，释放结点
空间
//释放头结点
4． 设有两个栈S 1，S 2都采用顺序栈方式，并且共享一个存储区的操作算法。
【答案】找的定乂:
两栈共享顺序存储空间所能达到的最多元素数
//假设元素类型为整型
； //栈空间
//top为两个栈顶指针
//S是如上定义的结构类型变量，为全局变量
(1)入栈操作:
//入栈操作。i 为栈号，i ＝〇表示左栈Sl ，i ＝l 表示右栈s2，x 是入栈元素。入栈成功返回1，否则返回
为了尽量利用
空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S 1，S 2有关入栈和出找
(2)出栈操作
//出栈算法。i 代表栈号，i ＝0时为s1栈，i ＝l 时为s2栈。出栈成功返回出栈元素，否则返﹣
1
//算法结束
5． 已知一棵高度为K 具有n 个结点的二叉树，按顺序方式存储。
(1)编写用前序遍历树中每个结点的非递归算法；
(2)编写将树中最大序号叶结点的祖先结点全部打印输出的算法。 【答案】(1)算法如下:
全局变量
递妇遍历以顺序方式存储的二叉树bt ，i 是根结点下标(初始调用时为
1)
是桟s 的栈顶指针，栈容量足够大
访问根结点，设虚结点
以0表示
右子女的下标位置入
栈
沿左子女向下
取出栈顶元素
结束
(2)算法如下:
打印最大序号叶结点的全部袓先
找最大序号叶结点，该结点存储时在最后
的双亲结点f