c++ - 练习期末考试题， "Data Structures"课

Question

我正在为数据结构类(class)做期末练习，我有几个问题希望得到帮助:

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

   我需要将其更改为深度优先搜索。我相信每次递归我都必须重新访问根，但我很困惑，因为那样我就永远不会离开根。也许是临时根？不确定!

2. 对于我们的链表实现，我必须描述 2 个使用我们的复制构造函数的场合。我知道它被称为函数调用。但还有什么原因呢？

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

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

Answer 1

1. 加上搜索代码就已经是深度优先搜索了。

2. 您已经遇到过 BST 作为参数按值传递 给函数的情况。你又一次复制对象是什么时候？ (提示:一个也和函数有关)

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

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