2023年数据结构第5套模拟试卷

Q1:在顺序表中插入或删除一个元素， 需要平均移动 表中一半元素， 具体移动的元素个数与 表长和该元素在表中的位置 无关

Q2:线性表中结点的集合是 无限 的， 结点间的关系是 一对一的。

Q3:向一个长度为 n 的向量的第 i 个元素(1≤i≤n+1)之前插入一个元素时， 需向后移动 n-i+1 个元素

Q4:向一个长度为 n 的向量中删除第 i 个元素(1≤i≤n)时， 需向前移动 n-i+1 个元素。

Q5:在顺序表中访问任意一结点的时间复杂度均为 O(n) ， 因此， 顺序表也称为 随机存取 的数据结构。

Q6:顺序表中逻辑上相邻的元素的物理位置 必定相邻。 单链表中逻辑上相邻的元素的物理位置 不一定 相邻

Q7:在单链表中， 除了首元结点外， 任一结点的存储位置由 其直接前驱结点的链域的值 指示

Q8:在 n 个结点的单链表中要删除已知结点*p， 需找到它的前驱结点的地址，其时间复杂度为 O（1）。

Q9:链表的每个结点中都恰好包含一个指针

Q10:链表的物理存储结构具有同链表一样的顺序。

Q11:链表的删除算法很简单， 因为当删除链中某个结点后， 计算机会自动地将后续的各个单元向前移动。

Q12:线性表的每个结点只能是一个简单类型， 而链表的每个结点可以是一个复杂类型。

Q13:顺序表结构适宜于进行顺序存取， 而链表适宜于进行随机存取

Q14:顺序存储方式的优点是存储密度大， 且插入、 删除运算效率高

Q15:线性表在物理存储空间中也一定是连续的。

Q16:线性表在顺序存储时， 逻辑上相邻的元素未必在存储的物理位置次序上相邻

Q17:线性表的逻辑顺序与存储顺序总是一致的。

Q18:进栈操作时，必须判断栈是否已满

Q19:链栈在入栈前不需要判断栈是否满，只需要为入栈元素动态分配一个结点空间，而顺序栈在入栈前必须判断栈是否满，我认为这道题并未说明进栈是顺序栈的进栈还是链栈的进栈，就判断了栈是否满，所以错了

Q20:快速排序的平均时间复杂度和最坏时间复杂度分别是O(nlgn)、O(n^2)

Q21:在含有 n 个结点的二叉排序树上查找某结点时其平均查找长度 ASL 的范围是从n至log2n

Q22:深度为k的二叉树最多有2k-1(减去一个大1)个结点 最少k个结点

Q23:空指针域是n+1 非空指针域是n-1 具有2n个结点

Q24:在n个结点的单链表中要删除已知结点*p,需找到它的_前趋结点_，其时间复杂度为_O(n)

Q25:在数据的存放无规律而言的线性表中进行检索的最佳方法不是顺序查找。

Q26:在各种查找方法中，平均查找长度与结点个数n无关的查找方法是(散列查找 )

Q27:哈希表的平均查找长度不是表长(节点个数)n的函数,而是哈希表装填因子alpha的函数,与节点个数无关

Q28:线性表按存储方式的不同可分为__顺序表________、_____链表______和散列表等三种

Q29:线性链表是线性表的链式存储结构

Q30:数据的逻辑结构与存储结构必定是一一对应的

Q31:空串就是空白串

Q32:冒泡排序算法在最好的情况下的元素交换次数为 0

Q33:某二叉树中度为 2 的结点有 18 个， 则该二叉树中有 _19___ 个叶子结点。

Q34:算法复杂度主要包括时间复杂度和 _ 空间___ 复杂度

Q35:程序执行的效率与数据的存储结构密切相关

Q36:请判断本项叙述是否正确？

Q37:所谓稀疏矩阵指的是零元素个数远远多于非零元素个数且分布没有规律的矩阵

Q38:稀疏矩阵是指非零元素的个数远小于零元素

Q39:对稀疏矩阵进行压缩的目的是为了节省存储空间

Q40:稀疏矩阵压缩存储后,必会失去随机存取功能.

Q41:在长度为 64 的有序线性表中进行顺序查找， 最坏情况下需要比较的次数为

Q42:对长度为 n 的线性表进行顺序查找， 在最坏情况下所需要的比较次数为______。

Q43:在待排序的元素序列基本有序的前提下， 效率最高的排序方法是

Q44:希尔排序属于

Q45:在下列几种排序方法中， 要求内存量最大的是______。

Q46:下列数据结构中， 能用二分法进行查找的是

Q47:下列关于栈的描述正确的是

Q48:数据结构研究的主要内容有:数据的逻辑结构、数据的存储结构和数据的运算三部分

Q49:下列关于栈的叙述正确的是

Q50:算法的空间复杂度是指