2022年数据结构模拟试卷补充2

Q1:在单链表中， 任何两个元素的存储位置之间都有固定的联系， 因为可以从头结点查找任何一个元素

Q2:数组是同类型值的集合

Q3:使用三元组表示稀疏矩阵的元素， 有时并不能节省存储时间

Q4:线性表可以看成是广义表的特例， 如果广义表中的每个元素都是原子， 则广义表便成为线性表

Q5:由树转换成二叉树， 其根结点的右子树总是空的

Q6:连通分量是无向图中的极小连通子图

Q7:有回路的图不能进行拓扑排序

Q8:散列法存储的基本思想是由关键码的值决定数据的存储地址

Q9:中序遍历二叉排序树的结点就可以得到排好序的结点序列

Q10:当待排序的元素很多时， 为了交换元素的位置， 移动元素要占用较多的时间， 这是影响时间复杂性的主要因素

Q11:对于 n 个记录的集合进行归并排序， 所需要的平均时间是 O(nlog 2 n)

Q12:对于 n 个记录的集合进行快速排序， 所需要的平均时间是 O(nlog 2 n)

Q13:若一个树叶是某子树的中序遍历序列中的最后一个结点， 则它必是该子树的前序遍历序列中的最后一个结点

Q14:若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点， 则它必是该子树的前序遍历序列中的最后一个结点

Q15:已知一棵二叉树的前序遍历和后序遍历序列,不能唯一确定这棵二叉树

Q16:线性表中的元素可以是各种各样的， 但同一线性表中的数据元素具有相同的特性，因此， 是属于同一数据对象

Q17:有关栈的描述， 正确的是

Q18:最小生成树不唯一，最小生成树代价唯一

Q19:最小代价生成树 。

Q20:对于一棵具有n个结点的树，则树中所有结点的度数之和为n-1

Q21:在一棵二叉排序树中， 按 前序 遍历得到的结点序列是一个有序序列。

Q22:后序遍历树和中序遍历与该树对应的二叉树， 其结果不同

Q23:已知二叉树的前序遍历和后序遍历序列并不能唯一地确定这棵树， 因为不知道树 的根结点是哪一个

Q24:若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点， 则它必是该子 树的前序遍历序列中的最后一个结点

Q25:若一个树叶是某子树的中序遍历序列中的最后一个结点， 则它必是该子树的前序 遍历序列中的最后一个结点

Q26:在哈夫曼编码中， 当两个字符出现的频率相同时， 其编码也相同， 对于这种情况应作特殊处理

Q27:设图 G 有 n 个顶点和 e 条边， 当 G 是非孤立顶点的连通图时有 2e=n, 故可推得深度优先搜索的时间复杂度为 。

Q28:图的深度优先或广度优先遍历的空间复杂性均为 。 (访问标志位数组空间)

Q29:在图 G 的邻接表表示中， 每个顶点邻接表中所含的结点数， 对于无向图来说等于该 顶点 度的 ， 对于有向图来说等于该顶点的 出度

Q30:有回路的图不能进行拓扑排序

Q31:连通分量是无向图中的极小连通子图

Q32:任何连通图的连通分量只有一个，即是其自身，非连通的无向图有多个连通分量

Q33:连通分量是无向图的极大连通子图，无向图连通图的连通分量是自身，非连通图有多个连通分量

Q34:二分查找法要求待查表的关键字值必须有序。

Q35:对有序表而言采用二分查找总比采用顺序查找法速度快

Q36:在二叉排序树中， 根结点的值都小于孩子结点的值。

Q37:散列存储法的基本思想是由关键字的值决定数据的存储地址。

Q38:哈希表是一种将关键字转换为存储地址的存储方法。

Q39:选择好的哈希函数就可以避免冲突的发生

Q40:在有序的顺序表和有序的链表上， 均可以采用二分查找来提高查找速度

Q41:采用分块查找， 既能实现线性表所希望的查找速度， 又能适应动态变化的需要。

Q42:哈希法的查找效率主要取决于哈希表构造时选取的哈希函数和处理冲突的方法。

Q43:在二叉排序树上删除一个结点时， 不必移动其它结点， 只要将该结点的父结点的相应的指针域置空即可。

Q44:理想情况下， 在散列表中查找一个元素的时间复杂度为： O（1）

Q45:对于长度为 n 的线性表， 若采用二分查找， 则时间复杂度为： O（log 2 n） 。

Q46:对于长度为 n 的线性表， 若进行顺序查找， 则时间复杂度为 O（1） 。

Q47:静态 查找表所含元素个数在查找阶段是固定不变的

Q48:顺序查找、 二分查找、 分块查找都属于 静态 查找

Q49:在分块查找方法中， 首先查找 索引 ， 然后再查找相应的块

Q50:顺序查找法， 表中元素不可以 任意 存放