2022年北京邮电大学计算机学院408计算机学科专业基础综合之数据

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

第 1 页，共 38 页

目录

2018年北京邮电大学计算机学院408计算机学科专业基础综合之数据结构考研强化五套模拟题

（一） ..................................................................................................................................... 2 2018年北京邮电大学计算机学院408计算机学科专业基础综合之数据结构考研强化五套模拟题

（二） ..................................................................................................................................... 8 2018年北京邮电大学计算机学院408计算机学科专业基础综合之数据结构考研强化五套模拟题

（三） ................................................................................................................................... 14 2018年北京邮电大学计算机学院408计算机学科专业基础综合之数据结构考研强化五套模拟题

（四） ................................................................................................................................... 22 2018年北京邮电大学计算机学院408计算机学科专业基础综合之数据结构考研强化五套模拟题

（五） (32)

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

第 2 页，共 38 页 2018年北京邮电大学计算机学院408计算机学科专业基础综合之数据结构考研强化

五套模拟题（一）

说明：根据本校该考试科目历年考研命题规律，结合出题侧重点和难度，精心整理编写。考研强化检测使用。共五套强化模拟题，均含有详细答案解析，考研强化复习必备精品资料。

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

一、算法设计题

1． 己知L 为链表的头结点地址，表中共有m(m ＞3)个结点，从表中第i 个结点(l ＜i ＜m)起到第m 个结点构成一个循环部分链表，设计将这部分循环链表中所有结点顺序完全倒置的算法。

【答案】算法如下:

//L 是有m 个结点的链表的头结点的指针。表中从第个结点到第m 个结点构成循环部分链表//本算法将这部分循环链表倒置

//p 是工作指针，初始指向第二结点(已假定i ＞

l)

//pre 是前驱结点指针，最终指向第i ﹣i 个结点

//计数器

//查找第i 个结点

//査找结束，P 指向第i 个结点

//暂存第i 个结点的指针

//p 指向第i ＋l 个结点，准备逆置

//上面while 循环结束时，j ＝i ﹣1现从第i ＋1结点开始逆置

//暂存P 的后继结点

+

//逆置P 结点

//P 恢复为当前待逆置结点

//计数器增

1

//将原第i 个结点的后继指针指向原第m 个结点

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

第 3 页，共 38 页 2． 已知指针P 指向带表头的中根次序线索二叉树中的某结点，试写一算法FFA(P ，q),该算法寻找结点P 的父亲结点q 。设线索二叉树的结点结构、表头结点结构和空树结构分别为(LTAG ，LLINK ，INFO ,RL1NK ，RTAG)，且规定线索树的最左下结点的LLINK 域和最右下结点的RLINKt 域指向表头。

【答案】算法如下:

在中序线索树t 上，求结点p 的双亲结点q

暂存

找P 的中序最右下的结点

顺右线索找到q 的后继(P 的袓先结点

)

若后继是头结点，则转到根结点

根结点无双亲

准备到左子树中找

P

找最右结点的过程中回找到

P

结束FFA

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

【答案】算法如下:

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

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

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

)

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

//A 中当前项为结

果项

//B 中当前项为结果

当前项

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

第 4 页，共 38 页

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

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

//结束行号比较处理

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

1)

//结束WHILE 循环。

//处理B 的剩余部

分

//处理A 的剩余部

分

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

n

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

为

1

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

//结束addmatrix

4． 设有顺序放置的n 个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红、白、蓝之一。要求重新安排这些砾石，使得所有红色砾石在前，所有白色砾石居中，所有蓝色砾石居后。重新安排时，对每粒砾石的颜色只能察看一次，并且只允许交换操作来调整砾石的位置。

【答案】算法如下:

r 为含有n 个元素的线性表，元素是具有红、白和蓝色的砾石，用顺序存储结构存储

本算法对其排序，使所有红色栎石在前，白色居中，蓝色在最后

当前元素是红色

当前元素是白色

当前元素是蓝色

本文来源：https://www.bwwdw.com/article/xhkq.html