Back to Subject

Unit 5: Heaps and Hashing - Practice Quiz

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

1 Which property is always satisfied by a binary heap?

Introduction to heaps Easy
A. It is a complete binary tree
B. It is always a binary search tree
C. It contains exactly two children per node
D. It stores data only in sorted order

2 In a max-heap, where is the largest element located?

Introduction to heaps Easy
A. In the left subtree
B. In the right subtree
C. At the last leaf
D. At the root

3 Where is a new element first placed when it is inserted into a binary heap?

Heap insertion Easy
A. At the leftmost internal node
B. At the next available leaf position
C. Directly above the root
D. At a randomly selected position

4 What operation restores heap order after inserting an element?

Heap insertion Easy
A. Reversing the entire array
B. Removing the root element
C. Sorting all elements again
D. Sifting the element upward

5 Which element is usually removed in a standard binary heap deletion?

Heap deletion Easy
A. The root element
B. The leftmost leaf
C. The smallest leaf
D. The deepest internal node

6 After deleting the root, which element commonly replaces it?

Heap deletion Easy
A. The last element
B. The second element
C. A newly generated element
D. The leftmost leaf

7 Which data structure is used as the main basis of heap sort?

Heap sort Easy
A. A binary heap
B. A hash table
C. A linked list
D. A graph

8 What is the usual time complexity of heap sort?

Heap sort Easy
A.
B.
C.
D.

9 What is the main purpose of hashing?

Introduction to hashing Easy
A. To locate data quickly
B. To connect nodes in a graph
C. To arrange data alphabetically
D. To compress every file

10 What is a collision in hashing?

Introduction to hashing Easy
A. Two keys map to one position
B. Two tables have different sizes
C. A table contains no empty positions
D. A key is larger than the table

11 What does a hash function return for a given key?

Hash functions Easy
A. A memory address only
B. A table index
C. A sorted list
D. A tree height

12 Which operation is commonly used in a simple hash function for integer keys?

Hash functions Easy
A. The factorial operation
B. The square-root operation
C. The comparison operation
D. The modulo operation

13 A hash table stores data using which type of access?

Hash tables Easy
A. Position-only access
B. Key-based access
C. Sequential-only access
D. Depth-based access

14 Which collision-resolution method is generally associated with open hashing?

Open hashing Easy
A. Double hashing
B. Quadratic probing
C. Separate chaining
D. Linear probing

15 In separate chaining, collided entries are usually stored in what structure?

Separate chaining Easy
A. A linked list
B. A circular queue
C. A separate matrix
D. A binary heap

16 Which technique is commonly used in closed hashing?

Closed hashing Easy
A. Tree traversal
B. Open addressing
C. External sorting
D. Separate chaining

17 In open addressing, where is a collided key placed?

Open addressing Easy
A. A linked list outside the table
B. The root of a heap
C. A separate database file
D. Another table position

18 How does linear probing search for an empty position?

Linear probing Easy
A. It checks only the first position
B. It checks random positions
C. It checks consecutive positions
D. It checks linked-list nodes

19 What type of sequence is used by quadratic probing?

Quadratic probing Easy
A. A sequence of linked nodes
B. A sequence based on sorted keys
C. A sequence based on squared steps
D. A sequence of consecutive steps

20 How does double hashing determine the next position after a collision?

Double hashing Easy
A. It uses a second hash function
B. It uses the table midpoint
C. It uses a linked-list pointer
D. It uses the previous key

21 A binary max-heap is stored in a zero-indexed array. If an element is at index , what are the indices of its children?

Introduction to heaps Medium
A. and
B. and
C. and
D. and

22 The array represents a max-heap. What is the array after inserting ?

Heap insertion Medium
A.
B.
C.
D.

23 The array represents a min-heap. Which array results after inserting ?

Heap insertion Medium
A.
B.
C.
D.

24 The array represents a max-heap. What is the heap after deleting the maximum element?

Heap deletion Medium
A.
B.
C.
D.

25 A min-heap is represented by . Which array results after deleting the root?

Heap deletion Medium
A.
B.
C.
D.

26 Heap sort builds a max-heap from and repeatedly moves the root to the end. What is the final array?

Heap sort Medium
A.
B.
C.
D.

27 Which statement correctly describes the worst-case performance and stability of standard in-place heap sort?

Heap sort Medium
A. It runs in time and is stable.
B. It runs in time and is not stable.
C. It runs in time and is not stable.
D. It runs in time because the heap is constructed in linear time and no additional ordering work is needed.

28 Two different keys are mapped to the same table index by a hash function. What has occurred?

Introduction to hashing Medium
A. A heap violation
B. A hash collision
C. A table overflow
D. A key inversion

29 For the hash function , which statement is true for the keys , , , and ?

Hash functions Medium
A. Only and collide.
B. Both and collide.
C. All four keys map to one index.
D. Only and collide.

30 A program stores sequential employee IDs in a hash table. Which property is most important when selecting a hash function?

Hash functions Medium
A. It should distribute IDs uniformly across the table.
B. It should map larger IDs only to larger indices.
C. It should always use the first digit of each ID.
D. It should preserve the numerical ordering of all employee IDs when assigning table positions.

31 A hash table has buckets and currently stores keys. What is its load factor?

Hash tables Medium
A.
B.
C.
D.

32 An open-hashing table uses and inserts colliding keys at the front of each chain. After inserting in that order, how many key comparisons are needed to find in bucket ?

Open hashing Medium
A.
B.
C.
D.

33 A separate-chaining table of size uses and appends keys to each chain. After inserting , which chains are correct?

Separate chaining Medium
A. Bucket : ; bucket :
B. Bucket : ; bucket :
C. Bucket : ; bucket :
D. Bucket : ; bucket :

34 A closed-hashing table has slots, of which contain active keys and none contain deleted markers. Which statement is correct?

Closed hashing Medium
A. Its load factor is , and two slots are empty.
B. Its load factor is , and eight slots are empty.
C. Its load factor is , and two slots are empty.
D. Its load factor is , and additional keys can be inserted indefinitely without resizing because collisions reuse occupied slots.

35 Why is a deleted slot usually marked with a tombstone instead of being made immediately empty in an open-addressing table?

Open addressing Medium
A. To ensure every unsuccessful search scans the entire table before reporting that the key is absent
B. To reduce the physical size of the table
C. To guarantee that future insertions avoid the slot
D. To preserve probe sequences used by later keys

36 A table of size uses with linear probing. Slots , , and are occupied. At which index will key be inserted?

Linear probing Medium
A. Index
B. Index
C. Index
D. Index

37 A linear-probing table contains a long consecutive block of occupied slots. Which effect is most likely as more colliding keys are inserted?

Linear probing Medium
A. Keys in the cluster are redistributed uniformly whenever a new colliding key reaches the occupied block.
B. The load factor automatically decreases.
C. Secondary clustering removes all collisions.
D. Primary clustering increases probe lengths.

38 A hash table of size uses quadratic probing with , starting at . If , what are the first four indices examined?

Quadratic probing Medium
A.
B.
C.
D.

39 A table of size uses the probe formula . If , why might insertion fail even when some slots are empty?

Quadratic probing Medium
A. Quadratic probing never checks the original hash index.
B. Every collision permanently reserves two additional empty slots, eventually preventing insertion despite available capacity.
C. The probe sequence can cycle through only a subset of slots.
D. The formula changes the table size after every collision.

40 A table of size uses and . Using , what are the first four indices examined for ?

Double hashing Medium
A.
B.
C.
D.

41 A complete -ary heap contains elements stored in a zero-indexed array. Children of index occupy indices through . What is the index of the first leaf?

Introduction to heaps Hard
A. 26
B. 25
C. 20
D. 24

42 The array represents a max heap. What is the array after inserting ?

Heap insertion Hard
A.
B.
C.
D.

43 A max heap is stored as . After one delete-max operation using the standard replacement-and-sift-down procedure, which array remains?

Heap deletion Hard
A.
B.
C.
D.

44 An arbitrary element is removed from a valid binary min heap, and the last element is moved into the vacated position. Which repair rule is correct?

Heap deletion Hard
A. Perform both upward and downward sifts because either direction may remain invalid afterward
B. Always sift upward because the replacement originated at a lower heap level
C. Sift upward if it is smaller than its parent; otherwise sift it downward if it exceeds a child
D. Always sift downward because deletion can only create violations with children

45 Heap sort begins with the max heap . What is the complete array after exactly two maximum extractions, including the sorted suffix?

Heap sort Hard
A.
B.
C.
D.

46 To find the largest elements of an unsorted array of elements without fully sorting it, an algorithm maintains a min heap of size at most . What are its worst-case time and auxiliary-space complexities?

Introduction to heaps Hard
A. time and space
B. time and space
C. time and space
D. time and space

47 A hash function is chosen from a universal family mapping distinct keys into slots. What is the maximum expected number of colliding unordered key pairs guaranteed by universality?

Introduction to hashing Hard
A.
B.
C.
D.

48 Every key in a data set has the form , and a table has slots. Which replacement for is guaranteed to preserve the collision among all these keys?

Hash functions Hard
A. A universal hash modulo a prime above the key range
B. A multiplication hash using an irrational constant
C. Any hash function depending only on
D. A randomized tabulation hash over all key bits

49 A hash table doubles its capacity whenever an insertion would make the load factor exceed . Rehashing existing entries costs . Under uniform hashing, what is the amortized expected cost per insertion over a long sequence?

Hash tables Hard
A. because collisions grow with the load factor
B. because each resize doubles the capacity
C. because resize costs form a geometric series
D. because some insertions trigger complete rehashing

50 One hundred keys are independently hashed uniformly into buckets using open hashing. What is the expected number of empty buckets?

Open hashing Hard
A.
B.
C.
D.

51 A separate-chaining table has chain lengths . Assuming each stored key is equally likely to be searched and keys are examined sequentially within a chain, what is the expected number of key comparisons for a successful search?

Separate chaining Hard
A.
B.
C.
D.

52 In a closed-hashing table, a key in the middle of a probe sequence is deleted. Why is its slot normally marked with a tombstone instead of being marked empty?

Closed hashing Hard
A. A tombstone prevents future insertions from creating duplicate hash values
B. An empty slot could terminate searches for keys stored later in that probe sequence
C. An empty slot would force every subsequent key to be reinserted immediately
D. A tombstone reduces the load factor without changing the table capacity

53 Under the uniform-hashing model for open addressing, the expected number of probes in an unsuccessful search is approximately . What is the expectation when the load factor is ?

Open addressing Hard
A.
B.
C.
D.

54 A linear-probing table of size uses . Keys are inserted in that order. How many slots are examined in an unsuccessful search for , counting the final empty slot?

Linear probing Hard
A. 6
B. 8
C. 5
D. 7

55 For linear probing, the standard approximation for an unsuccessful search is . What is the estimate at load factor ?

Linear probing Hard
A.
B.
C.
D.

56 A table of size uses quadratic probing . If , which sequence gives the first six distinct slots visited?

Quadratic probing Hard
A.
B.
C.
D.

57 For a prime table size , quadratic probing uses . Which condition guarantees that an insertion finds an empty slot?

Quadratic probing Hard
A. The load factor is below
B. The load factor is below
C. The table size is a power of two
D. The number of keys is relatively prime to

58 A table of size uses double hashing with and . Which key produces a probe step that cannot visit every table slot?

Double hashing Hard
A.
B.
C.
D.

59 A table of size uses , where and . What are the first six slots probed for ?

Double hashing Hard
A.
B.
C.
D.

60 An open-addressing table is resized from capacity to capacity . Why must stored keys generally be rehashed rather than copied to the same array indices?

Hash tables Hard
A. Probe sequences are valid only when the table contains no deleted entries
B. Copying indices would necessarily make the new load factor exceed one
C. Existing indices become invalid because every key's stored value changes
D. Hash values and probe sequences may depend on the new table capacity
Previous MCQ
Unit 4
Next MCQ
Unit 6