2021数据结构全真试题解析

"这是一份2021年的数据结构全真试题，包含了选择题和非选择题，总分100分，考试时长150分钟。试题分为两大部分，选择题30分，非选择题70分，共10页。试题涉及到的数据结构相关知识包括算法定义、链表存储、时间复杂度分析、栈和队列的操作、字符串特性和操作、模式匹配算法效率、广义表的概念、稀疏矩阵表示、树的度数关系以及无向图的邻接矩阵等。" 以下是根据给定试题内容详细解释的知识点： 1. 算法：算法是解决问题的有限运算序列，它不仅包含计算机程序，更注重于解决问题的方法和步骤。题目中提到的D项"解决问题的有限运算序列"是对算法的正确理解。 2. 线性表的链式存储：线性表采用链式存储时，结点的存储地址可以是连续的，也可以是不连续的，这取决于内存分配的情况。因此，B项"连续与否均可"是正确的。 3. 链表链接时间复杂度：将长度为n的单链表链接在长度为m的单链表之后，需要遍历m个结点进行连接操作，所以时间复杂度为O(m)，对应C项。 4. 共享栈：两个栈共享一个向量空间可以节省存储空间，因为不是每个栈都单独占用存储空间，降低了上溢发生的可能性。B项"节省存储空间，降低上溢发生的机率"是正确的。 5. 循环队列出队操作：执行出队操作后，头指针需要向后移动一位，考虑到循环队列，头指针更新为D项"front=(front+1)%m"。 6. 串的定义：串是一种特殊的线性表，可以为空串，且元素可以是任意字符。因此，A项"串是一种特殊的线性表"正确，而B、C、D项错误。 7. 模式匹配时间复杂度：在最坏情况下，即目标串的每一个字符都需要与模式串进行比较，时间复杂度为O(n)。 8. 非空广义表的表头：非空广义表的表头可以是原子或子表，因此D项"可以是子表或原子"正确。 9. 稀疏矩阵表示：这个题目涉及到稀疏矩阵的三元组表示，但具体答案需要根据行表来推算，这里没有提供具体的行表信息，无法给出答案。 10. 树的度数关系：在一颗度为3的树中，若度为3的节点有2个，度为2的节点有1个，可以通过握手原理来计算度为0的节点数，但这里同样缺少必要信息，无法得出准确答案。 11. 无向图邻接矩阵：无向图的邻接矩阵是对称的，每个边会在矩阵中出现两次，所以零元素的个数为n² - 2e，对应D项。 12. 删除与顶点相关的弧：在邻接表表示的有向图中，删除与某个顶点vi相关的所有弧需要遍历与vi关联的邻接表，时间复杂度为O(e)。 这些知识点涵盖了数据结构中的基础概念，如链表、栈、队列、串、模式匹配、广义表、稀疏矩阵、树的性质和图的表示等，对于理解和复习数据结构课程非常重要。