2019秋数据结构B期末考试试题与解析

"这是一份2019秋数据结构B课程的期末考试A卷，包含多项选择题，涉及数据结构和算法分析的基础知识。题目涵盖了一维数组压缩存储、算法的时间与空间复杂度、链表判断、二维数组存储、稀疏矩阵转置、二叉树性质、数据结构定义、二叉排序树查找长度、图的邻接矩阵以及链表节点删除等概念。" 详细知识点说明： 1. **一维数组压缩存储**：在描述中提到的9阶下三角矩阵A按照列优先顺序压缩存储在一维数组B中，其中B[0]存储的是a11。这个知识点涉及到如何计算下三角矩阵中特定元素在压缩存储数组中的位置。对于下三角矩阵，由于非对角线上方的元素不存储，我们可以根据列优先的顺序来确定元素的位置。 2. **算法分析**：算法分析的目的在于评估和改进算法的效率，重点关注时间复杂度和空间复杂度，这两者分别衡量了算法执行时间和内存使用。 3. **链表操作**：判断带头结点的单链表是否为空，通常通过检查头结点的next指针是否为空来实现，即head->next==NULL。 4. **二维数组存储**：二维数组在内存中按行存放，计算元素A[8][5]的起始地址时，需要考虑元素的大小（这里是3个字节）以及数组的行和列索引。 5. **稀疏矩阵转置**：稀疏矩阵的三元组表形式转置，不仅仅是行列互换，还需要调整三元组的顺序。 6. **二叉树性质**：在二叉树中，度为2的结点数，度为1的结点数，以及叶子结点数之间存在一定的关系，可以通过霍夫曼树的性质推算出叶子结点的数量。 7. **二叉树遍历**：先根序列和后根序列是二叉树遍历的不同方式，它们可以揭示结点之间的关系，例如在先根序列中x在y之前，而后根序列中x在y之后，意味着x是y的祖先。 8. **数据结构的定义**：给定的数据结构二元组A=(D，R)，其中D是数据元素集合，R是关系集合，根据关系可以判断数据结构的类型，这里是一个树形结构。 9. **二叉排序树查找长度**：在一棵深度为h的二叉排序树中查找所有元素的最长查找长度为h，因为最坏的情况是树退化成链表。 10. **图的邻接矩阵**：根据邻接矩阵的定义，可以判断图的类型，如无向图、有向图、强连通图或完全图。 11. **链表节点删除**：删除链表中的结点A需要修改指针，通常是将前一个结点的next指针指向A的下一个结点，然后释放A所占的内存空间。 这些知识点都是数据结构与算法领域的重要基础，对于理解数据的组织、存储和操作至关重要。在实际编程和解决问题时，这些概念经常被应用。