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． 以顺序存储结构表示串，设计算法。求串S 中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。
【答案】算法如下:
//串用一维数组s 存储，本算法求最长重复子串，返回其长度
//index记最长的串在s 串中的开始位置，max
记其长度
//length记局部重复子串长度，i 为字符数组下标
//上一个重复子串结束
//当前重复子串长
度大，则更新
max
//初始化下一重复子串的起始位置和长度
(”最长重复子串的长度为
.//算法结束
，在串中的位置
，max ，index) ；
时间复杂度:算法的时间复杂度为O(n)，每个字符与其后继比较一次。
3． 有n 个记录存储在带头结点的双向链表中，现用双向起泡排序法对其按上升序进行排序，请写出这种排序的算法(注:双向起泡排序即相邻两趟排序向相反方向起泡) 。
【答案】算法如下:
对存储在带头结点的双向链表head 中的元素进行双向起泡排序
设标记
双向链表尾，算法过程中是向上起泡的开始结点
是工作指针，指向当前结点
假定本趟无交换
向下(右) 起泡，一趟有一个最大元素沉底
交换两结点指针，涉及6条链
有交换
先将结点从链表上摘下
将temp 插到p 结点前
无交换，指针后移
准备向上起泡
向上(左) 起泡，一趟有一个最小元素冒
出
交换两结点指针，涉及6条链
有交换
先将temp 结点从链表上摘
下
将temp 插到p 结点后(右
)
无交换，指针前移
准备向下起泡
算法结束
4． 线性表中元素存放在向量A(1，... ，，1) 中，元素是整型数。试写出递归算法求出A 中的最大和最小元素。
【答案】算法如下:
//一维数组A 中存放有n 个整型数，本算法递归的求出其中的最小数和最大数
//算法结束
5． 给定一个整数数组求出b 中最长平台的长度。
【答案】算法如下:
//求具有N 个元素的整型数组b 中最长平台的长度。
b 中连续的相等元素构成的子序列称为平台。试设计算法，
相关内容
相关标签