CS 1704 Fall 2002 Test 2 Answers Q A Reason -------------------------------------------------------------------------------- 1 3 The header file is intended to be #included in other program modules that need to use identifiers declared in the header file. 2 1 See reason for question 1. 3 1 The implementations of the Node member functions will refer to the type name Node (via the scope resolution if nothing else), and so the declaration of Node must be in scope within the cpp file. 4 5 Recompilation will be faster because only the cpp files that have been changed must be recompiled (relinking may be another matter). Since the declaration and implementation of a type are in separate files, distinct from other parts of a program, it is easier to extract that code for use in other projects. 5 2 Conditional compilation directives are used to ensure that the declarations in a header file are not included more than once. 6 3 1 blows it at the second statement, which destroys the second node before there's any provision to save access to the rest of the list. 2 blows it because the second and third statements are in the wrong order. 3 is fine. 7 6 1 is fine. 2 blows it at the third statement, which loses the connection that's needed to make the last statement work. 3 is fine, EXCEPT that the fourth line contains a unintentional syntax error. Therefore, 1 was also counted as a fully correct response. 8 3 For the function to do its job, it must be able to "walk the list" from beginning to end, so the list "bookmark" must be at the head node before the loop is started. 9 6 1 would render the loop pointless. 2 works because the return value from Get()is a reference, so assigning to it will modify the actual list contents. 3 works for the same reason, but stores the reference locally first. 4 doesn't work because it modifies a copy of the data element instead of the one in the list (since Tmp is an int instead of an int&). 10 3 1 fails because the call to delete destroys the acess to the rest of the nodes before Head is reset. 2 fails because it doesn't delete the last node; the loop exits too early. 3 is fine, straight from the notes. 4 would just delete the first node. 5 is silly, since SList allocates SNode objects dynamically. 11 5 From the notes, the dominant term is n^2. 12 2 From the notes, the dominant term is log(n). 13 4 From the notes, the dominant term is n log(n). 14 8 The ratio of times is estimated by (n^2)/(n log n) which simplifies to n / log n. Since n = 2^16 and the log is to base 2, we have: n 2^16 2^16 ----- == ------ == ------ == 2^12 which is approximately 4000. log n 16 2^4 15 3 The inside loop runs a constant number of times and so costs a constant number of operations. The body of the outer loop runs n - 1 times. So, all of that adds up to O(n) total cost. 16 7 Annoy(6) == 2 + Annoy(3) == 2 + 1 + Annoy(10) == 2 + 1 + 2 + Annoy(5) == 2 + 1 + 2 + 1 + Annoy(16) == 2 + 1 + 2 + 1 + 2 + Annoy(8) == 2 + 1 + 2 + 1 + 2 + 2 + Annoy(4) == 2 + 1 + 2 + 1 + 2 + 2 + 2 + Annoy(2) == 2 + 1 + 2 + 1 + 2 + 2 + 2 + 2 + Annoy(1) == 2 + 1 + 2 + 1 + 2 + 2 + 2 + 2 + 1 == 15 17 3 Each of the clauses of the condition is either an error state or an indication that the entire list has been processed. So, in any case, this indicates there are no more matches to be found, and there is no uncounted match, and so 0 should be returned. 18 7 This case handles the detection of a match. You need to count the current match, and then search the remainder of the list for more matches, and return the result. 19 6 Recursion requires lots of pushes/pops of the runtime stack, which iteration does not; that makes pure recursion more expensive. The recursive version will typically (not always) require fewer statements, basically because the runtime stack serves to manage computational details that would have to handles explicitly in an iterative version. 20 4 The Size() function must count the nodes in the list; that requires keeping track of a current position in the list, and that current position must initially be the head node. Since the client cannot pass the Head pointer to a member function (the pointer being private), there is no way for the client to pass in the correct starting info. 21. The basic algorithm is relatively simple: for each member one queue, determine if it is also a member of the other queue and if so, add it to a third queue which will be returned at the end. There are lots of solutions. Here is one: Queue Intersection(Queue A, Queue B) { Queue Result; // queue to store common elements int Candidate; // current element of A while ( !A.Empty() ) { // process ALL elements of A Candidate = A.deQueue(); // take next element of A if ( elementOf(Candidate, B) ) // if it's also in B Result.enQueue(Candidate); // put it in the intersection } return Result; // return the intersection } bool elementOf(int Value, Queue Q) { // "helper" function to do search while ( !Q.Empty() ) { if ( Value == Q.deQueue() ) // compare candidate to next elem of Q return true; // if they match, you're done } return false; // no match for Value in Q } One issue is that the search of B for an occurrence of Candidate will leave B empty. The solution above deals with that by passing B by value to the helper function. If you don't use a helper function, you could also manage this by keeping a copy of B and restoring it after each search, or by "cycling" B (placing the dequeue'd element back into the queue) and watching for the original first element to cycle back to the front. Note that the second approach only works because the terms of the problem state there won't be any duplicates within A or within B.