2018年大连理工大学人文与社会科学学部408计算机学科专业基础综合之数据结构考研核心题库
● 摘要
一、算法设计题
1． 写出算法，求出中序线索二叉树中给定值为X 的结点之后继结点，返回该后继结点的指针。线索树中结点结构为；
。其中，data 存放结点的值；lc 、rc 为指向左、
右孩子或该结点前驱、后继的指针，ltag 、rtag 为标志域，若值为0, 则lc 、rc 为指向左、右孩子的指针；若值为1，则lc 、rc 为指向其前驱、后继结点的指针。
【答案】算法如下:
先在带头结点的中序线索二叉树T 中査找给定值为x 的结点，假定值为x 的结点存在
设P 指向二叉树的根结点
结束
在中序线索二叉树T 中,, 求给定值为x 的结点的
后继结点
首先在T 树上査找给定值为x 的结点，由p 指向
' 若P 的右标志为1, 则P 的rc 指针指向其后继
结点P 的右子树中最左边的结点是结点P 的中序后继
结库
.
2． 设A 和B 均为下三角矩阵，每一个都有n 行n 列。因此在下三角区域中各有n(n＋l)/2个无素。另设有一个二维数组C ，它有n 行n ＋1列。试设计一个方案，将两个矩阵A 和B 中的下三角区域元素存放于同一个C 中。要求将A 的下三角区域中的元素存放于C 的下三角区域中，B 的下三角区域中的元素转置后存放于C 的上三角区域中。并给出计算A 的矩阵元素矩阵元素
在C 中的存放位置下标的公式。
//本算法将n 阶方阵的下三角矩阵A 和B 置于C 中，矩阵B 要逆置
第 2 页，共 37 页
和B 的
【答案】算法如下:
//算法结束
3． 设有一个数组中存放了一个无序的关键序列
【答案】算法如下:
4． 假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT 中，写出计算该算术表达式值的算法。
【答案】算法如下:
以后序遍历算法求以二叉树表示的算术表达式的
值
.
5． 请运用快速排序思想，设计递归算法实现求n(n>1)个不同元素集合中的第f(
【答案】算法如下:
第 3 页，共 37 页
。现要求将K n 放在将元素排序后
的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n(注:用程序实现) 。
求左子树表示的子表达式的值
求右子树表示的子表达式的值
) 小元素。
在后半部分继续进行划分
在前半部分继续进行划分
二、应用题
6． 带权图(权值非负，表示边连接的两顶点间的距离) 的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径，假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法:
①该最短路径初始时仅包含初始顶点，令当前顶点为初始顶点；
②选择离最近且尚未在最短路径中的顶点V ，加入到最短路径中，修改当前顶点③重复步骤②，直到请证明之；否则请举例说明。
【答案】题目中方法不一定能(或不能) 求得最短路径。举例说明:
图
(a)
图(b)
图(a)中，假设初始顶点1到目标顶点4之间有一条边，权值x ＝2。显然图(a)中这顶点1和顶点4之间的最短路径长度为2。若按照题目中给定的方法找到的路径为初始顶点1经过中间结点2、3到目标顶点4,
即初始顶点显然，短路径。
图(b)中，假设初始顶点为1、目标顶点为4, 欲求从顶点1到顶点4之间的最短路径。显然，按照题目中给定的方法无法求出顶点1到顶点4的路径，而事实上顶点1到顶点4的最短路径为
第 4 页，共 37 页
;
是目标顶点时为止。请问上述方法能否求得最短路径? 若该方法可行，
一目标顶点4, 所经过的边的权值分别为。
大于2。因此按照题目中给定的方法所求得的路径并不是这两个顶点之间的最
相关内容
相关标签