Data Structures Question Bank

UNIT-I
SHORT ANSWER QUESTIONS

1. What is a data structure and why do we need data structures?

2. How data structures are classified? List some common data structures.
3. Differentiate linear and non-linear data structure
4. Define ADT (Abstract Data Type) and Mention the features of ADT. What are benefits
of ADT?
5. What are the merits and demerits of array implementation of lists?
6. List out the different ways to implement the list?
7. What are the Advantages of Array.
8. What are the Advantages of Linked List over Array.
9. Define Stack? List the applications of stack?
10. Define Queue? List the applications of queue?
11. List out the basic operations that can be performed on a stack and queue?
12. What are the methods to implement stack in C?
13. What are the methods to implement queue in C?
14. What are enqueue and dequeue operations?
15. Distinguish between stack and queue.
16. What are the disadvantages of queue which is implementing using arrays and how to
overcome it.
17. List the different types of queues?
18. Convert the infix (a+b)*(c+d)/f into postfix & prefix expression
19. Convert the infix expression (a+b)-(c*d) into postfix form?
20. Define circular queue? List the operations that can be performed on Circular Queue?
21. Differentiate between double and circular linked list.
22. What is linked list? Write advantages of doubly linked list over singly linked list.
23. Show the detailed contents of stack to evaluate the given postfix expression.
{1 2 3 + * 3 2 1 - + *}
 LONG ANSWER QUESTIONS

1. Explain the operations of singly linked lists

2. Explain the operations of doubly linked lists
3. Explain the operations of circularly linked lists
4. Explain the steps involved in insertion and deletion into a singly and doubly linked
list.
5. Explain Stack ADT and its operations
6. Explain array based implementation of stacks
7. Explain linked list implementation of stacks
8. Explain the applications of Stacks
9. Explain how to evaluate arithmetic expressions using stacks
10. Explain queue ADT. Explain about the operations of Queue with an Example.
11. Explain array based implementation of queues
12. Explain linked list implementation of queues
13. Explain the applications of queues
14. What is algorithm? What are the properties of the an algorithm? Explain performance
analysis of an algorithm.
15. Write a C function for insertion operation in a circular linked list.
16. Write a function to convert a given singly linked list to double linked list

17. Write a C program to implement multiple stacks using single array.

18. Convert the infix expression a / b – c + d * e – a * c into postfix expression and trace
that postfix expression for given data a = 6, b = 3, c = 1, d = 2, e = 4.
19. Convert the following infix expression into postfix expression
A+B–C*D*E$F$G
 UNIT-II
SHORT ANSWER QUESTIONS

1. What is hashing?
2. Define Hash Table and Hash Function.
3. Write a function double hash to resolve collisions using double hashing
4. What is Rehashing
5. What is Extendible hashing?
6. What is separate chaining?
7. What is linear probing?
8. What is quadratic probing?
9. Define dictionaries.
10. What is skip list? List the operations of Skip List.
11. What is Hash Function? List out methods to calculate the hash function.
 LONG ANSWER QUESTIONS

1. Discuss about linear probing

2. What is collision? Explain different collision resolution techniques with examples.
3. Insert the following list of elements in to the hash table by using linear probing (size of
hash table is 10)
{ 16,23,43,18,34,59,30,22 }
4. Insert the following list of elements into the hash table by using Linear Probing (size
of the hash table is 10)

{ 36,48,66,27,23,87,10,12}
5. Describe the operations of skip list with an example.
6. Explain about the various hash collision resolution techniques with an example.
7. Explain about:
a)Rehashing
b)Extendible hashing.
8. Define Dictionaries. Explain with an Example.
9. Define Skip List. Explain the operations of Skip List
10. Define hashing. Explain Double hashing with an Example.
 UNIT-III
SHORT ANSWER QUESTIONS

1. Define Searching.
2. Define tree traversal
3. How many binary trees are possible with four nodes?
4. Define AVL tree? Give example.
5. What is B-tree of order m? Draw a B-tree of order 3.
6. What are binary trees? Mention different types of binary trees with example
7. What is Red-Black trees
8. What is splay trees
9. What is b-trees.
10. What are the properties of Red-Black tree:
 LONG ANSWER QUESTIONS

1. Explain tree traversals with an example

2. Write an algorithm that counts the number of nodes in a binary tree.
3. How a node can be deleted from the binary search tree? Explain the methods
4. Construct the B-tree of orders 4 for the following list of elements
{ K,L,T,A,G,H,P,W,R,U,Z,C,Y,B,J,M,E}
5. Construct the AVL tree with the following keys
{35,36,80,85,67,89,25,16,10,14,50 }

6. Construct a binary tree having the following traversal sequences:

Preorder traversal: A B C D E F G H I

Inorder traversal: B C A E D G H F I

7. Build an AVL tree with the following values:

{15, 20, 24, 10, 13, 7, 30, 36, 25, 42, 29}

8. Write short notes on:

a) Red-Black trees b) splay trees c) b-trees.
10. Construct the AVL tree of the following data
20, 40, 25, 18, 15, 5, 10, 46, 60
11. Explain how binary tree is represented using an array and linked list
12. Explain the threaded binary tree with suitable example
13. Write an algorithm to insert an element into the binary search tree.
14. Explain the properties of Red-Black tree:
15. Define Binary tree. Explain the Binary tree representations with an example.
16. Write an algorithm for creation of binary tree using in-order traversal and post-order
traversal.
17. Construct AVL tree of the following data
38,40,50,2,5,76, 25, 14,7
18. Insert the following list of elements from the AVL tree. Delete the elements 18, 2 and 30
from the AVL tree 12, 30, 36, 18, 25, 9, 4, 2, 17, 14 , 20, 47
19. Write an algorithm to delete an element from the binary search tree.
 UNIT-IV
SHORT ANSWER QUESTIONS

1. What is Graph? Define degree of vertex.

2. What is a graph? Explain various representations of graphs.

3. What is sorting? What is searching?
4. Define DFS.
5. What is Heap Sort?
6. What is external sorting
7. Differentiate between BFS and DFS
8. Define Maxheap.
9. What is selection sort?
10. What is insertion sort?
 UNIT-IV
LONG ANSWER QUESTIONS

1. Define a graph. List different graph traversal techniques.

2. Explain how BFS can be used to identify the connected components in a graph with an
example.
3. Explain the Radix sort with an example
4. Write an algorithm of Binary Search.
5. Implement Depth First Search (DFS) algorithm.
6. Apply selection sort on the following elements:
{21, 11, 5, 78, 49, 54, 72, 88}
7. Define a Max Heap. Construct a max heap for the following:
{12, 15, 9, 8, 10, 18, 7, 20, 25}
8. Write an algorithm for Heap sort
9. Compare Selection sort and Quick sort with an example
10. Write an algorithm of Linear Search.
11. Sort the following list of elements by using Insertion Sort
{15, 28, 46, 10, 35, 54, 5, 17}
12. Explain the Radix sort with ‘an example.
13. Explain Heap sort algorithm. Create Heap for the following elements and then sort them.
{ 13,102,405,136,15,105,390,432,28,444}
14. Explain about external sorting with an example.
15. Create Heap and sort the following list of elements
{ 12,8,10,6,24,6,11,9,18,14}
 UNIT-V
SHORT ANSWER QUESTIONS

1. Write short notes on standard trie.

2. Write Knuth-Morris-Pratt pattern matching algorithm
3. Write an algorithm of KMP.
4. Define Standard Tries
5. What are the Suffix tries.
6. What is trie? Example?

LONG ANSWER QUESTIONS

7. Consider the string = “GCATCGCAGAGAGTATACAGTACG” and search string is

“AGTATACA” by using the KMP algorithm
8. What is trie? Explain the compressed trie with an example
9. Explain about Boyer-Moore algorithm in detail.
10. Discuss about Suffix tries.
11. Write an algorithm of compressed Trie.
12. Explain about the Brute force algorithm with an example