DOC PREVIEW
UCF COP 3502 - COP 3502 Solution to Final exam review

This preview shows page 1-2-3 out of 10 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Solution to Final exam review:1. Study the following function:int Mystery(int n){ int i, j, sum= 0; for(i=0; i < 10; i++){ for(j=0; j < n; j++) sum += i * n; } return sum;} What value of sum will be returned when the call Mystery (20) is made? What is the complexity of this function?There are two summations corresponding to 2 “for loops”.The outer one goes from 0 to 9 and the inner one goes from oto n-1. Each time we are adding the product n*i to thevariable sum9 n-1   n ii=0 j=0Both n and i are independent of the loop variable j and canbe taken out. 9 n-1  ni  1i=0 j=0The inner loop sums up “1” n times.9 n2i i=0 = n2 9(10)/2 = 45 n2The call mystery(20) will return 45. 20.20 = 18000 complexity:To determine the order of complexity of the function , notethat the outer loop is independent of problem size n, whilethe inner loop is executed “n” times. Thus the complexityis O(n).2. Solve the recurrence relationT(n) = 2 T(n/2) + 2T(n/2) = 2 T(n/4) + 2T(n) = 4 T(n/4) + 2.2 + 2T(n/4) = 2 T(n/8) + 2T(n) = 8 T(n/8) + 2.4 + 2.2 + 2T(n/8) = 2 T(n/16) + 2T(n) = 16 T(n/16) + 2.8 + 2.4 + 2.2 + 2T(n) = 2k T(n/2k) + 2(2k-1 +. . . + 22 + 21 + 20 )Now 2(2k-1 +. . . + 22 + 21 + 20 ) is a geometric series, whose sum can be obtained as followsSum of a geometric seriesSn = a ( 1 + r + r2 + r3+ r4 +……+ rn-1 ) = a + ar + ar2 + ar3+ ar4 +……+ arn-1 = a(rn – 1 ) / ( r – 1)Thus T(n)= 2k T(n/2k)+ 2(2k -1)/(2-1)Letting 2k = n, k = log nT(n) = n + 2n – 23. LIN is a linear linked list. Write a function which converts LIN into a circular linked list. The function should return a pointer to the last element of the list. struct node * circular ( struct node * LIN){struct node * temp; if (LIN==NULL) return NULL; temp = LIN; while(LIN->next !=NULL) LIN = LIN->next; LIN->next = temp; return LIN;}4. Write a function which examines two linear linked lists A and B in memory, removes the first element from B and puts it in front of A. [6 pts ]void shift(struct node ** A, struct node **B) void shift(struct node ** A, struct node **B){ struct node * temp; temp = *B; *B= (*B)->next; temp->next = *A; *A= temp;}5. a)write a recursive routine which counts the number of nodes in a linked list.int count ( struct node * p){ if ( p ==NULL) return 0; else return 1 + count (p->next);}5.b) Write a function which deletes the left most node of a binary tree. If the root does not have a left subtree, it deletes the root node. In both cases it returns a pointer to the root of the new tree.struct treenode * delete(struct treenode *F){ if (F->left==NULL ) { F= F->right; return F; } else { if (F->left->left==NULL) F->left= F->left->right; else delete(F->left); }} 6. Delete the node 34 from the following BST and redraw the treeSince the node has two children, one solution could be to replace 34 by the largest element from its left subtree, which is 28. The tree would like this 563478204585122837528225640Now the old node 28 can be deleted from this tree. Its only one child 25, would now become the right child of node 20. The final tree takes the shapeThe deletion can also be done by replacing 34 with the smallest child in its right subtree, which is node 37, and then deleting the old copy of 37 resulting in the tree56287820451228375282256408556287820451225375282640857. Put the following elements in a hash table of size 10 using quadratic probing, as discussed in the lecture class.34, 76, 11, 5, 44, 84, 25position = h(k) % Tsize + i2 , h(k) % Tsize - i20 1 2 3 4 5 6 7 8 911 44 34 5 76 84 25 9. Write a recursive routine which prints the binary equivalent of a decimal number“num”.void binary ( int num){ if ( num < 2)printf("%d", num); else { binary( num/2); printf("%d", num%2);5637782045851228405282256}}10. Execute the algorithm on the tree shown below. Show the exact contents of both thestack and the queue when the algorithm completes execution. Assume that the initial callfrom the main program is: P4(root, 60) and that the tree nodes and pointers are definedas shown. The stack grows from left to right.struct treeNode{ int data;struct treeNode *left, *right;}struct treeNode *tree_ptr;void P4(struct tree_ptr *node_ptr, int key) {if (node_ptr != NULL){if (node_ptr->data <= key){push(node_ptr->data);P4(node_ptr->right, (key + 20));P4(node_ptr->left, (key - 20)); }else {enqueue(node_ptr->data);P4(node_ptr->left, (key - 10));P4(node_ptr->right, (key + 10));}}The stack grows to the right.stackqueue5350909569457225287099546180stack5354 61 69 70 99 25 28 45queue90 80 95 50 7211. In the following AVL tree , insert node 93 and then insert 65, so that the tree still remains an AVL tree. Balance if necessary. When 93 is added, it is still balanced. When 65 is added, the tree gets unbalanced, as B.F. of 62 is (2), BF of 67 is (-1) and BF of 65 is 0. There is a change in sign, and so needs a double rotation. Move 65 up , so that 62 falls on left side, and 67 is on right side.562772123862856778563812. An array A containing elements in random order is subjected to bubble sort and the result is stored in array B. What would be the time complexity if array B is now subjected to quick sort? Justify in one line.Since the array is already sorted, quick sort on array B would take O(n2 )_________________________________________________________________13. When Merge Sort is applied on the following array show the arrays that are going to be merged whenever the merge routine is called. [ 28 67 43 10 2 85 52]After merging [67 ]& [43 ] merged array is [43 67 ] After merging [28 ]& [43 67 ]merged array is [28 43 67 ] After merging [10 ] & [2 ] merged array is [2 10 ]56277212386585677893625638After merging [85 ]& [52 ] merged array is [52 85 ] After merging [2 10 ]& [52 85 ]merged array is [2 10 52 85 ] After merging [28 43 67 ] & [2 10 52 85 ] merged array is [2 10 28 43 52 67 85 ]14. Given an array [30 23 5 15 40 89 65 8 ], indicate the output of the following sorting methods after pass 2:i) Selection sortii) insertion sort iii) bubble sort Solution for [30 23 5 15 40 89 65 8]i) Selection sortpass1 : [ 5 23 30 15 40 89 65 8]pass2 : [ 5 8 30 15


View Full Document

UCF COP 3502 - COP 3502 Solution to Final exam review

Download COP 3502 Solution to Final exam review
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view COP 3502 Solution to Final exam review and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view COP 3502 Solution to Final exam review 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?