华东交通大学2010-2011学年数据结构期末考试试题

"华东交通大学2010—2011学年第一学期的数据结构期末考试试卷，包含选择题，涉及数据结构的基础概念、算法分析、线性表、链表操作、循环队列、栈与队列的特性、广义表以及二叉树等知识点。" 在这份试卷中，我们可以看到数据结构的一些核心概念和关键问题： 1. **算法**：问题1和2涉及到算法的基本概念。计算机算法是解决问题的步骤序列，而算法的计算量大小通常用复杂性来衡量，这是一个衡量算法执行时间或空间需求的度量。 2. **时间复杂度**：问题3考察了时间复杂度的计算。给定的程序段是两个嵌套循环，总执行次数为n²，所以时间复杂度为O(n²)。 3. **线性表**：问题4提到了线性表的定义，它是具有n个数据元素的有限序列，这里的数据元素可以是任何类型的信息。 4. **链表操作**：问题5涉及链表的插入操作。在单链表中，要在指针为p的结点后插入指针为s的结点，正确做法是B．s->next=p->next;p->next=s; 这样可以确保链接正确。 5. **循环队列**：问题6测试了循环队列元素个数的计算。在循环队列中，当前元素个数为(rear-front+1)%m。 6. **栈和队列**：问题7指出栈和队列都是限制存取点的线性结构。栈遵循“后进先出”（LIFO）原则，而队列遵循“先进先出”（FIFO）原则。 7. **堆栈操作**：问题8讨论了可能的堆栈输出序列，其中D选项d,c，a，b是不可能的，因为它违反了栈的LIFO性质。 8. **广义表操作**：问题9考察广义表的操作。Tail函数返回列表的剩余部分，Head返回列表的第一个元素。所以Head(Tail(Tail(A))))将返回d。 9. **二维数组存储**：问题10涉及二维数组的存储需求。数组有8行10列，每个元素占3个存储字，总共需要8*10*3=240个存储字。 10. **二叉树的性质**：问题11提出了二叉树节点度数的关系。在二叉树中，度为2的节点数+度为1的节点数+度为0的节点数（叶节点数）=节点总数。已知度为2的节点有10个，度为1的节点有5个，节点总数未知，但叶节点数可以通过这个公式推算。 通过这些题目，我们可以看到数据结构课程主要关注如何有效地组织和操作数据，包括基本数据结构如线性表、链表、栈、队列和二叉树，以及算法的时间复杂度分析。这些知识对于理解和设计高效的计算机程序至关重要。