武汉大学2010-2011学年第二学期数据结构考试试题解析

"这是一份来自武汉大学计算机学院2010-2011学年第二学期的“数据结构”考试试题A卷，包含了多项选择题，涉及数据结构的基本概念、算法的时间复杂度分析、有序顺序表的删除操作、链表操作、栈的元素进栈、中缀表达式转后缀表达式、环形队列的计算以及完全二叉树的节点数量等知识点。试卷要求所有答案写在答题纸上，并注明姓名和学号。" 在这份试题中，我们可以提炼出以下几个关键知识点： 1. **数据结构**：数据结构是指相互之间存在一种或多种特定关系的数据元素的集合，选项D正确。它不仅包含数据的存储结构，还涉及数据的操作和组织方式。 2. **算法时间复杂度**：对于题目中的算法`void fun(int n)`，其时间复杂度为线性，即O(n)，选项A正确。这意味着算法执行的次数与输入规模n成正比。 3. **有序顺序表的删除操作**：在长度为n的有序顺序表中，如果使用二分查找法查找并删除元素x，查找的时间复杂度是O(log2n)，但实际删除操作还需考虑移动元素，所以总的时间复杂度是O(n + log2n)，但在选择题中只考虑查找部分，因此为O(log2n)，选项B正确。 4. **循环单链表删除操作**：删除带头结点的循环单链表中元素值为x的结点，需要遍历链表，所以时间复杂度是O(n)，选项A正确。 5. **栈的元素进栈**：栈是一种后进先出（LIFO）的数据结构，元素x进栈时，应先将top指针减1，然后将x存入栈顶，选项C正确。 6. **中缀表达式转后缀表达式**：中缀表达式“2*(3+4)-1”转换为后缀表达式为“2#3#4#+*1#-”，选项B正确。后缀表达式可以方便地进行求值。 7. **环形队列元素个数计算**：环形队列中元素个数的计算需要考虑到队列可能满也可能空的情况，计算公式为`(rear-front+N)％N`，当rear和front都在0到N-1之间时，队列为空，否则根据公式计算元素个数，选项D正确。 8. **环形队列的操作**：若当前rear=0，front=3，队列中有3个元素。删除一个元素后，rear=0，front=4；再加入两个元素，rear=2，front=4。因此，删除一个元素后再加入两个元素后，rear和front的值分别为2和4，选项B正确。 9. **完全二叉树的节点数量**：一棵深度为h的完全二叉树至少有2^(h-1)个结点，选项A正确。这是因为第h层至少有一个结点，而完全二叉树的每一层都是满的，除了最后一层。 这些知识点涵盖了数据结构的基础理论、算法复杂度分析、链表操作、栈的使用、队列操作以及二叉树的性质，这些都是计算机科学基础课程中核心的内容。