COMP 182 Midterm Exam №2 Quizzes

COMP 182-16324-FA2022 Quizzes Midterm Exam #2 Midterm Exam #2 Due Nov 19, 2022 at 11am Points 50 Questions 50 Available Nov 19, 2022 at 12am Nov 19. 2022 at 3pm 15 hours Time Limit 90 Minutes This quiz is no longer available as the course has been concluded Attempt History Attempt Time Score LATEST Attempt 1 81 minutes 47 out of 50 1 Correct answers are no longer available Score for this quiz: 47 out of 50 Submitted Nov 19, 2022 at 10:22am This attempt took 81 minutes. Question 1 1/ pts Identify the new priority queue after enqueueing 40. 29 36 42 54 . 29 36 40 42 54 29 36 42 54 40 40 29 36 42 54 e 29 36 42 40 54 Question 2 1/ pts Identify the type of the following binary tree. a G $ Not full, complete not perfect Full. complete perfect Full complete not perfect Full not complete not perfect

Question 3 1/ pts When is a new node inserted as the left child? . When the new node's key is less than the current node and the current node's left child is null When the new node's key is less than the current node and the current node's left child is not null When the new node's key is greater than the current node and the current node's left child is null O When the new node's key is greater than the current node and the current node's left child is not null Question 4 1/ pts Identify the type of the following binary tree. G R Full complete not perfect Full. not complete, not perfect Not full. complete not perfect Full complete perfect Question 5 1/ pts What type of node is "English" Students Tom Mark English Math Science English Practical jps Theory doc Internal node Root Parent Leaf

Question 6 1/ pts Turn the following array into a binary max-heap using the heapify operation. 21 36 85 54 60 13 90 90 60 85 36 54 13 21 90 60 54 36 21 13 90 60 54 36 13 21 90 60 85 54 36 13 21 Question 7 1/ pts What is the sequence of ordering for the nodes of the following BST? 250 200 300 190 210 290 310 190 - 210 - 290 - 310 . 200 300 . 250 250 200 300 190 210 290 - 310 190 - 200 210 250 . 290 . 300 +310 190 - 210 . 200 250 . 300 - 290 - 310

Question 8 1/1 pts Identify the correct statement. MD5 produces a 256-bit hash value for any input data A hash value can help identify corrupted data A hash value cannot help verifying data integrity All hash values can help reconstruct original data Question 9 1/ 1 pts What is the depth of the "Practical.jpg" node? Students Tom Mark English Math Science English Practical.jpg Theory.doc 4 2 1 3

Question 10 1/1 1 pts Identify the correct rotation to balance the red-black tree. 78 82 96 96 78 82 82 78 96 78 82 96 78 96 82

Question 11 1/1 pts Identify the new treap created after deleting node F. 40. D 50 B F 30 40 A C E G 20 25 35 32 D 50 B G 30 32 A C E 20 25 35 D 50 B E 30 35 A C G 20 25 32 D 50 B G 30 32 A C E 20 25 35 D 50 B E 30 35 A C G 20 25 32

Question 12 1/1 pts Identify the binary tree that satisfies the max-heap property. 54 78 96 78 54 96 96 54 78 78 96 54

Question 13 1/1 pts Identify the balanced tree after inserting node 7 in the given red- black tree. 6 5 8 1 6 5 8 1 7 9 6 5 8 1 7 9 7 5 8 1 6 9 6 5 8 1 7 9

Question 14 1/1 pts Identify the correct red-black tree. 75 71 78 68 72 30 99 75 71 78 68 72 30 99 75 71 78 68 72 30 99 75 71 78 68 72 30 99

Question 15 1/1 pts What is the parent of the "Theory.doc" node? Students Tom Mark English Math Science English Practical.jpg Theory.doc Mark Science Tom Students Question 16 1/1 1 pts Identify the order of nodes that would be printed during a BST inorder traversal. 6 4 8 3 5 7 9 3,4, 5. 6. 7,8,9 6.3, 4. 5. 7. 8.9 9.8.7. 6. 5. 4. 3 3.5. 7,9 4. 8,6

Question 17 1/1 pts Which of the following is a treap? 78 P M 5 54 H 45 22 38 P 78 M 54 46 H 22 R 54 M 83 46 45 H : T 38 78 P M 54 46 N H 45 28 Question 18 1/1 pts Identify the ancestor(s) of node P. A x Y a XYA XY XA X

Question 19 1/1 pts Which is an internal node? A x P X Question 20 1/1 pts Is this an AVL tree? Justify your answer. 9 6 7 No. as the tree is not a binary search tree (BST) No. as both the left and right subtrees have height 0 Yes as the tree is a binary search tree (BST) Yes as both the left and right subtrees have height 0 Question 21 1/1 pts A 5-bucket hash table has the items 45, 56, and 67. The hash table's items will be positive integers. Which of the following is the correct way of representing the hash table? 45. 56.67 1.-1 45.56.67.0 45.56 67. 0.0 -1.45 56. 67. 1

Question 22 1/1 pts In Java, if nodeIndex is the integer index of a node in a binary max-heap, then calculates the parent index. parentIndex 2 nodeIndex 2 parent Index = (nodeIndex - 1) / 2 parentIndex = nodeIndex - 1/2 parent Index = 2 * nodeIndex - 1 Question 23 1/1 pts Which of the following rules does a valid BST follow? Right subtree keys S node's keys Left subtree keys < node's keys Left subtree keys > node's keys Right subtree keys < left subtree keys Incorrect Question 24 0/1 pts Every object in Java has a hashCode() method that returns an integer that . is always > 0 is always >= 0 is always negative may be negative, positive, or 0

Question 25 1/1 pts A direct access table has the items 21, 32, 43, 54. What will be the output of HashSearch(table, 5) ? e null false 0 54

Question 26 1/1 1 pts What is the tree when node 4 is removed? 6 4 8 3 6 8 6 8 3 6 3 8 6 3 8

Question 27 1/1 pts Identify the action to be taken to remove node 82. 70 95 Node 82 can be directly removed Color the parent black and the sibling red Rotate right at the sibling Rotate left at the parent node Question 28 1/1 pts Identify the depth of node Q. A x Q 2 0 3 1 Question 29 1/ pts If a hash table has 20 buckets and 12 elements, what will the load factor be? 0.6 1.2 0.8 8

Question 30 1/1 pts During insertions, if the bucket is occupied, iterating over i values to determine next empty bucket is called . probing sequence arithmetic sequence hashing sequence geometric sequence Question 31 1/ 1 pts Identify the error in the red-black tree. 75 71 78 68 99 A null child is considered to be a red leaf node The root node is black Every node is colored either red or black A red node's children cannot be red Question 32 1/ 1 pts A hash function uses an item's to compute the item's bucket index. bucket location key function

Incorrect Question 33 0/1 pts Which of the following is a valid reason for resizing a hash table? More than 5 items in a hash table Load factor is greater than 0.5 Adding more than 1 item in a bucket Load factor is less than 0.1 Question 34 1/1 pts Which array stores the following heap? 9 6 7 5 4 3 1 4569731 1345679 9654731 9675431 Question 35 1/1 1 pts Identify the number returned by the peek operation on the following priority queue. 1345679 9 5 7 1

Question 36 1/ 1 pts Which is the correct Java implementation for a binary search tree's Node class? class Node { public int key; public Node left; public Node right; public Node(int nodekey) { key nodeKey; next null; prev null; } } class Node { public int key; public Node next; public Node(int nodeKey) { key nodeKey; next null; } } class Node { public Node key public Node left; public Node right; public Node(int nodeKey) { key null: left null; right null; ) ) class Node { public int key; public Node left; public Node right; public Node(int nodeKey) { key nodekey; left null; right null; ) } O )

Incorrect Question 37 0/1 pts Identify the correct rotation to rebalance the given tree after the new node is inserted. New Node 5 9 4 7 8 7 5 8 4 9 5 4 8 7 9 5 4 7 8 9 8 5 9 4 7

Question 38 1 /1 pts What is the height of a BST built by inserting nodes in the order 20, 10, 30? 1 2 3 Question 39 1 /1 pts Identify the number returned by the dequeue operation on the following priority queue. 21 36 45 54 60 73 90 54 36 21 90

Question 40 1/1 pts Identify the rebalanced AVL tree after removing 60. 50 40 80 30 45 60 20 45 30 50 20 40 80 50 40 80 30 45 20 45 40 50 30 80 20 40 30 50 20 45 80

Question 41 1/1 pts Which XXX completes the Java AVL tree Node class's getBalance() method? int getBalance() ( int leftHeight = -1; if (left != null) { leftHeight = left. .height; } int rightHeight = -1; if (right != null) { rightHeight = right.height; } return XXX; } Math.min (leftHeight, rightHeight) leftHeight + rightHeight leftHeight - rightHeight Math.max(leftHeight, rightHeight) Question 42 1/: 1 pts What operation is used to compute a bucket index in the range 0 to 16 from a key? key 17 key % 17 key 17 key / 17

Question 43 1/1 pts What is the second node that is visited when searching for 7? 10 15 7 12 18 2 4 5 7 10 15 Question 44 1/ 1 pts Consider a hash table named marksTable that uses linear probing and a hash function of key % 5. What would be the location of the item 46? HashInsert (marksTable, item 49) HashInsert (marksTable, item 41) HashInsert (marksTable item 42) HashInsert (marksTable, item 44) HashInsert (marksTable item 46) Bucket 3 Bucket 1 Bucket 0 Bucket 2 Question 45 1/1 pts A perfect hash function maps items to buckets with no collisions uses chaining to resolve collisions uses open addressing to resolve collisions has O(N) time complexity for inserting into a hash table

Question 46 1/1 pts Which of the following is a valid binary search tree? 9 7 8 3 4 5 6 9 7 4 8 5 3 2 6 4 8 3 5 7 9 9 6 7 5 4 3 2

Question 47 1/1 pts Where will a new node 5 be inserted? 6 4 8 3 5 7 9 As 7's left child As 4's left child As 6's left child As 5's right child Question 48 1/: 1 pts A hash table named numTable uses a hash function of key % 10 and quadratic probing with c1=1 and c2=2. Into which bucket is item 44 inserted? HashInsert(numTable, item 1) HashInsert (numTable, item 12) HashInsert (numTable, item 23) HashInsert (numTable, item 34) HashInsert (numTable, item 44) 7 6 8 5

Question 49 1/1 pts Which is not a valid AVL tree due to being unbalanced? 6 3 8 4 5 7 9 6 4 8 3 5 7 2 6 3 8 4 5 7 9 10 6 4 9 3 7 2 8

Question 50 1/1 pts Which collision resolution technique places the item in another empty bucket? Chaining Closed addressing e Open addressing Open hashing Quiz Score: 47 out of 50