2018年西南科技大学计算机科学与技术学院814程序综合设计之数据结构教程考研仿真模拟五套题
● 摘要
一、算法设计题
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． 设整数序列ai ，a2，a3，…，an ，给出求解最大值的递归程序。
【答案】算法如下:
//设整数序列存于数组a 中，共有n 个，本算法求解其最大值
3． 设在4地(A, B , C , D) 之间架设有6座桥，如图所示。
要求从某一地出发，经过每座桥恰巧一次，最后仍回到原地。 (1)试就以上图形说明:此问题有解的条件是什么？
(2)设图中的顶点数为n ，试用C 或PASCAL 语言描述与求解此问题有关的数据结构并编写一个算法，找出满足要求的一条回路。
【答案】(1)只有所有的顶点的度都是偶数，才能有解。 (2)算法如下:
图中顶点的最大个数
弧(边) 结点
是邻接点在顶点向量中的下标，num 是边的编号
指向下一邻接点的指针
与弧(或边) 相关的信息指针
顶点结点
顶点信息及指向第一邻接点
的指针
邻接表
修改常规访问标志数组visited 的含义:当元素值为1时表示该边已访问；当元素值为0时表示该边尚未访问。
用邻接表作为存储结构的深度优先遍历算法
第一邻接点
结束dfs （ ）
求顶点的度
若顶点度为0, 或顶点的度不是偶
数，无解
无解
相关内容
相关标签