2018年中国石油大学(北京)地球物理与信息工程学院955数据结构(II)[专业硕士]考研核心题库
● 摘要
一、算法设计题
1． 已知关键字序列(
试写出一算法将(
利用(1)的算法写一个建大根堆的算法。 【答案】(1)算法如下:
''
假设
是大堆，本算法把
(2)
2． 对给定关键字序号j(1 中找到关键字从小到大排在第j 位上的记 调成大堆 ) 是大根堆。 ) 调整为大根堆； 录，写一个算法利用快速排序的划分思想实现上述查找(要求用最少的时间和最少的空间) 。 例如:给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。 【答案】算法如下； 在后半部分继续进行划分 在前半部分继续进行划分 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 的剩余部 分 //稀疏矩阵相应元素相加时，有和为零的元素，因而元素总数＜m ＋ n //三元组前移，使第一个三元组的下标 为 1 //修改结果三元组表中非零元素个数 //结束addmatrix 4． 已知非空双向链表由d 指出，结点结构为(llink，data ，rlink) ，请设计算法将链表中数据域值最大(假定唯一) 的那个结点移至链表的最前面。要求:不得额外申请新的双链表结点。 【答案】算法如下: //d是循环链表，本算法将链表中数据域值最大的结点移至链表的最前面 //设链表有头结点 //q指向待处理结点 //P记数据域值最大的结点 //将P 摘下 //插人P 结点 5． 试编写在带头结点的单链表中删除(一个) 最小值结点的(高效) 算法。delete(Linklist&L) 【答案】算法如下: //L是带头结点的单链表，本算法删除其最小值结点 //P为工作指针。指向恃处理的结点。假定链表非空 //pre指向最小值结点的前驱 //q指向最小值结点，初始假定第一元素结点是最小值结点 //查最小值结点 //指针后移 //从链表上刪除最小值结点 //释放最小值结点空间 //结束算法Delete 二、应用题