Q.1)What is Data structure ? Explain type of data structure.

Ans. Data structure is a branch of computer science which are a

building blocks of any program of the software.Choosing a
appropriate data structure for a program is the difficult task for
programmer.The study of data structure helps to understand the
basic concept in oraganising and storing data as well as
relationship among the dataset.It helps to determine the way of
information for storing,retrieving and modifying the data in
computer memory. It helps to understand how data is organised
and how data flow is manage to increase efficiency of any
process. The data structure is structural representation of logical
relationship between data elements.

Data structures are mainly classified into two types: linear and
non-linear data structures. In linear data structures, the elements
are arranged in a sequential manner, meaning each element is
connected to the one before and after it. Examples of linear data
structures include arrays, linked lists, stacks, and queues. An
array is a collection of elements stored in contiguous memory
locations and is used when the number of data elements is known
in advance. A linked list is a collection of nodes where each node
contains data and a pointer to the next node, making it useful for
dynamic memory allocation. A stack follows the Last In First Out
(LIFO) principle, where the last element added is the first one to
be removed. This is commonly used in scenarios like undo
operations in software or managing function calls. A queue, on the
other hand, follows the First In First Out (FIFO) principle, where
the first element added is the first one to be removed. Queues are
often used in process scheduling and task management.

non-linear data structures do not store data in a sequential

manner. Instead, elements are arranged in a hierarchical or
interconnected fashion. The most common non-linear data
structures are trees and graphs. A tree is a hierarchical structure
consisting of nodes, with one node designated as the root and
other nodes forming branches and leaves. Trees are widely used
in file systems, database indexing, and hierarchical data
representation. A graph is a collection of nodes (also called
vertices) connected by edges, and it can be used to represent
networks such as social media connections, road maps, or
communication networks.
Q.2) What is stack ? List and explain stack operation in details.

Ans. Stack is a linear data structure in which elements can be

inserted and deleted from one end which is called as TOP of the
stack.The elements that are inserted first and deleted at last are
i.e. “First in , Last out”(FILO). The elements that are inserted last
and deleted at first i.e. “Last in , First out”(LIFO). tacks are widely
used in programming for things like function call management,
expression evaluation, undo/redo functionality, and backtracking
algorithms. Because of its simple structure and powerful use
cases, the stack is one of the most important data structures in
computer science.

Operation Of Stack:-

1) Push:- The push operation is used to insert an element onto

the top of the stack. If the stack has a fixed size and is
already full, attempting to push another element results in a
stack overflow error.
2) Pop:- The pop operation is used to remove the top element
from the stack. If the stack is empty and a pop operation is
attempted, it results in a stack underflow.
3) Top:- The Top operation allows viewing the element at the
top of the stack without removing it, which is useful when
you need to see what's on top without modifying the stack.
4) isEmpty:- The isEmpty operation checks whether the stack
has any elements, returning true if it is empty and false
otherwise. This is helpful for avoiding errors when
performing pop or peek operations.
5) Size:- The size operation in a stack is used to determine the
number of elements currently stored in the stack. It does not
modify the stack in any way; instead, it simply returns an
integer value representing how many items have been
pushed onto the stack and not yet removed.
Q.3 Explain bubble sort with suitable example.

Ans. Bubble sort is a simple and straightforward comparison-

based sorting algorithm. It works by repeatedly stepping through
the list of elements to be sorted, comparing each pair of adjacent
elements, and swapping them if they are in the wrong order. This
process is repeated until the entire list is sorted. The algorithm
gets its name from the way smaller or larger elements “bubble” to
the top of the list with each pass, similar to air bubbles rising in
water.

In bubble sort, during the first pass, the algorithm starts with the
first two elements of the array and compares them. If the first
element is greater than the second, it swaps them. Then it moves
to the next pair, compares them, and swaps if necessary. This
process continues until it reaches the end of the list. At this point,
the largest element will have moved to its correct position at the
end of the list. The algorithm then repeats the same steps for the
remaining elements, excluding the last one (as it is already
sorted). This continues until no more swaps are needed,
indicating that the list is sorted.

For example, consider the array [5, 3, 8, 4, 2]. In the first pass,
the algorithm compares 5 and 3, and since 5 > 3, it swaps them to
get [3, 5, 8, 4, 2]. It continues comparing and swapping as
needed, eventually resulting in [3, 5, 4, 2, 8] by the end of the
first pass. The largest number, 8, has now reached its correct
position. The second pass sorts the remaining numbers, pushing
the next largest number into its correct place. After several
passes, the array becomes [2, 3, 4, 5, 8], which is the sorted
version of the original array.

Bubble sort is easy to understand and implement, but it is not

efficient for large datasets because of its high time complexity.
The average and worst-case time complexity of bubble sort is
O(n²), where n is the number of elements in the list. This is due to
the nested loop structure – for each element, it may need to
compare and possibly swap with every other element. However,
its simplicity makes it a useful algorithm for teaching sorting
concepts and for use in small datasets where performance is not a
major concern.
Q.4 Write a note on polish notion.

Ans. Polish Notation, also known as Prefix Notation, is a form of

mathematical and logical expression where the operator is placed
before the operands. This notation was introduced by Polish
mathematician Jan Łukasiewicz in the 1920s to simplify logical
expressions and eliminate the need for parentheses. Unlike the
commonly used infix notation, where operators are written
between the operands (e.g., A + B), Polish notation places the
operator at the beginning, resulting in expressions like + A B. This
arrangement clearly defines the order of operations without
requiring brackets or additional rules of precedence.

The main advantage of Polish notation is that it completely

removes ambiguity in expressions. For example, the infix
expression (5 + 3) * 2 would be written as * + 5 3 2 in Polish
notation. Here, the operator * applies to the result of + 5 3 and 2,
making the evaluation process straightforward and unambiguous.
This clarity is especially useful in computer science, where
expressions are often evaluated by compilers or interpreters.
Polish notation simplifies the parsing process since it can be easily
evaluated using stacks without the need to handle parentheses or
operator precedence rules.

In programming and computational logic, Polish notation plays a

significant role. It is commonly used in stack-based evaluations,
such as those implemented in expression parsers or calculators.
Although it is not used in day-to-day arithmetic by humans due to
its unfamiliar structure, it is highly efficient for machines. Prefix
expressions allow for faster and more efficient processing of
mathematical and logical expressions, which is why this notation
is widely applied in the design of compilers and interpreters.

In conclusion, Polish notation is a powerful and concise way to

represent expressions. It eliminates the need for parentheses,
simplifies expression evaluation, and is particularly suitable for
computers and symbolic logic systems. Its contribution to
mathematical logic and computer science makes it an important
concept, even if it is not commonly used in everyday arithmetic by
humans.
Q.5 Define searching ? write a linear search algorithm and explain
with example.

Ans. Searching is a fundamental operation in computer science

and data structures, which involves finding the location or
presence of a specific element, known as the key, within a
collection of data such as an array, list, or database. The goal of
searching is to determine whether the desired element exists in
the data structure, and if so, to find its position. Searching
techniques are used in a wide range of applications, from looking
up a contact in a phonebook to searching for records in a
database. Depending on the nature of the dataset and the
requirements of the application, different searching algorithms
are used. Among them, Linear Search is one of the simplest and
most commonly used methods, especially when dealing with small
or unsorted datasets.

Linear Search, also known as sequential search, is the simplest

searching technique in which each element in the list is checked
one by one, starting from the first element and moving
sequentially toward the last. In this method, the search key is
compared with each element in the array until a match is found. If
the key matches an element, the position (index) of that element
is returned, and the search stops. If no match is found after
checking all elements, the algorithm concludes that the element is
not present in the list.

For example, consider the array [10, 25, 30, 45, 50] and suppose
we want to search for the number 30. Linear search will start
comparing from the first element: it checks 10 (not a match), then
25 (still not a match), and finally finds 30 at the third position
(index 2, assuming indexing starts at 0). As soon as the match is
found, the search terminates successfully. If the key was not
present, the search would continue through the entire list and
return a message like "Element not found."

The main advantage of linear search is its simplicity. It is very

easy to understand and implement. Additionally, it does not
require the list to be sorted, which makes it a flexible choice for
many basic problems.
Q.6 Explain Selection sort with example.

Ans. Selection sort is a simple and intuitive comparison-based

sorting algorithm used to arrange elements in a specific order,
typically ascending or descending. The main idea behind selection
sort is to divide the array into two parts: a sorted portion and an
unsorted portion. Initially, the sorted portion is empty, and the
entire array is unsorted. The algorithm repeatedly selects the
smallest (or largest) element from the unsorted portion and
swaps it with the first unsorted element, thereby growing the
sorted portion one element at a time.

selection sort works as follows: it starts by finding the smallest

element in the entire array and swaps it with the element at the
first position. This puts the smallest element in its correct place.
Then, it looks for the second smallest element from the remaining
unsorted elements and swaps it with the second position, and so
on. This process continues until the entire array is sorted. The key
feature of selection sort is that it always selects the next
minimum (or maximum) element in each pass and places it in the
correct position.

Let’s understand this with an example. Consider the array:

[64, 25, 12, 22, 11]

• Pass 1: The algorithm finds the smallest element (11) and

swaps it with the first element (64), resulting in [11, 25, 12,
22, 64].

• Pass 2: It finds the next smallest element (12) and swaps it

with the second element (25), resulting in [11, 12, 25, 22,
64].

• Pass 3: The smallest in the remaining unsorted part is 22,

which is swapped with 25 to get [11, 12, 22, 25, 64].

• Pass 4: 25 is already the smallest in the remaining part, so

no swap is needed.

• Pass 5: Only one element left, so the array is fully sorted:

[11, 12, 22, 25, 64].
Q.7 Write and explain merge sort algorithm.

Merge Sort is a highly efficient and widely used sorting algorithm

that follows the Divide and Conquer strategy. The fundamental
idea behind merge sort is to divide the original array into smaller
sub-arrays, sort those sub-arrays individually, and then merge
them back together in a sorted manner. Unlike simpler sorting
algorithms like bubble sort or selection sort, which work by
repeatedly swapping adjacent elements, merge sort solves the
problem by breaking it down into smaller, more manageable
pieces and solving each piece independently. This makes it very
powerful, especially for large datasets.

The merge sort algorithm works in three main phases: dividing,

sorting, and merging. First, the array is recursively divided into
two halves until each sub-array contains only a single element. A
single-element array is always considered sorted by definition.
Once all the sub-arrays have been broken down to this level, the
next step is to merge them in a way that results in sorted arrays.
During the merging phase, two sorted sub-arrays are combined by
comparing the elements of both and placing the smaller (or larger,
depending on the sorting order) elements first. This process
continues until the entire array is merged back into a single sorted
array.

Example:

Let’s sort the array [38, 27, 43, 3, 9, 82, 10] using merge sort:

1. Divide: Split the array into two halves:

Left: [38, 27, 43]
Right: [3, 9, 82, 10]

2. Divide further:
Left → [38], [27, 43] → then [27], [43]
Right → [3, 9], [82, 10] → then [3], [9] and [82], [10]

3. Merge and sort:

Merge [27] and [43] → [27, 43]
Merge [38] and [27, 43] → [27, 38, 43]
Merge [3] and [9] → [3, 9], [82] and [10] → [10, 82]
Merge [3, 9] and [10, 82] → [3, 9, 10, 82]

4. Final merge:
Merge [27, 38, 43] and [3, 9, 10, 82] → [3, 9, 10, 27, 38, 43, 82]
Q.8 Define Queue ? List and explain application in details.

Ans. A queue is a linear data structure that follows the FIFO

principle, which stands for First In, First Out. This means that the
element that is inserted first will be the first one to be removed.
Just like a queue in real life (such as a line at a ticket counter),
elements are added at one end called the rear and removed from
the other end called the front. In other words, insertion
(enqueue) happens at the rear, and deletion (dequeue) happens
at the front.

1. CPU Scheduling:

One of the most common applications of queues is in operating

systems for CPU task scheduling. Processes waiting to be
executed by the CPU are stored in a queue. The process that
arrives first gets executed first. This helps in fair and efficient task
management and prevents any process from being starved.

2. Print Spooling:

When multiple documents are sent to a printer, they are placed in

a print queue. The printer processes the documents in the order
they arrive. This ensures that documents are printed in the same
sequence they were submitted, maintaining the order and priority.

3. Handling of Requests in Web Servers:

Web servers use queues to manage incoming requests from

multiple users. When many users access a website
simultaneously, the requests are queued. The server processes
each request one at a time, in the order they were received,
ensuring fair and organized handling.

4. Breadth-First Search (BFS) in Graphs:

In computer science, the BFS algorithm uses a queue to explore

nodes in a graph level by level. This is especially useful in
scenarios like finding the shortest path in an unweighted graph or
network analysis.

5. Data Buffering (IO Buffers):

Queues are often used in buffers like keyboard buffers or data

streaming buffers. When you type on a keyboard, the characters
are stored in a queue until the system processes them.
Q.9 List various type of linked list and explain doubly linked list.

Ans. The types are:

1. Singly Linked List:

• Each node has two parts: data and a pointer to the next
node.

• Traversal is unidirectional (from head to end).

• The last node points to NULL.

• Simple but limited in navigation (can’t go backward).

2. Doubly Linked List:

• Each node has three parts: data, pointer to the next node,
and pointer to the previous node.

• Allows bidirectional traversal (forward and backward).

• More flexible than singly linked lists but uses more memory
due to the extra pointer.

3. Circular Linked List:

• The last node points back to the first node instead of NULL.

• Can be singly or doubly circular.

• Useful in applications where the list needs to be repeatedly

cycled through.

4. Circular Doubly Linked List:

• A combination of doubly and circular linked list.

• Each node points to both the next and previous nodes, and
the last node links back to the first node.

• Allows continuous traversal in both directions.

A doubly linked list is a type of linear data structure in which each

element, known as a node, contains three parts: the data itself, a
pointer to the next node, and a pointer to the previous node. This
dual-linking mechanism allows for bi-directional traversal,
meaning the list can be navigated both forwards and backwards.
Q.10 What is binary tree? Explain threaded binary tree.

Ans. A binary tree is a hierarchical data structure in which each

node has at most two children, referred to as the left child and the
right child. It is called a binary tree because each node can have
zero, one, or two child nodes. The topmost node is called the root,
and nodes with no children are called leaves.

Each node in a binary tree typically contains:

1. Data – the value stored in the node.

2. Left pointer – pointing to the left child node.

3. Right pointer – pointing to the right child node.

Binary trees are used in various applications such as expression

trees, search trees, heaps, and binary search trees (BST). They
are very efficient for searching, insertion, and deletion operations
when balanced properly.

A Threaded Binary Tree is a special kind of binary tree that

enhances the efficiency of tree traversal, particularly in-order
traversal, by making use of otherwise NULL pointers. In a
traditional binary tree, each node has up to two child pointers:
one pointing to the left child and the other to the right child.
However, in many cases, especially in leaf nodes or when a node
does not have a particular child, these pointers are often set to
NULL. In a threaded binary tree, these NULL pointers are instead
used to "thread" the tree, meaning they point to the node’s in-
order predecessor or successor. This threading allows traversal of
the tree without using recursion or a stack, thereby optimizing
memory and improving execution speed.
Q.11 What is graph? Explain types of graph.

Ans. A graph is a non-linear data structure that is used to

represent pairwise relationships between a set of objects. It
consists of two main components: a set of vertices (or nodes) and
a set of edges that connect pairs of vertices. Graphs are used in
many real-world applications such as social networks,
transportation networks, computer networks, and web structures.
Each vertex represents an entity (like a city, person, or
computer), and each edge represents a connection or relationship
(like a road, friendship, or communication link) between two
entities.

Types of Graphs:

1. Directed Graph: In a directed graph, edges have a direction.

That means an edge from vertex A to vertex B (written as A
→ B) is not the same as an edge from B to A (B → A). Each
edge is an ordered pair of vertices. Directed graphs are useful
in representing one-way relationships, such as followers on
social media, link structures on websites, or task
dependencies in project scheduling.
2. Undirected Graph: In an undirected graph, the edges have no
direction. That means an edge between vertex A and vertex B
(A—B) indicates a bidirectional relationship. This type of
graph is often used to model mutual relationships such as
friendships, peer-to-peer networks, and physical roads
between locations.
3. Weighted Graph: A weighted graph is a graph in which each
edge is assigned a weight or cost. These weights can
represent things like distance, time, cost, or capacity,
depending on the problem. Weighted graphs are commonly
used in shortest path algorithms (like Dijkstra’s algorithm)
for applications such as route planning and network routing.
4. Unweighted Graph: In an unweighted graph, edges do not
have weights. All edges are considered to have equal
importance or cost. These graphs are suitable for simple
connectivity problems where the exact distance or weight is
not needed.
Q.12 Explain Multidimensional array with example.

Ans. A multidimensional array is a type of array that allows

storage of data in more than one dimension. Unlike a one-
dimensional array, which stores data in a linear sequence, a
multidimensional array organizes data in a tabular or matrix
format, making it ideal for representing complex data structures
such as tables, grids, or matrices. The most common form of a
multidimensional array is the two-dimensional (2D) array, which
can be visualized as rows and columns similar to a spreadsheet or
a chessboard. Each element in a 2D array is accessed using two
indices—one for the row and one for the column. For instance, if
we declare an array like int marks[3][4];, we are creating a table
with 3 rows and 4 columns where each element can be accessed
using syntax like marks[0][1], which refers to the element in the
first row and second column.

Example: Suppose we want to store the marks of 3 students in 4

subjects. A two-dimensional array can be used:

int marks [3][4] = {

{85, 90, 78, 92}, // Marks of Student 1

{88, 76, 95, 89}, // Marks of Student 2

{90, 91, 80, 86} // Marks of Student 3

};
Q.13) what is circular queue ? how to visit each element in
circular queue.

Ans. A Circular Queue is a special type of linear data structure that

overcomes the limitations of a simple or linear queue. In a normal
queue implemented using an array, once the rear pointer reaches
the end of the array, we cannot insert more elements even if there
is space available at the front due to deletions. This leads to
inefficient use of memory. To solve this problem, a circular queue
is used, where the last position is connected back to the first
position, forming a circle. This allows the queue to reuse the
empty spaces left by dequeued elements, thus efficiently utilizing
the allocated memory.

In a circular queue, the elements follow the First In First Out

(FIFO) principle just like a regular queue, but with a circular
arrangement. It maintains two pointers: front, which points to the
first element in the queue, and rear, which points to the last
element. When an element is added, the rear is incremented in a
circular manner using the modulo operator. Similarly, when an
element is removed, the front pointer is also incremented
circularly.

Visiting or traversing each element in a circular queue means

accessing all the elements from the front to the rear in the order
they are stored. Since the circular queue wraps around the end of
the array to the beginning, we must use a loop that accounts for
the circular nature of the structure. This is done using the modulo
(%) operator to ensure the index stays within the bounds of the
array.

To traverse the circular queue, we start from the front pointer and
keep moving to the next position using (index + 1) % size, and
we continue this process until we reach the rear pointer. This
ensures that all the elements currently present in the queue are
visited in the correct order.

For example, if the front is at index 3 and the rear is at index 1

(indicating that the queue has wrapped around), the traversal
would visit elements at index 3, 4, 0, and 1 in that order. This
way, we can display or process all the elements stored in the
circular queue without missing any, regardless of how the queue
has wrapped around the array.
Q.14) Explain tree briefly.

Ans. A tree is a widely used non-linear data structure that

simulates a hierarchical tree structure, with a set of connected
nodes. It is different from linear data structures like arrays,
stacks, and queues because it does not store data sequentially.
Instead, it organizes data in a hierarchical manner where one
element is connected to one or more sub-elements, forming a
structure that resembles a tree with branches. The topmost node
in a tree is called the root node, and every node in the tree
(except the root) has exactly one parent node and zero or more
child nodes.

Each connection between nodes is called an edge, and the nodes

with no children are known as leaf nodes. A tree is considered a
collection of nodes connected by edges, where there are no
cycles, and the entire structure is connected. The depth of a node
refers to the number of edges from the root to that node, while
the height of the tree is the longest path from the root to a leaf
node.

There are different types of trees in data structures, each serving

different purposes. The most common type is the binary tree,
where each node can have at most two children, referred to as the
left child and right child. A special kind of binary tree is the binary
search tree (BST), where the left child of a node always holds a
smaller value, and the right child holds a greater value. This
property makes searching very efficient. There are also balanced
trees like AVL trees and Red-Black trees that maintain balance to
keep operations fast. Other advanced trees include B-Trees and
Tries, which are widely used in databases, file systems, and
search engines.

Trees have many important applications in computer science.

They are used to represent hierarchical structures such as file
systems, organizational charts, and XML/HTML data. They are also
essential in various algorithms, such as those used for searching
and sorting, expression evaluation, compiler construction, and
artificial intelligence.