2018年北京市培养单位高能物理研究所862计算机学科综合(非专业)之数据结构考研强化五套模拟题
● 摘要
一、算法设计题
1． 在二叉排序树的结构中，有些数据元素值可能是相同的，设计一个算法实现按递增有序打印结点的数据域，要求相同的数据元素仅输出一个，算法还应能报出最后被滤掉而未输出的数据元素个数，对如图所示的二叉排序树，输出为:10，12，13，15，18，21，27，35，42。滤掉3个元素。
图
【答案】算法如下:
递增序输出二叉排序树中结点的值，滤去重复元素
中序遍历左子树
是当前访问结点的前驱，调用本算法时初值为
null
记重复元素，调用
本算法时初值为
前驱后移
中序遍历右子树
结束
算法
2． 设从键盘输入一整数的序列:a 1，a 2，a 3，... ，a n ，试编写算法实现:用栈结构存储输入的整数，
当
时，将
入栈；当
时，输出栈顶整数并出栈。算法应对异常情况(入栈满等) 给
出相应的信息。
【答案】算法如下:
栈空间容量
//s是元素为整数的栈，本算法进行入栈和出栈操作
//top为栈顶指针，定义top ＝0时为栈空
//n个整数序列进行处理
//从键盘读入整数序列
//读入的整数不等于﹣1时人栈
//读入的整数等于﹣1时出栈
//算法结束。
3． 有二叉排序树采用二叉链表方式存放，树中结点值各不相同，欲得到一个由大到小的结点值递减序列，简述处理方法思路，用非递归形式写出算法。
【答案】算法如下:
按递减次序输出二叉排序树结点的值
是元素为二叉树结点指针的栈，容量足够大
沿右子树向下
结束
4． 设整数序列ai ，a2，a3，…，an ，给出求解最大值的递归程序。
【答案】算法如下:
//设整数序列存于数组a 中，共有n 个，本算法求解其最大值
5． 编写对有序表进行顺序查找的算法，并画出对有序表进行顺序查找的判定树。假设每次查找时的给定值为随机值，又查找成功和不成功的概率也相等，试求进行每一次查找时和给定值进行比较的关键字个数的期望值。
【答案】算法如下:
在具有个元素的有序表R 中，顺序査找值为K 的结点，査找成功返回其位置
否则返回-1表示失败
元素序号
结束
，查找失败的平均查找
期望值分析:在等概率情况下，则查找成功的平均查找长度为等，则查找成功时和关键字比较的个数的期望值约为
。
长度为(n+2)/2(失败位置除小于每一个，还存在大于最后一个) 。若查找成功和不成功的概率也相
二、应用题
6． 已知有6个顶点(顶点编号为0--5) 的有向带权图G , 其邻接矩阵A 为上三角矩阵, 按行为主序(行优先) 保存在如下的一维数组中。
要求:
(1)写出图G 的邻接矩阵A 。 (2)画出有向带权图G 。
(3)求图G 的关键路径, 并计算该关键路径的长度。
【答案】(1)由题可以画出待定上三角矩阵的结构图如下(图中？为待定元素) :
可以看出, 第一行至第五行主对角线上方的元素分别为5, 4, 3, 2, 1个, 由此可以画出压缩存储数组中的元素所属行的情况, 如下图所示:
将各元素填入各行即得邻接矩阵:
相关内容
相关标签