2018年浙江大学光电信息工程学院408计算机学科专业基础综合之数

专注考研专业课13年，提供海量考研优质文档！

第 1 页，共 36 页

目录

2018年浙江大学光电信息工程学院408计算机学科专业基础综合之数据结构考研基础五套测试

题（一） .................................................................................................................................. 2 2018年浙江大学光电信息工程学院408计算机学科专业基础综合之数据结构考研基础五套测试

题（二） .................................................................................................................................. 9 2018年浙江大学光电信息工程学院408计算机学科专业基础综合之数据结构考研基础五套测试

题（三） ................................................................................................................................ 16 2018年浙江大学光电信息工程学院408计算机学科专业基础综合之数据结构考研基础五套测试

题（四） ................................................................................................................................ 23 2018年浙江大学光电信息工程学院408计算机学科专业基础综合之数据结构考研基础五套测试

题（五） (30)

专注考研专业课13年，提供海量考研优质文档！ 第 2 页，共 36 页 2018年浙江大学光电信息工程学院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

…… 此处隐藏：405字，全部文档内容请下载后查看。喜欢就下载吧 ……