Data Structures and Algorithms Test 2 Exam Questions with Answers

Data Structures and Algorithms Test 2 Exam Questions with Answers stack - Correct Answers: a data structure that only allows items to be inserted and removed at one end top - Correct Answers: the end of the stack where items are removed or inserted bottom - Correct Answers: end of stack where things are not removed or inserted Is access to other items in the stack allowed? - Correct Answers: no Stacks are last in first out (LIFO) - Correct Answers: true which of the following is NOT an operation that can be performed on a stack? - Correct Answers: Insert when working on a stack, peek removes the value from the top of the stack - Correct Answers: false Stacks is a last-in, first-out data structure - Correct Answers: true stacks are used by compliers to implement recursion - Correct Answers: true stacks can be implemented only using arrays - Correct Answers: false which of the following would result in an error? - Correct Answers: popping an empty stack when implementing a stack as a linked-list, you must make sure the stack isn't full before inserting an item - Correct Answers: false which of the following would NOT be a good use of stack - Correct Answers: keyboard buffer which of the following is true of implementing a stack as a linked-list - Correct Answers: the next reference for the bottom of the stack is null which of the following is true of an array based stack implementation? - Correct Answers: Requires an isFull method to check if the array is full a reference-based stack makes more efficient use of memory - Correct Answers: true queues are first-in, first-out data structures - Correct Answers: true if 5 items are added to a queue, the first item removed from the queue is the first item added to it - Correct Answers: true operations on a queue can be carried out at ___ - Correct Answers: both it's front and back a reference based implementation of a queue that uses a linear singly linked list would need at least ___ external references - Correct Answers: two which of the following is the code to insert a new node, referenced by newNode, into an empty queue represented by a circularly linked lise - Correct Answers: newNNext(newNode); lastNode=newNode; which of the following code fragments is used to delete the item at the front of the queue represented by a circular array? - Correct Answers: front = front(+1) %MAX_QUEUE; --count; which of the following operations inserts the element at the end of the queue? - Correct Answers: enqueue which of the following is not an ADT queue operation? - Correct Answers: push when implementing a queue using a reference-based approach, the operation dequeueAll is not needed. - Correct Answers: false when implementing a queue using an array-based approach, it is not necessary to determine if the queue is full before adding a new item to the queue - Correct Answers: false a queue can be used as a keyboard buffer - Correct Answers: true which of the following is not a means of implementing a queue? - Correct Answers: All of the following: linearly linked list, linear array, circularly linked list, circular array how many external referenced are necessary when implementing a queue using a circularly linked list? - Correct Answers: 1 when implementing a queue, a naive approach is more efficient in terms of memory when compared to a circular array approach - Correct Answers: false what should algorithm analysis be independent of? - Correct Answers: data, specific implementation, computers a comparison of algorithms should focus on significant differences, not reductions in computing costs based on clever coding tricks - Correct Answers: true when assessing the efficiency of a factorial program, which of the following operations would you focus on? - Correct Answers: multiplication which of the following operations would you focus on in order to assess the efficiency of a sorting algorithm? - Correct Answers: comparisons which of the following growth functions would represent the most inefficient algorithm for solving the problem? - Correct Answers: 2^n given the fact that a sort of n items requires n^2/2 +5 *n/2 - 3 major operations, the sort is - Correct Answers: O(n^2) the values of the growth-rate function O(log2n) grow faster than the values of the growth-rate function O(n). - Correct Answers: false low-order terms can be ignored in an algorithm's growth-rate function - Correct Answers: true the efficiency of the selection sort depends on the initial arrangement of the data - Correct Answers: false According the following statements: -Algorithm A requires time propoertional to n^2 -Algorithm B requires time propertional to nlog2n Algorithm A's time requirements increase at a slower rate than algorithm B's time requirement - Correct Answers: false the binary search algorithm is a quadratic algorithm - Correct Answers: false a bubble sort requires at most how many passes to sort an array of n items? - Correct Answers: n-1 the quicksort is _____ in the worst case. - Correct Answers: O(n^2) in the worst case, the insertion sort's comparison occurs how many times/ - Correct Answers: n*(n-1)/2 suppose that a selection sort of n items requires n^2/2+5*n/2-3 basic operations -- the selection sort is - Correct Answers: n^2 a merge sort is used to sort an array of 1000 values in ascending order. which of the following statements is true? - Correct Answers: The sort is the same, no matter what the order of the original elements suppose that the following list: 760 was input to the radix sort algorithm. What would the arrangement of the list after the second pass of the algorithm? - Correct Answers: 94 consider the following java array definition: int[] array = {22,18,23,16,19,26,15,13}; suppose this list was to be sorted with recursive mergeSort mehtod. How many times would the mergeSort method be invoked to successfully sort the given array? - Correct Answers: 15 int[] array = {22,13,23,15,19,16,26,18}; bubble sort algorithm how many comparisons would be made in order to arrange the data into ascending order if we use the basic version bubble sort algorith? - Correct Answers: 28 int[] array = {22,18,23,16,19,26,15,13}; sorted using selection sort. what would be the arrangement after the fourth pass through the array? - Correct Answers: 26 23 22 an algorithm's execution time is related to the number of ____ it requires - Correct Answers: operations the value of which of the following frowth-rate functions grows the fastest - Correct Answers: O(n^2) in the best case, a sequential search is ___ - Correct Answers: O(1) in the worst case, a binary search is_____ - Correct Answers: O(log2n) given the following array: 4 15 8 3 28 21 for an ascending sort, which of the following represents the array after the second pass of the selection sort? - Correct Answers: 3 4 8 15 28 21 the peek operation of the ADT stack changes the stack - Correct Answers: false in a reference-based implementation of a stack, it is necessary to call the isFull() method before invoking the push method - Correct Answers: false when the infix expressions are converted to postfix expressions, the operators always stay in the same order with respect to one another - Correct Answers: false the________ method of the ADT stack adds an item to the top of the stack - Correct Answers: push the _____ method of the ADT stack removes the element at the top of the stack - Correct Answers: pop which of the following methods of the ADT stack accepts a parameter? - Correct Answers: push SatckInterface provides the specifications for - Correct Answers: all the implementations of a stack What is the value of the prefix expression: -*38+65 - Correct Answers: 13` operations on a queue can be carried out at ________ - Correct Answers: both its front and back method to retrieve from the stack the item that was added most recently, but does not remove - Correct Answers: peek a stack is an instance - Correct Answers: true applications of stack - Correct Answers: checking balanced expressions, recognizing palindromes, evaluation algebraic expressions def of infix expressions - Correct Answers: operator appears between operands def of prefix expressions - Correct Answers: operator appears before its operands def of postfix expressions - Correct Answers: operator appears after its operands prefix and postfix expressions don't need order of operations - Correct Answers: true infix to postfix: operands always stay in the same order - Correct Answers: true items from the front of the queue use an operation called ____ - Correct Answers: dequeue before dequeue, always determine if the queue is empty - Correct Answers: true deleting an item from a one-element referenced based queue is a special case: code is: - Correct Answers: lastNode-null; to initialize or construct the queue, set: front to ____ back to _____ count to ______ - Correct Answers: 0 MAX_QUEUE-1 0 to sort a list of data items, the basic operation is - Correct Answers: comparison worst case, avg case, and best case for sequential search - Correct Answers: worst case: O(n) average case: O(n) best case: O(1) worst case of binary search - Correct Answers: O(log2n) another name for selection sort - Correct Answers: brute-force algorithm each node in a binary tree has - Correct Answers: at most two childer in _______, the left and right subtrees of any node has heights that differ by at most 1 - Correct Answers: balanced binary tree A _______________ of height h is full down to the level h-1, with level h filled in from left to right - Correct Answers: complete binary tree A full binary tree with height 4 has _____ nodes - Correct Answers: 15 A subtree of node n is a subtree rooted at___ - Correct Answers: a child of node n each node in a general tree has - Correct Answers: at most one parent in a _____ of height h, all nodes that are at a level less than h have two children each - Correct Answers: full binary tree which of the following is not a property of a complete binary tree of height h - Correct Answers: all leaves are at level h in a tree, the children of the same parent are called - Correct Answers: siblings a n ode on the path from the root to (but not including) node n is a ______ of node n - Correct Answers: ancestor in an array based representation of a complete binary tree (presuming subscripting beginning at 0), which of the following represents the right child of noe tree[i]? - Correct Answers: tree[2*i+2] the minimum height of a binary tree of n nodes is - Correct Answers: log2(n+1) in an array based representaiton of a complete binary tree (presuming subscripting beginning at 0), which of the following represents the parent of node tree[i]? - Correct Answers: tree[(i-1)] the maximum height of a binary tree of n nodes is - Correct Answers: n/2 the maximum number of comparisons for a retrieval operation in a binary search tree is the - Correct Answers: height of the tree A heap in which the root contains the item with the largest search key is called a - Correct Answers: maxheap a heap is a - Correct Answers: complete binary tree in an array-based implementation of a heap, the heapDelete operation is ______ - Correct Answers: O(logn) In an array-based implementation of a heap, the parent of the node in items [i] is always stored in - Correct Answers: item[(i-1)/2]` the heapsort is ______ in the worst case - Correct Answers: O(n*logn) which of the following is true about the heapsort - Correct Answers: the heapsort does not require a second array in an array-based implementation of a heap, the heapInsert operation is - Correct Answers: O(logn) In a maxheap, the root contains a search key greater than or equal to the search key in each of its children - Correct Answers: true the mergesort is more efficient than the heapsort in the worst case - Correct Answers: false A heap in which the root contains the item with the largest search key is called a _____ - Correct Answers: maxheap A heap is a - Correct Answers: complete binary tree in an array-based implementation of a heap, the heapDelete operation is - Correct Answers: O(logn) In an array-based implementation of a heap, the parent of the node in items[i] is always stored in - Correct Answers: items[(i-1)/2] the heapsort is _____ in the worst case - Correct Answers: O(n*logn) which of the following is true about the heapsort - Correct Answers: the heapsort does not require a second array in an array-based implementation of a heap, the heapInsert operation is _____ - Correct Answers: O(logn) In a maxheap, the root contains a search key greater than or equal to the search key in each of its children - Correct Answers: true the mergesort is more efficient than the heapsort in the worst case - Correct Answers: false A reference variable contains the location of an object in memory. - Correct Answers: true Syntax errors of a program are removed during the coding phase of the software life cycle. - Correct Answers: true A recursive solution can have more than one base case. - Correct Answers: true A client application can use the operations of an ADT without knowing how the ADT is implemented. - Correct Answers: true A reference-based implementation of the ADT list does not shift items during insertion or deletion. - Correct Answers: true By default, equality operators (== and !=) used with objects will compare the values associated with those objects. - Correct Answers: false When a linked list is empty, the value of the head reference is null. - Correct Answers: true The binary search algorithm can be applied to an unsorted array. - Correct Answers: false The use of a dummy head node eliminates the special case for insertion and deletion. - Correct Answers: true Each node in a linear linked list references both its predecessor and its successor. - Correct Answers: false Suppose c1 and c2 are objects of the class Circle. A Circle has a single data member, its radius. The Circle class has a default constructor (implemented correctly), but no other methods have been defined in the implementation of the Circle class. What will happen when we try to execute this code? Circle c1 = new Circle(12.0); Circle c2 = new Circle(12.0); boolean same = (s(c2)); - Correct Answers: The value of same will be false. In linked list each node contain minimum of two data fields. One field is data field to store the data, second field is? - Correct Answers: reference to node ______ can be used to enforce the walls of an ADT. - Correct Answers: encapsulation In a recursive method that checks if a given string is palindrome, the base case(s) should be ______. - Correct Answers: a string with length of zero and one Which of the following is an example of a syntax error? - Correct Answers: the beginning of a while loop is written as "whille" instead of "while". Which of the following statement(s) is used to insert a new node, referenced by newNode, at the end of a linear linked list? - Correct Answers: newN = curr; = newNode; In a linear linked list: - Correct Answers: the next reference of the last node has the value null. Data structures are part of an ADT's - Correct Answers: implementation Which of the following operation of the ADT list changes the list? - Correct Answers: remove Which of the following statements deletes (i.e. marks as garbage) the first node of a linear linked list? - Correct Answers: head = ; Suppose that we have an ordered array of 980 entries. How many elements would need to be moved/shifted if it was determined that an element was to be inserted at position 401? - Correct Answers: 580 A variant of linked list in which last node of the list points to the first node of the list is? - Correct Answers: Circularly linked list Which of the following will be true when the reference variable curr references the last node in a linear linked list? - Correct Answers: == null Comparing recursion with iteration, which of the following is TRUE: - Correct Answers: Recursion reduces the size of the code. In the ADT list, when an item is inserted into position i of the list, ______ - Correct Answers: the position of each item that was at a position greater than i is increased by 1 For a given anArray = <2, 3, 5, 6, 9, 13, 16, 19>, if you are asked to search a target value 6 using a recursive binary search algorithm, what should be returned? - Correct Answers: 3 Which of the following is a base case for a recursive binary search algorithm? (first is the index of the first item in the array, last is the index of the last item in the array, and mid is the midpoint of the array). - Correct Answers: first > last When you solve a problem by solving two or more smaller problems, each of the smaller problems must be ______ the base case than the original problem. - Correct Answers: closer to An array-based implementation of an ADT list: - Correct Answers: requires less memory to store a data element than a reference-based implementation. Which of the following statements deletes the node that curr references? If prev references the node before curr. - Correct Answers: = ; A recursive solution that finds the factorial of n always reduces the problem size by ______ at each recursive call. - Correct Answers: 1 In ______ recursion, there can be multiple activations of the same method existing at the same time. - Correct Answers: Indirect A recursive solution that finds the factorial of n (i.e. n!) generates how many recursive calls? The base case is fact(0) = 1. - Correct Answers: n What is the effect of the following recursive Java method, assuming that X and Y are positive integers? public static int Mystery (int X, int Y) { if (X == 0) return Y; else return 1 + Mystery(X - 1, Y); } - Correct Answers: It computes and returns X + Y. Consider the following Java program. What is output by the program? public static void main( void ) { int a, b, result; a = 3; b = 4; result = value( a, b ); Sf("%dn",result); } public static int value( int x, int n ) { if ( n > 0 ) return x * value( x, n - 1 ); else return 1; } - Correct Answers: 81 Consider the following Java program. How many times is the method value called? public static void main( void ) { int a, b, result; a = 3; b = 4; result = value( a, b ); Sln(result); } public static int value( int x, int n ) { if ( n > 0 ) return x * value( x, n - 1 ); else return 1; } - Correct Answers: 5 Given this code snippet for a referenced-based ordered linked list, which of the following best describes its purpose? private Node Mystery(int index) { Node curr = head; for (int skip = 1; skip < index; skip++) { curr = ; } // end for return curr; } // end find - Correct Answers: Locates a specified node in a linked list given index What best describes the purpose of this code snippet: for (Node curr = head; curr != null; curr = ) { // code goes in here } - Correct Answers: Traversing a linked list each pass of merges sort requires ____ comparisons - Correct Answers: n For mergesort, there are on the order of ____ comparisons for each of the ______ levels of recursion - Correct Answers: n; log2n for n-element list, how many calls to Merge Sort are there? - Correct Answers: 2n-1 worst case of quick sort and when it occurs - Correct Answers: O(n^2), when array is already sorted best case of quick sort - Correct Answers: O(nlog2n) average case quick sort - Correct Answers: O(nlog2n) quick sort is usually extremely fast in practice - Correct Answers: true radix sort is comparison base - Correct Answers: false selection sort worst case - Correct Answers: n^2 selection sort best case - Correct Answers: n^2 selection sort avg case - Correct Answers: n^2 bubble sort worst case - Correct Answers: n^2 bubble sort best case - Correct Answers: O(n) bubble sort avg case - Correct Answers: O(n^2) Insertion sort worst case - Correct Answers: n^2 insertion sort best case - Correct Answers: O(n) insertion sort avg case - Correct Answers: O(n^2) Mergesort worst case - Correct Answers: n*logn Mergesort avg case - Correct Answers: n*logn quicksort worst case - Correct Answers: n^2 wuicksort avg case - Correct Answers: n*logn radix sort worst scase - Correct Answers: n radix sort avg case - Correct Answers: n heapsort worst case - Correct Answers: n*logn heapsort avg case - Correct Answers: n*logn a set of one or more nodes, partitioned into a root node and subsets that are general subtrees of the root - Correct Answers: general tree the node directly above node n in the tree - Correct Answers: parent of node n a node descending directly below node n in the tree - Correct Answers: child of node n the only node in the tree with no parent - Correct Answers: root a node with no children - Correct Answers: leaf nodes with a single common parent (i.e. direct ancestor) - Correct Answers: siblings a node somewhere along the path from the root to that node n - Correct Answers: ancestor of node n a node on a path from n to a leaf - Correct Answers: descendant of node a tree that consists of a child (if any) of n and all the child's descendants - Correct Answers: subtree of node n the number of nodes on the longest path from the root to a leaf - Correct Answers: height a set of nodes that is either empty or partitioned into a root node and one or two subsets that are binary subtrees of the root; each node has at most two children, the left child and the right child - Correct Answers: binary tree a node directly below and to the left (or right) of node n in a binary tree - Correct Answers: left (or right) child of node n in a binary tree, the left (or right) child (if any) of node n plus its descendants - Correct Answers: left (or right) subtree of node n a binary tree where the value in any node n is greater than the value in every node in n's left subtree, but less than the value of every node in n's right subtree - Correct Answers: Binary search (ordered) tree - BST a binary tree with no nodes - Correct Answers: Empty binary tree a binary tree of height h with no missing nodes; all leaves are at level h and all other nodes each have two children - Correct Answers: Full binary tree a binary tree of height h that is full to level h - 1 and has level h filled in from left to right - Correct Answers: Complete binary tree a binary tree in which the left and right subtrees of any node have heights that differ by at most 1 - Correct Answers: Balanced binary tree preorder traversal - Correct Answers: NLR Inorder traversal - Correct Answers: LNR Postorder traversal - Correct Answers: LRN element x[i]'s children - Correct Answers: x[2i+1], x[21+2] element x[i]'s parent - Correct Answers: x[i/2] if i odd, x[i/2-1] if i even A full binary tree of height h>= 0 has ____ nodes - Correct Answers: 2^h-1 the max number of nodes that a binary tree of height h can have is_____ - Correct Answers: 2^h-1 the minimum height of a binary tree with n nodes is _____ - Correct Answers: [log2(n+1)] retrieval avg and worst case - Correct Answers: O(log n), O(n) insertion avg, best, worst case - Correct Answers: O(n^2), O(n), O(n^2) deletion avg and worst case - Correct Answers: O(logn), O(n) Traversal avg and worst case - Correct Answers: O(n), O(n) advantage of heapsort over mergesort - Correct Answers: heapsort does not require a second array heapsort compared to quicksort - Correct Answers: quicksort is the preferred sorting method Consider the array int[]array = [12, 19, 14, 63, 28, 43, 21, 17, 11, 22] how many comparisons would be required to locate the value 17 if the sequential search algorithm was used - Correct Answers: 8 in[] array = [22, 18, 23, 16, 19, 26, 15, 13] suppose this list was to be sorted by selection sort. What would be the list after the fourth pass through the array? - Correct Answers: [ 26 23 22] the _____ compares adjacent items and exchanges them if they are out of order - Correct Answers: bubble sort the enqueue operation throw QueueException whenit tries to - Correct Answers: add an item to an array-based implementation of a queue that is already full what is NOT an ADT operation - Correct Answers: push If a stack is used by an algorithm to check for balanced braces, which of the following it true once the end of the string is reached? - Correct Answers: the stack is empty which of the following methods of StackInterface does NOT throw StackException - Correct Answers: popAll the mergesort is a recursive sorting algorithm - Correct Answers: true which of the following would bot be a good use of a stack - Correct Answers: keyboard buffer when infix expressions are converted to postfix expressions, the operands always stay in the same order with respect to one another - Correct Answers: true -Algorithm A requires time proportional to n^2 -Algorithm B requires time proportional to nlog2n A's time requirement increases at a slower rate than B's - Correct Answers: false When implementing a queue using reference-based, the operation isFull() is not needed - Correct Answers: true Stacks are used by compilers to implement recursion - Correct Answers: true when working with a stack, peek removes the value from the top of the stack - Correct Answers: false