DSA Question Bank

Unit 1- Hashing

Question
Question Statement Marks
NO

Explain the basic concept of hashing. 2

Q1
Explain hash table and hash function with suitable example. 4
Q2
Identify difference between open and closed hashing techniques. 4
Q3
Describe the perfect hash function. 2
Q4
Describe is collision in hashing? Describe various collision resolution techniques. 4
Q5
Explain the terms related to hashing: 4
Q6 i)Load factor
ii)Load Density
Discuss the issues involved in Hashing. 4
Q7
Explain the term rehashing. 2
Q8

Explain different hashing functions. 4

Q9

What are the properties of good hashing function? 4

Q10
Describe extendible hashing technique. 4
Q11

Discuss hash Table overflow. 2

Q12
Write short note on Skip List. 2
Q13
Discuss the various operations that can be performed on Skip List 4
Q14
Write short note on Dictionary and ADT for the same. 4
Q15
Describe the ordered dictionaries. 4
Q16
What is bucket hashing? Explain with example. 4
Q17
What is hash function? Explain the following hash 8
Q18
functions :
 i)Mid-square
ii)Modulo Division
iii)Folding Method
iv)Digit Analysis.

What is collision? Explain any two methods of handling collision 6

Q19
What is hash function? What are issues in hashing? What are rules for designing hash 6
Q20 function? Give types of uniform hash functions.

What is hash function? Explain the different types of hash functions. 6

Q21
What are hashing methods? Explain in brief. 6
Q22
Insert the following data in hash table of size 10 using linear probing with chaining with 4
replacement.
Q23
Here, h(x)=x%10
21,35,31,37,32,33,48
Identify hash functions to calculate the hash values of the data. 3
Q24
Assume the size of hash table as 8.The hash function to be used to calculate hash value 3
Q25 of the data X is X%8.Insert the following values in hash table : 10,12,20,18,15.Use
linear probing without replacement for handling collision.
 Unit 2- Trees

Question
Question Statement Marks
NO

Explain general tree and describe its various representations. 4

Q1.
Describe the concept of binary tree and how we can convert general tree to 5
Q2
binary tree
Explain various binary tree traversal techniques. 4
Q3
Differentiate between depth first and breadth first search techniques. 4
Q4
Describe the various operations carried out on binary tree 4
Q5
Describe Binary search tree and operations carried out on it 4
Q6
Discuss the concept of Threaded binary tree. 4
Q7
Use in-order threaded binary tree to insert and delete nodes. 6
Q8
Explain the use of threaded binary tree? 4
Q9

Demonstrate the in-order traversal of in-order threaded binary tree 4

Q10

Use binary tree to create expression tree evaluation with example. 6

Q11

Explain use of binary tree in Huffman's coding 6

Q12
Describe construction of expression tree with example 6
Q13
Discuss Huffman’s coding with example 6
Q14
Discuss the various applications of trees. 4
Q15
Discuss binary tree extension and what is its use? 4
Q16
Explain an algorithm to find out the height of a binary tree. 6
Q17
Describe binary search trees and its use. 4
Q18
Given a set of input representing the nodes of a binary tree, Describe a non- 6
Q19 recursive algorithm that must be able to output the three traversal orders.
 Explain the concept of Binary Search Tree (BST)? Make a BST for the following 6
Q20 sequence of numbers 45, 36, 76, 23, 89, 115, 98, 39, 41, 56, 69, 48
Traverse the tree in Preorder, Inorder and postorder.
Two Binary Trees are similar if they are both empty or if they are both nonempty 6
Q21 and left and right sub trees are similar. Explain an algorithm to determine if two
Binary Trees are similar.
The degree of a node is the number of children it has. Demonstrate that in any 6
Q22 binary tree, the number of leaves are one more than the number of nodes of
degree 2.
Describe the maximum total number of nodes in a tree that has N levels? Note 4
Q23
that the root is level (zero).
Explain the non-recursive algorithm to traverse a tree in preorder. 6
Q24
Explain how many different binary trees and binary search trees can be made 6
Q25 from three nodes that contain the key values 1, 2 & 3?

Explain a non-recursive algorithm to traverse a binary tree in inorder. 6

Q26
use expression tree to represent following expression. Comment on the result 6
Q27 that you get when this tree is traversed in Preorder, Inorder and postorder. (a-b) /
((c*d)+e).
Discuss which one is faster? A binary search of an ordered set of elements in an 4
Q28
array or a sequential search of the elements
Given the following inorder and preorder traversal use following sequence to 6
construct a binary tree
Q29
Inorder sequence D, G, B, H, E, A, F, I, C
Preorder sequence A, B, D, G, E, H, C, F, I
Explain the following terms with respect to Binary trees (i) Strictly Binary Tree (ii) 6
Q30
Complete Binary Tree (iii) Almost Complete Binary Tree.
 Unit 3 - Graphs

Question
Question Statement Marks
NO

Explain graph and its storage representations 6

Q1.
Explain different graph traversal methods 6
Q2
Describe the greedy strategy with example 4
Q3
Explain Minimum spanning tree algorithm 6
Q4
Describe Greedy algorithms for computing minimum spanning tree 6
Q5
Explain Kruskals Algorithm with example 6
Q6
Explain Prim’s Algorithm with example 6
Q7
Write Dikjtra's Single source shortest path algorithm. 6
Q8

Describe topological ordering. 4

Q9

How the graph can be used in webgraph. 4

Q10
Explain use of graph in Google map. 4
Q11

Describe an algorithm for breadth first traversal of graph. Also write its 6
Q12
complexity.
Identify the difference between DFS and BFS 4
Q13
Explain with example various storage structures for graph 4
Q14
Explain pseudo code for any of the depth first search traversal of binary tree. 4
Q15
Explain any tree applications of graph in area of computer engineering 4
Q16
Differentiate between Prim’s and Kruskal’s algorithm for generating spanning tree 4
Q17 of graph
Explain the situation in which linked representation of graph is more beneficial 4
Q18
than array representation.
What are graph storage structures? Explain in detail. 6
Q19
 Explain pseudo code to find the shortest path in weighted graph. 6
Q20
Describe Dijkstra’s 6
Q21 Algorithm for finding shortest path and explain
it with example.
Write Kruskal’s Algorithm and explain it with example. 6
Q22
Explain algorithm to print a given graph in BFS. Give its time complexity. 6
Q23
Give complete specification of the graph ADT. Explain graph representation in 6
Q24
the form of adjacency matrix and adjacency
Explain algorithm for Breadth First Traversal of the graph. Also write its 6
Q25
complexity.
Identify the difference between Kruskal’s and 4
Q26
Prims algorithm for minimum spanning tree (MST).
Explain Graph as an ADT. 4
Q27
Write Kruskal’s Algorithm for MST and explain it with 6
Q28
example.
Explain the following: 6
i) What are graph storage structures?
Q29
ii) Topological sort.

define strongly and weekly connected in a graph? 4

Q30
 Unit 4 - Search Trees

Question
Question Statement Marks
NO

Explain the representation of Hash tables. 4

Q1
Discuss the difference between Static tree table and Dynamic tree table 4
Q2
Explain the dynamic programming technique. 4
Q3
Describe weight balanced trees. 4
Q4
Describe optimal binary search tree with example. 6
Q5
Describe height balanced trees. 4
Q6
Explain the concept of red black trees. 4
Q7
Explain how OBST is an example of dynamic programming. 4
Q8

Write and explain algorithm to insert node into AVL tree. 8

Q9

Explain with example LL, LR, RR, RL rotation for AVL tree. 8
Q10
Write a program in C/C++ for Word/Text processing using AVL Tree implementation. 8
Q11

What is symbol table? What are operations on symbol table? Give complete 6
Q12
specification of symbol table ADT.
Write and explain algorithm to delete node from AVL tree. 6
Q13
Explain different types of rotation for AVL tree with suitable example. 8
Q14
Explain the following terms with respect to height balanced tree: 8
1)LL
Q15 2)LR
3)RL
4)RR
Create an AVL search tree from given set of values: H, I, J, B, A, E, C, F, D, G, K, L 4
Q16
Construct the AVL Tree for following data: 5,4,7,1,3,2,15,20,10,12 4
Q17
Explain the C code for following function w.r.t AVL trees: 6
Q18 1)LR rotation
2)RL rotations
Construct the AVL tree for the following data by inserting each of the following data 5
Q19
item one at a time:
 10, 20, 15, 12, 25, 30, 14, 22, 35, 40.

Construct the AVL tree for the following data by inserting each data item one at a 4
Q20 time. 15, 20, 24, 10, 13, 7, 30, 36, 2

Create an AVL tree for following data by inserting it in order one at a time: 4
Q21
10,20,15,12,25,30
Enlist the names of static tree table with examples 2
Q22
 Unit 5 - Indexing and Multiway Trees

Question
Question Statement Marks
NO

Describe indexing. 2
Q1
Discuss different indexing techniques. 4
Q2
Explain search trees. And explain its different types. 6
Q3
Describe set as an ADT and various operations carried out on it. 6
Q4
Explain Multiway search tree with example. 6
Q5
Describe B-Tree and B+Tree with example of each. 6
Q6
Explain Trie Tree with example. 4
Q7
Describe Splay Tree with example. 4
Q8

Describe the concept of Red-Black Tree. 4

Q9

Explain K-dimensional tree. 4

Q10
Describe AA tree with example. 4
Q11

Describe the concept of heap and operations carried out on it. 4

Q12
How we can use heap in priority queue. 4
Q13
Explain heap sort. 4
Q14
Build the Min-Heap for the following data: 25, 12, 27, 30, 5, 10, 17, 29, 40, 35. 4
Q15
Explain a pseudo-C/C++ code to sort the data using heap sort in ascending order. 6
Q16
Create a 3-way B tree by inserting the following data one at a time: [6] 5, 3, 21, 9, 6
Q17 1, 13, 2, 7, 10, 12, 4, 8.
Write an ADT for a binary heap. Explain different operations on MAX heap in brief 8
Q18
with example (any three).
Describe multiway tree? State need of multiway trees. Explain B+ tree in brief. 8
Q19
 Construct a B tree of order 5 for the following data: 8
Q20 50, 85, 12, 10, 6, 60, 70, 80, 37, 100, 120, 65,
150, 62, 30, 17, 15, 28, 75, 78.
Write an algorithm to arrange numbers in ascending order using heapsort. 8
Q21 Arrange the following numbers in ascending order using heapsort:
48, 0, –1, 82, 10, 2, 100.
Construct a B tree of order 5 for the following data: 8
50, 85, 42, 10, 16, 60, 70, 80, 87, 100, 120, 65, 150, 62, 30,17, 18, 28, 75, 78.
Q22
What is the best and worst case complexity of insert and delete operation on B
tree ?
Describe B tree? Explain the process for deleting a particular value from B tree. 8
Q23
Describe algorithm to sort elements of a given array in ascending order using 8
Q24 heapsort. Sort the following numbers using heapsort in ascending order: 38, –10,
–11, 72, 98, 62, 44.
Explain multiway tree? Identify need of multiway trees. Explain B+ tree in brief. 8
Q25
Construct a B tree of order 5 for the following data: 8
Q26
50, 85, 12, 10, 6, 60, 70, 80, 37, 100, 120, 65,150, 62, 30, 17, 15, 28, 75, 78.
Describe an algorithm to arrange numbers in ascending order using heapsort. 8
Q26 Arrange the following numbers in ascending order using heapsort:
48, 0, –1, 82, 10, 2, 100.
Explain in brief MAX heap and MIN heap. Construct MAX heap for given list of 8
Q27
elements {40, 80, 35, 90, 45, 50, 70}.
Describe B tree? Explain the process for deleting a particular value from B tree. 8
Q28
State the need of B+ tree. Construct a B+ tree of order 5 for the following data: 30, 8
Q29
31, 23, 32, 22, 28, 24, 29, 15, 26, 27, 34, 39, 36.
Describe an algorithm to sort elements of a given array in ascending order using 8
Q29 heap sort. Sort the following numbers using heap sort:
48, 0, –1, 82, 108, 72, 54.
8
Q30
4
Q31
Explain an algorithm to search an element in B trees. 6
Q32
Describe B+ tree? Give the structure of its internal nodes. What are the order of B+ 8
Q33
tree & characteristics of B+ tree?
 Unit 6 - File Organization

Question
Question Statement Marks
NO

Describe file. What is the need of a file? How the files are stored on external 6
Q1 storage? What are the basic operations to be performed on files?

Explain cellular organizations 4

Q2
Identify the difference between direct access file and index sequential file 4
Q3
Discuss the difference between sequential & direct access files? 4
Q4
Explain how records are deleted logical from the file. 4
Q5
Explain what type of file organization is used to handle multiple key? Explain 4
Q6
in details.
Explain what type of file organization is used to handle multiple key? Explain in 4
Q7 details.

Explain the sequential file organization and its operation. 4

Q8

Explain the index sequential file organization and operation. 4

Q9

Explain the direct file organization and its operation 4

Q10

Explain the linked organization and its operation 4

Q11

Explain a K-way merging algorithm. 4

Q12
Describe multilist & coral rings. 4
Q13

Describe inverted files and cellular partitions. 4

Q14
Explain external sort. 4
Q15