2018年福州大学软件学院408计算机学科专业基础综合之数据结构考研强化五套模拟题
● 摘要
一、算法设计题
1. 已知一棵二叉树的前序遍历序列和中序遍历序列分别存于两个一维数组中,试编写算法建立该二叉树的二叉链表。
【答案】算法如下:
根据二叉树前序序列pre 和中序序列in 建立二叉树。元素下标
申请结点
是根
在中序序列中,根结点将树分成左右
子树
无左子树
递归建立左子树
无右子树
递归建立右子树
结束:
) 区分在遍
2. 假设在二叉链表的结点中增设两个域:parent 域指示其双亲结点:flag 域(取值为历的递推形式的算法。
【答案】算法如下:
在增加双亲指针
和标志域
的二叉树中,不用栈后序遍历二叉树
和
是两个序列首、尾
历过程中到达该结点时应继续向左、向右或访问该结点。试以此存储结构编写不用栈进行后序遍
向左
第 2 页,共 37 页
向右
访问根结点
找被访问结点的双亲
结束
3. 试将下列递归过程改写为非递归过程。
【答案】算法如下:
4. 试设计一个C 语言算法(或C 语言程序) :用单链表做存储结构,以回车符为结束标志,输入一个任意长度的字符串,然后判断该字符串是否为“回文”(正向读和反向读时,串值相同的字符串称为“回文”) ,输出信息“Yes ”或“NO ”;最后删除字符串并释放全部空间。例如:
若输入“ABCD12321DCBA”是回文,则输出“Yes”; 若输入“ABCD123DCBA”,不是回文,则输出“NO”。
要求:定义相关数据类型,不得使用数组(顺序表) 做字符串的存储结构和辅助存储空间。假定字符串的长度为n ,试分析上述算法的时间复杂度。
【答案】算法如下:
//本算法判断数据域为字符且长为n 的单链表是否是”回文" ,返回1或0表示成功或失败
//字符栈,容量足够大
//设链表带头结点
//前一半字符入栈,链表指针后移
//若链表有奇数个结点,则跳过中间结点
第 3 页,共 37 页
//不是回文
5. (1)试分别找出满足下列条件的所有二叉树:(a)前序序列和中序序列相同:(b)前序序列和后序序列相同;(c)中序序列和后序序列相同。
(2)已知非空二叉树的结点结构为(lchild,data , rchild) ,设计算法:从右向左依次将所有叶子的数据值放到向量(假定向量的空间大于叶子的总个数) 中。
【答案】(1)满足条件的二叉树如下:
(a)若前序序列与中序序列相同,则或为空树,或为任一结点至多只有右子树的二叉树。 (b)若前序序列与后序序列相同,则或为空树,或为只有根结点的二叉树。
(c)若中序序列与后序序列相同,则或为空树,或为任一结点至多只有左子树的二叉树。 (2)算法如下:
全局变量
从右向左依次将二叉树bt 的所有叶子的数据值放到a 向量中 .
中序遍历右子树
叶结点
中序遍历左子树
二、应用题
6. 设某文件经内排序后得到100个初始归并段(初始顺串) ,若使用多路归并排序算法,并要求三趟归并完成排序,问归并路数最少为多少?
【答案】设归并路数为k ,归并趟数为s ,则
,因
,且k 为整数,故k=5,
即最少5-路归并可以完成排序。
7. 试比较顺序文件、索引非顺序文件、索引顺序文件、哈希文件的存储代价,检索、插入、删除记录时的优点和缺点。
【答案】(1)顺序文件只能顺序查找,优点是批量检索速度快,不适于单个记录的检索。顺序,文件不能像顺序表那样插入、删除和修改,因文件中的记录不能象向量空间中的元素那样“移动”只能通过复制整个文件实现上述操作。
(2)索引非顺序文件适合随机存取,不适合顺序存取,因主关键字未排序,若顺序存取会引起磁头频繁移动。索引顺序文件是最常用的文件组织,因主文件有序,既可顺序存取也可随机存取。索引非顺序文件是稠密索引,可以“预查找”,索引顺序文件是稀疏索引,不能“预查找”,但
第 4 页,共 37 页
相关内容
相关标签