2018年辽宁工业大学电子与信息工程学院408计算机学科专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 写出按后序序列遍历中序线索树的算法。
【答案】算法如下:
求结点t 最左子孙的左线索
沿左分支向下
求结点t 最右子孙的右线索
沿右分支向下
若t 是
后序遍历中序线索二叉树
bt
沿左分支向下
左孩子为线索，右孩子为链，相当从左返回
P 为叶子, 相当从右返回
访问结点
修改P 指向双亲
是左子女，用最右子孙的右线索找双亲
.
转向当前结点右分支
结束
第 2 页，共 37 页
的右孩子，返回1, 否则返回
2． 已知非空双向链表由d 指出，结点结构为(llink，data ，rlink) ，请设计算法将链表中数据域值最大(假定唯一) 的那个结点移至链表的最前面。要求:不得额外申请新的双链表结点。
【答案】算法如下:
//d是循环链表，本算法将链表中数据域值最大的结点移至链表的最前面
//设链表有头结点
//q指向待处理结点
//P记数据域值最大的结点
//将P 摘下
//插人P 结点
3． 假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT 中，写出计算该算术表达式值的算法。
【答案】算法如下:
以后序遍历算法求以二叉树表示的算术表达式的
值
.
4． 已知无向图采用邻接表存储方式，试写出删除边(i, j) 的算法。
【答案】算法如下:
在用邻接表方式存储的无向图g 中，删除边(i,
j)
删顶点i 的边结点(i, j) , pre 是前驱指针
第 3 页，共 37 页
求左子树表示的子表达式的值
求右子树表示的子表达式的值
释放空间
沿链表继续査找
删顶点j 的边结点(j,
i)
释放空间
沿链表继续査找
5． 结点类型和存储结构如下:
试设计一个排序算法，要求不移动结点的存储位置，只在结点的count 字段记录结点在排序中的序号，并将排序结果按升序输出。
【答案】算法如下:
对存储在数组R 中的记录进行排序
初始化
设R[0]作监视哨，Max 是该类型最大元
素
初始假定第一个元素有序
前驱
第一个元素
査找第i 个元素的序号
将笫i 个元素链入静态链表
二、应用题
6． 某文件系统空间的最大容量为
, 以磁盘块为基本分配单位, 磁盘块大小为1KB 。
文件控制块(FCB)包含一个512B 的索引表区。请回答下列问题。
(1)假设索引表区仅采用直接索引结构, 索引表区存放文件占用的磁盘块号。索引表项中块号最少占多少字节? 可支持的单个文件最大长度是多少字节？
(2)假设索引表区采用如下结构:第0〜7字节采用<起始块号, 块数>格式表示文件创建时预分
第 4 页，共 37 页
相关内容
相关标签