c++ - 练习期末考试题，“数据结构”课

Question

我正在为一门数据结构课程做练习期末考试，我有几个问题希望得到帮助：

1.  

   void BST::traverse(Vertex *V)  // post order traversal recursively
   {   
     if (V != NULL) 
       {
         traverse(V->Left);        
         traverse(V->Right);       
         cout << V->elem << endl;     
       }
   }
   

   我需要将其更改为深度优先搜索。我相信我必须在每次递归时重新访问根，但我很困惑，因为那时我永远不会离开根。也许是一个临时的根？没有把握！

2. 对于我们的链表实现，我必须描述使用我们的复制构造函数的两种情况。我知道它是为函数调用而调用的。但是还有什么原因呢？

3. 为什么我们使用大 O 表示法 [例如 O(n^2) 而不是说 2n^2 + 3n + 4)。我知道这样做时我们会忽略常量，但我还能给出更多答案吗？

4. 时间与空间的复杂性。对我来说最明显的是合并排序与快速排序，但是如果测试要求更多，你能想到另一个吗？我们在课堂上经历了这么多，我不敢相信我不能说出更多的名字。

Answer 1

1. 如果您只是将搜索代码添加到其中，它已经是深度优先搜索。

2. 您已经遇到过将 a 作为参数按值传递BST给函数的情况。您制作对象的另一个副本是什么时候？（提示：一个也和函数有关）

3. 因为当n很大时，2 ⁿ将比等式中的任何其他内容大得多，因此您只需将常数和其他所有内容都排除在外。Big-O 表示法绝对不是精确的，它只是让您知道随着输入变得非常大，问题的解决方案如何扩展。当n变得足够大时，复杂性是如此之大，以至于其他东西都相形见绌，基本上是 2 ⁿ。

4. 您必须对此更具体。您是否正在寻找两种以速度换空间的算法？

Answer 2

3 个大 O 符号只引用主导项。当 n 变大时，这是结果中最重要的部分。

4 考虑冒泡排序 - 我以前不喜欢它，因为它需要很长时间，但只需要空间来放置一个项目。