0

私はデータ構造クラスの最終練習に取り組んでおり、助けを得たいと思っていたいくつかの質問があります。

  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 表記を使用するのですか [たとえば、2n^2 + 3n + 4 の代わりに O(n^2) を使用します)。そうするときに定数を無視することは知っていますが、私ができる答えは他にありますか?

  4. 時間と空間の複雑さ。私にとって最も明白なのは、マージソートとクイックソートですが、テストでさらに要求があった場合に備えて、別のソートを考えてもらえますか? 私たちはクラスで非常に多くのことを調べたので、これ以上名前を挙げられないなんて信じられません。

4

2 に答える 2

4
  1. 検索コードを追加するだけで、すでに深さ優先検索です。

  2. BSTaが引数として関数に値で渡される機会がすでにあります。オブジェクトのコピーを作成する別の時間はいつですか? (ヒント: 関数にも関連するものがあります)

  3. whennが大きいため、2 nは方程式の他のものよりもはるかに大きくなるため、定数と他のすべてを除外します。Big-O 表記法は正確であることを意図したものではありません。入力が非常に大きくなるにつれて問題の解決策がどのように拡大するかを知らせるためだけのものです。十分にn大きくなると、複雑さが非常に大きくなり、他のものが小さくなり、基本的に 2 nになります。

  4. これについては、より具体的にする必要があります。スペースと速度を交換する 2 つのアルゴリズムをお探しですか?

于 2012-05-15T13:41:51.527 に答える
1

3 大 O 表記は支配的な用語のみを引用します。n が大きくなると、これが結果の最も重要な部分になります。

4 バブル ソートを検討する - 長い時間がかかるので嫌いでしたが、もう 1 つの項目のスペースしか必要としません。

于 2012-05-15T13:46:40.693 に答える