2018年同济大学交通运输工程学院408计算机学科专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 编写递归算法，从大到小输出给定二叉排序树中所有关踺字不小于X 的数据元素。要求你的算法的时间复杂度为
【答案】算法如下:
从大到小输出二叉排序树bst 中所有关键字不小于x 的数据元素
，其中，2为排序树中所含结点数，m 为输出的关键字个数。
2． 已知非空双向链表由d 指出，结点结构为(llink，data ，rlink) ，请设计算法将链表中数据域值最大(假定唯一) 的那个结点移至链表的最前面。要求:不得额外申请新的双链表结点。
【答案】算法如下:
//d是循环链表，本算法将链表中数据域值最大的结点移至链表的最前面
//设链表有头结点
//q指向待处理结点
//P记数据域值最大的结点
//将P 摘下
//插人P 结点
3． 假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法(注:已知树中的结点数) 。
【答案】算法如下:
求以双亲表示法作为存储结构的树的深度
深度加1, 并取新的双亲
最大深度更新
返回树的深度
’结束Depth
4． 已知两个链表A 和B 分别表示两个集合，其元素递增排列。编一函数，求A 与B 的交集，并存放于A 链表中。
【答案】算法如下:
//设工作指针pa 和pb ；
//结果表中当前合并结点的前驱的指针
//交集并入结果表中
//释放结点空
间
//释放结点空间
//释放结点空间
//置链表尾标记
//注:本算法中也可对B 表不作释放空间的处理
5． 请运用快速排序思想，设计递归算法实现求n(n>1)个不同元素集合中的第f(
【答案】算法如下:
在后半部分继续进行划分
) 小元素。
在前半部分继续进行划分
二、应用题
6． 输入一个正整数序列(53，17，12，66，58，70，87，25，56，60) ，试完成下列各题。
(1)按次序构造一棵二叉排序树BS 。
(2)依此二叉排序树，如何得到一个从大到小的有序序列？ (3)画出在此二叉排序树中删除“66”后的树结构。 【答案】(1)构造的二叉排序树如图1所示:
图1二叉排序树
(2)若二叉树非空，要得到一个从大到小的有序序列可以先中序遍历右子树；再访问根结点；最后中序遍历左子树。
(3)如图2所示:
图2
7． 将算术表达式
转化为二叉树。
【答案】该算术表达式转化的二叉树如图所示。
图