“Techno – Social Excellence”

Marathwada MitraMandal’s
INSTITUTE OF TECHNOLOGY (MMIT)

"Excellence in the field of AI & DS"

Department of Artificial Intelligence and Data Science
Unit Wise Question Bank
Unit -I Hashing
Q.1 Write a short note on Skip List. 6M
Q.2 Construct hash table of size 10 using linear probing with replacement strategy 6M
Q.3 for collision
Construct resolution.The
hash table of sizehash function
10 using linearis probing
h(x)=x % 10.Calculate
without total numbers
replacement 6M
Q.4 of comparisons
strategy
Explain about a required
for collision
Skip List for
withsearching
resolution.The hash
an example.consider
functionslot
is per bucket
h(x)=x
Give applications % is 1.
of 10.
Skipconsider
List. slot 6M
25,3,21,13,1,2,7,12,4,18
per bucket is 1. 31,3, 35
4,21,61,6,71,8,9,25
Q.5 For the given set of values , 36 , 25 , 47 , 2501 , 129 , 65 , 29 , 16 ,14 , 99. Create 6M
a hash table with size 15 and resolve collision using open addressing techniques
Q.6 What is hash function ? what are the different characteristics of good hash 6M
function ? Explain six different types of hash function ?

For the given set of values.

11, 33, 20, 88, 79, 98, 44, 68, 66, 22
Q.7 6M
Create a hash table with size 10 and resolve collision using chaining with
replacement and without replacement. Use the modulus Hash function. (key %
size.)
Q.8 What is hash function ? What are characteristics of good hash function ? Explain 6M
the different types of hash functions
Q.9 Explain about a skip list with an example. Give applications of skip list. 6M

Q.10 What is hash function ? Enlist characteristics of a good hash function. Explain 6M
modulo Division and folding method.

Assume the size of hash table as 8. The hash function to be used to calculate the
Q.11 hash value of the data X is : X % 8. Insert the following values in hash table : 10, 5M
12, 20, 18, 15. What is the average search cost of linear probing without
replacement for handling collision ?
Q.10 How are collisions handled in linear probing? 6M
Q.11 How are insertions and deletions handled in chained hash table? 6M
Q.12 What is rehashing ? How does it serve to overcome the drawbacks of linear 6M
Q.13 probing?
What are the advantages of using modulo arithmetic for building hash function ? 6M
Unit -II Trees
Q.1 Write a non-recursive pseudo code for post order traversal of binary tree. 5M
Q.2 Construct a binary tree from given two traversal: Inorder Traversal- 6M
Q.3 1,2,3,14,7,10,11,40,30
Write an algorithm to delete node from BST. Postorder Traversal- 6M
Q.4 1,3,2,7,10,40,30,11,14
Write an algorithm for preorder traversal of binary tree and give suitable 6M
Q.5 example.
Generate binary tree for the following pre-order and inorder traversal: 6M
Q.6 Inorder:
From theEgiven
A C Ktraversals
F H D G Bconstruct the binary tree. Preorder: F A E K C 4M
D H G B : G, B, Q, A, C, K, F, P, D, E, R, H
Pre-order
In-order : Q, B, K, C, F, A, G, P, E, D, H, R
Q.7 Construct Huffman's Tree and the prefix free code for all characters : 6M
Symbol ACEHI
Frequency35827
For the binary tree represented as an array, perform in-order threading on the
tree :
Q.8 4M

Q.9 Write pseudo-code for performing level order traversal of a binary tree. 4M
Q.10 Let characters a, b, c, d, e, f have probabilities 0.07, 0.09, 0.12, 0.22, 0.23, 0.27 6M
Q.11 respectively. Find anfor
Write an aigorithm optimal
PreorderHuffman code
traversal ofand draw
binary Huffman
tree tree.
and give What is the
suitable 6M
Q.12 average
example. codeand
The inorder length ?
postorder traversal of a tree are given below : 6M
Q.13 Inorder : EICFJBGDKHL postorder : IEJFCGKLHDB
Write a function for deletion of an element from threaded binary search tree. 6M
Draw the binary tree and write preoreder traversal.
Convert the following general tree into it's equivalent binary tree

Q.14 6M

Unit-III Graphs
Consider the given graph and find the shortest path by using Dijkstra's algorithm
from 'a' to 'g'.

Q.1 7M

Q.2 Draw any directed graph with minimum 6 nodes and represent graph using 6M
adjacency matrix , adjacency list ,adjacency multilist and inverse adjacency list.
 Consider the graph represented by following adjacency matrix. And find
minimum spanning tree of this by using Prim's Algorithm.

Q.3 6M

Construct MST from the given data using prims Algorithm

Q.4 6M

Find the shortest path in the following graph from node A , using Dijkstra's
Algorithm

Q.5 6M

Find the MST for the graph given using Kruskals Algorithm
and show all the steps.

Q.6 6M
 Define DFS and BFS for a graph. Show BFS and DFS for
the following graph with starting vertex as 1.

Q.7 7M

Q.8 Explain different types of Graph storage structure and give 6M

example
What of each
is topological ordering ? List their applications. Find the
topological sorting of a given graph.

Q.9 6M

Unit-IV
Q.1 Enlist the names of static tree table with suitable example 2M
Q.2 Construct the AVL tree for the following data by inserting each of the following data item 5M
Q.3 one at a time
Construct AVL tree for following sequence of keys. 6M
10,20,15,12,25,30,14,22,25,40.
1,2,3,4,8,7,6,5,11,10
Q.4 Construct the AVL tree for the following data by inserting each of the following data item 6M
Q.5 one at a time
What is OBST in data structure? And what are advantages of OBST? 5M
15,20,24,10,13,7,30,36,25
Q.6 Write a pseudo C++ Code for RL rotations in AVL Trees. 4M
Q.7 Write function for LL and LR rotation with respect to AVL tree. 6M
Q.8 Explain Static and Dynamic tree tables with suitable example 6M
Q.9 Explain dynamic programming with principle of optimality 5M
Q.10 Explain with example Splay Tree 6M
Q.11 Explain with example Red Black Tree 6M
Q.12 Explain with example : KD Tree 6M
Q.13 Write a short note on AA Tree 6M
Q.14 Explain AVL tree rotations with example. 5M
Unit-V
Q.1 Create a B tree of order 3 for the following data: 7M
Q.2 20,10,30,15,12,40,50
What is B+ Tree? Give structure of its internal node. What are the order of B+ tree and 7M
Q.3 characteristics
Create a B tree of
of B+ tree?
order 3 for the following data: 6M
Q.4 5,3,21,9,1,13,2,7,10,12,4,8
Explain with example: Trie Tree 6M
Q.5 What is B tree? 2M
Q.6 Construct B+ tree of order 4 for the following data: 6M
C,N,G,A,H,E,K,Q,M,F,W,L,T,Z,D,P,R,X,Y
 Q.7 Explain the delete operation in B tree with example. 6M
Q.8 Create the min-heap for given data : 4M
Q.9 25,12,27,30,5,10,17,29,40,3
Sort the data in ascending order using heap sort: 6M
Q.10 15,19,10,7,17,16
What is max heap? Write a function to insert an element in max heap. What is the time 7M
Q.11 complexity
Sort ofin
the data inserting an order
ascending element in max
using heapheap?
sort: 6M
Q.12 15,10,40,25
Construct B tree of order 5 for the following data: 6M
Q.13 78,21,14,11,,97,85,74,63,45,42,57
What is B+ tree? give structure of its internal node. What is difference between B and B+ 6M
Q.14 tree
Build B+ tree of order 3 for the following data: 5M
F,S,Q,K,C,L,H,T,V,W,M,R Unit-VI
Q.1 Define Sequential file organization.Give its advantages and disadvantages. 6M
Q.2 What is File? list different file opening modes in C++.Explain concept of inverted 6M
Q.3 files. short note on External sort
Write 5M
Q.4 Write a C++ program to create a file. Insert records into the file by opening file in 6M
Q.5 append
Explain mode search
indexed for specific
sequential record into file.
file organization.Compare it with direct access file 5M
Q.6 Explain linked organization with respect to inverted files. 7M
Q.7 Enlist types of indices.Explain any two. 5M
Q.8 Explain advantages of indexing over sequential files 2M
Q.9 Explain any three operations carried out on sequential file. write pseodo code for 6M
Q.10 each these
Explain three
linked operations.of a file.
organization 6M