2018年北京大学地球与空间科学学院907计算机学科专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 已知L 为没有头结点的的单链表中第一个结点的指针，每个结点数据域存放一个字符，该字符可能是英文字母字符、数字字符或其他字符，编写算法构造三个以带头结点的单循环链表表示的线性表，使每个表中只含同一类字符(要求用最少的时间和最少的空间) 。
【答案】算法如下:
L 是不带头结点的单链表第一个结点的指针，链表中的数据域存放字符
//本算法将链表L 分解成含有英文字母字符、数字字符和其他幸符的带头结点的三个循环链表
//建立三个链表的头结点
//置三个循环链表为空表
//分解原链表
//L指向待处理结点的后继
//处理字母字符
//处理数字字符
//处理其他符号
//结束while(L!＝
null) //算法结束
2． 已知深度为h 的二叉树，以一维数组应的算法。
【答案】算法如下:
计算深度为h 、以一维数组BT 作为其存储结构的二叉树的叶结点数，n 为数组长度
记叶结点数
作为其存储结构，试编写一算法，求该二叉
树中叶结点的个数，为简单起见，设二叉树中元素结点为非负整数，要求写出算法基本思想及相
若结点无孩子，则
是叶子
存储在数组后一半的元素是叶结点
3． 已知两个链表A 和B 分别表示两个集合，其元素递增排列。编一函数，求A 与B 的交集，并存放于A 链表中。
【答案】算法如下:
//设工作指针pa 和pb ；
//结果表中当前合并结点的前驱的指针
//交集并入结果表中
//释放结点空
间
//释放结点空间
//释放结点空间
//置链表尾标记
//注:本算法中也可对B 表不作释放空间的处理
4． 以三元组表存储的稀疏矩阵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
5． 设在4地(A, B , C , D) 之间架设有6座桥，如图所示。
要求从某一地出发，经过每座桥恰巧一次，最后仍回到原地。 (1)试就以上图形说明:此问题有解的条件是什么？
相关内容
相关标签