Consider a telephone book database of N clients.
Make use of a hash table implementation to quickly
look up client ‘s telephone number. Make use of two collision handling techniques and compare them
using number of comparisons required to find a set of telephone numbers (Python)
1
Implement all the functions of a dictionary (ADT) using hashing and handle collisions using chaining
with /without replacement.
Data: Set of (key, value) pairs, Keys are mapped to values, Keys must be comparable, Keys must be
unique,
2 Standard Operations:
Insert (key, value),
Find(key),
Delete(key) (python)
A book consists of chapters, chapters consist of sections and sections consist of subsections. Construct
a tree and print the nodes. Find the time and space requirements of your method.
Beginning with an empty binary search tree, construct binary search tree by inserting the values in the
order given. After constructing a binary tree –
• Insert new node
• Find number of nodes in longest path from root
4
• Minimum data value found in the tree
• Change a tree so that the roles of the left and
• right pointers are swapped at every node
• Search a value
Construct an expression tree from the given prefix expression eg. +-- a*bc/def and traverse it using post
order traversal (non-recursive) and then delete the entire tree.
5
There are flight paths between cities. If there is a flight between city A and city B then there is an edge
between the cities. The cost of the edge can be the time that flight take to reach city B from A, or the
amount of fuel used for the journey. Represent this as a graph. The node can be represented by airport
name or name of the city. Use adjacency list representation of the graph or use adjacency matrix
6 representation of the graph. Check whether the graph is connected or not. Justify the storage
representation used.
7 You have a business with several offices; you want to lease phone lines to connect them up with each
other; and the phone company charges different amounts of money to connect different pairs of cities.
You want a set of lines that connects all your offices with a minimum total cost. Solve the problem by
suggesting appropriate data structures.
Given sequence k = k1 <k2 < ... <kn of n sorted keys, with a search probability pi for each key ki . Build
the Binary search tree that has the least search cost given the access probability for each key?
A Dictionary stores keywords & its meanings. Provide facility
for adding new keywords, deleting keywords, updating values of any entry. Provide facility to display
whole data sorted in ascending/ Descending order. Also find how many maximum comparisons may
require for finding any keyword. Use Height balance tree and find the complexity for finding a keyword
9
Read the marks obtained by students of second year in an online Examination of particular subject. Find
out maximum and minimum marks obtained in that subject. Use heap data structure. Analyze the
algorithm.
10
Department maintains a student information. The file contains roll number, name, division and address.
Allow user to add, delete information of student. Display information of particular employee. If record
of student does not exist an appropriate message is displayed. If it is, then the system displays the student
details. Use sequential file to maintain the data.
11
Company maintains employee information as employee ID,
name, designation and salary. Allow user to add, delete information of employee. Display information
of particular employee. If employee does not exist an appropriate message is displayed. If it is, then the
system displays the employee details. Use index sequential file to maintain the data.
12
