2018年第二军医大学训练部408计算机学科专业基础综合之数据结构考研强化五套模拟题
● 摘要
一、算法设计题
1． 设表达式以字符形式己存入数组E 中，'#'为表达式的结束符，
试写出判断表达式中括号
是否配对的C 语言描述算法:EXYX(E)(注:算法中可调用栈操作的基本算法) 。 【答案】算法如下:
//E[ ]是有n 字符的字符数组，存放字符串表达式，以'#'结束。本算法判断表达式中圆括号是否匹配
//s是一维数组，容量足够大，是用于存放括号的栈
//top用作栈顶指针
//'#先入栈，用于和表达式结束符号'#'匹配
//字符数组E 的工作指针
//逐字符处理字符表达式的数组
//读人其他字符，不进行处理
2． 从键盘上输入一串正整数，最后输入-1作为结束标志。如:8，7，1，22，98，46，... ，75，-1。请设计一个非递归程序，创建一棵二叉排序树，并且该二叉排序树也必须是中序线索二叉树。设ltag ，data ，rta9，right) 。该二叉排序树上的结点结构为(teft，其中:data 域为结点的数据场。那么left 域中存在的是该结点的左儿子结点的地址。序遍历次序的前驱结点的地址。
【答案】算法如下:
从键盘上输入一串正整数，建立一棵初始为空的二叉排序树，同时也是线索二叉树
第 2 页，共 35 页
，
，那么left 域中存放的是该结点的按中
，那么right
域中存放的是该结点的右儿子结点的地址。
，那么right 域中存放的是该结点的按中序遍历次序的后继结点地址。
申请结点空间
结点赋值，其线
索初始化
查找结点的插入位置
f 是P 的双亲
根结点
左子女
修改线索
右子树根结点的值大于等于根结点的值
修改线索
读入下个数
算法结束
3． 已知关键字序列(
试写出一算法将(
利用(1)的算法写一个建大根堆的算法。 【答案】(1)算法如下:
''
假设
是大堆，本算法把
(2)
调成大堆
) 是大根堆。
) 调整为大根堆；
第 3 页，共 35 页
4． 设有一头指针为L 的带有表头结点的非循环双向链表，其每个结点中除有pred(前驱指针) ，data(数据) 和next(后继指针) 域外，还有一个访问频度域freq 。在链表被启用前，其值均初始化为零。每当在链表中进行一次Locate(L，X) 运算时，令元素值为x 的结点中freq 域的值增1，并使此链表中结点保持按访问频度非增(递减) 的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L，x) 运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。
【答案】算法如下:
//L是带头结点的按访问频度递减的双向链表
//本算法先査找数据x ，査找成功时结点的访问频度域增1，最后将该结点按频度递减插入链表中
//P为L 表的工作指针，q 为p 的前驱，用于査找插入位置
//查找值为x 的结点
("不存在所査结点\n”) ；exit(0)；
//令元素值为x 的结点的freq 域加
1
//将P 结点从链表上摘下
//以下査找P 结点的插人位置
//将P 结点插人
//返回值为x 的结点的指针
//算法结束
5． 设记录
的关键字为
。
，树结点
的败者树，要求除
指向败者记录，
和1
为全胜以外，只
记录下标。写一算法产生对应上述用O(1)辅助空间。
【答案】算法如下:
选得最小关键字记录后，沿从叶结点R[s]到根结点T[0]的路径调整败者树
是
指示新的胜者
第 4 页，共 35 页
的双亲结点
相关内容
相关标签