2018年安徽师范大学数学计算机科学学院896计算机理论基础之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 已知P 是指向单向循环链表最后一个结点的指针，试编写只包含一个循环的算法，将线性表(
) 改造为(
【答案】算法如下:
//本算法将线性表
//q指向a 1结点
//r记住a l 结点的指
针
//先将a 1结点放到正确位置
//从a 2结点开始
//暂存后继
//对称放置
//恢复待处理结点
2． 设从键盘输入一整数的序列:a 1，a 2，a 3，... ，a n ，试编写算法实现:用栈结构存储输入的整数，
当
时，将
入栈；当
时，输出栈顶整数并出栈。算法应对异常情况(入栈满等) 给
出相应的信息。
【答案】算法如下
:
栈空间容量
//s是元素为整数的栈，本算法进行入栈和出栈操作
//top为栈顶指针，定义top ＝0时为栈空
//n个整数序列进行处理
//从键盘读入整数序列
//读入的整数不等于﹣1时人栈
第 2 页，共 19 页
) 。
改造为
//读入的整数等于﹣1时出栈
//算法结束。
3． 设计算法将一个带头结点的单链表A 分解为两个具有相同结构的链表B 、C , 其中B 表的结点为A 表中值小于零的结点，而C 表的结点为A 表中值大于零的结点(链表A 的元素类型为整型，要求B 、C 表利用A 表的结点) 。
【答案】算法如下:
//本算法将带头结点的单链表A 分解成数据域值小于零和大于零的两个单链表B 和
C
//为C 申请结点空间
//C初始化为空表
//P为工作指针
//B表初始化
//暂存P 的后继
//小于0的放入B 表
//将小于0的结点链人B 表
//P指向新的待处理结点
//算法结束
4． 设有两个栈S 1，S 2都采用顺序栈方式，并且共享一个存储区的操作算法。
【答案】找的定乂:
两栈共享顺序存储空间所能达到的最多元素数
//假设元素类型为整型
； //栈空间
//top为两个栈顶指针
//S是如上定义的结构类型变量，为全局变量
(1)入栈操作:
第 3 页，共 19 页
为了尽量利用
空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S 1，S 2有关入栈和出找
//入栈操作。i 为栈号，i ＝〇表示左栈Sl ，i ＝l 表示右栈s2，x 是入栈元素。入栈成功返回1，否则返回
(2)出栈操作
//出栈算法。i 代表栈号，i ＝0时为s1栈，i ＝l 时为s2栈。出栈成功返回出栈元素，否则返﹣
1
//算法结束
5． 在输入数据无序的情况下，建立一个数据值为整型的递增有序的顺序存储线性表L ，且要求当输入相同数据值时，线性表中不能存在数据值相同的数据元素，试写出其算法。
顺序存储结构的线性表描述为:
线性表可能达到的最大长度}；
【答案】算法如下:
//在顺序表a 中査找值为x 的元素，査找成功返回0值，否则返回查找失败时的较大下标值
第 4 页，共 19 页