2018年安徽省培养单位合肥物质科学研究院408计算机学科专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 假设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)算法如下:
以嵌套括号表示结构打印二叉排序树
打印根结点值
左子女和右子女中至少有一个不空
输出左栝号
输出左子树的嵌套括号表示
若右子树不空，输出逗号
输出右子树的嵌套括号表示
输出右括号
2． 编写递归算法，从大到小输出给定二叉排序树中所有关踺字不小于X 的数据元素。要求你的算法的时间复杂度为
【答案】算法如下:
从大到小输出二叉排序树bst 中所有关键字不小于x 的数据元素
，其中，2为排序树中所含结点数，m 为输出的关键字个数。
3． 编写算法打印出由指针Hm 指向总表头的以十字链表形式存储的稀疏矩阵中每一行的非零元的个数。注意:行、列及总表头结点的形式为:
它们已用val 域链接成循环链表。非零元的结点形式也同上，每一行(列) 的非零元由right(down)域把它们链接成循环链表，该行(列) 的表头结点即为该行(列) 循环链表的表头。
【答案】算法如下:
//输出由Hm 指向的十字链表中每一行的非零元素个数
//数组A 记各行非零元个数，i 记行号
//循环完各行列表头
//P是稀疏矩阵行内工作指针，num 记该行非零个
数
//完成行内非零元的查找
//指针后移
//存该行非零元个数
//移到下一行列表头
//输出各行非零元个数
第
}算法结束
4． 在输入数据无序的情况下，建立一个数据值为整型的递增有序的顺序存储线性表L ，且要求当输入相同数据值时，线性表中不能存在数据值相同的数据元素，试写出其算法。
顺序存储结构的线性表描述为:
线性表可能达到的最大长度}；
【答案】算法如下:
//在顺序表a 中査找值为x 的元素，査找成功返回0值，否则返回查找失败时的较大下标值
//当査找失败时，low ＝high ＋
1
//结束对分査找函数
//本过程生成顺序表L
行非零元个数为
}
//稀疏矩阵非零元个数