QUESTION 1 Given the following heap, 90 82 55 71 22 35 0 1 2 3 4 5 6 Answer the QUESTIONS below in its related numerical answer box : a. If new item 80 will be inserted, in which index it will be stored? b. Next, remove an item from the heap. Which item will be removed? What is the new root? c. Next, what is the item in index 1? QUESTION 2 Given a weighted graph below, use Dijkstra's Algorithm to find the shortest path from the source node '1' to '5'. a. State the shortest path. b. State the total weight. c. Represent the graph using adjacency list. 4 4 T T T Arial 3 (12pt) QUESTION 3 Consider a hash table with size 11 using double hashing. The hash function is h1(k) = k mod 11, and the second hash function is h2(k) = 1+(k mod 9). For key 98, if the hash value from hy is already occupied, 98 will be probed to index 0 10 011 06 07 QUESTION 4 Consider a binary max-heap implemented using an array. Which one of the following represents a binary max-heap? 0 25,12,16,10,13,14,8 0 25,14,16,13,10,8,12 0 25,12,16,13,10,8,14 O 25,14,12,13,10,8,16 QUESTION 5 Click Save and Submit to save and submit. Click Save ALI Answers to save all answers. QUESTION 5 A graph is a collection of nodes called and line segments called that connect a pair of nodes. O edges, vertices o index, line o vertices, edges O vertices, path QUESTION 6 In a max-heap, the element with the greatest key is always in the which node? First node of right subtree Leaf node Root node First node of left subtree QUESTION 7 QUESTION 7 A priority queue can be implemented as a heap because O heap is not always sorted so any value can be the top priority heap is using array o the root can be easily identified as the topmost priority O heap always has a left bottom node that can be the top priority QUESTION 8 A chained hash table has an array size of 512. What is the maximum number of elements that can be placed in the table? O Exactly 512 elements There is no maximum Less than 512 elements About half of 512 elements QUESTION 9 QUESTION 9 For a given graph having v vertices and e edges. If all vertices must be spanned with minimum edges, which of the following is true? O V + 1 = e Ov=e-1 Ov=e Ov=e+1 QUESTION 10 Given the graph, which of the following is not a valid topological sort order? O F.BMZ,X,A,C,E,D O FB,A,Z,X,M,C,E,D O F,B,AM,Z,X,C,E,D O FBMAZX,C,E,D QUESTION 11 The spanning tree of a connected graph with 10 vertices contains O 10 edges O 9 edges O 11 edges 020 edges QUESTION 12 QUESTION 12 Which of the following would be the DFS traversal of the given Graph? B. E AEDCB ADEBC O EDCBA O ADECB QUESTION 13 What is the best definition of a collision in a hash table? Two entries with different data have the exact same key. O Two entries with different keys have the same exact hash value. Two entries with the exact same key have different hash values. Two entries are identical except for their keys. QUESTION 14 is one of the advantages of separate chaining over open addressing. O Hash function is easier Deletion is easier O Space used is less Searching has better efficiency QUESTION 15 In the insert operation of a heap tree, where is the new node initially inserted? O Next bottom leaf As a child to the root O At the root O Anywhere QUESTION 16 Which of the following is a disadvantage of using separate chaining using linked lists? O It requires bucket It requires array O It requires many pointers o It does not resolve collision QUESTION 17 A heap can be used as O decreasing order array O priority queue O binary search stack QUESTION 18 Graphs are represented using an adjacency queue. True False QUESTION 19 Hashing is the problem of finding an appropriate mapping of keys into addresses. O True O False QUESTION 20 In graph, the location of the parent node for any arbitrary node n is in (n-1/2) position. True False QUESTION 21 Faster access of data is the advantage of a hash table as a data structure. True O False QUESTION 22 In a binary min heap containing n numbers, the smallest element can be found in 0(1). True False QUESTION 23 Given the following hash table and hash function h(k) = k mod 13 0 13 2 30 20 10 11 12 139 10 11 25 Answer TWO QUESTIONS below in its related numerical answer box : a. If you have to use a linear probing hashing, what is the index location for 75? b. If you have to use a quadratic probing hashing, what is the index location for 75? QUESTION 24 Match the term with its related description. A. Separate chaining Minimum number of edges required to span all vertices and that minimizes B. Open addressing the cost C. Trickle down Shortest path between two vertices in the graph D. Topological sort Search sequentially for vacant cells, incrementing the index until an empty cell is found. E. Dijkstra's Algorithm A technique in hash table that will search for an empty cell in the array using F. Minimum Spanning Tree some systematic way when collision occurs. G. Linear probing The process of comparison and swapping a node down a tree until it's below a larger node and above a smaller one. H. Trickle up 1. Quadratic probing Click Save and Submit to save and submit. Click Save All Answers to save all answers
