2018年福州大学软件学院408计算机学科专业基础综合之数据结构考研基础五套测试题
● 摘要
一、算法设计题
1． 从键盘上输入一串正整数，最后输入-1作为结束标志。如:8，7，1，22，98，46，... ，75，-1。请设计一个非递归程序，创建一棵二叉排序树，并且该二叉排序树也必须是中序线索二叉树。设ltag ，data ，rta9，right) 。该二叉排序树上的结点结构为(teft，其中:data 域为结点的数据场。那么left 域中存在的是该结点的左儿子结点的地址。序遍历次序的前驱结点的地址。
【答案】算法如下:
从键盘上输入一串正整数，建立一棵初始为空的二叉排序树，同时也是线索二叉树
申请结点空间
结点赋值，其线
索初始化
查找结点的插入位置
f 是P 的双亲
根结点
左子女
修改线索
右子树根结点的值大于等于根结点的值
修改线索
读入下个数
第 2 页，共 36 页
，
，那么left 域中存放的是该结点的按中
，那么right
域中存放的是该结点的右儿子结点的地址。
，那么right 域中存放的是该结点的按中序遍历次序的后继结点地址。
算法结束
2． 已知非空双向链表由d 指出，结点结构为(llink，data ，rlink) ，请设计算法将链表中数据域值最大(假定唯一) 的那个结点移至链表的最前面。要求:不得额外申请新的双链表结点。
【答案】算法如下:
//d是循环链表，本算法将链表中数据域值最大的结点移至链表的最前面
//设链表有头结点
//q指向待处理结点
//P记数据域值最大的结点
//将P 摘下
//插人P 结点
3． 在输入数据无序的情况下，建立一个数据值为整型的递增有序的顺序存储线性表L ，且要求当输入相同数据值时，线性表中不能存在数据值相同的数据元素，试写出其算法。
顺序存储结构的线性表描述为:
线性表可能达到的最大长度}；
【答案】算法如下:
//在顺序表a 中査找值为x 的元素，査找成功返回0值，否则返回查找失败时的较大下标值
//当査找失败时，low ＝high ＋
1
//结束对分査找函数
第 3 页，共 36 页
//本过程生成顺序表
L
//顺序表L 初始化
//设x ＝9999时退出输入
//去查找x 元素
//不同元素才插入
//插入元素x ，线性表长度增
1
//结束过程creat
4． 写一算法找出n 个数的最大值和最小值，要求最坏条件下的元素比较次数为
。
【答案】算法如下:
用最多3n/2－2次比较在n 个元素r 中选出最大值和最小值
n 为偶数时
r 最小值
("最大值) ；
5． 假设串的存储结构如下所示，编写算法实现串的置换操作。
【答案】算法如下:
//s和t 是用一维数组存储的串，本算法将s 串第i 个字符开始连续j 个字符用t 串置换，操作成功返回1，否则返回0表示失败
//检査参数及置换后的长度的合法性
第 4 页，共 36 页
相关内容
相关标签