2016年河北工程大学信息与电气工程学院数据结构考研复试题库
● 摘要
一、选择题
1． 某以太网拓扑及交换机当前转发表如下图所示，主机发送1个数据帧，主机
A. B. C. D.
收到该帧后，向主机
交换机对这两个帧的转发端口分别是（ ）
向主机
发送一个确认帧，
答:B
【解析】
第一次交换机没有录这个数据报源MAC
地址的信息
的信息，只能选择从其他端口全部发送，同时记
确认帧发送时已经有
的信息
了所以只用从1端口转发。
2． 对下图进行拓扑排序，可以得到不同的拓扑序列的个数是（ ）。
A.4
B.3 C.2 D.1 答:B
【解析】拓扑排序的步骤为：
（1）在有向图中选一个没有前驱的顶点并且输出它；
（2）从图中删除该顶点和以它为尾的弧。重复上述两步，直至全部顶点均已输出。由于没有前驱的顶点可能不唯一，所以拓扑排序的结果也不唯一。题中所给图有三个不同的拓扑棑序序列，分别为abced ，abecd ，aebcd 。
3． 将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度为（ ）。
A.4 B.5 C.6 D.7 答:C
【解析】若二叉树中最多只有最下面两层的结点的度数可以小于2，并且最下面一层的叶结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树。具有n 个全二叉树的高度为
或
叉树的高度为
或
4． 从堆中删除一个元素的时间复杂度为（ ）。
答:B
【解析】堆中删除一个元素，需要重新调整堆，其时间复杂度为
5． 线性表的顺序存储结构是一种（ ）。
A. 随机存取的存储结构 B. 顺序存取的存储结构 C. 索引存取的存储结构 D.Hash 存取的存储结构 答:A
【解析】线性表包括顺序存储结构和链式存储结构，顺序存储结构能够随机存取表中的元素，但插入和删除操作较麻烦，链式存储结构不能随机访问表中的元素，但是能够表示元素之间的先后次序，而且插入和删除操作较容易。
6． 设图的邻接矩阵A 如下所示，各顶点的度依次是（ ）
结点的完
由完全二叉树类推到完全三叉树可知，n 个结点的完全三
A.1, 2, 1, 2 B.2, 2, 1, 1 C.3, 4, 2, 3 D.4, 4, 2, 2