Page 153 - Data Structures Handout_Neat

11.6 Exercise

Essay Questions
1. Explain the differences between sets and multisets and provide examples of their

applications in computer science.

2. Discuss how tables can be implemented using arrays and hash tables. Which

approach is more efficient and why?
3. Compare the KMP, Rabin-Karp, and Boyer-Moore algorithms in terms of efficiency

and practical use cases.

4. Describe how priority queues are implemented using heaps and explain their role

in operating system scheduling.
Programming Tasks

1. Write a C++ program to compute the union, intersection, and symmetric

difference of two sets.

2. Implement a simple table structure in C++ that stores student IDs and names, and
supports search by ID.

3. Implement the Rabin-Karp algorithm in C++ to search for a substring within a given

text.

4. Write a C++ program to simulate a priority queue for task scheduling using a max
heap.

Multiple Choice Questions (MCQs)

1. Which of the following data structures allows duplicate elements?

a) Set b) Multiset c) Queue d) Stack
2. Which string algorithm uses hashing for substring search?

a) KMP b) Rabin-Karp c) Boyer-Moore d) Binary Search

3. In a priority queue implemented with a max heap, which element is always at the

root?
a) The smallest element

b) The largest element

c) The first inserted element

d) The last inserted element

153