2017年湖南师范大学数学与计算机科学学院865数据结构考研强化模拟题
● 摘要
一、填空题
1．
给定一组数据
的值为_____。 【答案】5；96
【解析】每次找两个最小的权值构建哈夫曼树：
以它构造一棵哈夫曼树，则树高为_____，
带权路径长度
2． 有向图G=（V ，E ）, 其中V （G ）=[0, 1，2，3，4, 5}, 用
【答案】50; 4
3． 假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中，则非零元素中的存储位置k=_____。（注：矩阵元素下标从1开始）
【答案】93
【解析】对于上三角矩阵
，
4． 空格串是指_____，其长度等于_____。
【答案】由空格字符（
将
代入得93。
在B
值32）所组成的字符串；空格个数
5． 设正文串长度为n ，模式串长度为m ，则串匹配的KMP 算法的时间复杂度为_____。
【答案】
6． 数据结构是研讨数据的_____和_____以及它们之间的相互关系，并对与这种结构定义相应的_____，设计出相应的_____。
；算法 【答案】逻辑结构；物理结构；操作（运算）
7． 假定查找有序表
【答案】37/12
中每个元素的概率相等，则进行折半查找时的平均查找长度为_____
【解析】折半查找时每个的次数如表所示：
表
平均查找次数为
8． 已知链队列的头尾指针分别是f 和r , 则将值x 入队的操作序列是_____。
【答案】
【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。 9． 深度为H 的完全二叉树至少有_____个结点; 至多有_____个结点; H 和结点总数N 之间的关系是_____。
【答案】
10．栈是_____的线性表，其运算遵循_____的原则。
；后进先出 【答案】操作受限（或限定仅在表尾进行插入和删除操作）
二、选择题
11．有关二叉树下列说法正确的是（ ）。
A_二叉树的度为2
B. —棵二叉树的度可以小于2 C. 二叉树中至少有一个结点的度为2 D. 二叉树中任何一个结点的度都为2 【答案】B
【解析】树的度=MAX（结点1的度，结点2的度，结点3的度，... ，结点n 的度）。二叉树之所以称为二叉树，是因为二叉树中节点的度最大是2，也可以小于2。
12．分区分配内存管理方式的主要保护措施是（ ）。
A. 界地址保护 B. 程序代码保护 C. 数据保护 D. 栈保护 【答案】A
【解析】对于连续分配算法，无论固定分区或动态分区方法，程序都必须全部调入内存，不同的进程放于不同的内存块中，相互之间不可越界，因此需要进行界地址保护。通常的界地址保
护方法采用软硬件结合的方法。考生要注意本题与虚拟存储方法的区别。
13．某以太网拓扑及交换机当前转发表如下图所示，主机向主机发送1个数据帧，主机
A. B. C. D.
收到该帧后，向主机
发送一个确认帧，
交换机对这两个帧的转发端口分别是（ ）
【答案】B
【解析】
第一次交换机没有录这个数据报源MAC
地址的信息
了所以只用从1端口转发。
14．以太网的MAC 协议提供的是（ ）。
A. 无连接不可靠服务 B. 无连接可靠服务 C. 有连接不可靠服务 D. 有连接可靠服务 【答案】A 。
【解析】考查以太网MAC 协议，考虑到局域网信道质量好，以太网采取了两项重要的措施以使通信更简洁：①采用无连接的工作方式；②不对发送的数据帧进行编号，也不要求对方发回确认。因此，以太网提供的服务是不可靠的服务，即尽最大努力交付，差错的纠正由高层完成。
15．在一个有N 个元素的有序单链表中查找具有给定关键字的结点，平均情况下的时间复杂性为（ ）。
【答案】B
【解析】二分查找的时间复杂度为
在一个用N 个元素的有序单链表中查找具有给定
的信息，只能选择从其他端口全部发送，同时记
确认帧发送时已经有
的信息