Back to Subject

Unit 5: Heaps and Hashing - Practice Quiz

CSE205 — Data Structures And Algorithms 50 Questions
0 Correct 0 Wrong 50 Left
0/50

1 In a Max-Heap, what is the relationship between the value of a node and its children?

A. The node is greater than or equal to its children
B. There is no specific relationship
C. The node is less than or equal to its children
D. The node is equal to its children

2 Which data structure is commonly used to implement a Heap efficiently?

A. Array
B. Queue
C. Linked List
D. Stack

3 If a node is stored at index 'i' in an array representation of a binary heap (0-indexed), what is the index of its left child?

A. 2i + 1
B. 2i + 2
C. 2i
D. i / 2

4 What is the time complexity to insert a new element into a binary heap of size N?

A. O(N)
B. O(log N)
C. O(1)
D. O(N log N)

5 What is the time complexity to find the maximum element in a Max-Heap?

A. O(N log N)
B. O(1)
C. O(N)
D. O(log N)

6 Which operation is required to restore the heap property after extracting the root element?

A. Bubble Up
B. Linear Search
C. Heapify (Percolate Down)
D. Sorting

7 A binary heap is strictly a __.

A. AVL Tree
B. Binary Search Tree
C. Full Binary Tree
D. Complete Binary Tree

8 What is the parent index of a node at index 'i' in a 0-indexed array heap?

A. (i + 1) / 2
B. (i - 1) / 2
C. i / 2
D. 2i

9 What is the worst-case time complexity of HeapSort?

A. O(N^2)
B. O(log N)
C. O(N log N)
D. O(N)

10 HeapSort is generally considered stable. True or False?

A. True
B. Depends on implementation
C. Only for Min-Heap
D. False

11 Which of the following scenarios is the best use case for a Heap?

A. Implementing a Priority Queue
B. Finding the median in O(1)
C. Searching for an arbitrary element
D. Storing sorted data sequentially

12 What is the time complexity to build a heap from an unsorted array of N elements?

A. O(log N)
B. O(N log N)
C. O(N)
D. O(N^2)

13 In HeapSort, where is the sorted array constructed?

A. In-place within the same array
B. In a new array
C. In a linked list
D. In a binary search tree

14 What is the height of a binary heap with N nodes?

A. O(log N)
B. O(N^2)
C. O(N)
D. O(1)

15 Which hashing technique allows multiple keys to be stored in the same slot using a data structure like a linked list?

A. Open Addressing
B. Double Hashing
C. Separate Chaining
D. Linear Probing

16 What is a 'Collision' in hashing?

A. When a key cannot be hashed
B. When the hash table is full
C. When two different keys hash to the same index
D. When the load factor exceeds 1

17 In the context of hash tables, what is the Load Factor (alpha)?

A. Number of elements / Number of buckets
B. Number of buckets / Number of elements
C. Time taken to hash
D. Size of the key

18 Which simple hash function is defined as h(k) = k mod m?

A. Mid-Square Method
B. Multiplication Method
C. Folding Method
D. Division Method

19 In Open Addressing, where are colliding elements stored?

A. In a secondary hash table
B. In a separate linked list
C. In the same hash table at a different slot
D. They are discarded

20 What is the probe sequence for Linear Probing?

A. (h(k) + i * h2(k)) % m
B. h(k) % m
C. (h(k) + i) % m
D. (h(k) + i^2) % m

21 What is the main disadvantage of Linear Probing?

A. Complex implementation
B. Primary Clustering
C. Requires extra memory
D. Secondary Clustering

22 Quadratic Probing reduces primary clustering but suffers from which issue?

A. Infinite loops
B. Secondary Clustering
C. Stack overflow
D. Primary Clustering

23 Which collision resolution technique uses a second hash function?

A. Linear Probing
B. Separate Chaining
C. Double Hashing
D. Quadratic Probing

24 In Double Hashing, what property must the second hash function h2(k) have?

A. It should never evaluate to 0
B. It must result in 0
C. It must return a string
D. It must be equal to h1(k)

25 Which hashing method allows the load factor to exceed 1?

A. Open Addressing
B. Quadratic Probing
C. Separate Chaining
D. Linear Probing

26 What is the worst-case search time in a Hash Table using Separate Chaining?

A. O(N)
B. O(1)
C. O(log N)
D. O(N^2)

27 What is the average-case search time for a well-implemented hash table?

A. O(1)
B. O(log N)
C. O(N)
D. O(N log N)

28 What technique is used to handle deletions in Open Addressing tables?

A. Lazy deletion (Tombstones)
B. Physical deletion
C. Rehashing immediately
D. Shifting elements

29 When choosing a table size 'm' for the Division Method (h(k) = k % m), 'm' should preferably be:

A. A prime number
B. A multiple of 10
C. An even number
D. A power of 2

30 In the Mid-Square method of hashing, which part of the squared key is usually taken as the hash?

A. The first digits
B. The sum of all digits
C. The middle digits
D. The last digits

31 What happens when the load factor of a hash table becomes too high?

A. The table automatically deletes elements
B. Collisions increase and performance degrades
C. Nothing changes
D. Performance improves

32 The process of increasing the size of a hash table and re-inserting all existing elements is called:

A. Rehashing
B. Refactoring
C. Resizing
D. Restructuring

33 Which probing method uses the formula H(k, i) = (h(k) + c1i + c2i^2) % m?

A. Double Hashing
B. Linear Probing
C. Quadratic Probing
D. Random Probing

34 What is 'Perfect Hashing'?

A. A technique for dynamic datasets
B. A hashing technique with O(N) access
C. A technique with no collisions
D. A technique that uses minimal memory

35 If we have a Max-Heap array: [100, 80, 90, 40, 50, 70], what is the left child of 80?

A. 90
B. 70
C. 40
D. 50

36 In a Min-Heap, the root node always contains:

A. A random value
B. The minimum value
C. The maximum value
D. The median value

37 Which of the following is NOT a requirement for a good hash function?

A. It should distribute keys uniformly
B. It should be easy to compute
C. It should minimize collisions
D. It must be cryptographically secure

38 In Open Hashing (Separate Chaining), if the table size is 10 and we insert 20 elements, the load factor is:

A. 0.5
B. 20
C. 2.0
D. 10

39 What is the relationship between Open Hashing and Closed Addressing?

A. They are synonyms
B. They are unrelated
C. Open Hashing is Open Addressing; Closed Addressing is Separate Chaining
D. Open Hashing is Separate Chaining; Closed Addressing is Open Addressing

40 In Linear Probing, search for a key stops when:

A. We encounter an empty slot
B. All of the above
C. We find the key
D. We have searched the entire table

41 Which operation is typically faster in a Hash Table compared to a Binary Search Tree (BST)?

A. Finding the maximum element
B. Exact match search
C. In-order traversal
D. Finding the minimum element

42 When performing HeapSort on an array in ascending order, which type of heap is typically used?

A. Min-Heap
B. Binomial Heap
C. Max-Heap
D. Fibonacci Heap

43 In the folding method of hashing, the key is:

A. Partitioned into parts and added together
B. Multiplied by a constant
C. Squared
D. Divided by a prime

44 What is the primary benefit of Double Hashing over Quadratic Probing?

A. No secondary clustering
B. Guaranteed to find an empty slot in 1 step
C. Requires less memory
D. Simpler implementation

45 If a hash table using Open Addressing is full, what is the time complexity to insert a new item?

A. O(1)
B. O(N)
C. O(log N)
D. Infinite loop (until resized or error)

46 For string keys, a common hashing approach involves:

A. Multiplying the length by the first character
B. Taking the first character only
C. Adding ASCII values
D. Using a polynomial rolling hash

47 Which heap operation decreases the value of a key and restores the heap property?

A. Decrease-Key
B. Increase-Key
C. Extract-Min
D. Delete

48 In a hash table with size m = 10 and hash function h(k) = k % 10, where does key 23 go?

A. 0
B. 3
C. 2
D. 5

49 Using Linear Probing with h(k) = k % 10, if slots 2 and 3 are occupied, where does key 12 go?

A. 3
B. 5
C. 4
D. 2

50 What is the space complexity of a binary heap?

A. O(N)
B. O(1)
C. O(N log N)
D. O(N^2)
Previous MCQ
Unit 4
Next MCQ
Unit 6