2018年大连理工大学人文与社会科学学部408计算机学科专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 串以静态存储结构存储，结构如下所述，试实现串操作equal 算法。
串被确认的最大长度
【答案】算法如下:
//本算法判断字符串S 和字符串t 是否相等，如相等返回1，否则返回
//在类C 中，一维数组下标从零开始
//两串相等
//算法结束
2． 已知二叉树丁的结点形式为(llink，data ，count ，riink) ，在树中查找值为X 的结点，若找到， 则记数(count)加1; 否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。
【答案】算法如下:
在二叉排序树t 中査找值为x 的结点，若査到，则其结点的count 域值增1，否则，
将其
插入到二叉排序树中
f 指向当前结点的査找值为x 的结点，
双亲
无值为x 的结点，插入之
第 2 页，共 33 页
査询成功，值域为x 的结点的count 增
1
3． 从键盘上输入一串正整数，最后输入-1作为结束标志。如:8，7，1，22，98，46，... ，75，-1。请设计一个非递归程序，创建一棵二叉排序树，并且该二叉排序树也必须是中序线索二叉树。设ltag ，data ，rta9，right) 。该二叉排序树上的结点结构为(teft，其中:data 域为结点的数据场。那么left 域中存在的是该结点的左儿子结点的地址。序遍历次序的前驱结点的地址。
【答案】算法如下:
从键盘上输入一串正整数，建立一棵初始为空的二叉排序树，同时也是线索二叉树
申请结点空间
结点赋值，其线
索初始化
查找结点的插入位置
f 是P 的双亲
根结点
左子女
修改线索
右子树根结点的值大于等于根结点的值
修改线索
读入下个数
算法结束
第 3 页，共 33 页
，
，那么left 域中存放的是该结点的按中
，那么right
域中存放的是该结点的右儿子结点的地址。
，那么right 域中存放的是该结点的按中序遍历次序的后继结点地址。
4． 写一算法找出n 个数的最大值和最小值，要求最坏条件下的元素比较次数为
。
【答案】算法如下:
用最多3n/2－2次比较在n 个元素r 中选出最大值和最小值
n 为偶数时
r 最小值
("最大值) ；
5． 编写一算法，利用叶结点中的空指针域将所有叶结点链接为一个带有头结点的双链表，算法返回头结点的地址。
【答案】算法如下:
全局变量链表头指针
将
若bt 不空
中序遍历左子树
叶结点
第一个叶结点
生成头结点
头结点的左链空，右链指向第一个结点
第一个叶结点左链指向头结点，pre 指向当前叶结点
中序遍历右子树
最后一个叶结点的右链置空(链表结束标记
)
结束
；
当前叶结点链入双链表
树中的所有叶结点链成带头结点的双链表
二、应用题
6． 只要找出一个具有n 个元素的集合的第最适合? 给出实现的思想。
【答案】在具有n 个元素的集合中找第
个最小元素，应使用快速排序方法。其基本个最小元素，你所学过的排序方法中哪种
第 4 页，共 33 页