Computer Science 201 Data Structures & Algorithms s Exam Questions with Answers.

Computer Science 201: Data Structures & Algorithms s Exam Questions with Answers What is a pseudocode? Simple programming language. A text editor. A way of writing programming code in English. A structured method which can be compiled. - Correct Answers: A way of writing programming code in English. One of the important considerations when writing pseudocode is to _____. specify a programming language write everything in a paragraph write only one statement per line write only a portion of the program that is important - Correct Answers: write only one statement per line Which of the following pseudocodes is appropriate to compute area of a triangle? - Enter base length, B | Enter height, H | Compute the area = 1/2 * B * H - Display area - Enter the base length B and height H and compute area - Display area - Enter base length, B - Compute the area=2*B*H - Compute the area using the formula 1/2 * Base * Height - Display the area - Correct Answers: - Enter base length, B | Enter height, H | Compute the area = 1/2 * B * H - Display area Which statement is NOT an advantage of pseudocode? It is written easily in a word processing application. It is standardized. It is easy to modify. It can be used with structured programming languages. - Correct Answers: It is standardized. Which of the following is TRUE about pseudocode? It cannot be modified. It cannot be compiled. It can be compiled in any language you use. It is harder to write than making flowcharts. - Correct Answers: It cannot be compiled. Gwen is an IT programmer for a small, non profit company. She's been assigned to write some new code for her company's payroll department to assist with the roll-out of a new pay for performance system. The new code will affect employees' pay grades, salaries, and bonuses. Gwen has written pseudo-code and the actual code. What should be her next step in the process? Test and debug the code Release the code to the production environment Test the code with real-world users Train end users on the changes to the payroll program - Correct Answers: Test and debug the code A code editor that is used to check syntax, format, run, and test code is known as a/an _____. integrated development environment test environment artificial intelligence system integrated developer extension - Correct Answers: integrated development environment How does the IDE component, known as syntax highlighting, aid developers with writing program code? The tool highlights misspelled words. The tool automatically corrects common typos while typing. The tool makes it easier to recognize the various elements of code . The tool automatically corrects text formatting while typing. - Correct Answers: The tool makes it easier to recognize the various elements of code Explanation Syntax highlighting includes displaying code using different colors to indicate the different types of elements in code. Which of the following is NOT a typical component of an Integrated Development Environment? Debugger Grammar checking Autocompletion Syntax checking - Correct Answers: Grammar checking How does using a debugger in an integrated development environment benefit an individual who is writing code? It is best not to use a debugger, but instead to be thorough and read through all of the lines of code to find the bugs. A debugger can assist with generating test case scenarios which can then be used to test the code to find the bugs. A debugger can automatically fix the broken code for the individual once the bugs have been identified. A debugger walks through code in a systemic and automatic manner to find bugs, making the process less time consuming. - Correct Answers: A debugger walks through code in a systemic and automatic manner to find bugs, making the process less time consuming. A while loop is considered _____ if you don't know when the condition will be true Indefinite Passive Infinite Positive - Correct Answers: Indefinite What will be the result of the following code? int j = 0; while (j < 1000) { j = j - 1; } - Correct Answers: Endless loop A while loop runs code as long as the condition(s) is/are: False Positive True Negative - Correct Answers: True A while loop can evaluate _____ condition(s). Only one Exactly two Zero One or more - Correct Answers: One or more Which is the correct syntax for a while loop? while 1=0 { minute++; } while (total_panic < 1) { minute++; } while int panic { minute--; } while if i=7 then { minute++ } - Correct Answers: while (total_panic < 1) { minute++; } How is a single line comment created in Java? Two backward slashes at the beginning indicate that the line is a comment. Two forward slashes at the beginning indicate that the line is a comment. A forward slash followed by two asterisks at the beginning indicate that the line is a comment. A forward slash followed by an asterisk at the beginning indicate that the line is a comment. - Correct Answers: Two forward slashes at the beginning indicate that the line is a comment. What is an example of a documentation comment? /* This is the beginning and this is the end */ // This is the beginning and this is the end *// / This is the beginning and this is the end **/ /** This is the beginning and this is the end */ - Correct Answers: /** This is the beginning and this is the end */ What is an example of multi-line comment? * / The beginning of a multi-line * / the end of the comment // The beginning of a multi-line the end of the comment // /* The beginning of a multi-line the end of the comment */ * / The beginning of a multi-line the end of the comment * / - Correct Answers: /* The beginning of a multi-line the end of the comment */ What does JDK stand for? Java Developers Kit Java Developers Environment Junior Developers Kit Java Development Kit - Correct Answers: Java Development Kit The compiler is giving an error on the following statement. Why? float hoursWorked Missing brackets Missing a value Missing a variable Missing semicolon - Correct Answers: Missing semicolon A Java statement can be thought of as which one of the following? An expression An instruction A prompt A loop - Correct Answers: An instruction int marker = 10; What type of statement is the following? Integer Void Control Assignment - Correct Answers: Assignment if (i == 10) SIn("10") i += 10; Examine the following code. What is missing on the ''if statement''? Brackets/braces A semicolon An ''else statement'' An ''end if'' statement - Correct Answers: Brackets/braces Which of the following is a correctly written Java statement? double conversions = 15.34; for(int i =0; i<15;i++) while(f<3); new String - "joey" - Correct Answers: double conversions = 15.34; What is the correct way to nest comments? - Correct Answers: Why is cloning multi-dimensional arrays in Java not available using the clone method? A Java multi-dimensional array is an array of objects Java doesn't support pointers A Java multi-dimensional array is an array of primitives Only the copyArray or arraycopy methods work in Java - Correct Answers: A Java multi-dimensional array is an array of objects Because a multi-dimensional array is an array of arrays, it means it's an array of objects. We are not able to create a deep copy of an array of objects using clone or arraycopy methods. If you only want to clone a portion of an array in Java, which method do you use? cloneArray copyto arraycopy clone - Correct Answers: arraycopy If a program needed to create a copy of an array with new references to an object, what type of copy would be performed? Narrow copy Empty copy Deep copy Shallow copy - Correct Answers: Deep copy In Java, a _____ copy would copy only the double data types of an array. null shallow deep empty - Correct Answers: shallow Which of the following Java statements will make a clone of an array? double[] rates = oldR(); oldRcopy() = new rates[] double[] rates = new oldRates[].clone(); double[] rates = oldRcopy(); - Correct Answers: double[] rates = oldR(); When compared to an array, why is a linked list less efficient? All elements are indexed. You need to traverse each node. You can access any node's index. Pointers cannot be reset. - Correct Answers: You need to traverse each node. What is the result of executing the program shown? import .Arrays; public class Main { public static void main(String args) { String classList = {"John", "Jean","James"}; String graduatesList = {"John", "Jean", "James"}; if(As(classList, graduatesList)) { Sln("All the students in this class are graduating"); } else { Sln("Some of the students are not graduating."); } } } It prints out 'Some of the students are not graduating' It prints out 'All the students in this class are graduating' It prints out to the console 'Error: The 2 arrays are String arrays that can not be compared' It throws an error on the line where the 2 arrays are being compared because the s is missing on As - Correct Answers: It prints out 'All the students in this class are graduating' The Method is called As and it loops through each of the string elements of the 2 arrays to compare them (The elements) using the equals method, which for this case would prove that the 2 arrays are equivalent since they all contain the same elements but it will throw an error since the Method is spelled wrong. In a singly linked list, the tail node points to what? The head Null The node before the tail 0 - Correct Answers: Null In loop variants, the relationship between the variables _____. is none of the above is different before and after the loop cannot be determined is the same before and after the loops - Correct Answers: is the same before and after the loops The relationship of the variables immediately before and after a loop must hold true. In algorithm analysis, space complexity describes _____. the total time taken by the algorithm the total memory space consumed None of the above. the correct output for an algorithm - Correct Answers: the total memory space consumed Space complexity calculates total memory space consumed an an algorithm. Which method is used to prove a mathematical statement true, by assuming the negation of it to also be true? Manual analysis Induction Contrapositive Contradiction - Correct Answers: Contrapositive A contrapositive method first proves the negative of a given statement true, and then concludes that the original statement is also true. Why is it necessary to analyze an algorithm? To write a program for it. To check the time and space it consumes. All of the above To check the correctness of an algorithm - Correct Answers: All of the above Contrapositive and contradiction fall under which category of algorithm analysis? Loop Variants Induction Contra Attack Asymptotic - Correct Answers: Contra Attack A recursive algorithm has the following expression for its time complexity: T(n) = 2n. Considering this, mark the answer that is undoubtedly correct. This algorithm has a double linear time complexity. This algorithm has a linear time complexity. This algorithm has a linear time complexity and a linear space complexity. This algorithm has a double linear complexity. - Correct Answers: This algorithm has a linear time complexity. If you are performing a sequential search in Java, the data _____. does not need to be sorted must be Boolean must be an integer must be sorted - Correct Answers: does not need to be sorted What happens if an element is not found in a sequential search? Every item in the list was evaluated. The program crashes. An error is displayed in the output. A value of 0 is returned. - Correct Answers: Every item in the list was evaluated. In Big O notation, what is the significance of O(n)? Performance will increase exponentially. Performance increases linearly. Performance decreases at a logarithmic rate. There is no performance impact. - Correct Answers: Performance increases linearly. Given the following Java code that performs a sequential search, what is missing? public static double sequentialSearch(int[] arr, int searchKey) { int arraySize = h; for(int i = 0; i < arraySize; i++) { } return -1; } A) This code will compile as written. B) if(arr[i] == searchKey) { return i; } C) return i; D) if(searchKey == searchKey) { return i; } - Correct Answers: B) if(arr[i] == searchKey) { return i; } Given an array of 2.5 billion elements, what is the average case for a sequential search? The element is not found. The element is found at n/2. The element is found at n. The list is too large. There is no best case. - Correct Answers: The element is found at n/2. Consider the following Java code. Which part of an exponential search is it performing? while (j < size && array[j] <= key) { j = j * 2; } This code is finding the range of the key value. This code will not compile and is in error. This code performs the binary search. This is a recursive function. - Correct Answers: This code is finding the range of the key value. This code is looking for the range of the key value. It is the first step in the exponential search. Once it exits the while loop, the binary search can then be performed. When performing an exponential search in Java, what is the order of operations? Find the range for the element. Then complete a binary search. Perform a binary search. Then split the array in thirds. Complete a binary search. Then find the range for the element. Find the range for the element. Then perform a reverse logarithmic search. - Correct Answers: Find the range for the element. Then complete a binary search. Which of the following Java code items correctly performs the binary search method from the Arrays class? AySearch(myList, M(j, size), searcher); AySearch(myList, (j/2), M(j, size), searcher, i/2, myList); AySearch(searcher); AySearch(myList, (j/2), M(j, size), searcher); - Correct Answers: AySearch(myList, (j/2), M(j, size), searcher); The method can take 2 or 4 parameters. The correct answer sends the array (myList), starting at index /2 (j/2), and goes to the smallest value of j or the size of the array. It looks in that range for the value (searcher) When performing an exponential search in Java, what is the first thing you should do? Check to see if the element is first in the list. Perform a recursive search to find the element. Check if the element is in the middle of the list. Perform a binary search. - Correct Answers: Check to see if the element is first in the list. In relation to a binary search, what does the notation O(log n) indicate about performance? Performance is worse at the beginning, then evens out. Performance gets exponentially worse as n increases. There is no performance impact to the system. Performance is worse at the beginning and worsens toward n. - Correct Answers: Performance is worse at the beginning, then evens out. Because binary searches incrementally split the data set in half, the first iteration brings the heaviest load. The data set then shrinks and evens out as you approach n. In the Tower of Hanoi recursive method, why do we need calls to the method twice? solvePuzzle(n-1, begin, end, temp); solvePuzzle(n-1, temp, begin, end); This will prevent the program from crashing This is an error and the program can run with only one line To move a disc from start to the middle, then move it from the middle to end The code changes the last peg to the first peg by moving all pegs over from the third - Correct Answers: To move a disc from start to the middle, then move it from the middle to end If you are performing a sequential search in Java, the data _____. must be sorted must be Boolean does not need to be sorted must be an integer - Correct Answers: does not need to be sorted Which List algorithm is used for arranging the List elements in a random order? shuffle swap randomize reverse - Correct Answers: shuffle The shuffle algorithm puts the List elements in random order. Which method does the List interface inherit from the Iterable interface? removeIf forEach stream parallelStream - Correct Answers: forEach The List interface only inherits one method from the Iterable interface, and that is the forEach method. Which of the following is a benefit of using the Java Collections Framework? Code portability More robust codebase More readable code Coding shortcuts - Correct Answers: Code portability Writing code using the Java Collections Framework capitalizes on common behaviors for the entire collection. Which of the following sets are implemented classes of the List interface? ArrayList, LinkedList, Stack, and Vector ArrayList, DynamicLinkedList, Stack, and Sort ArrayList, LinkedList, Stack, and Sort ArrayList, RoleResolvedList, Add, and Role - Correct Answers: ArrayList, LinkedList, Stack, and Vector There are 10 implemented classes, including ArrayList, LinkedList, Stack, and Vector. Which package does the List interface belong to? java.String java.ArrayList - Correct Answers: The List interface belongs to the package. If a list contains three objects, what is the index number of the last object? 2 3 0 1 - Correct Answers: 2 How many forms of the add method can be used with lists? Three Two One Four - Correct Answers: Two The add method can be used with and without passing an index value. Which package does the sort method belong to? .ArrayList .List .Collections .LinedList - Correct Answers: .Collections In order to sort our list, we will use the sort method that belongs to the Collections class. So, we must import the .Collections package. Which method is used to retrieve the number of elements in a list? count size max length - Correct Answers: size To create a list, which of these packages must be imported? .Dictionary .Collections .LinedList .List - Correct Answers: .List In order to work on a list, we need to first create one. We must import both the .ArrayList and .List packages. An element within a positional list in Java is also called a(n) _____. head tail root node - Correct Answers: node Elements are called nodes. A node can be a head (at the start of the list), or a tail (at the end of the list) Which of the following best describes an abstract data type (ADT)? It does not require knowledge of how operations are carried out. Knowledge of the data and underlying code is required. Knowledge of Java's ADT library and insertion methods is required. Java does not support ADT. - Correct Answers: It does not require knowledge of how operations are carried out. An abstract data type (ADT) does not require that you know the underlying code, or how the data is structured. It provides the access and methods. Select the correct Java code that completes the method for inserting an element into a positional list. Node newNode = new Node(info); Node currentNode = head; while(--index > 0) { currentNode = currentN; } No method exists for inserting an element into a positional list. newNous = newNous; ous = ; newNode = node; node = newNode; newN = currentN; currentN = newNode; - Correct Answers: newN = currentN; currentN = newNode; This code moves the existing node forward, and slides in the new node just before it. Which two structures does a positional list combine? Queue, array Queue, stack Stack, array Index, array - Correct Answers: Queue, stack A queue lets you add only to the end of the list. A stack lets you only add to the top. A positional list provides the opportunity to perform either or both. Set < Integer > counts = new TressSet() (9343): (847); Based on the following Set, which of the following correctly iterates over all items in the Set? - Correct Answers: Iterator < Integer > itr = tor(); while (Next( )) { ( ); } What is the name of the initial node of a tree data structure? Bunch Root Branch Leave - Correct Answers: Root _____ are the most efficient type of tree data structures. Hierarchical trees Balanced trees Sorted trees Binary trees - Correct Answers: Binary trees What type of structure uses data stored inside a tree node? Hash-code Primary key Hash-map Key-value - Correct Answers: Key-value What is the main characteristic of binary trees? Each parent only has two children. Each node is connected twice. Search time can be reduced. Each root only has two nodes. - Correct Answers: Each parent only has two children. What determines if a value being stored in a tree needs to go to the right or to the left side of the root? If the value being stored is less or greater than the value in the root. If there is an existent root in the tree or not. If the tree being used is a binary tree or not. If all the children in the tree are in the same level. - Correct Answers: If the value being stored is less or greater than the value in the root. Which of the following is NOT a type of binary tree? Recursive binary tree Perfect binary tree Complete binary tree Full binary tree - Correct Answers: Recursive binary tree There are three types of binary trees described in the lesson. These are full, complete and perfect binary trees. Which of the following is NOT a type of binary tree traversal? Backorder traversal Inorder traversal Preorder traversal Postorder traversal - Correct Answers: Backorder traversal Preorder, postorder and inorder traversals are valid types of binary tree transversals. Backorder is not a type of binary tree traversal. Huffman code binary trees are used in which of the following? Image and video compression 3D video games Cryptography Job scheduling queues - Correct Answers: Image and video compression What is the main property of a binary tree? Every leaf node must have exactly two children. Every node can have a maximum of 0, 1 or 2 children. Every node must have at least 1 child. Every node should have exactly two children. - Correct Answers: Every node can have a maximum of 0, 1 or 2 children. The main property of a binary tree is that each node can have either 0, 1 or 2 children. Which of the following binary trees is a binary search tree? - Correct Answers: Which of the following binary trees is a binary search tree? number 1 Which major application uses B-tree data structure? Designing heap sort algorithm Writing routing algorithms Database building and indexing Priority Queuing - Correct Answers: Database building and indexing B-tree is used majorly in building a database and its indexing. An important use of heap data structure is _____. indexing databases priority queue building databases storing routing tables - Correct Answers: priority queue Since heaps are very useful in the data structures that require an element to be removed with highest or lowest priority, one of its major application areas is designing priority queues. In which of the following data tree structures does a parent node have more than two child nodes? Heap Hash B-tree Binary tree - Correct Answers: B-tree Which of the following data tree structures has a parent node that can't have more than two child nodes? Heap Both Binary tree and Heap B-tree Binary tree - Correct Answers: Both Binary tree and Heap In max heap type, which node has the element with the greatest value? First child node Last node of right sub tree Root node Last child node - Correct Answers: Root node What is the compareTo method used for? Select the most complete answer. Compares new elements Compares the first and last elements Compares two queues Compares two elements in the queue - Correct Answers: Compares new elements The compareTo method is used to compare new elements as they are added to the priority queue. This determines their priority. Which method is a combination of the peek and remove methods? offer clear comparator poll - Correct Answers: poll What type of data can a priority queue contain? Integers Any type of data Arrays Strings - Correct Answers: Any type of data Which keyword is used to create a PriorityQueue instance? new create queue add - Correct Answers: new We use the 'new' keyword to create the priority queue as in the following example: PriorityQueue<String> myPriorityQueue = new PriorityQueue<>(); What is natural order? Chronological First-In A sort order such as numeric or alphabetic First-Out - Correct Answers: A sort order such as numeric or alphabetic The default order of priority queues is referred to as natural order. That simply means that if the elements are numbers, they will be numerically ordered, and if they are strings, they will be alphabetized. What is the difference between 'merge' and 'meld' operations of the heap? 'merge' joins or combines two heaps into one heap and destroys the original heap, 'meld' joins or combines two heaps into one heap and preserves the original heaps. 'merge' joins or combines two heaps into one heap and also preserves the original heaps, 'meld' also combines two heaps into one heap but destroys the original heaps. 'merge' splits one heap into two heaps. 'meld' splits one heap into two heaps. - Correct Answers: 'merge' joins or combines two heaps into one heap and also preserves the original heaps, 'meld' also combines two heaps into one heap but destroys the original heaps. Both operations combine two heaps into one heap but 'merge' preserves the original heaps while 'meld' destroys the original heaps. What are the two types of heap data structure? Min-heap and Max-heap Median-heap and Min-heap Median-heap and Full-heap Max-heap and Median-heap - Correct Answers: Min-heap and Max-heap Heaps can be min-neap (where the root node has the lowest value) or max-heap (where the root node has the highest value). Which of the following statements is NOT correct? None of these statements are incorrect. The value of every parent node is greater than or equal to that of their child or node in min-heap. The value of every parent node is lesser than that of their children in min heap. Heap is a binary tree. - Correct Answers: The value of every parent node is greater than or equal to that of their child or node in min-heap. In min-heap the value of every parent is less than or equal to that of their children with the root node having the minimum element value. Which of the following is an important property of heap data structure? The right child of any node must always be greater than its left child. Every node has a maximum of 3 children in heap data structure. Heap follows binary search tree principles. The nodes must be inserted from left to right. - Correct Answers: The right child of any node must always be greater than its left child. Heap data structure does not follow binary search tree principle and thus there is no need for a node to have lesser value at the left child and greater value at the right child. The maximum number of children for any node on heap is either 0, 1 or 2. Which of the following is a property of max-heap? The value of the root element is the smallest of all other nodes in max-heap. The value of the root element is the greatest of all other nodes in max-heap. The value of level 0 left child element is the greatest of all other nodes in max-heap. The value of a child element is greatest of all other nodes in max-heap. - Correct Answers: The value of the root element is the greatest of all other nodes in max-heap. In a max-heap, the value of the root element must be greater than all the other nodes. Which method retrieves and removes the highest priority item of a priority queue? clear poll remove retrieve - Correct Answers: poll The poll method will retrieve the item with the highest priority and remove it. What is the default sort order for priority queues? Natural order Null Numeric Alphabetic - Correct Answers: Natural order Priority queues use a natural order to determine priority. Which method can we use to sort a priority queue by multiple elements? compareTo sort multiSort comparator - Correct Answers: compareTo The compareTo method can be used to sort priority queues by one, two, or more elements. Which interface must we implement in order to compare elements in a priority queue? PriorityQueue Comparable Driver Comparator - Correct Answers: Comparable The Comparable interface permits us to compare instances of elements in a priority queue. Which interface requires the compareTo method to be overridden? Comparable Driver PriorityQueue Comparator - Correct Answers: Comparable When we implement the Comparable interface, we are required to provide an @Override the abstract method compareTo. Which of the open addressing methods involves the simplest calculation for collision resolution? Quadratic Linear Chaining Double hashing - Correct Answers: Linear Linear probing is the simplest collision resolution technique, because we simply add the constant 1 to the current position until we get an empty location. Quadratic and double hashing techniques both involve additional equations for calculating the alternative location. Chaining is not an open addressing technique. Which of the following location states will be treated the same when doing an INSERT operation into the hash table in open addressing? None of the states will be treated the same in open addressing Occupied and Deleted Empty and Deleted Occupied and Empty - Correct Answers: Empty and Deleted When doing an INSERT operation, both Empty and Deleted spaces in the table will have values inserted into them. Deleted spaces will be treated differently from Empty spaces when doing data retrieval only. _____ occurs when there is an attempt to store a value in an occupied space in a hash table. Collision Delay Clustering Hashing - Correct Answers: Collision Given a second hash function of I(k) = (1 + k%7) , in which position in the table below would the key 53 be stored using the double hashing technique? [0][1][2][3][4][5][6][7][8][9] [E][E][E][3][E][E][E][E][E][E] 4 6 8 3 - Correct Answers: 8 We calculate the base address H(53) = 53%10 = 3 Since position 3 is occupied, we need to resolve the collision by computing the alternative location using double hashing with second hash equation as: I(k) = (1 + k%7) The full equation to use when a collision occurs the first time: (1*I(k) + base address)%(table length) Position for 53 = (1*I(53) + 3)%10 = ((1+53%7) + 3)%10 = ((1+4) +3)%10 = 8%10 = 8 What is the position where key 75 would be inserted into the table below using the quadratic probing method? [0][1][2][3][4][5] [6] [7] [8] [9] [E][E][E][3][E][5][25][E][E][35] 6 4 0 2 - Correct Answers: 4 We compute the base address as: H(75) = 75%10 = 5 Since position 5 is occupied, we use the quadratic function H(k) = (probe number 2+base address)%10 We would use probe number as 1 in this equation since this will be the first computation for inserting 75. H(75) = (1 2+ 5)%10 = (1 + 5)%10 = 6%10 = 6 Since position 6 is already occupied, we recompute using probe number as 2: H(75) = (2 2+ 5)%10 = (4 + 5)%10 = 9%10 = 9 Since position 9 is occupied, we recompute using the next probe number as 3: H(75) = (3 2+ 5)%10 = (9 + 5)%10 = 14%10 = 4 We would store 75 and position 4. Using linear probing, which table correctly shows how the sequence of keys 51, 67, and 86 be stored in the table below? [0] [1] [2][3][4][5][6][7][8][9] [E][11][31][E][E][E][E][E][E][E] - Correct Answers: [0][1][2][3][4][5][6][7][8][9] [E][11][31][51][E][E][86][67][E][E] To insert 51, we first compute the base address as: H(51) = 51%10 = 1 Since position 1 is occupied, we need to compute the alternation location as (1+current position)%10 In this case we compute (1 + 1)%10 = 2%10 = 2. Position 2 is also occupied, so we compute the next position using (1+2)%10 = 3. Since position 3 is empty, we store 51 in that position. The keys 67 and 86 do not cause collisions when we compute the base addresses, so we can store the keys at the base address. To insert key 67 we compute the base address as 67%10 = 7 Similarly, the base address for 86 is computed as 86%10 = 6 What are the main characteristics of a good Hash Function? Adaptable size and uniform distribution Use of positive indexes and open addressing Easy to compute and proper randomization Easy to compute and uniform distribution - Correct Answers: Easy to compute and uniform distribution What is the structure used for storing data in a Hash Table? Indexing Index-bit Hash-value Key-value - Correct Answers: Key-value When selecting a collision resolution method for Hash Tables, when are linked lists better than open addressing? When using modular hashing When the storage utilization is above 80% It is never better When the storage utilization is below 50% - Correct Answers: When the storage utilization is above 80% What are the key things to consider when it comes to using Hash Tables? Hash Function and Open Addressing Open Hashing and Close Hashing Hashing and Collision Resolution Hashing and Open Addressing - Correct Answers: Hashing and Collision Resolution Hashing will determine how the keys are created for the values and Collision Resolution will help deal with a hash function assigning the same key to multiple values What is a collision in Hash Tables? When the hash table runs out of space When two values are being inserted at the same time When the hash table has to use linked lists When the hash function assigns a key that has already been assigned - Correct Answers: When the hash function assigns a key that has already been assigned Which of the following is true of Robin Hood hashing? It allows a key to be moved once it is established Keys cannot be moved/altered once established Key-values can be duplicated and replicated in the table The hash table can never have any open slots - Correct Answers: It allows a key to be moved once it is established Robin Hood lets you move keys as needed to ensure the shortest distance between keys and key-value pairs. Which of the following is true of Robin Hood hashing? The hash table can never have any open slots Keys cannot be moved/altered once established Searches can be ended early Key-values can be duplicated and replicated in the table - Correct Answers: Searches can be ended early Once there is a 'hit', the search can stop; there's no need to keep going in the Robin Hood hashing method. In Robin Hood hashing, the 'rich' elements are best described as what? Rich elements are those with more than one address assigned A rich element has more than one key and/or key-value pair Remember the poor elements are those closest to the key; the rich ones are further away. Remember the rich elements are those closest to the key; the poorer ones are further away. - Correct Answers: Remember the rich elements are those closest to the key; the poorer ones are further away. The idea is to move the elements further away from their key so that the traversal is shorter. Which of the following is unnecessary in a Robin Hood hashing methodology? Empty elements Open addressing Key-value pairs Linked lists - Correct Answers: Linked lists Robin Hood hashing is an open addressing method for avoiding collisions, but you don't need a linked list as you would in a chaining methodology. Key-values still exist, and there will be empty spots in the table. What best describes the ratio of probe counts in Robin Hood hashing versus traditional open addressing algorithms? Lower Higher Zero Equal - Correct Answers: Lower In fact there are often only about 6 probe counts versus 72! Even if you get no results, there is still far less traversing/probing of the table. The last names of students in a class of 15, are all unique. The last names and the number of siblings they have, are saved in a TreeMap. Which method will you use to find the first value, alphabetically, of the last name? lastEntry floorKey firstEntry ceilingKey - Correct Answers: firstEntry In this case, the last names will be automatically saved in alphabetical oder. The firstEntry() method will retrieve the last name starting with A in ascending order. Student ID 021 recently left the school. The teacher would like to know what the active ID is for the student just before student ID 021. She uses a TreeMap to save student IDs and names. What method can she use from the TreeMap to retrieve this information? lowerKey(key) floorKey(key) higherKey(key) ceilingKey(key) - Correct Answers: lowerKey(key) Read Answer Explanation ExplanationThe lowerKey (Key) will retrieve the next lowest value. In this case lowerKey(021) will retrieve the next lowest value to find the ID just before 021. The pet names in a dog training camp of 10 dogs is unique. The pet names and the home address they live in are saved in a TreeMap. You would like to know which alphabet is the last in order. Which method will you use to find the highest value of the dogs name? floorkey lastEntry ceilingKey firstEntry - Correct Answers: lastEntry The pet names will be automatically saved in alphabetical order. The lastEntry() method will retrieve the last dogs name. Following a test, all students who qualified for a prize were entered in a database. Later it was found that student ID 035 was disqualified. The teacher would like to find out the ID for the student just after 035 who is next qualified. What method can they use from the TreeMap to retrieve this information? floorKey(key) higherKey(key) ceilingKey(key) lowerKey(key) - Correct Answers: higherKey(key) Read Answer Explanation ExplanationThe heigherKey(key) retireves the least key that is the next higher in the map. In this case higherKey(035) will find the next higher ID after ID 035. There are 30 students in a class with student IDs from 001 to 030. What method can be used to retrieve the IDs of students from 20 through 30 if the data is stored in a Map ADT? studentMng(20, 30); studentMng(20, 31); studentMMap(20, 30); studentMMap(20, 31); - Correct Answers: studentMMap(20, 31); The submap method will retrieve values starting from the lowest key (fromKey - inclusive), to the highest key (toKey - exclusive). Since the first and last student IDs to be retrieved are 20 and 30 respectively, inorder not to miss the last student ID (30), you have to specify 31 as the toKey. Separate chaining is NOT affected by _____. table size or memory space available poor hash function or large input data poor hash function or memory space available index key values or memory space available - Correct Answers: poor hash function or large input data index key values or memory space available Separate chaining is less vulnerable to issues with poor hash functions and factors that affect input loading. Which characteristic causes the poor turnaround times for searching operations in separate chaining? Very long link chains Redundant storage spaces Poor hash function Large volume data input values - Correct Answers: Very long link chains The biggest advantage of separate chaining is its collision avoidance capabilities. This means that many data items may be hashed with the same keys creating long link chains. But, this adversely affects the turnaround time for searching operations. Data collision occurs in a hash table when _____ two different table cells hash to the same index key in a hash table two different keys are stored to the same hash value in a table two different values hash to the same index key in a hash table the hash function is overloaded with data - Correct Answers: two different values hash to the same index key in a hash table Data collision occurs in a hash table when two different values hash to the same index key in the table. Separate chaining is defined as _____. -The method by which linked lists of values are built in association with each location within the hash table where a collision occurs. -The method by which hashed links are built within data input values where the volume of the input data is unknown -The method of separating data input sets into unique storage spaces avoiding collisions -The method of separating index keys of the data input values avoiding collisions - Correct Answers: the method by which linked lists of values are built in association with each location within the hash table where a collision occurs. Separate chaining is defined as a method by which linked lists of values are built in association with each location within the hash table where a collision occurs. Separate chaining is best used in situations where _____ input loading is at its optimal the input data is small and the hash function is good the volume of the input data and the frequency of hash keys generation and re-assignment are unknown the volume of data to number of table cells is 1:1 - Correct Answers: the volume of the input data and the frequency of hash keys generation and re-assignment are unknown Separate chaining is best used in situations where the volume of the input data and the frequency with which the hash keys are generated and re-assigned are not known. A shop has a number of printers each with a different serial number. Some of the printers are on sale. What gets printed out after the following code is executed: costP ('HP101', '$195'); costP('HP203', '$204')' costP('HP101', $159'); Sln(costP()): Null Error 2 3 - Correct Answers: 2 The Map busInfo contains bus numbers and the first stop the bus halts at after it leaves the bus depot. The following code was implemented: busI ('206', 'Maple Street'); busI ('206', 'Green Town'); What happens after the two lines of code are executed? The Map data type busInfo() has one key-value pair: 206-Green Town The Map data type busInfo() runs into an error since '206' is repeated twice The Map data type busInfo() has two key-value pairs: Maple Street-206 and Green Town-206 The Map data type busInfo() has two key-value pairs: 206-Maple Street and 206-Green Town - Correct Answers: The Map data type busInfo() has one key-value pair: 206-Green Town The Map data type carPlates contains license plate numbers and car make and model in the state of New York. One of the cars in the Map data type is a Toyota Camry with license plate 12015, and another is a Honda Accord with license plate 50064. When the following code is executed, what gets printed out? Sln (carPinsValue('Toyota Camry')): - Correct Answers: True Which of the following is a benefit of Robin Hood hashing? Next open address is always filled Probe counts increase exponentially Empty slots are always used Searches can be ended early - Correct Answers: Searches can be ended early One of the most fundamental rules in a balanced BST nodal structure's representation is _____. keys on the left of a node should be larger than the node and keys on the right side of a node should be less than that node three nodes can share one child a root node should have three children keys on the right of a node should be larger than the node and keys on the left side of a node should be less than that node - Correct Answers: keys on the right of a node should be larger than the node and keys on the left side of a node should be less than that node A Sort Map is _____. a searchable collection of elements a searchable collection of maps a node with a minimum of 2 children an element with left and right nodes - Correct Answers: a searchable collection of elements What is a Binary Search Tree (BST)? BSTs are a collection of trees, branches, and leaves BSTs are searchable collections of elements characterized by a nodal tree structure. BSTs are Boolean trees made of digital movable branches BSTs are Boolean trees made of digital movable nodes and leaves - Correct Answers: BSTs are searchable collections of elements characterized by a nodal tree structure. The balance factor is defined as _____. the imbalance condition caused by an insertion operation the imbalance condition caused by a deletion operation the difference in nodal height between the left and right child nodes on a branch the difference in nodal rotation between the left and right child nodes on a pivot - Correct Answers: the difference in nodal height between the left and right child nodes on a branch The balance factor measures the difference in height between the left and right child node with respect to a particular node. Which of the following illustrations have all their correct balance factors correctly displayed (in red)? - Correct Answers: The balance factor measures the difference in height between the left and right child nodes with respect to a particular node. In the correct answer: For the top node 12, follow it down to the bottom, 3 (on the left) - 3 (on the right) = 0 For node 4, 0 (on the left) - 2 (on the right) = -2 For node 32, 1 (on the right) - 2 (on the left) = -1. AVL implementations can be less efficient in situations where _____. there are frequent data lookup queries frequent left and right node balancing there are frequent deletion operations the balance factors are greater than -1 - Correct Answers: there are frequent deletion operations AVL trees are characterized by _____. self-balancing properties, binary nodes and balance factor between-1 and 1 self-balancing properties, binary nodes and balance factor between -2 and 1 multi-way search properties, binary nodes and balance factor >3 automatic deletion properties, multi-way search properties and, binary nodes - Correct Answers: self-balancing properties, binary nodes and balance factor between-1 and 1 AVL trees are self-balancing binary trees with a balance factor between -1 and 1. Which of the following trees has been correctly updated by inserting node 68? - Correct Answers: 68 is added and the left node 85 makes the tree unbalanced. A left rotation around 85 and a swap with 55 making 68 a right child of 55 and the tree is balanced. Based on the code below, what is the most relevant operation being performed? if (node == Child) { rightRotate(node); leftRotate(node); } else { leftRotate(node); rightRotate(node); } Creating a new node in a binary search tree. Reversing a rotation of a splay tree. Upward and left rotation of a splay tree. Zig-zag rotation of a splay tree. - Correct Answers: Zig-zag rotation of a splay tree. What is meant by the O(log(n)) notation? Performance is impacted at a exponential rate. Performance starts out low, then spikes dramatically as n increases. As the number of nodes increases, performance levels out. As the number of elements decreases, performance increases rapidly. - Correct Answers: As the number of nodes increases, performance levels out. Since searching binary trees is a divide and conquer approach, the initial search has the biggest performance hit. As you continue to reduce the tree by halves, performance evens out. Which of the following is true with splay tree rotations? Rotations are only allowed for normalized trees. There are only two possible rotations. Each rotation moves the node once. Each rotation moves the root node twice. - Correct Answers: Each rotation moves the node once. Read Answer Explanation With splay tree rotations, a node is moved once and there are at most two rotations. The operations available are zig, zig-zag, and zig-zig. A splay tree is best described as what type of data structure? Binary search tree Positional list Circular list Multi-dimensional array - Correct Answers: Binary search tree Read Answer Explanation A splay tree is a type of binary search tree, which has branches splayed in different directions. For larger structures, this improves performance over binary search trees. After a zig-zig operation performed on the tree below, which of the following trees will remain? - Correct Answers: In a zig-zig operation, the node moves up through the tree and winds up being the parent in a single-node line. Multiway search trees are not binary search trees because _____. they are self-balancing trees a node can contain more than one child node they are color coded trees a node can contain more than 2 child nodes - Correct Answers: a node can contain more than 2 child nodes Binary means 2. Binary search trees can contain a maximum of two child nodes, whereas Multiway search trees can contain more than 2 child nodes. An overflow occurs when _____. the number of child nodes is less than the number of associated key values the number of child nodes is more than the number of associated keys values the number of keys within the node equals the number at the root node the number of keys within a node exceeds the maximum number allowed - Correct Answers: the number of keys within a node exceeds the maximum number allowed An overflow occurs in a node when the number of key values within that node exceeds the maximum number allowed. Which of the following is a characteristic specific to the red-black tree? All child nodes must be red. The root node can hold any number of child nodes. If a node is red, then its child nodes are black. Each node may have N number of children where N=4. - Correct Answers: If a node is red, then its child nodes are black. With red-black trees, nodes are either red or black in color. If a node is red, all child leaves are black. Which of the following search trees is balanced? - Correct Answers: Answer 1 Answer 2 is incorrect because 40 cannot be on the left of 25. The left node is supposed to be a smaller number than 25. Answer 3 is incorrect because the second level node on the extreme right has more than three key values. This creates an overflow. Answer 4 is incorrect because the root node value makes the tree unbalanced. It needs to be between 20 and 40. Key 61 needs to be inserted into the following 2-3-4 tree. What would the correct result be? The insertion will be successful as key 61 already exists. The insertion will not happen. There will be a search hit on key 61 as it already exists. The insert operation would be successful as the are multiple blank nodes for the insertion to be completed. The insertion will be unsuccessful. The root node has reached its maximum capacity of child nodes. - Correct Answers: The insertion will not happen. There will be a search hit on key 61 as it already exists. The insertion will be successful as key 61 already exists. When an insertion process happens, the key in question is first searched for. If there is a search miss and the rules of the tree are adhered to, then the insertion is carried out. If a search hit is encountered, the insertion will fail. What is a search algorithm? a tool used to dynamically grow a tree based database A search algorithm is a program used to search algorithms, their tools and characteristics a set of tools that used for index nodes and numbers a set of codes or program that uses search keys and input strings to search directory database or web page. - Correct Answers: a set of codes or program that uses search keys and input strings to search directory database or web page. A search algorithm has search keys or strings as input and uses its codes and procedures to search the relevant text, directories, databases or web pages and extract the required results. Which Big O Notation applies to a binary search tree that is balanced? O(log2MlogMN) O(n) O(log(n)) O(n2) - Correct Answers: O(log(n)) Read Answer Explanation O(log(n)) applies to most search trees, unless they are not balanced. In that case, you revert back to O(n) Which of the following algorithms requires the data lists or database to be in a numbered or indexed format to work efficiently? Binary search Tree Search Full text search Linear search - Correct Answers: Binary search Read Answer Explanation The binary search works most efficiently in a sorted database. The Splay Tree algorithm differs from AVL in that _____. Its data structure cycles the nodes sequentially with decrease efficiency. Its data structure has the ability to self-balance allowing the least frequent accessed nodes to be nearer the root increasing efficiency. Its data structure has the ability to rotate allowing the most frequent accessed nodes to be nearer the root increasing efficiency. Its data structure cycles the unbalanced nodes sequentially with decrease efficiency. - Correct Answers: its data structure has the ability to rotate allowing the most frequent accessed nodes to be nearer the root increasing efficiency Read Answer Explanation Splay Trees have the additional advantage of moving frequently accessed nodes closer to the root of the tree making them much more efficient over time. Which algorithms have multiple child nodes (more than 2)? Multiway Tree and 2-3-4 trees The Splay Tree and Multiway Tree The AVL Tree and 2-3-4 Trees Binary Search Tree and The Splay Tree - Correct Answers: Multiway Tree and 2-3-4 trees What is a Binary Search Tree (BST)? BSTs are Boolean trees made of digital movable branches BSTs are Boolean trees made of digital movable nodes and leaves BSTs are a collection of trees, branches, and leaves BSTs are searchable collections of elements characterized by a nodal tree structure. - Correct Answers: BSTs are searchable collections of elements characterized by a nodal tree structure. A Sort Map is _____. a searchable collection of maps an element with left and right nodes a searchable collection of elements a node with a minimum of 2 children - Correct Answers: a searchable collection of elements One of the most fundamental rules in a balanced BST nodal structure's representation is _____. three nodes can share one child a root node should have three children keys on the right of a node should be larger than the node and keys on the left side of a node should be less than that node keys on the left of a node should be larger than the node and keys on the right side of a node should be less than that node - Correct Answers: keys on the right of a node should be larger than the node and keys on the left side of a node should be less than that node The algorithm which sorts elements in an array by the use of the divide and conquer paradigm is the _____. Selection Sort Algorithm Marble Sort Algorithm Merge Sort Algorithm Bubble Sort Algorithm - Correct Answers: Merge Sort Algorithm Read Answer Explanation Merge Sort Algorithm involves the dividing the array into multiple sub-arrays. Each sub-array is then sorted and then brought back together into a sorted array. This method is often referred to as the divide and conquer paradigm. Using the Big-O Notation, the best and worse case scenario for the Selection Sort algorithm is represented by _____ Best case:O(n^2) Worst Case:O (n log n) Best case:O(log n) Worst Case:O(1) Best case:O (n log n) Worst Case: O(n^2) Best case: O(n^2) Worst Case: O(n^2) - Correct Answers: Best case: O(n^2) Worst Case: O(n^2) The Selection Sort best and worst case scenarios both follow the time complexity format: O(n^2) as the sorting operation involve two nested loops. The Big-O Notation is the _____. standard by which the performance of algorithmic functions is measured method by which sort algorithms are developed standard by which the number of recursions in the algorithmic functions is measured performance indicator for sub arrays - Correct Answers: standard by which the performance of algorithmic functions is measured Read Answer Explanation The Big-O Notation is the standard by which the performance of algorithmic functions is measured A sorting algorithm is defined as _____. The process of reordering a group of items into a specified order. The process of performing algorithmic functions The process of memory accessing components of an algorithmic function The process of splitting an array into multiple sub-arrays for access into memory - Correct Answers: the process of reordering a group of items into a specified order. A sorting algorithm is used to reorder a group of items into a specified order. In which of the following sort algorithms does the arrangement of elements not affect its performance? Selection Sort algorithm Insertion Sort algorithm Bubble Sort algorithm Manage Sort algorithm - Correct Answers: Selection Sort algorithm The arrangement of elements does not affect its performance of the Selection Sort algorithm .Bubble sort uses a _____ for-loop structure. double single triple quadruple - Correct Answers: double Bubble sort compares _____ elements of an array at a time. all four three five two - Correct Answers: two What is the requirement for an internal sort? Enough disk space. A computer that is fast enough. A Quick Sort program Enough memory to hold all the data. - Correct Answers: Enough memory to hold all the data. What is the test for the end condition in the following recursive piece of code? public void quicksort( int left, int right ) { int i, last; if (left >= right ) return; swap( left, (left + right)/2 ); last = left; for ( i = left+1; i <= right; i++ ) if ( data[i] < data[left] ) swap( ++last, i ); swap( left, last ); quicksort( left, last-1 ); quicksort( last+1, right ); } // quicksort return; quicksort( left, last-1 ); if ( data[i] < data[left] ) if (left >= right ) - Correct Answers: if (left >= right ) Why is the Quick Sort considered one of the most efficient sorting algorithms? Its performance only degrades if the list is sorted. Its both quick and efficient It has an average performance of O(n^2) It has an average performance of O(n log n) - Correct Answers: It has an average performance of O(n log n) Given an unsorted array {28, 32, 4, 15, 12, 45, 25, 33, 22, 56, 47, 11, 6}, what is the correct subarray after 3 recursive calls to merge sort? {28, 32} {4, 12, 15} {28, 32, 4, 15} {12, 45, 25} - Correct Answers: {28, 32} What is the best case complexity of merge sort? O(n) Ω(n log n) θ(n log n) O(n2) - Correct Answers: Ω(n log n) The average case performance of selection sort is: O(n2) O(n log n) O(n) O(2n) - Correct Answers: O(n2) What is the advantage of selection sort? It required additional memory for operation. it requires no additional memory for operation. It is faster and requires fewer iterations. It is highly scalable. - Correct Answers: it requires no additional memory for operation. Consider a situation where the minimum number of swap operation is required. Which sorting algorithm is best for this use-case? Selection Sort Heap Sort Insertion Sort Merge Sort - Correct Answers: Selection Sort When it comes to an insertion sort, what does the following really mean? O(N2) The processing time for an algorithm is constant The processing time for an algorithm is linear The processing time for an algorithm is proportional to the square of the data set The processing time for an algorithm is proportional to system resources - Correct Answers: The processing time for an algorithm is proportional to the square of the data set Why does an insertion sort take additional system resources to process? The repeated loops through the array actually reduce processing time The Java compiler is limited in its ability Usually, insertion sorts are fast only when they have limited elements The repeated loops through the array increase processing time - Correct Answers: The repeated loops through the array increase processing time What is Bubble sort performance? O(nn) O(1) O(n2) O(n) - Correct Answers: O(n2) Which one of the following answers is possible output for this program? (suggestion: run the code in your local Java environment or at: ) - Correct Answers: In a Java merge sort, the unsorted array is recursively divided into subarrays until the subarray size is _____. two four one zero - Correct Answers: one What is the operation called that is performed by selection sort to move numbers from the unsorted section to the sorted section of an array? Sorting Selection Merging Swapping - Correct Answers: Swapping In the nested loop for the insertion sort, why do we decrement? This is an error; sorting should increment To get to the last element in the array The sort orders from end to beginning The sort needs to go past the last element - Correct Answers: The sort orders from end to beginning In Java, strings are _____, meaning they cannot be changed once they are created. immutable complex changeable simple - Correct Answers: immutable Explanation Immutable means that it cannot be changed. Any modifications or other methods operate on completely new instances of the original String object. Consider the following code. What is true of the String object after the last line of code? StringBuilder newString = new StringBuilder("Jane Eyre"); newSse(); The original object is changed to eryE enaJ It still exists in original form; a new object is created A new object with a value of eryE enaJ has been created It has been deleted completely and is now no longer available - Correct Answers: The original object is changed to eryE enaJ Read Answer Explanation Strings are immutable, except if you use StringBuilder, which lets you create mutable (changeable) String objects. Consider the following string: String a1 = "LeRoy"; Which of the following will correctly create a character array from this string? a1 = toCharArray(); char array = new CharArray(); char[] newa1 = CharArray(); toCharArray().a1 - Correct Answers: char[] newa1 = CharArray(); Read Answer Explanation This code takes each character from the String a1 and creates a new data structure (character array) Given the following Java code, what is the value of the String variable i10? String i9 = "Enter"; String i10 = i9; i9 = "Exit"; Sln(i10); Enter Undefined 0 Exit - Correct Answers: Enter Read Answer Explanation Even though i10 was set to equal i9, changing i9 does not impact the value of i10. Which of the following best describes the function of the Java code below? char[] r2 = {'r', '2', '-', 'd', '2'}; String r2d2 = new String(r2); Creating a StringBuilder object for the new character array Creating a character array that appends the String object Creating a new String object from the character array Replacing the String object with a character array - Correct Answers: Creating a new String object from the character array Read Answer Explanation The character array r2 is being used as the value for the new String object r2d2. The worst case time complexity of the Boyer-Moore Algorithm is: O(mn) O(m+n) O(mlogn) O(n^2) - Correct Answers: O(mn) The worst case time complexity of Boyer-Moore is O(mn) What is a bad character rule? The character that does not match with the pattern string is a bad character. When the mismatch is encountered the pattern is shifted until the next mismatch. When there is a match. The character that does not match with the pattern string is a bad character. When the mismatch is encountered the pattern is shifted until the mismatch is a match or until the pattern crosses the mismatched character The character that matches with the second occurrence in the pattern string is a bad character. When the mismatch is encountered the pattern is shifted until the mismatch is a match or until the pattern crosses the mismatched character - Correct Answers: The character that does not match with the pattern string is a bad character. When the mismatch is encountered the pattern is shifted until the mismatch is a match or until the pattern crosses the mismatched character The character that does not match with the pattern string is a bad character. When the mismatch is encountered the pattern is shifted until the mismatch is a match or until the pattern crosses the mismatched character. Which