2018年中山大学数据科学与计算机学院408计算机学科专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 从键盘上输入一串正整数，最后输入-1作为结束标志。如:8，7，1，22，98，46，... ，75，-1。请设计一个非递归程序，创建一棵二叉排序树，并且该二叉排序树也必须是中序线索二叉树。设ltag ，data ，rta9，right) 。该二叉排序树上的结点结构为(teft，其中:data 域为结点的数据场。那么left 域中存在的是该结点的左儿子结点的地址。序遍历次序的前驱结点的地址。
【答案】算法如下:
从键盘上输入一串正整数，建立一棵初始为空的二叉排序树，同时也是线索二叉树
申请结点空间
结点赋值，其线
索初始化
查找结点的插入位置
f 是P 的双亲
根结点
左子女
修改线索
右子树根结点的值大于等于根结点的值
修改线索
读入下个数
第 2 页，共 38 页
，
，那么left 域中存放的是该结点的按中
，那么right
域中存放的是该结点的右儿子结点的地址。
，那么right 域中存放的是该结点的按中序遍历次序的后继结点地址。
算法结束
2． 设有一个数组中存放了一个无序的关键序列
【答案】算法如下:
3． 己知L 为链表的头结点地址，表中共有m(m＞3) 个结点，从表中第i 个结点(l＜i ＜m) 起到第m 个结点构成一个循环部分链表，设计将这部分循环链表中所有结点顺序完全倒置的算法。
【答案】算法如下:
//L是有m 个结点的链表的头结点的指针。表中从第个结点到第m 个结点构成循环部分链表//本算法将这部分循环链表倒置
//p是工作指针，初始指向第二结点(已假定i ＞
l) //pre是前驱结点指针，最终指向第i ﹣i 个结点
//计数器
//查找第i 个结点
//査找结束，P 指向第i 个结点
//暂存第i 个结点的指针
//p指向第i ＋l 个结点，准备逆置
//上面while 循环结束时，j ＝i ﹣1现从第i ＋1结点开始逆置
//暂存P 的后继结点
+
//逆置P 结点
//P恢复为当前待逆置结点
//计数器增
1
第 3 页，共 38 页
。现要求将K n 放在将元素排序后
的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n(注:用程序实现) 。
//将原第i 个结点的后继指针指向原第m 个结点
4． 已知L 为没有头结点的的单链表中第一个结点的指针，每个结点数据域存放一个字符，该字符可能是英文字母字符、数字字符或其他字符，编写算法构造三个以带头结点的单循环链表表示的线性表，使每个表中只含同一类字符(要求用最少的时间和最少的空间) 。
【答案】算法如下:
L 是不带头结点的单链表第一个结点的指针，链表中的数据域存放字符
//本算法将链表L 分解成含有英文字母字符、数字字符和其他幸符的带头结点的三个循环链表
//建立三个链表的头结点
//置三个循环链表为空表
//分解原链表
//L指向待处理结点的后继
//处理字母字符
//处理数字字符
//处理其他符号
//结束while(L!＝
null) //算法结束
5． 设从键盘输入一整数的序列:a 1，a 2，a 3，... ，a n ，试编写算法实现:用栈结构存储输入的整数，
当
时，将
入栈；当
时，输出栈顶整数并出栈。算法应对异常情况(入栈满等) 给
出相应的信息。
【答案】算法如下
:
栈空间容量
//s是元素为整数的栈，本算法进行入栈和出栈操作
//top为栈顶指针，定义top ＝0时为栈空
//n个整数序列进行处理
//从键盘读入整数序列
//读入的整数不等于﹣1时人栈
//读入的整数等于﹣1时出栈
第 4 页，共 38 页
相关内容
相关标签