本文格式为Word版，下载可任意编辑2022年浙江大学光电信息工程学院408计算机学科专业基础综合之数据结构考研基础五套测试题 专注考研专业课13年，供给海量考研优质文档！ 第 1 页，共 36 页 目次 2022年浙江大学光电信息工程学院408计算机学科专业根基综合之数据布局考研根基五套测试 题（一） .................................................................................................................................. 2 2022年浙江大学光电信息工程学院408计算机学科专业根基综合之数据布局考研根基五套测试 题（二） .................................................................................................................................. 9 2022年浙江大学光电信息工程学院408计算机学科专业根基综合之数据布局考研根基五套测试 题（三） ................................................................................................................................ 16 2022年浙江大学光电信息工程学院408计算机学科专业根基综合之数据布局考研根基五套测试 题（四） ................................................................................................................................ 23 2022年浙江大学光电信息工程学院408计算机学科专业根基综合之数据布局考研根基五套测试 题（五） (30) 专注考研专业课13年，供给海量考研优质文档！ 第 2 页，共 36 页 2022年浙江大学光电信息工程学院408计算机学科专业根基综合之数据布局考研基 础五套测试题（一） 说明：根据本校该考试科目历年考研命题规律，结合出题侧重点和难度，用心整理编写。
根基检测使用共五套试题，均含有细致答案解析，也是众多专业课机构参考借鉴资料，考研必备 —————————————————————————————————————————— 一、算法设计题 1． 设T 是一棵满二叉树，写一个把T 的后序遍历序列转换为前序遍历序列的递归算法 【答案】算法如下: 将满二叉树的后序序列转为前序序列， 是序列初始和结果结点的下 标 根结点 左子树或右子树的结点数 将左子树前序序列转 为后序序列 将右子树前序序列转为 后序序列 2． 在二叉排序树的布局中，有些数据元素值可能是一致的，设计一个算法实现按递增有序打印结点的数据域，要求一致的数据元素仅输出一个，算法还应能报出结果被滤掉而未输出的数据元素个数，对如下图的二叉排序树，输出为:10，12，13，15，18，21，27，35，42滤掉3个元素 图 【答案】算法如下: 递增序输出二叉排序树中结点的值，滤去重复元素 专注考研专业课13年，供给海量考研优质文档！ 第 3 页，共 36 页 中序遍历左子树 是当前访问结点的前驱，调用本算法时初值为 null 记重复元素，调用 本算法时初值为 前驱后移 中序遍历右子树 终止算法 3． 若x 和y 是两个采用依次布局存储的串，编写一个对比两个串是否相等的函数。
【答案】算法如下: //本算法判断两个依次存储的串x 和y 是否相等，相等返回1，否那么返回 //对应字符相等，指针后移 4． 假设K1，...，Kn 是n 个关键词，试解答： (1)试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为K1，K2，…，Kn 时，用算法建立一棵以llink —rlink 链接表示的二叉查找树 (2)设计一个算法，打印出该二叉查找树的嵌套括号表示布局例如，K1=B ，K2=A ，K3=D ，K4=C ，K5=E ，那么用二叉查找树的插入算法建立如下图的二叉查找树 图 该二叉查找树的嵌套括号表示布局为:B(A ，D(C ，E)) 【答案】(1)算法如下: 在二叉排序树bst 上査找值为K 的结点，返回其双亲结点指针 f 专注考研专业课13年，供给海量考研优质文档！ 第 4 页，共 36 页 以存储在数组R 中的n 个关键字，建立一棵初始为空的二叉排序树 不再插入一致值结点 . 申请结点空间 根结点 左子女 右子女 终止算法 (2)算法如下: 以嵌套括号表示布局打印二叉排序树 打印根结点值 左子女和右子女中至少有一个不空 输出左栝号 输出左子树的嵌套括号表示 若右子树不空，输出逗号 输出右子树的嵌套括号表示 输出右括号 5． 用邻接多重表存储布局，编写FERST-ADJ(G ，V)函数，函数返回值为第一个邻接点，若V 没有邻接点，返回零。
【答案】算法如下: 在邻接多重表g 中，求v 的第一邻接点,若存在，返回第一邻接点，否那么返回 确定顶点v 在邻接多重表向量中的下标,不考虑不存在v 的情 况 取第一个边结点 返回第一邻接点，和 中必有一个等于 i — 7 —。
