DATA STRUCTURE

IMPORTANT QUESTIONS AND QUESTION BANK

UNIT-I LINEAR DATA STRUCTURES – LIST
2-
Marks

1. What are the advantages of Linked List over arrays?

2. State the advantage of ADT.
3. What is the disadvantage of linked list over array?
4. Illustrate the difference between linear linked list and circular linked
list.
5. Define linked list.
6. Define an Abstract Data Type.
7. Distinguish between linear and nonlinear data structure.
8. Differentiate arrays and linked lists
9. List out the advantage of circular linked list.
10. Binary search cannot be performed on a linked

list. Examine. 13-Marks

1. Write a function to add polynomials represented by linked

representation. Apply the function for the following input.
2. What are the various operations on array? Write a procedure to
insert an element in the middle of the array.
3. 1) Write a program to merge two sorted linked list(P & Q-assume
that they are available) to get a single sorted list S.
e.g. P:1→2→45→56
Q:3→24→56→63→66
.
2) write a non-recursive procedure to reverse a singly linked list.
4. 1) write a function to add two polynomials represented
by linked representation. Apply the function for the
following input.
A=3x2+2x18+1, B=8x12+3x10+3x8+10x6.
2) write a function to delete the node n from the given
doubly linked list p ↔ q ↔ r ↔ n ↔ s ↔ t ↔ z↔.
5. Explain the insertion operation linked list. How nodes are
inserted after a specified node?
6. What is the application of linked list in dynamic storage
management?
7. 1) Give the algorithm to perform insertion on a doubly
linked list.
2) Give the algorithm to perform deletion on a doubly linked
list.
8. Discuss the algorithm for linked list implementation of list.
9. Describe the various operation of the list ADT with example.
10. Develop the program to add the values of the nodes of a
linked list and then calculate the mean.
 UNIT-II LINEAR DATA STRUCTURES – STACKS, QUEUES
2-Marks

1. Convert the following infix expression to postfix expression

using stack a + b*c+ (d +e +f)/g.
2. What is the application of stacks?
3. What are priority queues? What are ways to implement priority
queue?
4. A priority queue is implemented as a Max- heap. Initially it has 5
elements. The level order traversal of the heap is : 10,8,5,3,2. Two
new elements 11 and 7 are inserted into the heap in that order.
Give the level order traversal of the heap after the insertion of
elements.
5. List the application of the stacks.
6. State the rule to be followed during infix to postfix conversions.
7. Discuss stack and queue.
8. List the application of queue.
9. Define double ended queue.
10. What is

circular queue? 13-Marks

1. What are circular queues. Write the procedures to insert an element

to circular queue and delete an element from a circular queue using
array implementations.
2. Write algorithms to check if the given parenthesized arithmetic
expression contains balanced parenthesis and to convert such
expression to prefix form and evaluate it. Illustrate with example.
3. State the advantage of circular queue over linear queue. Write the
function for insertion in a circular queue.
4. Build the max heap for the following
90,150,70,40,100,20,30,10,110. And show the result of delete max.
5. Write an algorithm for push and pop operation on stack using linked
list.
6. What is Dequeue? Explain its operation with example.
7. Illustrate the enqueue and dequeue operations on double ended
queue.
8. Briefly describe the operations of queue with examples.
 9. Describe with an example how to evaluate arithmetic expression
using stacks.
10. 1) Describe about queue ADT in detail?
2) explain any one application of queue with suitable example?
 UNIT-III NON-LINEAR DATA STRUCTURES – TREES
2-Marks

1. For the tree in fig (a) List the siblings for node E. (b) Compute the

height.
2. How to resolve null links in a binary tree?
3. The depth of complete binary tree is 8 and compute the number
of nodes in leaf
4. What do you mean by level of the tree?
5. Define a binary search tree.
6. How do you calculate the depth of a B-tree?
7. Define a heap and show how it can be used to represent a priority
queue.
8. List out the various operation that can be performed on B-tress
9. Define balance factor of AVL tree.
10. List the

application of tree. 13-Marks

1. Write the following routines to implement the basic binary search

tree operations. (i) Perform search operation in binary Search Tree.
(ii) Find min and Find maximum.
2. 1) Write a routine for AVL tree insertion. Insert the following
elements in the empty tree and how do you balance the tree after
each element insertion? Elements: 2,5,4,6,7,9,8,3,1,10.
2) Brief about B+ tree. And discuss the application oh heap.
3. 1) write a routine for post order traversal. Is it possible to find
minimum and maximum value in the binary search tree using
traversal? Discuss.
2) Display the given tree (figure 13. a) using in order, Pre order and
postorder traversals.
 3) Delete 11 and 10 from the above binary search tree. And
display the tree after each deletion.
4. Explain the tree traversal techniques with an example.
5. How to insert and delete an element into a binary search tree and
write down the code for the insertion routine with an example.
6. Write an algorithm for inserting and deleting a node in a binary
search tree.
7. Discuss in detail the various methods in which a binary tree can be
represented. Discuss the advantage and disadvantage of each
method.
8. Discuss the different traversal technique in a binary tree with
suitable algorithms and examples?
9. Explain the construction of expression tree with examples. Give the
applications of trees.
10. Explain the following operation on a binary search
tree with suitable algorithms.
1) Find a node.
2) Find the minimum and maximum elements of binary search
tree.

UNIT-IV NON-LINEAR DATA STRUCTURES - GRAPHS

2-Marks

1. What is the representation of the graphs?

2. Define Euler circuits.
3. What is Bi-connectivity?
4. Given a weighted, undirected graph with |V| nodes, assume all
weights are non- negative. If each edge has weight ≤ω, what can
you say about the cost of Minimum spanning tree?
5. What is meant by strongly connected in a graph?
6. Define adjacency list.
7. What is graph and its types?
8. Give the purpose of Dijkstra’s algorithm.
9. Define the length of the graph.
10. Define minimum spanning tree. Give an
example. 13-Marks

1. State and explain topological sort with suitable example.

2. Apply an appropriate algorithm to find the shortest path from ‘A’ to
every other node of A. For the given graph fig
 3. Explain in detail about strongly connected component and
illustrate with an example.
4. Find Euler path or Euler circuit using DFS for the following graph

Fig. 14b
5. Explain the depth first and breadth first traversal.
6. Explain the various application of Graphs.
7. Describe in detail about the following representation of
a graph. 1)Adjacency Matrix
2) Adjacency list.
8. 1)Explain the topological sorting of a graph G with example.
2)Quote the step wise procedure for topological sort.
9. Compare any two applications of graph with your own example.
10. Describe any one of the shortest path algorithms with suitable
example

UNIT-V SEARCHING, SORTING AND HASHING TECHNIQUES

2-Marks

1. State the complexity of binary search.

2. Compare linear search and Binary search.
3. What are the advantage and disadvantage of separate chaining
and linear probing?
4. Brief about Extendible hashing.
5. What do you mean by internal and external sorting?
6. Define radix sort.
7. What is hashing?
8. Develop the simple algorithm for a linear search.
9. Develop an algorithm for a quick sort.
10. Give the time complexities of bubble sort and quick sort.
13-Marks

1. State and explain the shell sort. State and explain the algorithm for
shell sort. Sort the element using shell sort.
2. Distinguish between linear search and binary search. State and
explain the algorithms for both the search with example.
3. Consider a hash table with 9 slots. The hash function is h(k)=k mod
9. The following keys are inserted in the order
5,28,19,15,20,33,12,17,10. Draw the contents of the hash table
when the collision are resolved by
1) chaining
2) linear probing
3) double hashing. The second hash function h2(x)=7-(x mod 7)
4. 1)Write a function to perform merge sort. Give example
2) write a routine for insertion sort. Sort the following sequence using
insertion sort.3,10,4,2,8,6,5,1.
5. Write an algorithm to implement selection sort with suitable
example.
6. Write an algorithm for binary search with suitable example.
7. Describe how the divide and conquer technique is implemented
in a binary search.
8. Explain the various collision techniques in detail with an example.
9. 1)sort the sequence 3,1,4,1,5,9,2,6,5 using insertion sort.
2)Describe the routine for insertion sort.

10. Describe the open addressing and chaining methods of

collusion resolution techniques in hashing.