## EE 2204 Data Structure & Algorithm (DSA) Anna University Important Questions 2 marks and 16 marks questions | EE2204 important questions from all 5 units for 3rd semester EEE dpt ( included 5 sets of AU previous year question paper) ...

## Posted by R.Anirudhan

## **we will update the important questions and topics soon ..here we have listed the repeated questions asked in AU question Papers**

CLICK HERE TO DOWNLOAD DSA IMPORTANT QUESTIONS & 5 sets 0f Question papers

#
EE2204 DATA
STRUCTURES AND ALGORITHMS 3
0 0 3

**Unit 1**

**Part a**

**1. What is meant by an abstract data type?**

An
ADT is a set of operation. Abstract data types are mathematical
abstractions.Eg.Objects such as list, set and graph along their operations can
be

viewed as ADT’s.

viewed as ADT’s.

**2. What are the operations of ADT?**ADT.

**3. What is meant by list ADT?**

List
ADT is a sequential storage structure. General list of the form a1, a2,

a3.…., an and the size of the list is ‘n’. Any element in the list at the position I is

defined to be ai, ai+1 the successor of ai and ai-1 is the predecessor of ai.

b.Insert

c.Make empty

d.Remove

e.Next

f.Previous

g.Find kth

a. Simple array implementation of list

b.Linked list implementation of list

a. Print list operation can be carried out at the linear time

b. Find Kth operation takes a constant time

a3.…., an and the size of the list is ‘n’. Any element in the list at the position I is

defined to be ai, ai+1 the successor of ai and ai-1 is the predecessor of ai.

**4. What are the various operations done under list ADT?**

a**.**Print listb.Insert

c.Make empty

d.Remove

e.Next

f.Previous

g.Find kth

**5. What are the different ways to implement list?**a. Simple array implementation of list

b.Linked list implementation of list

**6. What are the advantages in the array implementation of list?**a. Print list operation can be carried out at the linear time

b. Find Kth operation takes a constant time

**7. What is a linked list?**
Linked
list is a kind of series of data structures, which are not necessarily

adjacent in memory. Each structure contains the element and a pointer to a record

containing its successor.

adjacent in memory. Each structure contains the element and a pointer to a record

containing its successor.

**8. What is a pointer?**

Pointer is a variable,
which stores the address of the next element in the list.

Pointer is basically a number.

Pointer is basically a number.

**9. What is a doubly linked list?**
In a simple linked list,
there will be one pointer named as ‘NEXT

POINTER’ to point the next element, where as in a doubly linked list, there will be

two pointers one to point the next element and the other to point the previous

element location.

POINTER’ to point the next element, where as in a doubly linked list, there will be

two pointers one to point the next element and the other to point the previous

element location.

**10. Define double circularly linked list?**
In a doubly linked list,
if the last node or pointer of the list, point to the first

element of the list, then it is a circularly linked list.

element of the list, then it is a circularly linked list.

**11. What is the need for the header?**
Header of the linked list
is the first element in the list and it stores the

number of elements in the list. It points to the first data element of the list.

a. Polynomial ADT

b.Radix sort

c.Multi lists

b.Queue

number of elements in the list. It points to the first data element of the list.

**12. List three examples that uses linked list?**a. Polynomial ADT

b.Radix sort

c.Multi lists

**13. Give some examples for linear data structures?**

a. Stackb.Queue

**14. What is a stack?**
Stack is a data structure
in which both insertion and deletion occur at one

end only. Stack is maintained with a single pointer to the top of the list of

elements. The other name of stack is Last-in -First-out list.

end only. Stack is maintained with a single pointer to the top of the list of

elements. The other name of stack is Last-in -First-out list.

**15. Write postfix from of the expression –A+B-C+D?**
A-B+C-D+

**16. How do you test for an empty queue?**
To test for an empty
queue, we have to check whether READ=HEAD

where REAR is a pointer pointing to the last node in a queue and HEAD is a

pointer that pointer to the dummy header. In the case of array implementation of

queue, the condition to be checked for an empty queue is READ<FRONT.

where REAR is a pointer pointing to the last node in a queue and HEAD is a

pointer that pointer to the dummy header. In the case of array implementation of

queue, the condition to be checked for an empty queue is READ<FRONT.

**17.What are the postfix and prefix forms of the expression?**

A+B*(C-D)/(P-R)

Postfix form: ABCD-*PR-/+

Prefix form: +A/*B-CD-PR

Postfix form: ABCD-*PR-/+

Prefix form: +A/*B-CD-PR

**18. Explain the usage of stack in recursive algorithm implementation?**
In recursive algorithms,
stack data structures is used to store the return

address when a recursive call is encountered and also to store the values of all the parameters essential to the current state of the procedure.

address when a recursive call is encountered and also to store the values of all the parameters essential to the current state of the procedure.

**19. Write down the operations that can be done with queue data structure?**
Queue is a first – in -first
out list. The operations that can be done with

queue are addition and deletion.

queue are addition and deletion.

**20. What is a circular queue?**
The queue, which wraps
around upon reaching the end of the array is called

as circular queue.

as circular queue.

**Unit 1 part B**

**1. Explain the linked list implementation of list ADT in Detail?**

a

**.**Definition for linked list

b. Figure for linked list

c. Next pointer

d. Header or dummy node

e. various operations

f. Explanation

g. Example figure

h. Coding

**2. Explain the cursor implementation of linked list?**

a

**.**Definition for linked list

b. Figure for linked list

c. Next pointer

d. Header or dummy node

e. various operations

f.Explanation

g.Example figure

h.Coding

**3. Explain the various applications of linked list?**

a. Polynomial ADT

Operations

Coding

Figure

b. Radix Sort

Explanation

Example

c. Multilist

Explanation

Example figure

**4. Explain the linked list implementation of stack ADT in detail?**

a

**.**Definition for stack

b. Stack model

c.Figure

d.Pointer-Top

e.Operations

f.Coding

g.Example figure

**5. Explain the array implementation of queue ADT in detail?**

a

**.**Definition for stack

b. Stack model

c. Figure

d. Pointer-FRONT, REAR

e. Operations

f.Coding

g.Example figure

**Unit 2& 3**

**Part A**

**1. Define non-linear data structure**

Data structure which is
capable of expressing more complex relationship

than that of physical adjacency is called non-linear data structure.

than that of physical adjacency is called non-linear data structure.

**2. Define tree?**
A tree is a data
structure, which represents hierarchical relationship between

individual data items.

individual data items.

**3. Define leaf?**
In a directed tree any
node which has out degree o is called a terminal node

or a leaf.

or a leaf.

**4. What is meant by directed tree?**
Directed tree is an
acyclic diagraph which has one node called its root with

in degree o while all other nodes have indegree
I.

in degree o while all other nodes have in

**5. What is a ordered tree?**
In a directed tree if the
ordering of the nodes at each level is prescribed then

such a tree is called ordered tree.

such a tree is called ordered tree.

**6. What are the applications of binary tree?**
Binary tree is used in
data processing.

a. File index schemes

b. Hierarchical database management system

a. File index schemes

b. Hierarchical database management system

**7. What is meant by traversing?**
Traversing a tree means
processing it in such a way, that each node is

visited only once.

visited only once.

**8. What are the different types of traversing?**
The different types of
traversing are

a. Pre-order traversal-yields prefix from of expression.

b. In-order traversal-yields infix form of expression.

c. Post-order traversal-yields postfix from of expression.

a. Pre-order traversal-yields prefix from of expression.

b. In-order traversal-yields infix form of expression.

c. Post-order traversal-yields postfix from of expression.

**9. What are the two methods of binary tree implementation?**
Two methods to implement
a binary tree are,

a. Linear representation.

b. Linked representation

a. Linear representation.

b. Linked representation

**10. Define pre-order traversal?**
Pre-order traversal
entails the following steps;

a. Process the root node

b. Process the left subtree

c. Process the right subtree

a. Process the root node

b. Process the left subtree

c. Process the right subtree

**11.Define post-order traversal?**
Post order traversal
entails the following steps;

a. Process the left subtree

b. Process the right subtree

c. Process the root node

a. Process the left subtree

b. Process the right subtree

c. Process the root node

**12. Define in -order traversal?**
In-order traversal
entails the following steps;

a. Process the left subtree

b. Process the root node

c. Process the right subtree

a. Process the left subtree

b. Process the root node

c. Process the right subtree

**13. What is a balance factor in AVL trees?**
Balance factor of a node
is defined to be the difference between the height

of the node's left subtree and the height of the node's right subtree.

of the node's left subtree and the height of the node's right subtree.

**14. What is meant by pivot node?**
The node to be inserted
travel down the appropriate branch track along the

way of the deepest level node on the branch that has a balance factor of +1 or -1 is

called pivot node.

way of the deepest level node on the branch that has a balance factor of +1 or -1 is

called pivot node.

**15. What is the length of the path in a tree?**
The length of the path is
the number of edges on the path. In a tree there is

exactly one path form the root to each node.

exactly one path form the root to each node.

**16. Define expression trees?**
The leaves of an
expression tree are operands such as constants or variable

names and the other nodes contain operators.

names and the other nodes contain operators.

**17. What is the need for hashing?**
Hashing is used to
perform insertions, deletions and find in constant

average time.

average time.

**18. Define hash function?**
Hash function takes an
identifier and computes the address of that identifier

in the hash table using some function.

in the hash table using some function.

**19. List out the different types of hashing functions?**
The different types of
hashing functions are,

a. The division method

b. The mind square method

c. The folding method

d. Multiplicative hashing

e. Digit analysis

b. Overflow

a. The division method

b. The mind square method

c. The folding method

d. Multiplicative hashing

e. Digit analysis

**20. What are the problems in hashing?**

a. Collisionb. Overflow

**21. What are the problems in hashing?**
When two keys compute in
to the same location or address in the hash table

through any of the hashing function then it is termed collision.

through any of the hashing function then it is termed collision.

**Unit 2 and 3 part B**

**1. Explain the different tree traversals with an application?**

a

**.**In order

Explanation with an example

Figure

b. Preorder

Explanation with an example

Figure

c. Post order

Explanation with an example

Figure

**2. Define binary search tree? Explain the various operations with an example?**

a

**.**Definition

b. Figure for binary search tree

c. Operations

d.Codings

e.Explanation

f.Example

**3. Define AVL trees? Explain the LL, RR, RL, LR case with an example?**

a

**.**Definition

b. LL, RR, RL, LR case

c.Figure

d.Example

e.Explanation

**4. Define priority queue? Explain the basic heap operation with an example?**

a

**.**Definition

b. Basic operation

Insert

Delmin

Delmax

c. Coding

d. Explanation

e.Example

**5. Explain any two techniques to overcome hash collision?**

a

**.**Separate chaining

Example

Explanation

coding

b. Open addressing

Linear probing

Quadratic probing

**Unit 4**

**Part A**

**1. Define Graph?**

A graph G consist of a
nonempty set V which is a set of nodes of the graph,

a set E which is the set of edges of the graph, and a mapping from the set for edge

E to a set of pairs of elements of V. It can also be represented as G=(V, E).

a set E which is the set of edges of the graph, and a mapping from the set for edge

E to a set of pairs of elements of V. It can also be represented as G=(V, E).

**2. Define adjacent nodes?**
Any two nodes which are
connected by an edge in a graph are called

adjacent nodes. For E is associated with a pair of nodesÃŽexample, if and edge x

(u,v) where u, v V, then we say that the edge x connects the nodes u and v. ÃŽ

adjacent nodes. For E is associated with a pair of nodesÃŽexample, if and edge x

(u,v) where u, v V, then we say that the edge x connects the nodes u and v. ÃŽ

**3. What is a directed graph?**
A graph in which every
edge is directed is called a directed graph.

**4. What is a undirected graph?**
A graph in which every
edge is undirected is called a directed graph.

**5. What is a loop?**
An edge of a graph which
connects to itself is called a loop or sling.

**6. What is a simple graph?**
A simple graph is a
graph, which has not more than one edge between a

pair of nodes than such a graph is called a simple graph.

pair of nodes than such a graph is called a simple graph.

**7. What is a weighted graph?**
A graph in which weights
are assigned to every edge is called a weighted

graph.

graph.

**8. Define out degree of a graph?**
In a directed graph, for
any node v, the number of edges which have v as

their initial node is called the out degree of the node v.

their initial node is called the out degree of the node v.

**9. Define indegree of a graph?**
In a directed graph, for
any node v, the number of edges which have v as

their terminal node is called the indegree of the node v.

their terminal node is called the indegree of the node v.

**10. Define path in a graph?**
The path in a graph is
the route taken to reach terminal node from a starting

node.

node.

**11. What is a simple path?**

A path in a diagram in
which the edges are distinct is called a simple path.

It is also called as edge simple.

It is also called as edge simple.

**12. What is a cycle or a circuit?**
A path which originates
and ends in the same node is called a cycle or

circuit.

circuit.

**13. What is an acyclic graph?**
A simple diagram which
does not have any cycles is called an acyclic

graph.

graph.

**14. What is meant by strongly connected in a graph?**
An undirected graph is
connected, if there is a path from every vertex to

every other vertex. A directed graph with this property is called strongly

connected.

every other vertex. A directed graph with this property is called strongly

connected.

**15. When is a graph said to be weakly connected?**
When a directed graph is
not strongly connected but the underlying graph is

connected, then the graph is said to be weakly connected.

b. Adjacency list

connected, then the graph is said to be weakly connected.

**16. Name the different ways of representing a graph?**

a. Adjacency matrixb. Adjacency list

**17. What is an undirected acyclic graph?**
When every edge in an
acyclic graph is undirected, it is called an undirected

acyclic graph. It is also called as undirected forest.

b. Depth first search

acyclic graph. It is also called as undirected forest.

**18. What are the two traversal strategies used in traversing a graph?**

a. Breadth first searchb. Depth first search

**19. What is a minimum spanning tree?**
A minimum spanning tree
of an undirected graph G is a tree formed from

graph edges that connects all the vertices of G at the lowest total cost.

graph edges that connects all the vertices of G at the lowest total cost.

**20. What is NP?**
NP is the class of
decision problems for which a given proposed solution

for a given input can be checked quickly to see if it is really a solution.

for a given input can be checked quickly to see if it is really a solution.

**Unit 4 part B**

**1. Explain the various representation of graph with example in detail?**

a

**.**Adjacency matrix

Figure

Explanation

Table

b. Adjacency list

Figure

Explanation

Table

**2. Define topological sort? Explain with an example?**

a. Definition

b. Explanation

c. Example

d. Table

e. Coding

**3. Explain Dijkstra's algorithm with an example?**

a. Explanation

b. Example

c. Graph

d. Table

e. coding

**4.Explain Prim's algorithm with an example?**

a. Explanation

b. Example

c. Graph

d. Table

e. Coding

**5. Explain Krushal's algorithm with an example?**

a

**.**Explanation

b. Example

c. Graph

d. Table

e. Coding

**Unit V**

**Part A**

**1. Write down the definition of data structures?**

A data structure is a
mathematical or logical way of organizing data in the

memory that consider not only the items stored but also the relationship to each

other and also it is characterized by accessing functions.

memory that consider not only the items stored but also the relationship to each

other and also it is characterized by accessing functions.

**2. What is meant by problem solving?**
Problem solving is a
creative process, which needs systemization and

mechanization.

mechanization.

**3. Give few examples for data structures?**
Stacks, Queue, Linked
list, Trees, graphs

**4. What is problem definition phase?**
The first step in solving
a problem is to understand problem clearly. Hence,

the first phase is the problem definition phase. That is, to extract the task from the

problem statement. If the problem is not understood, then the solution will not be

correct and it may result in wastage of time and effort.

the first phase is the problem definition phase. That is, to extract the task from the

problem statement. If the problem is not understood, then the solution will not be

correct and it may result in wastage of time and effort.

**5. Define Algorithm?**
Algorithm is a solution
to a problem independent of programming

language. It consist of set of finite steps which, when carried out for a given set of

inputs, produce the corresponding output and terminate in a finite time.

language. It consist of set of finite steps which, when carried out for a given set of

inputs, produce the corresponding output and terminate in a finite time.

**6. Define Program?**
Set of instructions to
find the solution to a problem. It is expressed in a

programming language in an explicit and unambiguous manner.

programming language in an explicit and unambiguous manner.

**7. Mention how similarities among the problems are used in problem solving?**
This method is used to
find out if a problem of this sort has been already

solved and to adopt a similar method in solving the problem. The contribution of

experience in the previous problem with help and enhance the method of problem

for the current problem.

solved and to adopt a similar method in solving the problem. The contribution of

experience in the previous problem with help and enhance the method of problem

for the current problem.

**8. What is working backward from the solution?**
When we have a solution
to the problem then we have to work backward to

find the starting condition. Even a guess can take us to the starting of the problem.

This is very important to systematize the investigation to avoid duplication of our

effort.

find the starting condition. Even a guess can take us to the starting of the problem.

This is very important to systematize the investigation to avoid duplication of our

effort.

**9. Mention some of the problem solving strategies?**
The most widely strategies
are listed below

Divide and conquer

Binary doubling strategy

Dynamic programming

Divide and conquer

Binary doubling strategy

Dynamic programming

**10. What is divide and conquer method?**
The basic idea is to
divide the problem into several sub problems beyond

which cannot be further subdivided. Then solve the sub problems efficiently and

join then together to get the solution for the main problem.

b.Efficient in execution time

c.Concise and compact

d.Completeness

e.Definiteness

f.Finiteness

b.Operating System

c.Database Management system

d.Network analysis

which cannot be further subdivided. Then solve the sub problems efficiently and

join then together to get the solution for the main problem.

**11. What are the features of an efficient algorithm?**

a**.**Free of ambiguityb.Efficient in execution time

c.Concise and compact

d.Completeness

e.Definiteness

f.Finiteness

**12. List down any four applications of data structures?**

a**.**Compiler designb.Operating System

c.Database Management system

d.Network analysis

**13. What is binary doubling strategy?**
The reverse of binary
doubling strategy, i.e. combining small problems in to

one is known as binary doubling strategy. This strategy is used to avoid the

generation of intermediate results.

one is known as binary doubling strategy. This strategy is used to avoid the

generation of intermediate results.

**14. Where is dynamic programming used?**
Dynamic programming is
used when the problem is to be solved in a

sequence of intermediate steps. It is particularly relevant for many optimization

problems, i.e. frequently encountered in Operations research.

sequence of intermediate steps. It is particularly relevant for many optimization

problems, i.e. frequently encountered in Operations research.

**15. Define top-down design?**
Top-down design is a
strategy that can be applied to find a solution to a

problem from a vague outline to precisely define the algorithm and program

implementation by stepwise refinement.

problem from a vague outline to precisely define the algorithm and program

implementation by stepwise refinement.

**16. Mention the types of bugs that may arise in a program?**
The different types of
bugs that can arise in a program are

Syntactic error

Semantic error

Logical error

Syntactic error

Semantic error

Logical error

**17. What is program testing?**
Program testing is
process to ensure that a program solves the smallest

possible problem, when all the variables have the same value, the biggest possible

problem, unusual cases etc.

possible problem, when all the variables have the same value, the biggest possible

problem, unusual cases etc.

**18. What is program verification?**
Program verification
refers to the application of mathematical proof

techniques, to verify that the results obtained by the execution of the program with

arbitrary inputs are in accord with formally defined output Specifications.

techniques, to verify that the results obtained by the execution of the program with

arbitrary inputs are in accord with formally defined output Specifications.

**19. How will you verify branches with segments?**
To handle the branches
that appear in the program segments, it is necessary

to set-up and proves verification conditions individually.

to set-up and proves verification conditions individually.

**20. What is proof of termination?**
To prove that a program
accomplishes its stated objective in a finite number

of steps is called program termini nation. The prooft of termination is obtained

directly from the properties of the interactive constructs.

of steps is called program termini nation. The prooft of termination is obtained

directly from the properties of the interactive constructs.

**Unit V part B**

**1. Explain top-down design in detail?**

a

**.**Definition

b.Breaking a problem in to sub problems

c.Choice of a suitable data structure

d.Constructions of loops

e.Establishing initial conditions for loops

f.Finding the iterative construct

g.Terminations of loops

**2. What are the steps taken to improve the efficiency of an algorithm?**

a

**.**Definition

b.Redundant computations

c.Referencing array elements

d.Inefficiency due to late termination

e.Early detection of desired output conditions

f.Trading storage for efficiency gains

**3. Design an algorithm fro sine function computation. Explain it with an example?**

a. Algorithm development

b.Algorithm description

c.Pascal implementation

d.Application

**4. Design an algorithm for reversing the digit of an integer. Explain it with an**

example?

a. Algorithm development

example?

b.Algorithm description

c.Pascal implementation

d.Application

**5. Design an algorithm for base conversion. Explain it with an example?**

Algorithm development

Algorithm description

Pascal implementation

Application