2018年北京师范大学系统科学学院408计算机学科专业基础综合之数据结构考研基础五套测试题
● 摘要
一、算法设计题
1． 编写程序，统计在输入字符串中各个不同字符出现的频度并将结果存入文件(字符串中的合法字符为A 〜Z 这26个字母和0〜9这10个数字) 。
【答案】算法如下:
（ ）
//统计输入字符串中数字字符和字母字符的个数
//初始化
//’#’表示输入字符串结束
'//数字字符
//字母字符
//输出数字字符的个数
("数字％d 的个数＝
//求出字母字符的个数
("字母字符％c 的个数＝
//算法结束。
2． 写出按后序序列遍历中序线索树的算法。
【答案】算法如下:
求结点t 最左子孙的左线索
沿左分支向下
求结点t 最右子孙的右线索
沿右分支向下
若t 是
第 2 页，共 34 页
) ；
) ；
的右孩子，返回1, 否则返回
后序遍历中序线索二叉树
bt
沿左分支向下
左孩子为线索，右孩子为链，相当从左返回
P 为叶子, 相当从右返回
访问结点
修改P 指向双亲
是左子女，用最右子孙的右线索找双亲
.
转向当前结点右分支
结束
3． 试编写在带头结点的单链表中删除(一个) 最小值结点的(高效) 算法。delete(Linklist&L)
【答案】算法如下:
//L是带头结点的单链表，本算法删除其最小值结点
//P为工作指针。指向恃处理的结点。假定链表非空
//pre指向最小值结点的前驱
//q指向最小值结点，初始假定第一元素结点是最小值结点
//查最小值结点
//指针后移
//从链表上刪除最小值结点
//释放最小值结点空间
//结束算法Delete
4． 结点类型和存储结构如下:
试设计一个排序算法，要求不移动结点的存储位置，只在结点的count 字段记录结点在排序中的序号，并将排序结果按升序输出。
【答案】算法如下:
第 3 页，共 34 页
对存储在数组R 中的记录进行排序
初始化
设R[0]作监视哨，Max 是该类型最大元
素
初始假定第一个元素有序
前驱
第一个元素
査找第i 个元素的序号
将笫i 个元素链入静态链表
5． 在一棵以二叉链表表示的二叉树上，试写出按层次顺序遍历二叉树的方法，统计树中具有度为1的结点数目的算法。
【答案】算法如下:
层次遍历二叉树，并统计度为1的结点的个数
统计度为1的结点的个数
是以二叉树结点指针为元素的队列
出队，访问结点
度为1的
结点
非空左子女入队
非空右子女入队
返回度为1的结点的个数
二、应用题
6． 某局域网采用CSMA/CD协议实现介质访问控制，数据传输率为10Mbps ，主机甲和主机乙之间的距离为2km ，信号传播速度是200000km/s.请回答下列问题，要求说明理由或写出计算过程.
(1)若主机甲和主机乙发送数据时发生冲突，则从开始发送数据时刻起，到两台主机均检测到冲突时刻止，最短需经过多长时间? 最长需经过多长时间？(假设主机甲和主机乙发送数据过程中，其他主机不发送数据）
(2)若网络不存在任何冲突与差错，主机甲总是以标准的最长以太网数据帧(1518字节）向主
第 4 页，共 34 页
相关内容
相关标签