北京市培养单位资源与环境学院866计算机原理[专业硕士]之数据结

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

第 1 页，共 40 页

目录

2018年北京市培养单位资源与环境学院866计算机原理[专业硕士]之数据结构考研冲刺狂背五

套题（一） .............................................................................................................................. 2 2018年北京市培养单位资源与环境学院866计算机原理[专业硕士]之数据结构考研冲刺狂背五

套题（二） .............................................................................................................................. 9 2018年北京市培养单位资源与环境学院866计算机原理[专业硕士]之数据结构考研冲刺狂背五

套题（三） ............................................................................................................................ 17 2018年北京市培养单位资源与环境学院866计算机原理[专业硕士]之数据结构考研冲刺狂背五

套题（四） ............................................................................................................................ 24 2018年北京市培养单位资源与环境学院866计算机原理[专业硕士]之数据结构考研冲刺狂背五

套题（五） (33)

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

第 2 页，共 40 页 2018年北京市培养单位资源与环境学院866计算机原理[专业硕士]之数据结构考研冲

刺狂背五套题（一）

说明：本套狂背五套题按照考研侧重点和出题难度，严格筛选提取了历年考试高频核心试题及重点题型，更突出针对性和实战性，适用于考研冲刺最后狂背。

——————————————————————————————————————————

一、算法设计题

1． 已知递增有序的单链表A ，B 分别存储了一个集合，请设计算法以求出两个集合A 和B 的差集A ﹣B(即仅由在A 中出现而不在B 中出现的元素所构成的集合)，并以同样的形式存储，同时返回该集合的元素个数。

【答案】算法如下:

//A 和B 均是带头结点递增有序的单链表，本算法求两集合的差集，*n 是结果集合中元素个数，初始为

//p 和q 分别是链表A 和B 的工作指针

//pre 为A 中p 所指结点的前驱结点的指针

//A

链表中当前结点指针后移

//B 链表中当前结点指针后移

//处理A ,B 中元素值相同的结点，

应刪除

//删除结点

2． (1)试分别找出满足下列条件的所有二叉树:(a)前序序列和中序序列相同:(b)前序序列和后序序列相同；(c)中序序列和后序序列相同。

(2)已知非空二叉树的结点结构为(lchild ，data ,rchild)，设计算法:从右向左依次将所有叶子的数据值放到向量(假定向量的空间大于叶子的总个数)中。

【答案】(1)满足条件的二叉树如下:

(a)若前序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。 (b)若前序序列与后序序列相同，则或为空树，或为只有根结点的二叉树。

(c)若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树。

(2)算法如下:

全局变量

从右向左依次将二叉树bt 的所有叶子的数据值放到a 向量中 .

中序遍历右子树

叶结点

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

第 3 页，共 40 页

中序遍历左子树

3． 以三元组表存储的稀疏矩阵A ，B 非零元个数分别为m 和n 。试用类PASCAL 语言编写时间复杂度为0(m ＋n)的算法将矩阵B 加到矩阵A 上去。A 的空间足够大，不另加辅助空间。要求描述所用结构。

【答案】算法如下:

＝大于非零元素个数的某个常量

//本算法实现以三元组表存储的各有m 和n 个非零元素两个稀疏矩阵相加，结果放到A 中

//L ，p 为A ，B 三元组表指针，k 为结果三元组表榫针(下标

)

//行号不等时，行号大者的三元组为结果三元组表中一项

//A 中当前项为结

果项

//B 中当前项为结果

当前项

//行号相等时，比较列号

//结束行号相等时的处理

//结束行号比较处理

//结果三元组表的指针前移(减

1)

//结束WHILE 循环。

//处理B 的剩余部

分

//处理A 的剩余部

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

第 4 页，共 40 页

分

//稀疏矩阵相应元素相加时，有和为零的元素，因而元素总数＜m ＋

n

//三元组前移，使第一个三元组的下标

为

1

//修改结果三元组表中非零元素个数

//结束addmatrix

4． 写出按后序序列遍历中序线索树的算法。

【答案】算法如下:

求结点t 最左子孙的左线索

沿左分支向下

求结点t 最右子孙的右线索

沿右分支向下

若t 是

的右孩子，返回1,否则返回

后序遍历中序线索二叉树

bt

沿左分支向下

左孩子为线索，右孩子为链，相当从左返回

P 为叶子,相当从右返回

访问结点

修改P 指向双亲

是左子女，用最右子孙的右线索找双亲

.

转向当前结点右分支

结束

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