CS 3303 Exam Questions and Answers 2022

A solution is said to be efficient if it: - ANSWER It solves the problem within the required resource constraints. An ADT is: - ANSWER the realization of a data type as a software component. The implementation of a data type as a data structure is the physical form of an ADT. True or false? - ANSWER True Which of the following is NOT one of the design patterns mentioned in our text? Flyweight? Visitor? Composite? Synergy? - ANSWER Synergy If A={1, 2, 3, 4} and B={4, 5, 6}, find A∪ B . A: { x | x is all positive integers } B: {1,2,3,4,5,6} C: {1,2,3,4,4,5,6} D: {4} - ANSWER B: {1, 2, 3, 4, 5, 6} According to the properties of logarithms, log(nm) = A: a. log n - log m B: n log n C: log n + log m D: log(n^m) - ANSWER C: log n + logm Recursion is when an algorithm uses a series of loop structures to repeat an operation until the answer has been computed. True or false? - ANSWER False Which of the following is not a mathematical proof technique? A: proof by mathematical induction B: proof by contradiction C. Direct proof D. proof by consensus - ANSWER D. proof by consensus Which of the following is not a characteristic of an algorithm? A: It must be correct. B: It must be composed of concrete steps. C: It can have no ambiguity. D: It must be composed of an infinite number of steps. - ANSWER D: It must be composed of an infinite number of steps. The upper bound for the growth of the Algorithms running time is represented by: A: Big Oh (O) B: Big Omega(Ω) C: Big Theta(Θ) D: Exponential Growth - ANSWER A: Big Oh(O) Asymptotic Algorithm Analysis is primarily concerned with? - ANSWER The growth rate demonstrated in the algorithm running time equation True/False: Big Theta (Θ) indicates that the Upper and Lower bounds of an algorithm are the same. - ANSWER True For the following code fragment, select the option that represents the most appropriate asymptotic analysis: for (int i = 0; i h; i++) { Sln(a[i]); } A: O(n) B: O(2^n) C: O(n log n) D: O(n^2) - ANSWER O(n) For the following code fragment, select the option that represents the most appropriate asymptotic analysis: for (int i = 1; i = n; i *= 2) { for (int j = 0; j n; j++) { count++; } } Option 1. O( 1 ) Option 2. O( 2n ) Option 3. O( n log n ) Option 4. O( n2 ) - ANSWER O(n log n) Explanation: Here the outer loop is done log n times and the inner loop is done n times, so T(n) = n log n. (Note that the default base for logarithms in Computer Science is 2.) For the following code fragment, select the option that represents the most appropriate asymptotic analysis: if (h 0) { return a[h - 1]; } else { throw new NoSuchElementException(); } Option 1. O( 1 ) Option 2. O( 2n ) Option 3. O( n log n ) Option 4. O( n2 ) - ANSWER O(1) Explanation: Here n = h, and T(n) = 1. For the following code fragment, select the most appropriate asymptotic analysis: // Towers of Hanoi static void solveHanoi(int disks, char fromPole, char toPole, char withPole) { if (disks = 1) { solveHanoi(disks-1, fromPole, withPole, toPole); moveDisk(fromPole, toPole); solveHanoi(disks-1, withPole, toPole, fromPole); } } static void moveDisk(char fromPole, char toPole) { moves++; } Option 1. O( n ) Option 2. O( 2^n ) Option 3. O( n log n ) Option 4. O( n2 ) - ANSWER O( 2^n ) For the following code fragment, select the option that represents the most appropriate asymptotic analysis: public static int binarySearch(int[] a, int key) { int left = 0; int right = h-1; while (left = right) { int mid = left + (right-left)/2; if (key a[mid]) right = mid-1; else if (key a[mid]) left = mid+1; else return mid; } //not found return -1; } Option 1. Ω( 1 ), O( log n ) Option 2. Ω( n ), O( 2n ) Option 3. Θ( n log n ) Option 4. Θ( log n ) - ANSWER Ω( 1 ), O( log n ) For the following code fragment, select option that represents the most appropriate asymptotic analysis: for (i=0; in; i++) { // // Search in array a for smallest element starting at i to n-1 // minIndex = findSmallestElement(a, i, n-1) a[i] = a[minIndex]; } findSmallestElement( int a[], int i, int n ) { int largest = a[i]; while(in) { if(a[i] a[largest]) largest = i; i++; } return(largest); } Option 1. O( n ) Option 2. O( 2n ) Option 3. O( n log n ) Option 4. O( n2 ) - ANSWER O( n2 ) index-of-smallest element in a[i..j] takes j-i+1 operations • n + (n-1) + (n-2) + (n-3) + ... + 3 + 2 + 1 • this is n2 For the following code fragment, select the option that represents the most appropriate asymptotic analysis: // Recursive Fibonacci generator static long fibr(int n) { if ((n == 1) || (n == 2)) return 1; // Base case return fibr(n-1) + fibr(n-2); // Recursive call } Option 1. O( n ) Option 2. O( 2n ) Option 3. O( n log n ) Option 4. O( n2 ) Select one: a. Option 1 b. Option 2 Correct c. Option 3 d. Option 4 - ANSWER O( 2^n) A list is... - ANSWER A finite ordered sequence of data times. True/False: A list is said to be empty when all of its elements have a zero value. - ANSWER FALSE The most time-consuming operations on an array based list implementation is: - ANSWER inserting a new element into the head of the list True/False: A linked list implementation relies upon static memory allocation where static refers to the requirement to pre-allocate all of the memory that will be used for the list. - ANSWER False True/False: A linked list creates order through the use of pointers that link one element to another. - ANSWER True True/False: Inserting or removing an item at position n-1 within a linked list has the same cost in terms Q (n) time as the same operation in an array-based implementation of a list. - ANSWER False The freelist ... Select one: a. Provides access to memory within the operating system that has not yet been allocated b. Provides access to memory objects which have no Big O ( n ) time. c. Facilitates and encourages the use of the new operator. d. Holds the list nodes that are no longer in use. - ANSWER D: holds the list nodes that are no longer in use True/False: In a queue, placing new items in the queue is referred to as a push and taking an item out of the queue is called a pop. - ANSWER False. In linked lists there are no NULL links in: Select one: a. Single linked list b. Linear doubly linked list c. Circular linked list Correct d. None of these - ANSWER C. Circular Linked List In a stack which option would access the 3rd element from the top of the stack S Option 1. S.push(-1); Option 2. S.dequeue(-3); Option 3. S.pop(); S.pop(); S.pop(); Option 4. S.pop(n-3); Select one: a. Option 1 b. Option 2 c. Option 3 Correct d. Option 4 - ANSWER B. Option 3 The upper bound for the growth of the algorithms running time is represented by: A: Big Oh(O) B: Big Omega (Ω) C: Big Theta (Θ) D: Exponential growth - ANSWER A: Big Oh(O) A leaf is any node that... A: has one child B: is an internal node with no ancestors C: is any node with two empty children D: is the ancestor of the root node - ANSWER C: is any node with two empty children The full binary tree theorem states "the number of leaves in an empty full binary tree is one more than the number of internal nodes." True / False - ANSWER False The process of visiting all of the nodes of a binary tree in some order is called a traversal. True / False - ANSWER True A full binary tree has a restricted shape which starts at the root and fills the tree by levels from left to right. true / false - ANSWER False A binary tree traversal that lists every node in the tree exactly once is called: A: a traversal B: a visitor design pattern C: an enumeration D: natural ordering sequence - ANSWER C: an enumeration A preorder traversal visits every node starting at the leaf nodes and works up the tree. True / False - ANSWER False Correctly identify the following heap structure by selecting the best answer: A: partially ordered heap B: max-heap structure C: priority heap D: min-heap structure - ANSWER B: max-heap structure Select the answer that best defines Huffman Coding: (Or tell us what it is.) - ANSWER An approach of assigning codes to characters such that the frequency of the code depends upon the relative frequency of the corresponding character in use. According to Shaffer, a heap data structure has two properties: - ANSWER It is a complete binary tree AND...the values stored in it are partially ordered. A finite set of one or more nodes such that there is one designated node call the root is a: (select the best answer) - ANSWER a tree The process of determining if two objects are in the same set and then merging those sets is called: - ANSWER union / find A traversal of a general tree that traverses the roots subtrees from left to right, then visits the root is called a preorder traversal. - ANSWER false path compression - ANSWER A method that is designed to create extremely shallow trees is called: A tree whose internal nodes all have exactly K children is called a K-ary tree. true / false - ANSWER true An important advantage of the sequential tree implementation is that - ANSWER It saves space because there are no pointers. A sequential tree can be represented using a bit vector? - ANSWER true The list of children approach uses both pointers and an array structure to represent the tree. - ANSWER true The weighted union rule joins a tree with fewer nodes to a tree with more nodes by making the smaller tree's root point to the root of the larger tree. - ANSWER true