哈工大2004数据结构与算法期末试题解析

"这是一份2004年哈工大的数据结构与算法期末试题，涵盖了数据结构和算法的基础知识，包括链表、二元树、数列、图论、排序算法、散列表等多个主题。" 这篇试题主要考察了以下几个方面的知识点： 1. **时间复杂度**：题目中提到的程序时间复杂性为 (3n + nlog2n + n^2 + 8)，要求表达其数量级。数量级通常只保留最高阶项，因此这个表达式的时间复杂度为 O(n^2)。 2. **图的性质**：所有顶点的度数之和与边数的关系。在无向图中，每条边连接两个顶点，因此所有顶点的度数之和等于边数的两倍。 3. **外部排序**：在外部排序中，为了生成初始归并段，可能使用的方法包括多路归并、快速排序等。 4. **散列法查找**：冲突解决方法，如开放寻址法、链地址法、再哈希法等。 5. **树的性质**：在一株具有n个结点的树中，所有结点的度数之和等于2(n-1)，这是根据握手定理得出的。 6. **Kruskal算法**：它的平均和最坏时间复杂性为O(E log E)，其中E是边的数量，适用于求解无向图的最小生成树。 7. **二元查找树**：在最坏情况下，即树退化成链表，查找一个元素的时间复杂性为O(n)。 8. **归并排序**：对于n个元素的归并排序，归并的趟数是log2n，因为归并排序是基于分治策略的。 9. **链表查找**：在成功查找链表中值为x的结点时，平均比较次数为n/2。 10. **广义表操作**：广义表((a), a)的表头是(a)，表尾是(a)。 11. **二元树的高度与结点数**：高度为h的二元树，只有度数为0和2的结点，这样的树最少包含2^(h-1)个结点，即完全二叉树。 选择题部分涉及了链表判空、关键路径分析、向量地址计算、栈的输出序列、有向图回路检测以及哈希表的设计。例如： - 单链表head为空的判定条件是head->next=NULL。 - 关键路径分析中的错误选项：关键路径上的关键活动提前完成并不一定会使整个工程提前完成。 - 向量地址计算：第五个元素地址是100加上4个元素的存储空间，即100 + 2 * 4 = 108。 - 栈的不可能输出序列：abcde，因为栈遵循后进先出的原则，所以a必须是最后一个出栈的元素。 - 判定有向图是否存在回路可以使用深度优先遍历算法。 这些题目涵盖了数据结构和算法的核心概念，对理解这些基础知识非常重要。