2018年长江大学计算机技术(专业学位)408计算机学科专业基础综合之数据结构考研基础五套测试题
● 摘要
一、算法设计题
1． 编写一算法，利用叶结点中的空指针域将所有叶结点链接为一个带有头结点的双链表，算法返回头结点的地址。
【答案】算法如下:
全局变量链表头指针
将
若bt 不空
中序遍历左子树
叶结点
第一个叶结点
生成头结点
头结点的左链空，右链指向第一个结点
第一个叶结点左链指向头结点，pre 指向当前叶结点
中序遍历右子树
最后一个叶结点的右链置空(链表结束标记
)
结束
；
中找到关键字从小到大排在第j 位上的记
2． 对给定关键字序号j(1 当前叶结点链入双链表 树中的所有叶结点链成带头结点的双链表 录，写一个算法利用快速排序的划分思想实现上述查找(要求用最少的时间和最少的空间) 。 例如:给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。 【答案】算法如下； 在后半部分继续进行划分 在前半部分继续进行划分 3． 写出一个递归算法来实现字符串逆序存储。 【答案】算法如下: //字符串逆序存储的递归算法 r //需要使用静态变量 // 规定 是字符串输入结束标志 //字符串逆序存储 //字符串结尾标记 //结束算法InvertStore 4． 给出以十字链表作存储结构，建立图的算法，输入(i, j , V) , 其中i , j 为顶点号，v 为权值。 【答案】算法如下: 建立有向图的十字链表存储结构 假定权值为整型 建立顶点向量 当输入i 、j 、v 之一为0时，结 束算法运行 申请结点 弧结点中权值域 算法结束 5． 设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 要逆置 //算法结束 【答案】算法如下: 和B 的 二、应用题 6． 对于后序线索二叉树，怎样查找任意结点的直接后继? 对于中序线索二叉树，怎样查找任意结点的直接前驱？ 【答案】(1)后序线索树中结点的后继的方法如下:根结点无后继；当结点的rtag=1时，其右线索指向后继；当结点的rtag=0且是其双亲的右孩子，或是双亲的左孩子且双亲无右孩子时，其双亲是该结点的后继；当结点是其双亲的左孩子且双亲有右孩子时，其双亲结点右子树中最左下的叶结点是其后继。 (2)对中序线索二叉树的某结点，若其左标记等于1，则左孩子为线索，指向直接前驱；否则，其前驱是其左子树上按中序遍历的最后一个结点。 7． 我们知道，对于n 个元素组成的线性表进行快速排序时，所需进行的比较次数与这n 个元素的初始排序有关。问: 当n=7时，在最好情况下需进行多少次比较? 请说明理由。 当n=7时，给出一个最好情况的初始排序的实例。 当n=7时，在最坏情况下需进行多少次比较? 请说明理由。 当n=7时，给出一个最坏情况的初始排序的实例。 【答案】(1)在最好情况下，每次划分能得到两个长度相等的子文件。假设文件的长度那么第一趟划分得到两个长度均为以此类推，总共进行 的子文件，第二趟划分得到4个长度均为 ， 的子文件， (n+1)趟划分，各子文件的长度均为1，排序完毕。当n=7时，k=3，在 最好情况下，第一需比较6次，第二趟分别对两个子文件(长度均为3，k=2)进行排序，各需2次，