Homework SourseQ1 public void operationZ throws StackUnderflowException if
| Q1. public void operationZ() throws StackUnderflowException { if(stackTop == null) throw new StackUnderflowException(); stackTop = stackTop.link; }//end operationZ What does it mean if stackTop equals NULL in the operation above? a. The stack is full b. The stack is empty c. The element does not exist d. The stack is nonempty but not full Q2. The bottom element of the stack is the last element added to the stack. a. true b. false Q3. What is the equivalent postfix expression for the infix expression: (x - y) * (v + w)? a. x v * y w - + b. - x y + v w * c. x * y + v * w - d. x y - v w + * Q4. The item added to the stack last will be the item removed last. a. true b. false Q5. StackClass s = new StackClass(50); int x, y, z; s.push(new IntElement(3)); s.push(new IntElement(7)); x = s.pop(); s.push(new IntElement(5)); y = s.pop(); z = s.pop(); Given the sequence of operations above, what is the value of x? a. 0 b. 3 c. 5 d. 7 Q6. StackClass s = new StackClass(50); int x, y, z; s.push(new IntElement(3)); s.push(new IntElement(7)); x = s.pop(); s.push(new IntElement(5)); y = s.pop(); z = s.pop(); Given the sequence of operations above, what is the value of y? a. 0 b. 3 c. 5 d. 7 Q7. In a linked list implementation of a stack, only a fixed number of elements can be pushed onto the stack. a. true b. false Q8. In a linked representation, memory for the stack elements is allocated dynamically. a. true b. false Q9. Add and delete are two basic operations of queues. a. true b. false Q10. FIFO is similar to the way customers in line at a bank are serviced. a. true b. false Q11. The method front returns the first element in the queue. a. true b. false Q12. A technique in which one system models the behavior of another system is called simulation. a. true b. false Q13. In a(n) ____ queue, customers or jobs with higher priority are pushed to the front of the queue. a. circular b. priority c. linked d. array-based Q14. Whenever an application is modeled on a FIFO structure, ____ are used. a. lists b. queues c. stacks d. arrays Q15. In a priority queue, customers or jobs with higher priority are pushed to the back of the queue. a. true b. false Q16. Queue can be derived from the class ____. a. LinkedListClass b. stack c. list d. array Q17. One of the disadvantages of chaining is that if the item size is small, a considerable amount of space is wasted. a. true b. false Q18. Hashing collision resolution techniques are classified into which of the following categories? a. open addressing only b. chaining only c. closed addressing only d. both open addressing and chaining Q19. One requirement of linear search is that the item must be in the array. a. true b. false Q20. On average, the number of comparisons made by a sequential search is equal to one-third the size of the list. a. true b. false Q21. In linear search, you search an array starting from the middle component. a. true b. false Q22. In sequential search, the array must be ordered. a. true b. false Q23. If we want to design a search algorithm that is of an order less than log2n, then it ____ be comparison based. a. must b. could c. cannot d. should Q24. In chaining, the average number of comparisons for an unsuccessful search is equal to the load factor. a. true b. false Q25. Both random and quadratic probing eliminate ____. a. primary clustering b. secondary clustering c. rehashing d. random probing Q26. Merge sort uses a pivot just like quick sort. a. true b. false Q27. The insertion sort algorithm sorts the list by moving each element to its proper place. a. true b. false Q28. The functions implementing sorting algorithms are included as private members of the related class. a. true b. false Q29. Merge sort can be implemented for only array based lists. a. true b. false Q30. Insertion sort tries to reduce the number of key comparisons relative to which of the following? a. heap sort b. merge sort c. selection sort d. quick sort Q31. The worst case for the number of comparisons in quick sort is O(n2). a. true b. false Q32. Suppose that L is a list of n elements, where n > 0. Let A(n) denote the number of key comparisons in the average case of merge sort. Which of the following is true? a. A(n) = O(n log2n) b. A(n) = O(n log n) c. A(n) = O(n2 log n) d. A(n) = O(n2 log2n) Q33. The selection sort algorithm sorts a list by selecting the smallest element in the (unsorted portion of the) list, and then moving this smallest element to the ____ of the (unsorted) list. a. pivot b. top c. middle d. bottom Q34. Quick sort overcomes the worst case scenario of heap sort. a. true b. false Q35. The iterative preorder tree traversal function is known as ____. a. nonrecursive preorder traversal b. recursive preorder traversal c. preorder traversal d. nonrecursive postorder traversal Q36. In a binary search tree, the key in the ____ node is larger than every key in the left subtree and smaller than every key in the right subtree. a. child b. root c. right d. head Q37. Any node in a binary tree can be called a leaf node. a. true b. false Q38. There is a unique path from the ____ to every node in the binary tree. a. branch b. root c. reference d. info Q39. Each node in a binary tree contains data and a link to the left child and a link to the right child. a. true b. false Q40. In an AVL tree: 1) the height of the left and right subtrees of the root differ by at most 2, and 2) the left and right subtrees of the root are AVL trees. a. true b. false Q41. There are ____ cases to consider when deleting a node from a binary search tree. a. two b. three c. four d. five Q42. In an preorder traversal, the binary tree is traversed as follows: 1) Traverse the left subtree, 2) Visit the node, and 3) Traverse the right subtree. a. true b. false Q43. The adjacency matrix AG is a two-dimensional n x n matrix such that the (i, j)the entry of AG is 1 if there is an edge from vi to vj; otherwise, the (i, j)the entry is zero. a. true b. false Q44. The ____-first traversal of a graph is similar to traversing a binary tree level by level. a. height b. depth c. breadth d. width Q45. In an undirected graph G = (V, E), the elements of E are ordered pairs. a. true b. false Q46. A tree T is called a ____ tree of graph G if T is a subgraph of G such that V(T ) = V(G), that is, all the vertices of G are in T. a. spanning b. binary c. binary search d. short Q47. The edges connecting two vertices can be assigned a nonnegative real number, called the ____ of the edge. a. height b. weight c. depth d. level Q48. A graph G has a spanning tree if and only if G is disconnected. a. true b. false Q49. The two most common graph traversal algorithms are the height first traversal and breadth first traversal. a. true b. false Q50. The depth first traversal is similar to the postorder traversal of a binary tree. a. true b. false |
| Q1. public void operationZ() throws StackUnderflowException { if(stackTop == null) throw new StackUnderflowException(); stackTop = stackTop.link; }//end operationZ What does it mean if stackTop equals NULL in the operation above? a. The stack is full b. The stack is empty c. The element does not exist d. The stack is nonempty but not full Q2. The bottom element of the stack is the last element added to the stack. a. true b. false Q3. What is the equivalent postfix expression for the infix expression: (x - y) * (v + w)? a. x v * y w - + b. - x y + v w * c. x * y + v * w - d. x y - v w + * Q4. The item added to the stack last will be the item removed last. a. true b. false Q5. StackClass s = new StackClass(50); int x, y, z; s.push(new IntElement(3)); s.push(new IntElement(7)); x = s.pop(); s.push(new IntElement(5)); y = s.pop(); z = s.pop(); Given the sequence of operations above, what is the value of x? a. 0 b. 3 c. 5 d. 7 Q6. StackClass s = new StackClass(50); int x, y, z; s.push(new IntElement(3)); s.push(new IntElement(7)); x = s.pop(); s.push(new IntElement(5)); y = s.pop(); z = s.pop(); Given the sequence of operations above, what is the value of y? a. 0 b. 3 c. 5 d. 7 Q7. In a linked list implementation of a stack, only a fixed number of elements can be pushed onto the stack. a. true b. false Q8. In a linked representation, memory for the stack elements is allocated dynamically. a. true b. false Q9. Add and delete are two basic operations of queues. a. true b. false Q10. FIFO is similar to the way customers in line at a bank are serviced. a. true b. false Q11. The method front returns the first element in the queue. a. true b. false Q12. A technique in which one system models the behavior of another system is called simulation. a. true b. false Q13. In a(n) ____ queue, customers or jobs with higher priority are pushed to the front of the queue. a. circular b. priority c. linked d. array-based Q14. Whenever an application is modeled on a FIFO structure, ____ are used. a. lists b. queues c. stacks d. arrays Q15. In a priority queue, customers or jobs with higher priority are pushed to the back of the queue. a. true b. false Q16. Queue can be derived from the class ____. a. LinkedListClass b. stack c. list d. array Q17. One of the disadvantages of chaining is that if the item size is small, a considerable amount of space is wasted. a. true b. false Q18. Hashing collision resolution techniques are classified into which of the following categories? a. open addressing only b. chaining only c. closed addressing only d. both open addressing and chaining Q19. One requirement of linear search is that the item must be in the array. a. true b. false Q20. On average, the number of comparisons made by a sequential search is equal to one-third the size of the list. a. true b. false Q21. In linear search, you search an array starting from the middle component. a. true b. false Q22. In sequential search, the array must be ordered. a. true b. false Q23. If we want to design a search algorithm that is of an order less than log2n, then it ____ be comparison based. a. must b. could c. cannot d. should Q24. In chaining, the average number of comparisons for an unsuccessful search is equal to the load factor. a. true b. false Q25. Both random and quadratic probing eliminate ____. a. primary clustering b. secondary clustering c. rehashing d. random probing Q26. Merge sort uses a pivot just like quick sort. a. true b. false Q27. The insertion sort algorithm sorts the list by moving each element to its proper place. a. true b. false Q28. The functions implementing sorting algorithms are included as private members of the related class. a. true b. false Q29. Merge sort can be implemented for only array based lists. a. true b. false Q30. Insertion sort tries to reduce the number of key comparisons relative to which of the following? a. heap sort b. merge sort c. selection sort d. quick sort Q31. The worst case for the number of comparisons in quick sort is O(n2). a. true b. false Q32. Suppose that L is a list of n elements, where n > 0. Let A(n) denote the number of key comparisons in the average case of merge sort. Which of the following is true? a. A(n) = O(n log2n) b. A(n) = O(n log n) c. A(n) = O(n2 log n) d. A(n) = O(n2 log2n) Q33. The selection sort algorithm sorts a list by selecting the smallest element in the (unsorted portion of the) list, and then moving this smallest element to the ____ of the (unsorted) list. a. pivot b. top c. middle d. bottom Q34. Quick sort overcomes the worst case scenario of heap sort. a. true b. false Q35. The iterative preorder tree traversal function is known as ____. a. nonrecursive preorder traversal b. recursive preorder traversal c. preorder traversal d. nonrecursive postorder traversal Q36. In a binary search tree, the key in the ____ node is larger than every key in the left subtree and smaller than every key in the right subtree. a. child b. root c. right d. head Q37. Any node in a binary tree can be called a leaf node. a. true b. false Q38. There is a unique path from the ____ to every node in the binary tree. a. branch b. root c. reference d. info Q39. Each node in a binary tree contains data and a link to the left child and a link to the right child. a. true b. false Q40. In an AVL tree: 1) the height of the left and right subtrees of the root differ by at most 2, and 2) the left and right subtrees of the root are AVL trees. a. true b. false Q41. There are ____ cases to consider when deleting a node from a binary search tree. a. two b. three c. four d. five Q42. In an preorder traversal, the binary tree is traversed as follows: 1) Traverse the left subtree, 2) Visit the node, and 3) Traverse the right subtree. a. true b. false Q43. The adjacency matrix AG is a two-dimensional n x n matrix such that the (i, j)the entry of AG is 1 if there is an edge from vi to vj; otherwise, the (i, j)the entry is zero. a. true b. false Q44. The ____-first traversal of a graph is similar to traversing a binary tree level by level. a. height b. depth c. breadth d. width Q45. In an undirected graph G = (V, E), the elements of E are ordered pairs. a. true b. false Q46. A tree T is called a ____ tree of graph G if T is a subgraph of G such that V(T ) = V(G), that is, all the vertices of G are in T. a. spanning b. binary c. binary search d. short Q47. The edges connecting two vertices can be assigned a nonnegative real number, called the ____ of the edge. a. height b. weight c. depth d. level Q48. A graph G has a spanning tree if and only if G is disconnected. a. true b. false Q49. The two most common graph traversal algorithms are the height first traversal and breadth first traversal. a. true b. false Q50. The depth first traversal is similar to the postorder traversal of a binary tree. a. true b. false |
Solution
Ans for Question 1
-> StackTop always point to the top element of the stack. So if it is null, then there is no element in the stack.The stack is empty (option b)
Ans for Question 2
-> No, Stack is a LIFO property (Last In First Out). So bottom element is the first element added to the stack ( Option b)
Ans for Question 3
-> The postfix expression will be x y - v w + * ( Option d)
Ans for Question 4
-> No, As for the FIFO property, The item added to the stack last will be the item removed first.So it is false ( Option b)
Ans for Question 5
-> After push 3 and 7, The stack will be [ 3 7 ] and the top points to 7. When it perform pop() then the top element will be popped( here 7 ). After this, the stack will be [ 3 ]. Now again is push 5. So the stack will be [ 3 7 ]. Then y=s.pop(); y=7; So value of y=7. (option d)
Ans for Question 6
-> When we push 3 and 7 in the stack named s, the stack looks like [ 3 7 ] and top points to 7. Now x=s.pop(). so x = 7 and stack look like [ 3 ]. Now again we insert 5. So, now it looks like [ 3 5 ] and top = 5. Now y=s.pop(). so it returns the top element that is 5. So y=5.(Option c)
Ans for Question 7
-> That depends on how to implement it. We can make it both fixed size and variable no. But in general, as link list is used, so it is variable size. So it is false( Option 7)
Ans for Question 8
-> True.memory allocation of the list is dynamical.
Ans for Question 9
-> No, There is no add delete operation, There is ENQUEUE and DEQUEUE operation. ENQUEUE for insert element in Queue and DEQUEUE for remove element.(Option b)
Ans for Question 10
-> Yes,FIFO mean first in first out. That\'s in mountain in bank ( Option a)
Ans for Question 11
-> Yes, Front returns the first inserted element of the Queue.(Option a)
