2018年西安交通大学生命科学与技术学院814计算机基础综合之数据结构考研基础五套测试题
● 摘要
一、单项选择题
1． 现在有一颗无重复关键字的平衡二叉树(AVL 树) , 对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中, 正确的是（ ）。
A. 根节点的度一定为2
B. 树中最小元素一定是叶节点
C. 最后插入的元素一定是叶节点
D. 树中最大元素一定是无左子树
【答案】D
【解析】二叉树的中序遍历定义是“若二叉树为空, 则空操作; 否则:
①中序遍历左子树; ②访问根节点; ③中序遍历右子树”。
A 项错误, 当树中仅有一个或者两个结点时, 根节点的度就可能不为2; B 项错误, 树中最小元素是中序遍历时最后访问的节点, 当没有右子树时, 最后访问的节点是根节点; C 项错误, 当最后插入的元素破坏树的平衡后, 树会进行调整, 使其成为中间节点; D 项正确, 由中序遍历的特点可知, 左子树的值大于根节点, 所以最大元素一定没有左子树。
2． 下列网络设备中，能够抑制广播风暴的是（ ）.
(1)中继器
(2)集线器
(3)网桥
(4)路由器
A. 仅(1)和(2)
B. 仅(3)
C. 仅(3)和(4)
D. 仅(4)
【答案】D
【解析】中继器和集线器工作在物理层，不能抑制网络风暴. 为了解决冲突域的问题，提高共享介质的利用率，通常利用网桥和交换机来分隔互联网的各个网段中的通信量，以建立多个分离的冲突域. 但是，当网桥和交换机接收到一个未知转发信息的数据帧时，为了保证该帧能被目的结点正确接收，将该帧从所有的端口广播出去. 于是可以看出，网桥和交换机的冲突域等于端口的个数，广播域为1. 因此网桥不能抑制网络风暴.
3． 图G 是n 个顶点的无向完全图，则下列说法不正确的是（ ）
A.G 的邻接多重表需要n(n－1) 个边结点和n 个顶点结点
B.G 的连通分量个数最少
C.G 为连通图
D.G 所有顶点的度的总和为n(n—1)
【答案】A
A 项中G 的邻接多重表中需要【解析】个边结点和n 个顶点结点。此时连通分量最少
为1。无向完全图中任意两个顶点之间都存在路径，则G 必为连通图。每个顶点的度为n －1，则n 个结点的度的总和为n(n－1) 。
4． 设无向图的顶点个数为m 则该图最多有（ ）条边。
A.n-1 B. C.
D.0E.n2
【答案】B
【解析】在数据结构中仅讨论简单图，在计算无向图的最多边时，不考虑顶点与顶点的边。因此边数最多时，构成的是无向完全图。此时的边数为。
5． 执行（ ）操作时，需要使用队列做辅助存储空间。
A. 查找哈希(Hash)表
B. 广度优先搜索网
C. 前序(根) 遍历二叉树
D. 深度优先搜索网
【答案】B
【解析】查找哈希表不需要辅助存储空间，前序遍历二叉树和深度优先搜索网需要使用栈做辅助存储空间，广度优先搜索树需要队列做辅助存储空间。
6． 在下列存储形式中，哪一个不是树的存储形式？（ ）
A. 双亲表示法
B. 孩子链表表示法
C. 孩子兄弟表示法
D. 顺序存储表示法
【答案】D
【解析】顺序存储就是利用一段连续的存储单元依次存储线性表中的元素。树中某个结点的孩子可以有多个，这就意味着，无论用哪种顺序将树中所有的结点存储到数组中，结点的存储位置都无法直接反映逻辑关系。因此简单的顺序存储表示不能满足树的基本要求。常用的三种树的
表示法为:双亲表示法、孩子链表示法、孩子兄弟表示法。
7． 在系统内存中设置磁盘缓冲区的主要目的是（ ）。
A. 减少磁盘次数
B. 减少平均寻道时间
C. 提高磁盘数据可靠性
D. 实现设备无关性
【答案】A
【解析】访问磁盘的开销远远大于访问内存的开销。磁盘缓冲区便是利用主存中的存储空间, 来暂存从磁盘中读出(或写入) 的信息, 频繁使用的一部分磁盘数据和信息, 暂时存放在磁盘缓存中, 可减少访问磁盘的次数。
8． 稀疏矩阵一般的压缩存储方法有两种，即（ ）。
A. 二维数组和三维数组
B. 三元组和散列
C. 三元组和十字链表
D. 散列和十字链表
【答案】C
【解析】稀疏矩阵一般的压缩方法为三元组表和十字链表。三元组表就是将非零元素及其对应的行和列构成一个三元组(行标，列标，值) 。十字链表相比三元组表而言，主要是对每个结点增加了两个链域。如果数组经常运算时，会产生大量数据元素的移动，此时，采用链表存储结构更为恰当。
9． 图中有关路径的定义正确的是（ ）。
A. 由顶点和相邻顶点构成的边所形成的序列
B. 由不同顶点所形成的序列
C. 由不同边所形成的序列
D. 上述定义都不是
【答案】A
【解析】顶点到顶点之间的一条路径是指顶点序列。路径上边的数目称为路径的长度。
10．引入二叉线索树的目的是（ ）。
A. 加快查找结点的前驱或后继的速度
B. 为了能在二叉树中方便地进行插入与删除
C. 为了能方便地找到双亲