CSc 17 Final Examination Monday 15 December 1997 4 PM >>>>>>>>>>>>>>>>>>>>>ANSWERS<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< CLOSED BOOK, CLOSED NOTES. ANSWERS AVAILABLE AFTER THE TEST ON MY WEB PAGE AND ON THE BULLETIN BOARD CSCKAY 1. (20 pts) Suppose we have a class called Stack whose instances implement a stack of floats in the usual way and whose member functions include bool empty(), void push(float x), and float pop(). Write a member function swap() which exchanges the top two entries if there are two or more entries on the stack and which leaves the stack alone if there is one or no entry on the stack. >>>>>>>>>>>>>>>>>> void Stack::swap() {float top,next; if (!empty()) {top=pop(); if (empty()) push(top); else {next=pop(); push(top); push(next); } } } >>>>>>>>>>>>>>>>>>> 2. (15 pts) Starting with an empty binary tree, draw a picture of the tree after each of the numbers 12, 4, 8, 6, 9, 7, 18, 22 is entered into the tree, in that order, where a) the tree is used to sort the data in ascending order b) the tree is maintained as a heap >>>>>>>>>>>>>>>>>>>>>>>> a) 12 --> 12 --> 12 --> 12 --> 12 --> 12 --> 12 --> 12 / / / / / / \ / \ 4 4 4 4 4 4 18 4 18 \ \ \ \ \ \ \ 8 8 8 8 8 8 22 / / \ / \ / \ / \ 6 6 9 6 9 6 9 6 9 \ \ \ 7 7 7 b) 12 --> 12 --> 12 --> 12 --> 12 --> 12 --> 18 --> 22 / / \ / \ / \ / \ / \ / \ 4 4 8 6 8 9 8 9 8 9 12 18 12 / / \ / \ / / \ / \ / \ / \ 4 4 6 4 6 7 4 6 7 8 9 6 7 8 / 4 >>>>>>>>>>>>>>>>>>>>>>> 3. (20 pts) In some applications, we want to have very long integers, say with a few hundred digits, but C++ limits us to about 10 digits. Write the specifications for an Abstract Data Type (ADT) for VeryLongIntegers. >>>>>>>>>>>>>>>>>>>>>>> ADT VeryLongIntegers: Input Operation Precondition: parameter is a VeryLongInteger in an unknown state Postcondition: paremeter set to value entered from keyboard Output Operation: Precondition: parameter is a well defined VeryLongInteger Postcondition: value of parameter displayed on screen Plus (Minus, Product) Operation: Precondition: parameter is a well defined VeryLongInteger, a second well defined VeryLongInteger is given Postcondition: the sum (difference, product) of the two VeryLongIntegers is returned as a VeryLongInteger Ratio (Modulus) Operation: Precondition: parameter is a well defined VeryLongInteger, a second well defined, non-zero VeryLongInteger is given. Postcondition: the result (remainder) from dividing the two is returned as a very long integer Less (LessEq, Greater, GreaterEq, Eq, NotEq) Operation: Precondition: parameter is a well defined VeryLongInteger, a second well defined VeryLongInteger is given. Postcondition: the truth (true or false) of the corresponding comparison is returned. Copy Operation: Precondition: parameter is a well defined VeryLongInteger, a second well defined VeryLongInteger is given. Postcondition: a copy of the parameter is returned as a VeryLongInteger. >>>>>>>>>>>>>>>>>>>>> 4. (25 pts) Assume that a well defined binary tree has been constructed from instances of the class BinaryNode, where the instances have the (private) data members int key; BinaryNode child[2]; and the root of the tree is BinaryNode *root. Write a member function "freq" such that the call freq(root,x) returns the frequency with which the int x appears in the tree. You may make no assumptions about the order in which the data appear in the tree. >>>>>>>>>>>>>>>>>>>>> int freq(BinaryNode *root,int x) {if (root==NULL) return 0; else if (root->key==x) return (1+freq(root->child[0])+freq(root->child[1])); else return(freq(root->child[0])+freq(root->child[1])); } >>>>>>>>>>>>>>>>>>>>> 5. (15 pts) I have defined the following function for class node, but I have neglected to write down the pre- and post-conditions. Provide them. preconditions: >>>>>>>>>>>>>>>>>> rt points the first node in well defined linked list of nodes having at least one node, with the last node in the list pointing to the first node (the linked list forms a ring) postconditions: return the number of nodes in the linked list >>>>>>>>>>>>>>>>>>> int node::unknown(node *rt) {node *ptr; int x; ptr=rt; x=1; while (ptr->next != rt) {x++; ptr=ptr->next; } return x; } 6. (30 pts) Write a function countLines such that the call countLines(inFile) returns the number of lines in the file inFile. Assume we have declared char ch; ifstream inFile("aFile"); Also assume that inFile is open for reading and at the beginning of the file aFile. >>>>>>>>>>>>>>>> int countLines(ifstream & in) {int count=0; char kh; in.get(kh); while (!in.eof()) { count++; while (kh!='\n') {in.get(kh); if (in.eof()) kh='\n'; } if (!in.eof()) in.get(kh); } return count; } >>>>>>>>>>>>>>>>>>>>>>>>>>> 7. (25 pts) Write a function max such that the call max(x,first,last) returns the largest entry in the array x between and including the entries at first and at last, where 0 <= first <= last <= 49, and we have declared int first, last; float x[50]; Thus, if first = 4 and last = 7, the functions returns the largest entry among the entries at locations 4, 5, 6, and 7. >>>>>>>>>>>>>>>>>>>>>>>>>>> float max(float x[],int first,int last) {int j; float temp; temp=x[first]; for (j=first+1; j<=last; j++) {if (temp < x[j]) temp=x[j]; } return temp; } >>>>>>>>>>>>>>>>>>>>>>>>>> 8. (15 pts) Perform a "Big-O" analysis on the algorithm you used in question 7. >>>>>>>>>>>>>> If n is the number of entries in the list, then I need to examine each entries ==> n comparisons ==> O(n). >>>>>>>>>>>>>> 9. (20 pts) State the algorithm for solving the N-Queens problem. >>>>>>>>>>>>>> Use a recursive algorithm to place the nth queen in the nth row. If n=0, then we have solved the problem and can print a solution. Otherwise, for each column from 1 to N, try to place the nth queen in that column. If it can be placed, record it being placed, recursively try to place the remaining queens in rows 1 through (n-1), and remove the nth queen upon returning from the recursion. >>>>>>>>>>>>>> 10. (15 pts) What happens when we make the call f("Gboqx Ubbbsjno") where f is the function void f(char x[]) {int loc=0; while (x[loc]!='\0') {if (x[loc]!=' ') if (loc%2 == 0) x[loc]=x[loc]+1; else x[loc]=x[loc]-1; cout << x[loc]; loc++; } } >>>>>>>>>>>>>>> The message "Happy Vacation" appears on the screen >>>>>>>>>>>>>>>