INTRODUCTION :

1) What is Data Structure ? Explain types of data structure.

DATA STRUCTURE :
Data may be organized in different ways in computer memory. The logical or
mathematical model of particular organization of data in computers memory is called as “
Data Structure ”.
The choice of particular data structure depends on two considerations.

1 It must be rich enough in a structure to mirror actual relationship of data with

real world.
2 The structure must be simple enough so that one can effectively process the data.

TYPES OF DATA STRUCTURE :

The data structure can be classified into different data types using different criteria’s.
Following are some types of data structure.

 According to Data Organization :

a) Linear Data Structure :
The data structure in which memory locations are allocated in
continuous memory locations is called “Linear data structure”.
E.g. : Array, Stack, Queue etc.

b) Non Linear Data Structure :

The data structure in which the elements are not stored in continuously
fashion is called a “Non linear data structure”. This means that the elements are
stored randomly in computer’s memory.
E.g. : Tree, Graph etc.

 According to Memory Allocation Time Data Structure :

a) Static Data Structure :
The data structure in which memory space is reserve during the process
of compilation and it can not be increased or decreased during the process of
execution is called “Static data structure”.

b) Dynamic Data Structure :

The data structure in which the memory space is allocated at the
execution time of a program is called as “Dynamic data structure”.

 According to Data Types Data Structure :

a) Primitive Data Structure :
The most elementary data types are called as “Primitive data
structure”. They are directly operated by machine language instruction.
The structure used to represent int, char, float etc are
 primitive data structure.
b) Non Primitive Data Structure :
The data structure that are made up of data types are known
as “Non primitive data structure”. They are not directly operated by machine
language instruction.
The data structure used to represent array, structure, file etc
are known as non primitive data structure.

2) Discuss algorithmic analysis.

ALGORITHM ANALYSIS :
It is necessary to learn how to perform analysis of algorithm. The first step of analysis
is the “correctness” of an algorithm. This analysis can be done by manual execution of
algorithm on some data values.
Isolating the instructions of two types “Active instruction” and “Book keeping
instruction”. The instruction, which are executed by computer or contains arithmetic
operations are called active instruction. The instructions, which are used for initialization or
for maintaining the values of variable, are called “Book keeping instruction”.
In above algorithm there is only one active instruction, which is
SUM  SUM + A [ I ]
Suppose, this instruction requires t1 amount of time and if get executed N number of
times. Therefore, the approximate time require for above algorithm is t1 * N. Here,
bookkeeping instructions are not taken in consideration because they require minimum time
for their execution.

 Space Analysis :
It is very difficult to calculate the space analysis of a algorithm because
it requires lot of factors to be considered and therefore generally space
analysis of algorithm is not perform.

3) What is an array? Discuss the various ways to represent two dimensional

array in memory.

ARRAY :
Array is a finite set of finite number of homogeneous element which is also known as
“vector”. Array elements are stored as a successive memory set.

REPRESENTATION :

The two dimensional array can be represented by equivalent one-dimensional array in

memory. The two dimensional array requires m rows and n columns. The elements of two-
dimensional matrix can be stored either row wise or column wise.
 If the element of two dimensional matrix are stored column wise then the address of
th
( i,j ) element is given by

Loc( Ai,j ) = L0 + ( ( j – 1 ) * m + ( i – 1 ) ) * C

Similarly, to compute ( calculate ) the address of particular element in two

dimensional array which is stored row wise is

Loc( Ai,j ) = L0 + ( ( i - 1 ) * n + ( j – 1 ) )  C

4) Define following terms :

1] Entity 2] Fields 3] Records 4] Files

1) ENTITY :
Any entity has certain properties refers as attributes, which may be designed values.
The values may be either numeric or non numeric.

2) FIELDS :
It is a single elementary unit of information representing an attribute of an entity set
where entities with similar attributes ( e.g. all students in an educational institute ) from an
entity set.

3) RECORDS :
It is the collection of field’s records of a given entity such as number of students in
educational institutes.

4) FILES :
It is the collection of records of the entities in a given set. Each record in a file consists
of fields, but the values in a certain field may uniquely determine the record in a file. Such
field id called primary keys.

STACK :

1) Explain LIFO data structure.

STACK :

Stack is list of elements in which an element may be inserted or deleted only at one
end, called top of stack. This means, in particular, that elements are removed from a stack in
the reverse order of that in which they are inserted into a stack.
It is also known as FILO ( First in Last out ) type of memory because the element
which is inserted first is the element which is deleted at last. It is also called as LIFO ( Last in
First out ).
 A special terminology can be used to describe the operation of insertion and deletion.
The operation of insertion is called “PUSH” and the operation of deletion is called “POP”.

2) Convert following expression into Postfix format.

i) A+(B*C)
ii) (A+ B )/ ( C– D)
iii) ( A+ B ) / ( C + D * E )

i) A+ (B*C)
= A + ( BC* )
=A+X X = BC*
= AX+
= A*BC+

ii) ( A + B ) / (C – D )
= ( AB+ ) / ( CD- )
=X/Y X = AB+; Y = CD-
= XY/
= AB+CD-/

iii) ( A+ B ) / ( C + D * E )
= ( AB+ ) / ( C + DE* )
= ( AB+ ) / ( CDE*+ )
= AB+CDE*+/

3) Explain Stack by using linked list.

A Stack can be represented either using sequential data structure like array or non
sequential data structure like linked list.
The stack can be defined as a data structure in which elements can be inserted only
from one end called top of the stack and deleted only from one end called top of the stack i.e.
First is Last out or Last in First out.
If you want to use a linked list as a stack then, there must be the constraints on insert
and delete operation in linked list, you want insert node as well as you can delete node.
When we use linked list as stack then we can insert node only as last node and not
anywhere else. Similarly, we can delete a node, which are only last node and not any other
node.
Following algorithm shows the implement stack using link list.

ALGORITHM FOR “PUSH” OPERATION :

1) [ create new node ]

ITEM [ TEMP ] = ITEM
NEXT [ TEMP ] = NULL
 2) [ check list is present ]
If HEAD != NULL then
NEXT [ END ] = TEMP
END = TEMP

3) [ If list is Empty ]
HEAD = END= TEMP

4) Exit;

ALGORITHM FOR “POP” OPERATION :

1) [ Is list Empty ?]
If HEAD == NULL then
Print “Underflow” & Exit

2) [ Only one element present in stack ]

If HEAD == END then
HEAD = END = NULL & Exit

3) Repeat While NEXT [ TEMP ] != END

TEMP = NEXT [ TEMP ]
4) NEXT [ TEMP ] = NULL
END = TEMP

5) Exit

4) State any two application of stack. Explain.

1) POLISH NOTATIONS :

Suppose Q is an expression without parenthesis. When this expression is evaluated, it

is evaluated according to rules of priority. If you want to override the rules of priority
parenthesis are used.
In most of the expression operator symbol appears in between two operands. An
expression in which the operator symbol appears in between two operands is called infix
expression.

E.g. : a + b
a*b

Polish notation refers to the notation in which operator symbol is placed before its
operands. It is also known as prefix notation.
 E.g. : +ab
*ab

The fundamental property of polish notation is that the orders in which operator are
evaluated is completely determined by position of operator and not by priority. We never
requires parenthesis while writing expression using polish notation. The expression in polish
notation is fast for execution as compare to infix notation.

E.g. : A+(B*C)
= A + ( * BC )
= A+X * BC = X
= + AX
= + A * BC

Reverse polish notation is also called postfix notation. In this notation the operator is
placed ofter the operands.

E.g. : ab+
ab*

2) RECURSIVE FUNCTION :

Another application of stack is process of recursion in this process of recursion

actually uses. The data structure stack for maintaining the value of previous function call.
Suppose we have given program with recursion to convert it into without recursion we have
to use. The data structure stack to element recursion statement use the stack is necessary.
Recursive is a program in which a function calls itself. Such function is called
recursive function.

E.g. : Consider following program for calculate factorial of a number using recursive
function.

void main( )
{
int n=4, f;
f = Fact (n);
printf (“ \n FACTORIAL IS : %d”,f);
}

int fact (n)

{
int f;
if (n = = 1)
return 1;
else
f = n* Fact (n – 1)
return ( f );
}

The function control is transferred from main function to fact function the value 4 is
passed as an argument to the function fact when the statement :
F = n * F( n – 1)
Is executed again the function Fact ( ) called with an argument value three before calling the
second Fact( ) with argument the there the value of n will get push( ) in stack. Regularly in
different function call to Fact the value 3,2 are push in stack. The recursive process stop
when value of n = 1 transfers the control the previous control will value 1 at this stage
function POP( ) will get called relative values of n. The value 2 will get poped and whole
statement is executed. Successively the POP( ) are executed to relative top most value in
stack.

5) What is stack ? Write an algorithm to insert & delete an element from the
stack .

STACK :

Stack is list of elements in which an element may be inserted or deleted only at one
end, called top of stack. This means, in particular, that elements are removed from a stack in
the reverse order of that in which they are inserted into a stack.
It is also known as FILO ( First in Last out ) type of memory because the element
which is inserted first is the element which is deleted at last. It is also called as LIFO ( Last in
First out ).
A special terminology can be used to describe the operation of insertion and deletion.
The operation of insertion is called “PUSH” and the operation of deletion is called “POP”.

ALGORITHM FOR “INSERT” OPERATION :

PUSH : This algorithm insert element ITEM on TOP of the stack. The variable
MAXSTK gives maximum number of elements that can be stored in
stack.

1) [ Is stack full ? ]
If TOP = MAXSTK
Then write “OVERFLOW” & Exit
 2) [ Increase value of TOP ]
TOP = TOP + 1

3) [ Insert element ]
STACK [ TOP ] = ITEM

4) STOP

ALGORITHM FOR “DELETE” OPERATION :

POP : This algorithm deletes element (TOP) from stack and store it in
variable ITEM.

1) [ Is stack empty ? ]
If TOP = 0
Then print “UNDERFLOW” and Exit

2) [ Delete TOP element ]

ITEM = TOP

3) [ Decrease the TOP ]

TOP = TOP – 1

4) STOP

QUEUE :

1) Explain FIFO data structure.

QUEUE :

A queue is a linear list of elements in which deletions can take place only at one end,
called the “Front”, and insertions can take place only at the other end, called the “Rear”. The
terms “Front” and “Rear” are used in describing a linear list only when it is implemented as
a queue.
Queue a are also called “First in First out” ( FIFO ) lists, since the first element in a
queue will be the first element out of the queue. In other words, the order in which elements
enter a queue is the order in which they leave. This contrasts with stacks, which are “Last in
First out” ( LIFO ) lists.

2) State the disadvantages & advantages of stack & queue using linked list.
ADVANTAGES :
The advantages of the stack and queue are that all stacks and queue being used by a
program can share same available list. When these both need a node takes from an available
list and when stack no longer need a node it returns to available list. No space has been pre-
allocated to any single stack.
Advantage is the entire stack and queue of a program have access to the same free list
of nodes. Another may use nodes not used by one stack, as long as the total number of nodes
in use at any one time is not greater than the total number of nodes available.

DISADVANTAGES :
A node in a link list occurs more storage than a element in an array, string in a link list
Two types of information is stored ( info, pointer part i.e. next ) for a single node, where in
array only one type of information is needed ( info part ) because array elements are stored
in continuous memory location hence no need to stored address of next element.
Another disadvantage is the additional time spent in managing the available list. Each
addition and deletion of an element from stack or a queue involves a corresponding deletion
or addition to the available to the available list.

3) What is queue ? Write an algorithm to insert and delete an element to form

the queue .

QUEUE :

A queue is a linear list of elements in which deletions can take place only at one end,
called the “Front”, and insertions can take place only at the other end, called the “Rear”. The
terms “Front” and “Rear” are used in describing a linear list only when it is implemented as
a queue.
Queue a are also called “First in First out” ( FIFO ) lists, since the first element in a
queue will be the first element out of the queue. In other words, the order in which elements
enter a queue is the order in which they leave. This contrasts with stacks, which are “Last in
First out” ( LIFO ) lists.

ALGORITHM FOR INSERTION OPERATION :

This algorithm used to insert an element in queue represented by array
“QUEUE” having number of elements given by variable “MAX”. The variable “REAR”
used to insert an elements having initial value 0 and N is temporary variable.

1) [ check Queue is Full ? ]

If REAR = MAX
Then write “Queue is full” and Exit
2) [ Read element & store it in queue ]
Read N
REAR := REAR + 1
Queue[ REAR ] := N
3) [ Finish ]
 Return

ALGORITHM FOR DELETION OPERATION :

This algorithm removes an element from queue data structure represented by
an array “QUEUE” having number of elements given by “MAX”. The variable
“FRONT” used to remove element having initial value 0. N is temporary variable.

1) [check queue is Empty ? ]

If FRONT = REAR then
Write “Queue is empty.” And Exit

2) [ Remove element from queue ]

FRONT = FRONT + 1
Queue[ FRONT ] = N
Write N

3) Exit

4) Write a short note on priority queue.

PRIORITY QUEUE :

A priority queue is collection of elements such that each element has been assigned a
priority. The order in which the elements are deleted or process comes from following rules :

i) An element of higher priority is process before any element of lower priority.

ii) Two elements with some priority are process according to the order in which they
inserted in queue.

The priority queue is represented with help of “Link List” is computer’s memory.
The structure array is not suitable to represent a priority queue.
The array representation of a priority queue is more time-efficient than the one-way
list. This is because when adding an element to a one-way list, one must perform a linear
search on the list. On the other hand, the one-way list representation of the priority queue
may be more space-efficient than the array representation. This is because in using the array
representation, overflow occurs when the number of elements in any single priority level
exceeds the capacity for that level, but in using the one-way list, overflow occurs only when
the total number of elements exceeds the total capacity. Another alternative is to use a linked
list for each priority level.

5) Define term : Circular queue.

CIRCULAR QUEUE :

In simple queue there is one problem/drawback related to the overflow of queue.

When REAR reaches to the last location of queue and if we delete first two elements in
queue, even though there are empty locations, we will get message, as “Queue is full”. This
means that whenever REAR reaches at the last location and there are some empty locations
it is not possible for us to insert new element in queue.
To overcome this problem concept of circular queue is introduced. In circular queue
when FRONT & REAR reaches at the last location of queue, we will transfer them at
starting location.
In simple queue the assumption is that the location at which FRONT is pointing the element
at that location is deleted whereas in circular queue assumption that the location to which
FRONT is pointing the element at that location will delete.

LINKLIST :

1) Write an algorithm to find length of string stored as a linked list.

LENGTH : This function is used to find the length of string stored as linked list.
HEAD is a starting node of linked list.

1) [ Initialization ]
LEN = 0
TEMP = HEAD

2) [ Is list Empty ? ]
If HEAD = = NULL then
Print “List is Empty.” & Exit

3) Repeat while TEMP != NULL

TEMP = NEXT [ TEMP ]
LEN = LEN + 1

4) Print value of LEN

5) Exit

2) Explain representation of string using a linked list .

Computers are being used very frequently for word processing i.e. for inputting
processing and outputting matter. Therefore, computer must able to correct and modify
printed matter, which usually means deleting changing, and inserting words, sentences or
even paragraphs in a text. For this matter the fix length memory cells do not easily provide
all their operations.
According for most extensive word processing applications strings are stored by
means of linked list. The string can be store by two different ways one character per node or
a word per node.
Advantages :
The advantage of representing a string using a linked list is that you can perform word-
processing easily i.e. insertion, deletion or changing a character becomes easy.

Disadvantages :
The disadvantage is that the manipulating algorithms may becomes complicated.

3) Write an algorithm to count number of nodes in a link list ?

This algorithm counts number of nodes in a link list.

1) [ Initialize ptr ]
ptr = START

2) [ Initialize counter ]
count = 0

3) Repeat step 4 and 5

While ptr != NULL

4) [ Increase count ]
count := count +1

5) [ Update ptr ]
ptr := LINK [ ptr ]

6) print count

7) Exit

TREE

1) Explain the following terms :

a) Tree b) NULL Tree c) Leaf Node d) Degree of node e) Degree of Tree
f) Parent Node g) Siblings h) Desendence i) Ancestors j) Forest

a) Tree : A tree is finite set of nodes with one special node called the root and remaining
nodes are portion into n >=0 disjoined set t1,t2,……,tn where each of those sets
is a tree t1,t2,….,tn are called “Sub Trees” of the root.

b) NULL Tree : A tree with no node is a null tree.

c) Leaf Node : A Leaf node is a terminal node of a tree it does not have any node
connected to it.
d) Degree of Node : Degree of sub trees of a node is called it’s degree.
e) Degree of Tree : A degree of tree is maximum degree of the node in the tree.

f) Parent Node : A parent node is a node having other node connected to it. These nodes
are called children of that node.

g) Siblings : Children of same parents are called siblings.

h) Desendence: Desendence of a node are all those nodes, which are reachable from hat
node.

i ) Ancestors : Ancestors of a node are all the nodes along the path from the root to that
node.

j) Forest : If the root node and the edges connecting to the root to the nodes at level one are
deleted them. Number of sub trees with roots which are the nodes at level one
are obtain. This set of disjoint trees is known as “Forest”

2) Define : Level of a tree ?

The level numbers are the numbers assign to each node in a tree . A number ‘0’ is
assign to the root of tree. The level number of each node is one more than level number of
its parent.
The nodes in binary tree belongs to same level number are said to belongs to same
generation.