09数据结构期中 答案1
数据结构是计算机科学中的核心课程,它涉及到如何高效地组织和管理数据,以便于执行各种操作,如查找、插入和删除。以下是从给定的文件内容中提取的一些关键知识点: 1. **栈**:栈是一种后进先出(LIFO)的数据结构。题目中提到的“顺序进栈”和“出栈序列”,是栈操作的基本概念。合法的出栈序列必须遵循LIFO原则,例如,元素6先进栈,最后出栈。 2. **顺序表**:在顺序表中插入元素时,如果表是顺序存储的,可能需要移动大量元素来保持顺序。在125个元素的顺序表中插入一个元素,平均需要移动62.5个元素,这是因为平均情况下需要将表中一半的元素向右移动一位。 3. **广义表**:广义表是一种可以包含其他表的表,是递归定义的数据结构。在广义表A中取出原子项e的操作涉及到对表的头部和尾部的提取,具体操作是C选项,通过head(tail(tail(A)))获取。 4. **循环队列**:循环队列是队列的一种实现方式,利用数组的循环特性。入队操作通常是在队尾进行,当队列非空时,rear指针向后移动一位。因此,正确的入队操作是B选项:rear=(rear+1) mod (m+1)。 5. **双向循环链表**:在双向循环链表中插入节点涉及改变前后节点的链接。根据题目中给出的链表节点结构,正确插入新节点q的操作是C选项,这会确保链表的正确连接。 6. **完全二叉树**:完全二叉树的性质指出,除了最后一层外,每一层都是完全填充的,且所有结点都尽可能地集中在左边。对于有1001个结点的完全二叉树,无法确定确切的叶子结点数,因为这不是2的幂,所以选项D是正确的。 7. **二叉树遍历**:根据前序遍历(ABCDEF)和中序遍历(CBAEDF),可以推断出二叉树的形态。后序遍历没有唯一解,但通常B选项(FEDCBA)是最常见的后序遍历结果。 8. **二叉链表**:在二叉链表表示的二叉树中,根结点的右指针通常是空的,因为它不指向最左或最右的孩子。 9. **二维数组存储**:二维数组按照列优先顺序存储时,可以通过公式计算元素位置,例如A[6,6]的地址为100+(6*10+6)*2=252。 10. **二叉线索树**:引入二叉线索树是为了在二叉树中快速找到结点的前驱或后继,因此答案是A。 **填空题知识点**: 1. 程序段执行次数与n有关,是n的阶乘加1。 2. 链栈插入节点的语句通常是`H->next = s; s->next = H;` 3. Huffman树中,结点总数是叶子结点数n0加1。 4. 链队列只有一个结点的条件是front和rear相等。 5. 在已知结点后插入节点的时间复杂度是O(1),在给定值结点后插入的时间复杂度是O(n),在最坏情况下需要遍历整个链表。 6. 满二叉树的叶子结点数是n/2,非终端结点数是n/2 - 1。 7. 稀疏矩阵的存储,非0元素少,一般采用三元组或压缩存储。 这些知识点涵盖了数据结构中的栈、队列、广义表、二叉树、链表、数组和稀疏矩阵等多个重要概念。理解并掌握这些基本概念对于学习和应用数据结构至关重要。