CS111 C++ Practice Quiz #9

Directed Graphs and Algorithms from STL



    Part I: Directed Graphs

    Please use the figure below for the questions in this section of the quiz.


  1. Construct an Adjacency Matrix for the graph shown above. Use an additional one-dimensional array as a key to the Adjacency Matrix.
  2. Construct an Adjacency List for the directed graph shown above.
  3. Name the algorithm that locates a path between verteces using a stack.
  4. Name the algorithm that locates a path between verteces using a queue.





    Part II: STD

    There are 70 function templates in the Algorithms STL. This quiz tests you on only a handful.
  5. What output is produced by the following program?
      #include <iostream>
      #include <numeric>
      using namespace std;
      int main() {
        int Array[10] = {0,1,1,2,3,4,8,13,21,34};
        int sum = accumulate (Array, Array + 10, 200);
        cout << "sum is " << sum << endl;
        return 0;
      }


  6. What output is produced by the following program?
      #include <iostream>
      #include <algorithm>
      using namespace std;
      int main() {
        int Array[10] = {0,1,1,2,3,4,8,13,21,34};
        bool found1 = binary_search(Array, Array+10, 2);
        cout << found1;
        bool found2 = binary_search(Array, Array+4, 21);
        cout << " " << found2 << endl;
        return 0;
      }


  7. What output is produced by the following program?
      #include <iostream>
      #include <algorithm>
      using namespace std;
      int main() {
        int Array[10] = {0,1,1,2,3,4,8,13,21,34};
        copy (Array+7, Array+10, Array+2); for (int i=0; i < 10; i++)
          cout << " " << Array[i];
        return 0;
      }


  8. What output is produced by the following program?
      #include <iostream>
      #include <algorithm>
      using namespace std;
      int main() {
        int Array[10] = {0,1,1,2,3,4,8,13,21,34};
        copy_backward (Array+6, Array+10, Array+6);
        for (int i=0; i < 10; i++)
          cout << " " << Array[i];
        return 0;
      }


  9. What output is produced by the following program?
      #include <iostream>
      #include <algorithm>
      using namespace std;
      int main() {
        int Array[10] = {0,1,1,2,0,2,0,13,0,2};
        int howMany = count (Array, Array+10, 2); cout << howMany; return 0;
      }


  10. What output is produced by the following program?
      #include <iostream>
      #include <algorithm>
      using namespace std;
      int main() {
        int Array[10] = {0,1,1,2,3,4,8,13,21,34};
        int *f = find (Array, Array+10, 21);
        cout << "The element found is " << *f << " and its index is " << f - Array;
        return 0;
      }


  11. What output is produced by the following program?
      #include <iostream>
      #include <algorithm>
      using namespace std;
      int main() {
        int Array[10] = {1, 0, 1, 2, 9999, 2, 67, 13, 0, 8};
        int *x = max_element (Array, Array+10);
        cout << "The element found is " << *x << " and its index is " << x - Array;
        return 0;
      }


  12. What output is produced by the following program?
      #include <iostream>
      #include <algorithm>
      using namespace std;
      int main() {
        int x = min(11, 23, -1, 2, 9999, 2, 67, 13, 0, 8); cout << x; return 0;
      }


  13. What output is produced by the following program?
      #include <iostream>
      #include <algorithm>
      using namespace std;
      int main() {
        char C[11] = "ABCDEFGHIJ";
        random_shuffle(C, C+10);
        cout << C;
        return 0;
      }





Answers
  1. The two arrays are string Vertices[4] and int Edges[4][4]
  2. The two structures required are :
    and
    The Adjacency list will then look like the following image:
  3. Depth First Search
  4. Breadth First Search
  5. sum is 287. 200 is added to the sum of all the integers in the array.
  6. 1 0. Found1 is true because the value 2 was found somewhere between cells 0 and 10. Found2 was false because the value 21 was not found between cells 0 and 4.
  7. 0 1 13 21 34 4 8 13 21 34 - Values in cells Array[7] through Array[10] are copied into cells beginning at cell Array[2].
  8. 0 1 8 13 21 34 8 13 21 34
  9. 3 There are a total of three 2's in the array from cells [0] through [9].
  10. The element found is 21 and its index is 8
  11. The element found is 9999 and its index is 4
  12. -1
  13. DICAJBGEFH - May be shuffled differently. Note the extra cell for the NULL terminator.