1

Test 3CS / SE 2630Sample

60 points

(3) 1. Explain why it is important to use version control software when a group works on a software project. In particular, what problem arises when a group works on a project that version control can solve. Be specific, give a concrete example.

(3) 2. What are some advantages of understanding your personal software process? Do you see any disadvantages?

(9) 3. What is the Big O (e.g.: 1, LogN, N, NlogN, N2, ...2N) for each of the following?

______a) Adding to the rear of an STL vector

______b) Adding to the rear of an STL deque

______c) Binary Search of a Sorted Array

______d) Heap Sort

______e) Adding to a priority queue implemented with a heap

______f) Add an element to a balanced binary search tree

______g) Removing an element from an STL set

______h) Adding to the front of an STL list

______i) Finding all M-cliques in a graph of N nodes

(5) 4. Apply the algorithm from class that builds a heap out of any array. Draw a picture and put your final answer in the array underneath. You must draw a proper picture to get full credit.

Index / 0 / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8
Array
Elements / 2 / 5 / 7 / 4 / 3 / 8 / 1 / 6 / 9
Heap
Elements

(6) 5. Write the recursive routine ReheapDown. I'll start you off. Assume you can call Swap.

// Assumes left and right subtrees of root are heaps. If biggest kid > parent, swap and recurse.

void ReheapDown ( InfoType a[], int n, int root )

{

if ( 2 * root + 1 < n ) // does it have children?

{

int maxKidIndex = 2 * root + 1; // set it to the left kid

(7) 6. a) Draw the following undirected graph. b) Write the adjacency matrix. c) List all 3-cliques

G = (V, E), V(G) = {1, 2, 3, 4, 5, 6}

E(G) = { (1,2), (1,3), (1,4), (1,6), (2,3), (3,4), (3,6), (4,5), (5,6) }

(5) 7. Given the following code segment:

for ( int i = -1; i <= n + 2; i++ )

for ( int j = i + 1; j <= n + 5; j++ )

The number of times box is executed is :______

Below are some STL containers and methods to use for the remainder of the test.

The listed "parameters" are really "hints" of what the parameters should be.

string: concat - operator+ stream output - operator< stream input - operator>

set: begin(), end(), insert(item), erase(iterator), find(item) - find returns an iterator

map: iterator find(key) // returns iterator pointing to entry for key

operator[] // if key in map, returns reference to key's value. If key not present,

creates new entry (using default constructor) and returns reference.

Recall: Given a map iterator, iter, then iter->first is the key, ier->second is the value
(6) 8. Write a function that returns all of the words in a list concatenated together. For example, if the list is {a, santa, at, nasa}, the returned result would be asantaatnasa. You must use a const_iterator.

string CatAll ( const list<string> & words )

{

(6) 9. Assume airline flight information is represented as a graph that records which cities have direct flights to which other cities. Assume the graph is stored using adjacency lists, which is implemented using an STL map as with the following declarations:

typedef map<string, set<string> > TFlights;

TFlights flights;

where the second parameter set<string> is a list of cities to which the string in the first parameter has direct flights. Write a segment of code that set the variable boolean variable found to true if there is a direct flight from "Madison" to "Boston", false otherwise.

(10) 10. Write a segment of C++ code that uses an STL set of STL strings to read text input from standard in (cin) and print each distinct word in alphabetical order to standard output (cout). Assume a word is defined as a nonempty sequence of non-white characters.