Assignment – 1
Graphs & Hashing
University Questions on Unit V
Names Roll No.
Anushree Bajaj 02
Bhargavi Buradkar 05
Pragati Patel 14
Trupti Gandhare 26
Vijaya Deogade 28
Index Page No.
Unit – 5 02 - 06
1
S – Summer paper (Even Sem) W- Winter paper (Odd
Sem)
Unit-V :
Graphs: Representation of Graph, Matrix Representation of Graph, List of Representation of Graph,
Directed Graphs (Digraphs), Breadth first search and Depth first search, spanning trees.
Hashing: Hash tables, hash functions, hashing techniques, Collision resolution techniques, overflow
handling.
1. Explain hashing function & Collision handling mechanism in detail. ( S-23)
2. What is a graph and what are its applications? Explain graph representation techniques.
( S-23, 15, 14 / W-17)
3. Differentiate between DFS & BFS along with an example. ( S-23)
4. Write a short not on – ( S-23)
i) Spanning Tree
ii) Graph terminology
5. Differentiate between BFS and DFS techniques for graph traversal. ( W-22,16 / S-17,15,14)
6. What is graph? Explain the following with respect to graph: ( W-22 / S-17)
i) Indegree of a node
ii) Outdegree of a node
iii) The adjacency matrix
iv) The adjacency list
v) The adjacency multi list
7. Describe DFS and BFS algorithm with example. Also discuss its complexity.
( W-22, 17, 15 / S-18, 14, 16 )
8. What is collision in hashing ? How can it be avoided ? What are the different collision
handling mechanism? Explain any two with suitable example.
( W-22, 17, 16, 15, 14 / S-18, 17, 15, 14 )
9. Explain open hash table and closed hash table. ( W-22, 16 / S-17 )
10. Construct a minimum spanning tree for the given graph using Kruskal's algorithm. (S-17, 16 )
2
11. Explain any two hashing methods with proper example. ( W-19 )
12. How many minimum spanning tree does the following graph have? Draw them. ( W-19 )
13. For the following directed graph, write: ( W-19 )
i) Indegree & outdegree of each vertex.
ii) Adjacency list
iii) Adjacency matrix
14. Explain the following : (S-17, 16)
i) Hamiltonian path
ii) Types of graphs
iii) Activity Networks
15. What is symbol table ? What are different data structures used for symbol table ? Discuss.
(S-17, 14 / W-17, 15, 14 )
16. Give the following list of elements 22, 26, 89, 45, 12, 32, 90, 55, 69, 96 and the hash
function: (Index = key % 10). Show the hash table. Use collision Resolution through Linear
probing. (S-18)
17. Give the following list of elements 63, 92, 89, 12, 32, 90, 69, 96, 98, 91 use division method
of hashing to store the given values. (S-17 / W-15 )
18. Construct a minimum cost spanning tree (MST) for the given graph using Kruskal's
algorithm.
( W-17, 16. 14 / S-15)
19. For the following graph, write: (W-17)
3
i) Indegree of a node
ii) The adjacency matrix
iii) The adjacency list
iv) The adjacency multi list
20. Differentiate between static and dynamic hash tables.. ( W-16, 17 )
21. What is hashing? Explain division method of hashing to store the following values in hash
table 25, 45, 96, 101, 102, 162, 197, 201, 84 Use suitable collision handling mechanism.
( S-15, 14 / W-17, 16 )
22. Describe DFS algorithm. Find out the DSF traversal of the following graph starting at node A.
( S-18, 16 )
23. Define the following. ( S-14, 16 / W-16, 15, 14 )
i) Complete graph.
ii) Degree of a graph.
iii) Path of a graph.
iv) Strongly connected component.
v) Hamiltonian path.
vi) Isolated Vertex.
vii) Path and cycle
viii) Parent and child
ix) Spanning Tree
x) Multigraph
Explain each term with a suitable example.
24. Explain various hashing techniques with example. ( W-18 )
25. What is Hashing? Explain division method for hashing to store the values in Hash tables and
size 11, 25, 45, 97, 101, 102, 162, 197, 202. ( W-18 )
26. Write down adjacency matrix, adjacency list & adjacency multi list for the following graph.
(W -18)
27. What is the weight of a minimum spanning tree of the following graph? Show stages in
establishing a MST. ( W-18 )
4
28. Define following terms with example ( W-18 )
i) Topological sorting
ii) Critical path
29. Write non-recursive algorithm for Breadth-First search ( S-15, 16 / W-16 )
i) Types of graphs
ii) Activity Networks
30. What are the advantages of adjacency list representation of a graph over the adjacency matrix
representation? ( W-16 )
31. Insert the integers 64, 36, 21, 8, 34, 19, 13 into initially empty hash tables using hash function
h(x) = x mod y. ( W-16 )
i) Using Linear resolution of collision.
ii) Using Linear resolution of collision with slip size 3
32. Why B+ tree is considered a better structure than B-tree for implementation of an indexed
sequential. ( S-16 )
33. Explain collision resolution and hash function. ( S-16 )
34. Distinguish between ( S-16 )
i) Files and records
ii) Sequential and Random access
iii) Input, Output and input/output files
iv) Text and binary files
v) Absolute addressing and relative address
35. For the following graph, write: ( S-15 )
(i) Indegree and Outdegree of each vertex
(ii) Adjacency matrix
(iii) Adjacency list
(iv) Adjacency multilist Representation
36. Insert the integers 13, 5, 22, 8, 34, 19, 21 into initially empty hash tables using hash function
h(x) = x mod y. ( S-15 )
i) Using Linear resolution of collision.
ii) Using Linear resolution of collision with slip size 3
37. Construct a minimum spanning tree for the given graph using Kruskal's algorithm. ( W-15 )
5
38. Using division method of hashing to store the following values in hash table. 64, 98, 123, 200,
214, 193, 163, 201 Use suitable method for handling collision. (W-19, 15, 14 / S-18 )
39. Construct a minimum spanning tree for the given graph using Prim’s algorithm: ( S-14)
40. Given the following list of elements 25, 26, 89, 45, 12, 32, 90, 55, 69, 96 and the hash
Function (Index = key %10). Show the hash table. Use Collision Resolution through linear
probing. ( S-14 )
41. Suppose graph is stored in memory. Write a non-recursive procedure for breadth first search
traversal of a graph and write BF’s spanning tree for following graph. ( W-14 / S-18 )
42. Suppose a graph of n vertices is stored in a memory by using adjacency matrix, write a
function to compute indegree and out degree of a vertex of a graph. ( W-14 )
43. Explain following collision handling techniques: ( W-14 / S-18 )
(i) Linear probing
(ii) Quadratic probing
(iii) Double hashing
(iv) Bucket and chaining
(v) Coalesnd chaining
References – Book & Previous year paper
