Data Structures:

1) Explain the classification of data structure. (***)

Ans.: Data Structure is defined as the particular way of organizing data and operations
performed on that data. Data structure is mainly classified as Primitive and Non-primitive Data
structures The Data structures that can be manipulated directly by machine-level instructions are
called Primitive Data structures. E.g. integers, floating-point numbers, characters, pointers, etc.
DS Organising data + Operations on the data

Non-primitive data structures are derived from the primitive data structures. These are more
complex data structures. The Non-Primitive Data structures are further classified as
(a) Linear, and (b) Non-linear Data structures.
Linear Data structures show the relationship of logical adjacency between the elements. E.g.
Arrays, Queues, stacks, Linked lists.
The Non-linear Data structures show relationship other than logical adjacency. E.g.: Trees,
Graphs.
or Data structures

Primitive Data structures Non- primitive Data structures

E.g.: Integer, Linear Data structures Non-linear Data structures

floating point,
character, E.g.: Arrays, E.g.: Trees,
pointer, etc. Stacks, Graphs
Queues,
Linked list

2) What are the various operations performed on Primitive data structures? (***)
Ans.: The various operations that can be performed on primitive data structures are:
Create: This operation creates a new data structure. That is, it creates (or allocates or reserves)
memory space to store the data items.
For e.g.: int n;
It creates memory space at the time of compilation to store the value of ‘n’.

Destroy: It is used to destroy or remove the data structures from the memory space. When the
program execution ends, the data structure has to be automatically destroyed and the memory
allocated should be freed (or de-allocated).
E.g.: C++ uses delete operator to de-allocate block of memory (even destructors are used in C++
for this purpose; Java uses garbage collector to de-allocate unused memory).
Select: Select operation is used to access the data within data structure. For e.g.:
total=a+b; sum=sum+n; (Values of a & b are selected for addition)

Update: Update operation is used to change or modify data in the data structure.
For e.g.: int maxmarks ; //Creation
maxmarks = 100 ; //Update operation
Later, it may be changed or updated as: maxmarks = 70;
n=n+1; n=n+2, etc.
3) Difference between Linear Search and Binary Search ***
Linear Search Binary Search
Elements of an array need not be in an order Elements of an array need to be stored in an
order
Searching starts from the 1st position. Searching starts from the Middle position
Does not divide the array into 2 parts Divides the array into 2 parts while searching
Maximum number of comparisons involved Maximum number of comparisons involved
are N. are log2N. (Number of comparisons required
are lesser.)
4) Write an algorithm to Delete an element from the array ***
Algorithm: A is an array with N elements. P is the position of the element to be
deleted.
Step 1: for (I = P to N-1) // from the given position till end of the array
A[I] = A[I+1] // Shift all the elements.
End of for
Step 2: N = N-1 // Decrement array size
Step 3: Exit

5) Write an algorithm for Traversal in an array. ***

Algorithm: A is the array with N elements.
for (I = 0 to N-1) // Access array elements once from the 1st position till end
Print A[I] // or Read A[I] or sum=sum+A[I]. Do any operation
End of for
6) List any 3 Applications of Stacks. ***
 Conversion of infix expression into prefix or postfix expression.
 Evaluation of Expression.
 Function execution
 Recursive function call
 To keep track of changes made in text editor (or To do “undo” operation in text editors)
 To keep track of the WebPages visited while browsing.
7) What is a queue? What are its types? ***
A queue is an ordered collection of items where the addition of new items and the removal of
existing items is done at different ends. Queue can be of four types:
a. Simple Queue
b. Circular Queue
c. Priority Queue
d. DEqueue (Double Ended queue)

8) Show the memory representation of a stack.

 a[0] a[1] a[2] a[3] a[4] or
a[4]
11 22 33
a[3]
top =2
a[2] 33
top refers / points to top of the stack. top =2
a[1] 22
33 is the top element in the stack.
a[0] 11

9) Write the memory representation of a Queue.

Front=0
a[0] a[1] a[2] a[3] a[4] Front points to front element in the Queue
11 22 33 Rear points to rear element in the Queue.
Array a is used to store the Queue elements

Rear =2

5-Marks Questions:
10) What are the various operations performed on arrays (or linear data structures) ? ***
Ans.: The basic operations on Arrays or linear data structures are as follows:
 Traversal: The process of accessing each data item exactly once to perform some operation
is called traversing. e.g.: reading, or printing array elements.
 Insertion: The process of adding a new data item into the given collection of data items is
called insertion.
 Deletion: The process of removing an existing data item from the given collection of data
items is called deletion.
 Searching: The process of finding the location of a data item in the given collection of data
items is called as searching.
 Sorting: The process of arranging the data items in ascending or descending order is
called sorting.
 Merging: The process of combining the data items of two linear data structures to form a
single data structure is called merging.
11) Write an algorithm to Insert an element into an array at a given position. (***)
Ans.: To insert an element at a given position, shift all the subsequent elements into the higher
order position from the end (or last Index).
Algorithm: Insertion(A,N,ELE,P): A is an array with N elements. ELE is the element to
be inserted at position P.
Step 1: for (I = N-1 downto P) //Shift all the elements from last position to
A[I+1] = A[I] //given position to provide space
End of for
Step 2: A[P] = ELE // insert new element at given position
Step 3: N = N+1 //Increment array size
Step 4: Exit

12) Write an Algorithm for Insertion sort. (***)

Algorithm- InsertionSort(A,N): Let, A is an array with N elements in unsorted order. The
following algorithm sorts the elements in Ascending order.
Step 1: for ( I = 1 to N-1)
Step 2: J=I [for Number of comparisons]
Step 3: while (J>0 and A[J]<A[J-1] ) // Insert element at the right place
temp=A[J-1]
A[J-1] = A[J] // Insert smaller number in the previous position
A[J]=temp
J=J-1 // Decrement number of comparisons
End of while
Step 4: End of for
Step 5: Exit

13) Write an Algorithm for Linear search. ***

Algorithm: LinearSearch(A,N,ELE) : A is an array with N elements. ELE is the element
to be found in the given Array. LOC is the Location of the element found.
Step 1: LOC=-1 // Initially, No element found
Step 2: for(P= 0 to N-1) // Start searching from beginning to end
if(A[P]=ELE)
LOC=P // Copy the position of the element found
GOTO STEP3
End of if
End of for

Step 3: if (LOC>=0)
PRINT “Found at”, LOC
else
PRINT “Not Found”

14) Write an Algorithm to find “Frequency of Occurrence of an element in a given array”. (i.e.,
Number of times an element exists in an array). ***
Algorithm: FreqOccurence (A,N,ELE) : A is an array with N elements. ELE is the
element to search in the given Array. FREQ is the number of times the element found.
Step 1: FREQ=0 // Initially, Number of times element found is Zero
Step 2: for(P= 0 to N-1) // Start searching from beginning to end
if(A[P]=ELE)
FREQ=FREQ+1 // Increment frequency of occurrence
End of if
End of for
Step 3: if (FREQ>0)
PRINT “Found”, FREQ, “Times”
else
PRINT “Not Found”

15) Write an Algorithm for Binary search. (***)

Algorithm: BinarySearch(A,N,KEY) : A is a sorted array with N elements. KEY is the
element to be found in the given Array. SI, the Starting Index and EI, the Ending Index
respectively. MID is the mid position of the Array segment.
Step 1: LOC=-1, SI=0, EI=N-1 // Initially, element NOT found
Step 2: while (SI <= EI) // Repeat till (startingIndex <= endingIndex)
MID= (SI+EI)/2 // Calculate mid position
if (KEY = A[MID] ) // Is the search element is at mid position
LOC = MID
GOTO Step3
else if (KEY < A[MID]) // Search element is < mid element ?
EI = MID-1 // Divide the array into 2 parts
else
SI = MID+1 // No, Search element is > mid element
End of while
Step 3: if (LOC >= 0)
PRINT “Element found at:”, LOC
else
PRINT “Element NOT found”
Step 4: Exit

16) Write about different Stack operations. (***)

stack(): Creates an empty stack.
push(item): Adds a new item to the top of the stack.
pop(): Removes the top item from the stack.
peek(): Returns the top item from the stack but does not remove it.
isEmpty(): Tests whether the stack is empty.
size(): Returns the number of items on the stack.

17) Write an algorithm to PUSH an item onto the stack. (***)

PUSH (STACK, N, TOP, ITEM)
This procedure inserts ITEM into the STACK. STACK is an array that contains N elements. TOP
is a pointer to the top element of the array. ITEM is the element to be inserted.
Step 1: If (TOP = N-1) then [check whether stack is full]
PRINT “Stack Overflow” // Since stack is full
Exit
End of If
Step 2: TOP = TOP + 1 [Increment the TOP pointer]
Step 3: STACK[TOP] = ITEM [Insert the ITEM]
Step 4: Return
Note: If stack is not full, then only we can insert an element. So, In step1, check whether stack is full

18) Write an algorithm to POP an item from the stack. (***)

Ans.: POP (STACK, TOP): This procedure deletes top element from STACK. STACK is an
array that store N items. TOP is a pointer to the top element of the array.
Step 1: If (TOP = -1) then [check whether stack is empty]
PRINT “Stack Underflow” // Since, stack is empty
Exit
End of If
Step 2: ITEM = STACK[TOP] [Copy the top element / item to be deleted]
Step 3: TOP = TOP – 1 [Decrement the top]
Step 4: Return
Note: If stack is not empty, then only we can delete an element. So, first check whether stack is empty.

Queue
A queue is a FIFO (first-in first-out) data structure where the addition of new items takes
place at the REAR end and the removal of existing items takes place at FRONT end.

A queue is an ordered collection of items where the addition of new items is done at rear
end and the removal of existing items is done at front end. Queues can be of four types:
a. Simple Queue
b. Circular Queue
c. Priority Queue
d. DEqueue (Double Ended queue).

Types Of Queues
Queue can be of four types:
1. Simple Queue
2. Circular Queue
3. Priority Queue
4. Double Ended Queue
Simple Queue

⚫ In a simple queue, insertion takes place at the rear and removal occurs at
the front. It strictly follows FIFO rule.

Circular Queue

⚫ The last element points to the first element making a circular link.

⚫ Advantage of a circular queue over a simple queue is better memory

utilization.

⚫ If the last position is full and the first position is empty then, an
element can be inserted in the first position.
Priority Queue

⚫ A priority queue is a special type of queue in which each element is associated with a
priority value and is served according to its priority.

⚫ For example, if you add an element with a high priority value to a priority queue, it may
be inserted near the front of the queue, while an element with a low priority value may
be inserted near the rear end.

⚫ In priority queue, the values are removed on the basis of priority. The
element with the highest priority is removed first.

⚫ Elements with the same priority occur, they are served according to their
order in the queue.

Dequeue (Double Ended queue)

⚫ Double Ended Queue is a type of queue in which insertion and removal of

elements can be performed either from the front or rear end.

⚫ Thus, it does not follow FIFO rule (First In First Out).

 Enqueue Operation / Insertion:

 First, check if the queue is full or not.

 For the first element, set the value of FRONT to 0.
 Increment the REAR index by 1.
 Add the new element in the position which was pointed by REAR.

Algorithm to Insert an element into the Queue:

Enqueue( QUEUE, N, FRONT, REAR, ITEM )

QUEUE is an array consisting of N elements. REAR pointer contains the location
of the last element. ITEM is the element to be inserted.
Step 1: If (REAR = N-1) Then [Check for overflow]
PRINT “Q Overflow”
Exit
Step 2 If (FRONT = NULL) Then [Check whether QUEUE is empty]
FRONT = 0
REAR = 0
Else
REAR = REAR + 1 [Increment REAR Pointer]
Step 3: QUEUE[REAR] = ITEM [Copy ITEM to REAR position]
Step 4: Return

DEQUEUE Operation / Remove / Delete

 First, check if the queue is empty
 Return the value pointed by FRONT
 Increase the FRONT index by 1
 For the last element, reset the values of FRONT and REAR to -1

Algorithm to Delete an element from the Queue:

Dequeue(QUEUE, FRONT, REAR): QUEUE is an array consisting of N elements. FRONT
pointer contains the location of the element to be deleted. REAR contains the location of the last
element.
Step 1: If ( FRONT = NULL ) Then [Check whether QUEUE is empty]
PRINT “Q Underflow”
Exit
Step 2: ITEM = QUEUE[FRONT] [element deleted from the queue]
Step 3: If ( FRONT = REAR ) Then [If QUEUE has only one element]
FRONT = NULL
REAR = NULL
Else
FRONT = FRONT + 1 [Increment FRONT pointer, after deletion]
Step 4: Return

Different operations that can be performed on a queue

a). queue(): Creates a new empty queue.
b). enqueue(item): Adds a new item to the rear of the queue.
c). dequeue(): Removes the front item from the queue.
d) peek(): Returns the element at the rear end without removing it.
e). size() : Returns the number of items in the queue.
f). isEmpty(): Tests to see whether the queue is empty.

Application of QUEUES

• CPU scheduling
• Disk Scheduling
• Handling of interrupts in real-time systems.
• Call Center phone systems use Queues to hold people calling them in order.
• Queues in routers/ switches
• Mail Queues
• Spooling in printers
• Handling Buffer for devices like keyboard
• Memory management