2018年长江大学计算机技术(专业学位)408计算机学科专业基础综合之数据结构考研核心题库
● 摘要
一、算法设计题
1． 已知关键字序列(
试写出一算法将(
利用(1)的算法写一个建大根堆的算法。 【答案】(1)算法如下:
''
假设
是大堆，本算法把
(2)
2． 已知一棵二叉树的前序遍历序列和中序遍历序列分别存于两个一维数组中，试编写算法建立该二叉树的二叉链表。
【答案】算法如下:
根据二叉树前序序列pre 和中序序列in 建立二叉树。元素下标
申请结点
是根
在中序序列中，根结点将树分成左右
子树
无左子树
递归建立左子树
无右子树
递归建立右子树
结束:
和
是两个序列首、尾
调成大堆
) 是大根堆。
) 调整为大根堆；
3． (1)试分别找出满足下列条件的所有二叉树:(a)前序序列和中序序列相同:(b)前序序列和后序序列相同；(c)中序序列和后序序列相同。
(2)已知非空二叉树的结点结构为(lchild，data , rchild) ，设计算法:从右向左依次将所有叶子的数据值放到向量(假定向量的空间大于叶子的总个数) 中。
【答案】(1)满足条件的二叉树如下:
(a)若前序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。 (b)若前序序列与后序序列相同，则或为空树，或为只有根结点的二叉树。
(c)若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树。 (2)算法如下:
全局变量
从右向左依次将二叉树bt 的所有叶子的数据值放到a 向量中 .
中序遍历右子树
叶结点
中序遍历左子树
4． 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。
【答案】算法如下:
//la，lb 分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列 //本算法将两链表合并成一个按元素值递减次序排列的单链表
//pa, pb 分别是链表la 和lb 的工作指针
//la作为结果链表的头指针，先将结果链表初始化为空
//当两链表均不为空时
//将pa 的后继结点暂存于
r
//将pa 结点链于结果表中，同时逆置
//恢复pa 为当前待比较结点
//将pb 的后继结点暂存于
r
//将pb 结点链于结果表中，同时逆置
//恢复pb 为当前待比较结点
//避免再对pa 写下面的While 语句
//算法Union 结束
5． 按图的宽度优先搜索法写一算法判别以邻接矩阵存储的有向图中是否存在由顶点到顶点的路径
。
设有向图有n 个顶点
判断以邻接矩阵方式存储的有向图中是否存在由顶点到顶点的路径
是队列，容量足够大，元素是顶点编号
人队
到顶点
不存在路径
【答案】算法如下:
二、应用题
6． 文件F 由200条记录组成, 记录从1开始编号, 用户打开文件后, 欲将内存中的一条记录插入文件F 中, 作为其第30条记录, 请回答下列问题, 并说明理由。
(1)若文件系统为顺序分配方式, 每个存储块存放一条记录, 文件F 的存储区域前后均有足够空闲的存储空间, 则要完成上述操作最少要访问多少存储块？F 的文件控制区内容会有哪些改变？
(2)若文件系统为链接分配方式, 每个存储块存放的一条记录和一个链接指针, 则要完成上述操作最少要访问多少存储块？若每个存储块大小为1KB , 其中4个字节存放指针, 则该系统支撑文件的最大长度是多少？
【答案】(1)因为要最少访问, 所以选择将前29块前移一个存储块单元, 然后将要写入的记录写入到当前的第30条的位置上。由于前移都要先访问原存储块将数据读出, 再访问目标存储块将数据写入,
所以最少需要访问
块存储块
F 的文件区的文件长度加1, 起始块号减1
(2)采用链接方式则需要顺序访问前29块存储块, 然后将新纪录的存储块插入链中即可, 把新