Back to Subject
View Notes

Unit 5 - Practice Quiz

CSE205

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

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

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

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

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
B. 2i + 1
C. 2i + 2
D. i / 2

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

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

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

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

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

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

7 A binary heap is strictly a __.

A. Full Binary Tree
B. Complete Binary Tree
C. Binary Search Tree
D. AVL 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 / 2
C. 2i
D. (i + 1) / 2

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

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

10 HeapSort is generally considered stable. True or False?

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

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

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

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

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

13 In HeapSort, where is the sorted array constructed?

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

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

A. O(N)
B. O(log N)
C. O(N^2)
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. Separate Chaining
C. Linear Probing
D. Double Hashing

16 What is a 'Collision' in hashing?

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

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

A. Number of buckets / Number of elements
B. Number of elements / Number of buckets
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. Folding Method
C. Division Method
D. Multiplication Method

19 In Open Addressing, where are colliding elements stored?

A. In a separate linked list
B. In a secondary hash table
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) % m
B. (h(k) + i^2) % m
C. (h(k) + i * h2(k)) % m
D. h(k) % m

21 What is the main disadvantage of Linear Probing?

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

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

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

23 Which collision resolution technique uses a second hash function?

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

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

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

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

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

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

A. O(1)
B. O(log N)
C. O(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. Physical deletion
B. Shifting elements
C. Lazy deletion (Tombstones)
D. Rehashing immediately

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

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

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 last digits
C. The middle digits
D. The sum of all digits

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

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

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

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

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

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

34 What is 'Perfect Hashing'?

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

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

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

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

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

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

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

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. 2.0
C. 10
D. 20

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

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

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

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

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

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

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

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

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

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

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

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

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(log N)
C. O(N)
D. Infinite loop (until resized or error)

46 For string keys, a common hashing approach involves:

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

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

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

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

A. 2
B. 3
C.
D. 5

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

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

50 What is the space complexity of a binary heap?

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