2018年西南财经大学经济信息工程学院408计算机学科专业基础综合之数据结构考研核心题库
● 摘要
一、算法设计题
1． 请运用快速排序思想，设计递归算法实现求n(n>1)个不同元素集合中的第f(
【答案】算法如下:
在后半部分继续进行划分
在前半部分继续进行划分
2． 假设K1，... ，Kn 是n 个关键词，试解答：
(1)试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为K1，K2，…，Kn 时，用算法建立一棵以llink —rlink 链接表示的二叉查找树。
(2)设计一个算法，打印出该二叉查找树的嵌套括号表示结构。例如，K1=B，K2=A，K3=D，K4=C，K5=E，则用二叉查找树的插入算法建立如图所示的二叉查找树。
) 小元素。
图
该二叉查找树的嵌套括号表示结构为:B(A，D(C，E)) 。 【答案】(1)算法如下:
在二叉排序树bst 上査找值为K 的结点，返回其双亲结点指针
f
以存储在数组R 中的n 个关键字，建立一棵初始为空的二叉排序树
不再插入相同值结点
.
申请结点空间
根结点
左子女
右子女
结束算法 (2)算法如下:
以嵌套括号表示结构打印二叉排序树
打印根结点值
左子女和右子女中至少有一个不空
输出左栝号
输出左子树的嵌套括号表示
若右子树不空，输出逗号
输出右子树的嵌套括号表示
输出右括号
3． 设计算法将一棵以二叉链表存储的二叉树按顺序方式存储到一维数组中(注:按层从上到下，由左到右) 。
【答案】算法如下:
是结点在一维数组中的编
号
队列，容量足够大
本算法将二叉树的二叉链表存储结构转换为顺序存储结构
seq
初始化，#代表虚结点
根结点入队
存入顺
序存储结构
左
子女入队
右
子女人队
4． 设有两个栈S 1，S 2都采用顺序栈方式，并且共享一个存储区的操作算法。
【答案】找的定乂:
两栈共享顺序存储空间所能达到的最多元素数
//假设元素类型为整型
； //栈空间
//top为两个栈顶指针
//S是如上定义的结构类型变量，为全局变量
(1)入栈操作:
//入栈操作。i 为栈号，i ＝〇表示左栈Sl ，i ＝l 表示右栈s2，x 是入栈元素。入栈成功返回1，否则返回
(2)出栈操作
为了尽量利用
空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S 1，S 2有关入栈和出找
相关内容
相关标签