2018年曲阜师范大学软件学院859数据结构考研核心题库
● 摘要
一、算法设计题
1． (1)试分别找出满足下列条件的所有二叉树:(a)前序序列和中序序列相同:(b)前序序列和后序序列相同；(c)中序序列和后序序列相同。
(2)已知非空二叉树的结点结构为(lchild，data , rchild) ，设计算法:从右向左依次将所有叶子的数据值放到向量(假定向量的空间大于叶子的总个数) 中。
【答案】(1)满足条件的二叉树如下:
(a)若前序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。 (b)若前序序列与后序序列相同，则或为空树，或为只有根结点的二叉树。
(c)若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树。 (2)算法如下:
全局变量
从右向左依次将二叉树bt 的所有叶子的数据值放到a 向量中 .
中序遍历右子树
叶结点
中序遍历左子树
2． 编写一算法，利用叶结点中的空指针域将所有叶结点链接为一个带有头结点的双链表，算法返回头结点的地址。
【答案】算法如下:
全局变量链表头指针
将
若bt 不空
中序遍历左子树
叶结点
第一个叶结点
生成头结点
头结点的左链空，右链指向第一个结点
第一个叶结点左链指向头结点，pre 指向当前叶结点
第 2 页，共 55 页
树中的所有叶结点链成带头结点的双链表
当前叶结点链入双链表
中序遍历右子树
最后一个叶结点的右链置空(链表结束标记
)
结束
；
3． 己知两个定长数组，它们分别存放两个非降序有序序列，请编写程序把第二个数组序列中的数逐个插入到前一个数组序列中，完成后两个数组中的数分别有序(非降序) 并且第一数组中所有的数都不大于第二个数组中的任意一个数。注意，不能另开辟数组，也不能对任意一个数组进行排序操作。
例如:
第一个数组为:4，12，28 第二个数组为:1，7，9，29，45 输出结果为:
第一个数组
第二个数组
【答案】算法如下:
//A和B 是各有m 个和n 个整数的非降序数组，本算法将B 数组元素逐个插入到A 中 //使A 中各元素均不大于B 中各元素，且两数组仍保持非降序排列
.
" 交换A[m﹣1]和
B[0]
//寻找A[m﹣1]的插入位置
//寻找B[0]的插入位置
算法结束
4． 已知P 是指向单向循环链表最后一个结点的指针，试编写只包含一个循环的算法，将线性表(
) 改造为(
【答案】算法如下:
//本算法将线性表
//q指向a 1结点
//r记住a l 结点的指
针
第 3 页，共 55 页
) 。
改造为
//先将a 1结点放到正确位置
//从a 2结点开始
//暂存后继
//对称放置
//恢复待处理结点
5． 设键盘输入n 个英语单词，输入格式为词个数，试编一程序，建立一个单向链表，实现:
(1)如果单词重复出现，则只在链表上保留一个。
(2)除满足(1)的要求外。链表结点还应有一个计数域，记录该单词重复出现的次数，然后输出出现次数最多的前k(k＜＝n) 个单词。
【答案】定义结点数据类型如下:
//频度域，记单词出现的次数
//maxsize是单词中可能含有的最多字母个数
(1)算法如下:
（ ）
//建立有n(n＞0) 个单词的单向链表，若单词重复出现，则只在链表中保留一个
//申请头结点
//链表初始化
//建立n 个结点的链表
//a是与链表中结点数据域同等长度的字符数组
//p是工作指针，pre 是前驱指针
//单词重复出现，频度增
1
//指针后移
//该单词没出现过，应插入
//将新结点插入到链表最后
第 4 页，共 55 页
其中n 表示随后输入英语单
相关内容
相关标签