2018年北京大学地球与空间科学学院408计算机学科专业基础综合之数据结构考研基础五套测试题
● 摘要
一、算法设计题
1． 写一算法找出n 个数的最大值和最小值，要求最坏条件下的元素比较次数为
。
【答案】算法如下:
用最多3n/2－2次比较在n 个元素r 中选出最大值和最小值
n 为偶数时
r 最小值
("最大值) ；
2． 已知二叉树采用二叉链表存储，设计算法以输出二叉树T 中根结点到每个叶结点的路径。
【答案】算法如下::
打印从根结点bt 到结点p 之间路径上的所有结点
.
是元素为二叉树结点指针的栈，容量足够大
是数组，元素值为0或1, 访问左、右子树的标志，tag 和s 同
步
根结点就是所找结点
左子女入栈，并置标记
找到结点P , 栈中元素均为结点P 的祖先
从根结点到P 结点的路径为
沿左分支向下
本题不要求输出遍历序列，
这里只出栈
沿右分支向下
结束算法
为叶结点
从根结点到P 结点的路径为
输出从根到叶子q 的路径上的所有袓先
3． 元素集合已存入整型数组树T 的非递归算法:CSBT(r，A)
【答案】算法如下:
中，试写出依次取A 中各值构造一棵二叉排序
以存储在数组K 中的n 个关键字，建立一棵初始为空的二叉排序
树
在调用时，
T=null
f 是P 的双亲
申请结点空间
根结点
左子女
右子树根结点的值大于等于根
结点的值
算法结束
4． 若x 和y 是两个采用顺序结构存储的串，编写一个比较两个串是否相等的函数。
【答案】算法如下:
//本算法判断两个顺序存储的串x 和y 是否相等，相等返回1，否则返回
//对应字符相等，指针后移
5． 从键盘上输入一串正整数，最后输入-1作为结束标志。如:8，7，1，22，98，46，... ，75，-1。请设计一个非递归程序，创建一棵二叉排序树，并且该二叉排序树也必须是中序线索二叉树。设ltag ，data ，rta9，right) 。该二叉排序树上的结点结构为(teft，其中:data 域为结点的数据场。那么left 域中存在的是该结点的左儿子结点的地址。序遍历次序的前驱结点的地址。
【答案】算法如下:
从键盘上输入一串正整数，建立一棵初始为空的二叉排序树，同时也是线索二叉树
申请结点空间
结点赋值，其线
索初始化
查找结点的插入位置
f 是P 的双亲
根结点
左子女
修改线索
右子树根结点的值大于等于根结点的值
修改线索
读入下个数
算法结束
，
，那么left 域中存放的是该结点的按中
，那么right
域中存放的是该结点的右儿子结点的地址。
，那么right 域中存放的是该结点的按中序遍历次序的后继结点地址。
二、应用题
相关内容
相关标签