2018年同济大学物理科学与工程学院408计算机学科专业基础综合之数据结构考研强化五套模拟题
● 摘要
一、算法设计题
1． 当一棵有n(
) 个结点的二叉树按顺序存储方式存储在
中时，试写一个算法，求
出二叉树中结点值分别为X 和Y 的两个结点的最近公共祖先结点的值。
【答案】算法如下:
二叉树顺序存储在数组
中，本算法求结点i 和j 的最近公共祖先结点的值
下标为i 的结点的双亲结点的下标
下标为j 的结点的双亲结点的下标
所査结点的最近公共祖先的下标是
，值是
设元素类型为
整型
2． 写一算法找出n 个数的最大值和最小值，要求最坏条件下的元素比较次数为
。
【答案】算法如下:
用最多3n/2－2次比较在n 个元素r 中选出最大值和最小值
n 为偶数时
r 最小值
("最大值) ；
3． 设从键盘输入一整数的序列:a 1，a 2，a 3，... ，a n ，试编写算法实现:用栈结构存储输入的整数，
当
时，将
入栈；当
时，输出栈顶整数并出栈。算法应对异常情况(入栈满等) 给
出相应的信息。
【答案】算法如下:
栈空间容量
//s是元素为整数的栈，本算法进行入栈和出栈操作
//top为栈顶指针，定义top ＝0时为栈空
//n个整数序列进行处理
//从键盘读入整数序列
//读入的整数不等于﹣1时人栈
//读入的整数等于﹣1时出栈
//算法结束。
4． 起泡排序算法是把大的元素向上移(气泡的上浮) ，也可以把小的元素向下移(气泡的下沉；请给出上浮和下沉过程交替的起泡排序算法。
【答案】算法如下:
相邻两趟向相反方向起泡的起泡排序算法，
起泡的上下界
设不发生交换
以上向下起泡
有交换，修改标志
change
修改界
气泡下沉，小元素上浮(向左
)
修改下界
5． 已知P 是指向单向循环链表最后一个结点的指针，试编写只包含一个循环的算法，将线性表(
) 改造为(
【答案】算法如下:
//本算法将线性表
//q指向a 1结点
//r记住a l 结点的指
针
//先将a 1结点放到正确位置
//从a 2结点开始
) 。
改造为
//暂存后继
//对称放置
//恢复待处理结点
二、应用题
6． 设将n(n>l)个整数存放到一维数组R 中. 试设计一个在时间和空间两方面都尽可能高效的算法，将R 中存有的序列循环左移P(0 中的数据由 . 要求: (1)给出算法的基本设计思想. (2)根据设计思想，采用C 或C++或JA V A 语言描述算法，关键之处给出注释. (3)说明你所设计算法的时间复杂度和空间复杂度. 【答案】(1)算法的基本设计思想:先将n 个数据由得到最终得到结果 (2)用C 语言算法描述如下: 变换为 原地逆置， 然后 ， 再将数组R 中的前，ti-P 个数和后P 个数分别原地逆置，
相关内容
相关标签