2018年东华大学计算机科学与技术学院408计算机学科专业基础综合之数据结构考研强化五套模拟题
● 摘要
一、算法设计题
1． 设二叉排序树的各元素值均不相同，采用二叉链表作为存储结构，试分别设计递归和非递归算法按递减序打印所有左子树为空，右子树非空的结点的数据域的值。
【答案】(1)递归算法如下:
递减序输出二叉排序树t 中所有左子树为空右子树非空的结点数据域的值
(2)非递归算法如下:
递减序输出二叉排序树t 中所有左子树为空、右子树非空的结点的数据域的值
S 是二叉排序树结点指针的栈，容量足够大
沿右分支向下
去左分支
算法结束
2． 请运用快速排序思想，设计递归算法实现求n(n>1)个不同元素集合中的第f(
【答案】算法如下:
第 2 页，共 36 页
) 小元素。
在后半部分继续进行划分
在前半部分继续进行划分
3． 写出一个递归算法来实现字符串逆序存储。
【答案】算法如下:
//字符串逆序存储的递归算法
r
//需要使用静态变量
//
规定
是字符串输入结束标志
//字符串逆序存储
//字符串结尾标记
//结束算法InvertStore
4． 编写算法，求二叉树的宽度。
【答案】算法如下:
求二叉树bt 的最大宽度
空二叉树宽度为
Q 是队列，元素为二叉树结点指针，容量
足够大
front 为队头指针，rear 为队尾指针
last 为同层最右结点在队列中的位置
temp 记当前层宽度，maxw 记最大宽度
根结点入队
同层元素数加
1
左子女入队
右子女入队
一层结束
指向下层最右元素
更新当前最大宽度
第 3 页，共 36 页
5． 写出一趟快速排序算法。
【答案】算法如下:
一趟快速排序算法，枢轴记录到位，并返回其所在位置
二、应用题
6． 特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能? 为什么？
【答案】特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律，因此可以对非零元素分配单元(对值相同元素只分配一个单元) ，将非零元素存储在向量中，元素的下标i 和j 和该元素在向量中的下标有一定规律，可以用简单公式表示，仍具有随机存取功能。而稀疏矩阵是指非零元素和矩阵容量相比很小
且分布没有规律。用十字链表作存储结构自然失去了随机
存取的功能。即使用三元组表的顺序存储结构，存取下标为i 和j 的元素时，要扫描三元组表，下标不同的元素，存取时间也不同，最好情况下存取时间为O(1)，最差情况下是O(n)，因此也失去了随机存取的功能。
7． 文件存储结构的基本形式有哪些? 一个文件采用何种存储结构应考虑哪些因素？
【答案】文件的基本组织方式有顺序组织、索引组织、散列组织和链组织，常用的结构有顺序结构、索引结构、散列结构。
(1)顺序结构，相应文件为顺序文件，其记录按存入文件的先后次序顺序存放。顺序文传本质上就是顺序表。若逻辑上相邻的两个记录在存储位置上相邻，则为连续文件；若记录之间以指针相链接，则称为串联文件。顺序文件只能顺序存取，要更新某个记录，必须复制整个文件。顺序文件连续存取的速度快，主要适用于顺序存取，批量修改的情况。
(2)带索引的结构，相应文件为索引文件。索引文件包括索引表和数据表，索引表中的索引项包括数据表中数据的关键字和相应地址，索引表有序，其物理顺序体现了文件的逻辑次序，实现了文件的线性结构。索引文件只能是磁盘文件，既能顺序存取，又能随机存取。
(3)散列结构，也称计算寻址结构，相应文件称为散列文件，其记录是根据关键字值经哈希函
第 4 页，共 36 页