DS THEORY

Q1)Define data structure. Write a short note on classification of data structure .

ANS) Data structures are a specific way of organizing data in a specialized

format on a computer so that the information can be organized, processed,
stored, and retrieved quickly and effectively.

1] Linear data structure: Data structure in which data elements are arranged
sequentially or linearly, where each element is attached to its previous and
next adjacent elements, is called a linear data structure.

Examples of linear data structures are array, stack, queue, linked list, etc.

* Static data structure: Static data structure has a fixed memory size. It is
easier to access the elements in a static data structure.

An example of this data structure is an array.

* Dynamic data structure In dynamic data structure, the size is not fixed. It can
be randomly updated during the runtime which may be considered efficient
concerning the memory (space) complexity of the code.

Examples of this data structure are queue, stack, etc.

2] Non-linear data structure: Data structures where data elements are not
placed sequentially or linearly are called non-linear data structures. In a non-
linear data structure, we can’t traverse all the elements in a single run only.

Examples of non-linear data structures are trees and graphs.

Q2)What do you mean by complexity of an algorithm? Explain its types

Ans) Complexities of an Algorithm:

The complexity of an algorithm computes the amount of time and spaces

required by an algorithm for an input of size (n). The complexity of an algorithm
can be divided into two types. The time complexity and the space complexity.
Time Complexity of an Algorithm:

The time complexity is defined as the process of determining a formula for total
time required towards the execution of that algorithm. This calculation is totally
independent of implementation and programming language.

Space Complexity of an Algorithm:

Space complexity is defining as the process of defining a formula for prediction of

how much memory space is required for the successful execution of the
algorithm. The memory space is generally considered as the primary memory

Q3)Write a short note on primitive and abstract data type.

Ans) Primitive Data Type (Primitive Data Structure):

A primitive data type is a data type that is predefined. The predefined data type is
also known as built-in data type. These primitive data type may be different for
different programming languages. For example- int, float, char etc.

Non Primitive Data Type (Non Primitive Data Structure):

Non primitive data type is a data type that is not predefined. It is defined by the
user like arrays, linked list, files etc.

An abstract data type (ADT) is a mathematical model for data types. An abstract
data type is defined by its behavior (semantics) from the point of view of a user,
of the data, specifically in terms of possible values, possible operations on data of
this type, and the behavior of these operations.

Q6) Write and explain Merge sort algorithm using suitable example.

Ans) Merge sort is a sorting technique based on divide and conquer technique.
With worst-case time complexity being Ο(n log n), it is one of the most respected
algorithms.
Merge sort first divides the array into equal halves and then combines them in a
sorted manner.

To understand merge sort, we take an unsorted array as the following −

We know that merge sort first divides the whole array iteratively into equal halves
unless the atomic values are achieved. We see here that an array of 8 items is
divided into two arrays of size 4.

This does not change the sequence of appearance of items in the original. Now
we divide these two arrays into halves.

We further divide these arrays and we achieve atomic value which can no more
be divided.

Now, we combine them in exactly the same manner as they were broken down.
The smaller value will be placed first.

In the next iteration of the combining phase, we compare lists of two data values,
and merge them into a list of found data values placing all in a sorted order.

After the final merging, the list should look like this −
Q7) Write a short note on Link list
Ans) A linked list is a sequence of data structures, which are connected together
via links.
Linked List is a sequence of links which contains items. Each link contains a
connection to another link. Linked list is the second most-used data structure
after array.
Types of Linked List
Following are the various types of linked list.
 Simple Linked List − Item navigation is forward only.
 Doubly Linked List − Items can be navigated forward and backward.
 Circular Linked List − Last item contains link of the first element as next and
the first element has a link to the last element as previous.
Q13) What is Stack? Explain its operations.
Ans )A stack is a data structure which is used to store data in a linear fashion. It
follows a Last in, First out (LIFO) principle i.e. the data which is inserted most
recently in the stack will be deleted first from the stack. Some of the stack
operations are given below. The following are some common operations
implemented on the stack:
o push(): When we insert an element in a stack then the operation is known
as a push. If the stack is full then the overflow condition occurs.
o pop(): When we delete an element from the stack, the operation is known
as a pop. If the stack is empty means that no element exists in the stack,
this state is known as an underflow state.
o isEmpty(): It determines whether the stack is empty or not.
o isFull(): It determines whether the stack is full or not.'
o peek(): It returns the element at the given position.
o count(): It returns the total number of elements available in a stack.
o change(): It changes the element at the given position.
o display(): It prints all the elements available in the stack.
 Q16)Write a note on insertion and deletion in Queue data structure.
o Queue is a linear data structure where the first element is inserted from
one end called REAR and deleted from the other end called as FRONT.
o Front points to the beginning of the queue and Rear points to the end of
the queue.
o Queue follows the FIFO (First - In - First Out) structure.
o According to its FIFO structure, element inserted first will also be removed
first.
o In a queue, one end is always used to insert data (enqueue) and the other
is used to delete data (dequeue), because queue is open at both its ends.
o The enqueue() and dequeue() are two important functions used in a
queue.

Q17)Define Recursion. Also explain when to use it and its demerits

Ans) Recursion is the programming technique that uses the algorithm of
calling itself to meet a specific condition.
Advantages Disadvantages

Solve problem which is

Slower than nonrecursive function
naturally recursive.

Reduce unnecessary calling

Requires lots of memory
of function

Reduce the length of code Not more effective in terms of space and time
 Help in solving data structure
Hard to analyze code
problems

Computer runs out of memory if recursive calls

Stack evolution and infix
are not properly checked.

Q24)Explain the various tree traversal techniques.

Ans)Traversal is a process to visit all the nodes of a tree and may print their values
too. Because, all nodes are connected via edges (links) we always start from the
root (head) node. That is, we cannot randomly access a node in a tree. There are
three ways which we use to traverse a tree −
 In-order Traversal
 Pre-order Traversal
 Post-order Traversa
In-order Traversal

In this traversal method, the left subtree is visited first, then the root and later
the right sub-tree..

Pre-order Traversal

In this traversal method, the root node is visited first, then the left subtree and
finally the right subtree.

Post-order Traversal
In this traversal method, the root node is visited last, hence the name. First we
traverse the left subtree, then the right subtree and finally the root node.
Q25)Define the following Graph Terminologies: 1. Directed Graph 2. Out degree
and In degree 3. Adjacent Vertices 4. Hamiltonian Path 5. Multigraph
1) a directed graph (or digraph) is a graph that is made up of a set
of vertices connected by directed edges, often called arcs.
2)Indegree-The number of edges coming into a vertex in a directed graph.
Outdegree-Outdegree of vertex V is the number of edges which are going out
from the vertex V.

3)Adjacent Vertices-Two node or vertices are adjacent if they are connected to

each other through an edge.

4) Hamiltonian Path-A Hamiltonian path or traceable path is a path that visits

each vertex of the graph exactly once.

5)Multigraph-A graph is said to be a multigraph if the graph doesn't consist of

any self-loops, but parallel edges are present in the graph