YEAR-2015

Each questions carry 2 marks

a) Define non-linear data structure.

 Data structures where data elements are not arranged sequentially or linearly are called non-linear data
structures. In a non-linear data structure, single level is not involved. Therefore, we can't traverse all the
elements in single run only. It utilizes computer memory efficiently in comparison to a linear data structure.
Its examples are trees and graphs. Non-linear data structures are useful for representing complex
relationships and data hierarchies, such as in social networks, file systems, or computer networks.
b) What is complete binary tree?
 Complete binary tree: A tree is called a complete binary tree if tree satisfies following conditions:

a. Each node has exactly two children except leaf node.

b. All leaf nodes are at same level.

c. If a binary tree contains m nodes at level l, it contains atmost 2m nodes at level l + 1.

Fig.-Complete Binary Tree

c) What is Abstract Data Type?
 An Abstract Data Type (ADT) is defined as a mathematical model of the data objects that make up a data type
as well as the functions that operate on these objects.
An Abstract Data Type (ADT) is the specification of the data type which specifies the logical and mathematical
model of the data [Link] does not specify how data will be organized in memory and what algorithm will be
used for implementing the operations. An implementation chooses a data structure to represent the ADT.

The important step is the definition of ADT that involves mainly two parts:

a. Description of the way in which components are related to each other.

b. Statements of operations that can be performed on the data type.

Examples are List ADT, Stack ADT, Queue ADT.

d) Define big O notation.
 Big-O notation represents the upper bound of the running time of an algorithm. Therefore, it gives the worst-
case complexity of an algorithm.
Given two functions f(n) and g(n), we say that f(n) is O(g(n)) if there exist constants c > 0 and n0 >= 0 such
that f(n) <= c*g(n) for all n >= n0.
It returns the highest possible output value (big-O) for a given input.
The execution time serves as an upper bound on the algorithm's time complexity.
 Time complexity

e) What is priority queue?

 A priority queue is a special type of queue in which each element is associated with a priority value. And,
elements are served on the basis of their priority i.e. higher priority elements are served first. If elements
with the same priority occur, they are served according to their order in the queue.
 Elements with higher priority are retrieved or removed before those with lower priority.
 When a new item is added, it is inserted according to its priority.
 The binary heap is the most common implementation of a priority queue:
 A min-heap allows quick access to the element with the smallest value.
 A max-heap allows quick access to the element with the largest value.

f) What is Dynamic Memory Allocation?

 The process of allocating or de-allocating a block of memory during the execution of a program is
called Dynamic Memory Allocation.

g) What are the application of tree in data structure?

[Link] Data Representation
Trees naturally represent data in a hierarchy.
Example: File systems, organizational charts, XML/HTML documents.

2. Searching Operations
Many efficient searching structures are based on trees.
Example: Binary Search Tree (BST) → quick search, insert, delete.

3. Database Indexing
Trees help in fast data retrieval in databases.
Example: B-Trees, B+ Trees used in DBMS indexing.

4. Routing Algorithms (Networks)

Tree structures help find shortest paths and efficient routing.
Example: Spanning trees in computer networks.

5. Expression Parsing
 Used by compilers to evaluate and analyze expressions.
Example: Expression Trees, Syntax Trees, Parse Trees.

YEAR-2016

a) What is hashing? Name any two hashing function.

In data structures, hashing is a well-known technique to search any particular element among several
elements. It minimizes the number of comparisons while performing the search. Hashing is extremely
efficient. The time taken by it to perform the search does not depend upon the total number of elements .
It completes the search with constant time complexity O(1).
 Types of Hash Functions
There are many hash functions that use numeric or alphanumeric keys. Somes are
Division Method.
Multiplication Method
Mid-Square Method
Folding Method
b) What are the drawbacks of doubly linked list over singly linked list?

i. It uses extra memory when compared to the array and singly linked list.
ii. Traversing a doubly linked list can be slower than traversing a singly linked list.
iii. Implementing and maintaining doubly linked lists can be more complex than singly linked lists.
iv. Like SLLs, DLLs still don't support direct (random) access; you must traverse sequentially from the head or
tail, but DLLs allow backward traversal, which SLLs lack.
c) Write down two applications of queue.

d) In which condition a queue is to be empty. Give an example.

 A queue is empty when front = -1 (or front > rear).

This means there is no element present in the queue.

Example:
If a queue has no elements initially, then front = rear = -1, so the queue is empty.

e) In which condition an element cannot be inserted in circular queue.

 An element cannot be inserted in a circular queue when (rear + 1) % size == front, i.e., when the circular
queue is full.

f) What will be the corresponding binary tree representation of expression A+B*C.

 The corresponding binary expression tree for the expression A + B * C is:

 g) What is non-linear data structure? Give example.
Year-2015 Q. a
h) Write down difference between malloc() and calloc().

[Link]. malloc() calloc()

1. malloc() is a function that calloc() is a function that assigns a

creates one block of memory of specified number of blocks of
a fixed size. memory to a single variable.

2. It takes one argument It takes two arguments.

3. malloc() is faster than calloc. calloc() is slower than malloc()

4. malloc() has high time calloc() has low time efficiency

efficiency

6. Syntax : void* malloc(size_t Syntax : void* calloc(size_t num,

size); size_t size);

7. malloc() does not initialize the calloc() initializes the memory to zero
memory to zero

YEAR-2017

a) Name two sorting techniques that are recursive in nature.

The two most common sorting techniques that are recursive in nature are Merge Sort and Quicksort.
b) Name the data structure used by the two graph traversal algorithm : BFS and DFS.
Breadth-First Search (BFS) uses a Queue.
Depth-First Search (DFS) uses a Stack.
c) What do you mean by height balanced tree?

A height balanced tree is a balanced binary search [Link] an AVL tree, balance factor of every node is either -1, 0 or
+[Link] factor of a node is the difference between the heights of left and right subtrees of that node.

Balance factor = height of left subtree - height of right subtree

Height balancing of tree is required:

Height balancing of tree is required to implement an AVL tree. Each node must contain a balance factor, which
indicates its states of balance relative to its sub-tree.

AVL tree, red-black tree are examples of height-balanced trees.

d) What do you understand by sparse matrix?
A sparse matrix in which most of its elements are zero. It is characterized by a small number of non-zero
elements compared to the total number of elements (mxn). In other words, a sparse matrix has a significant
proportion of zero values, often exceeding half of the total elements.
Given m and n, a sparse matrix of size mxn can be defined as follows:
 m: The number of rows
 n: The number of columns
For example, consider the following 4x4 matrix:
0001
0000
2000
0003
e) Write down the equivalent postfix expression of [(a+b)*c]-d.
The equivalent postfix expression for the given infix expression is ab+c*d-.

[(a+b)*c]-d
=[(ab+)*c]-d
=(ab+c*)-d
= ab+c*d-
f) Name the tree traversal algorithms that traverses the root node at last and at the first.
The tree traversal algorithms that visit the root node at specific times are:
 Traverses the root node at last: Post-order traversal (Left -> Right -> Root).
 Traverses the root node at the first: Pre-order traversal (Root -> Left -> Right).

g) How do we detect if an ordinary queue is empty or not?

Year-2016 Q.d
h) Give one example of linear data structure and one example of non-linear data structure.
One example of a linear data structure is an array or a linked list, and one example of a non-linear data
structure is a tree or a graph.

Year-2018

a) Differentiate between linear and non-linear Data [Link] one example of each type.
[Link] Linear Data Structure Non-linear Data Structure
1. In a linear data structure, data In a non-linear data structure, data
elements are arranged in a linear elements are attached in
order where each and every element hierarchically manner.
is attached to its previous and next
adjacent.
2. In linear data structure, single level is Whereas in non-linear data
involved. structure, multiple levels are
involved.
3. Its implementation is easy in While its implementation is complex
comparison to non-linear data in comparison to linear data
structure. structure.
4. In linear data structure, data While in non-linear data structure,
elements can be traversed in a single data elements can't be traversed in
run only. a single run only.
 5. In a linear data structure, memory is While in a non-linear data structure,
not utilized in an efficient way. memory is utilized in an efficient
way.

6. Its examples are: array, stack, queue, While its examples are: trees and
linked list, etc. graphs.
7. Applications of linear data structures Applications of non-linear data
are mainly in application software structures are in Artificial
development. Intelligence and image processing.
8. Linear data structures are useful for Non-linear data structures are useful
simple data storage and for representing complex
manipulation. relationships and data hierarchies,
such as in social networks, file
systems, or computer networks.
9. Performance is usually good for Performance can vary depending on
simple operations like adding or the structure and the operation, but
removing at the ends, but slower for can be optimized for specific
operations like searching or operations.
removing elements in the middle.

b) What is AVL tree .Give one example.

An AVL tree defined as a self-balancing Binary Search Tree (BST) where the difference between heights of
left and right subtrees for any node cannot be more than one.
Balance Factor = left subtree height - right subtree height
For a Balanced Tree(for every node): -1 ≤ Balance Factor ≤ 1

Example of an AVL Tree:

c) Define Priority Queue.

Year-2015 Q.e

d) What do you mean by big-Oh notation in respect to performance analysis of algorithm.

Year-2015 Q.d

e) Write the equivalent prefix expression of the following arithmetic expression {(a*b)-d}/e.

The prefix expression (Polish Notation) for {(a*b)-d}/e is / - * a b d e.

{(a*b)-d}/e
= {(*ab)-d}/e
=(-*abd)/e
=/-*abde

f) Write the names of two Different techniques to represent an undirected graph.

The names of two different techniques commonly used to represent an undirected graph are: Adjacency
Matrix and Adjacency List.
g) When does collision occur in hashing.

In Hashing, hash functions were used to generate hash values. The hash value is used to create an index
for the keys in the hash table. The hash function may return the same hash value for two or more keys.
When two or more keys have the same hash value, a collision happens. To handle this collision, we
use Collision Resolution Techniques.

h) What is double ended queue?

Deque or Double Ended Queue is a generalized version of Queue data structure that allows insert and
delete at both ends. Below is an example program of deque

Year-2019

The postfix expression for the given infix expression is 𝐴 𝐵 𝐶 𝐴 + * 𝐶 / +

a) What is the postfix expression for the following infix expression?A+B* (C+A)/C

A+B* (C+A)/C
=A+B*(CA+)/C
=A+(BCA+*)/C
=A+(BCA+*C/)
=ABCA+*C/+

b) What is the sequence of values popped out of stack when the following sequence of operations are
performed on a stack?

PUSH (10), PUSH (20), POP, PUSH (10), POP, PUSH (20)

Here's a step-by-step breakdown:

1. Start: Stack is empty [].
2. PUSH(10): Stack: [10]
3. PUSH(20): Stack: [10, 20] (20 is at the top)
4. POP: Pops 20. Stack: [10]
5. PUSH(10): Stack: [10, 10]
6. POP: Pops 10. Stack: [10]
7. PUSH(20): Stack: [10, 20]

The sequence of popped values is 20, 10

c) What is the number of distinct binary trees with 3 nodes?

There are 5 distinct binary trees with 3 nodes, which can be calculated using Catalan numbers C n

(2 n)!
C n=
(n+1)! n !

C 3=5

d) What is the no. of internal nodes of degree 2 in binary tree that has n leaf nodes ?
In a full binary tree (where every node has either 0 or 2 children), the number of leaf nodes (N) is always one
more than the internal nodes (I) with two children: N=I+1
i.e. Total No. of leaf node in Binary Tree = (Total No. of nodes with 2 children or internal nodes) +1.
So, the no. of internal nodes of degree 2 in binary tree that has n leaf nodes is (n-1).

e) Which data structure is good one to represent sparse matrix ?

The linked list (or sparse matrix representation using linked lists) is the best data structure to represent a
sparse matrix.

Reason:
It stores only the non-zero elements along with their row and column positions, which saves memory
compared to a 2-D array.

f) Define strictly binary tree.

A strictly binary tree (also called a full or proper binary tree) is a binary tree where every node has
either zero children (is a leaf) or exactly two children, meaning no node can have only one child.

The above figure is an example of a Strict Binary Tree.

The internal nodes (node 1, node 2, node 3, node 5)
have 2 children each, whereas the leaf nodes (node
4, node 6, node 7, node 8, node 9) have no children.

g) What is Dequeue?
Year-2018 Q.h

h) What do you mean by height-balance tree?

Year-2017 Q.c

Year-2024 (Paper- MJ 3-T)

1. Distinguish between linear Data Structure and nonlinear Data Structure.

 Year-2018 Q.a
2. What do you mean by abstract data type?
Year-2015 Q.c
3. Define hashing.
Year-2016 Q.a
4. Define a sparse matrix.
Year-2017 Q.d
5. Define left skewed binary tree.
A skewed binary tree is a type of binary tree in which all the nodes have only either one child or no child.
In Left Skewed Binary Tree, all the nodes are having a left child or no child at all. It is a left side dominated
tree. All the right children remain as null.

6. Define full binary tree with an example.

A full binary tree is a binary tree with either zero or two child nodes for each node.

A full Binary tree is a special type of binary tree in which every parent node/internal node has either two
or no children. It is also known as a proper binary tree.

7. What element would be the best choice for pivot element in quick sort?

8. What are the qualities of a good algorithm?

 Input: An algorithm has zero or more inputs. Each that contains a fundamental operator must accept zero
or more inputs.

 Output: An algorithm produces at least one output. Every instruction that contains a fundamental
operator must accept zero or more inputs.
 Finiteness: An algorithm must terminate after a finite number of steps in all test cases.
 Effectiveness: An algorithm must be developed by using very basic, simple, and feasible operations so that
one can trace it out by using just paper and pencil.
 Clear and Unambiguous: The algorithm should be unambiguous. Each of its steps should be clear in all
aspects and must lead to only one meaning.
 Year-2024 (Paper- MI 3-T)
1. What is the difference between time complexity and space complexity?

2. Mention two differences between stack and queue.

Feature Stack Queue

Definition A linear data structure that A linear data structure
follows the Last In First Out that follows the First In
(LIFO) principle. First Out
(FIFO) principle.
Primary Push (add an item), Pop Enqueue (add an item),
Operations (remove an item), Peek (view Dequeue (remove an
the top item) item), Front (view the
first item), Rear (view
the last item)
Insertion/Removal Elements are added and Elements are added at
removed from the same end the rear and removed
(the top). from the front.
Use Cases Function call management (call Scheduling processes in
stack), expression evaluation operating systems,
and syntax parsing, undo managing requests in a
mechanisms in text editors. printer queue, breadth-
first search in graphs.
Examples Browser history (back button), Customer service lines,
reversing a word. CPU task scheduling.

3. What is the difference between BFS and DFS?

Parameters BFS DFS

Stands for BFS stands for Breadth First DFS stands for Depth First Search.
Search.
Data BFS(Breadth First Search) uses DFS(Depth First Search) uses Stack
Structure Queue data structure for finding data structure.
the shortest path.
Definition BFS is a traversal approach in DFS is also a traversal approach in
which we first walk through all which the traverse begins at the root
nodes on the same level before node and proceeds through the nodes
moving on to the next level. as far as possible until we reach the
node with no unvisited nearby nodes.
Conceptual BFS builds the tree level by level. DFS builds the tree sub-tree by sub-
 Difference tree.
Approach It works on the concept of FIFO It works on the concept of LIFO (Last
used (First In First Out). In First Out).
Applications BFS is used in various DFS is used in various applications
applications such as bipartite such as acyclic graphs and finding
graphs, shortest paths, etc. If strongly connected components etc.
weight of every edge is same, There are many applications where
then BFS gives shortest path both BFS and DFS can be used like
from source to every other Topological Sorting, Cycle Detection,
vertex. etc.

4. Compare between heap and binary search tree.

S No. Heap Binary Search Tree

1. In heap, for every node other than the root, the In binary search tree, for every node except the leaf
key value of the parent node is greater or node, the left child has a less key value and right
smaller or equal to the key value of the child child has a greater key value.
node.
2. It guarantees that the element at higher level is It guarantees the order (from left to right).
smaller or greater than element at lower level.
3. Time complexity to find min/max is O(1). Time complexity to find min/ max element is O(log
n).

5. Write down the basic of principle of divide and conquer technique.

Divide and Conquer Algorithm is a problem-solving technique used to solve problems by dividing the main
problem into subproblems, solving them individually and then merging them to find solution to the original
problem.

The Three Steps

1. Divide: Break the main problem into two or more smaller subproblems that are instances of the same
problem, but with reduced input size.
2. Conquer: Solve the subproblems recursively. If a subproblem is small enough (a base case, like a single
element), solve it directly.
3. Combine: Merge the solutions from the subproblems to form the solution to the original problem.
6. Convert (a+b*c)/d into prefix form.
The prefix (Polish notation) form of (a+b*c)/d is /+a*bcd
(a+b*c)/d
={a+(*bc)}/d
=(+a*bc)/d
=/+a*bcd

7. A two dimensional array of size 8 × 8 whose base address is 600 and every element occupies 4 bytes of
memory .Find the address of A[6,4] in column major order.

The formula to calculate the memory address of an element in a two-dimensional array stored in column-major
order is:

where 𝐵 is the base address, 𝑖 is the row index, 𝑗 is the column index, 𝑅 is the number of rows, and 𝐸 is the size
of each element in bytes.

Here, From the problem description:

 Base address (𝐵) =600

 Row index (𝑖) =6

 Column index (𝑗) =4

 Number of rows (𝑅) =8(array is 8 * 8)

 Element size (𝐸) =4 bytes

Address =600+(6+4×8)×4=752

8. Let us consider a function f (n) = 1000 nlog n+500 n+4. What is the time complexity?

Year-2022(paper-C5 T)

a) What do you mean by multi-dimensional array?

A multi-dimensional array in C can be defined as an array that has more than one dimension. Having more
than one dimension means that it can grow in multiple directions. Some popular multidimensional arrays
include 2D arrays which grows in two dimensions, and 3D arrays which grows in three dimensions.

Example:
A 2-D array A[3][4] stores data in 3 rows and 4 columns.

b) What is dequeue?

Year-2018 Q.h

c) Define sparse matrix.

Year-2017 Q.d
 d) What is non-linear data structure? Give one example.

Year-2015 Q.a

e) Describe complete binary tree.

Year-2015 Q.b

f) Briefly describe one application of queue.

Application of Queue:

One important application of a queue is CPU scheduling in an operating system.

Processes waiting for execution are placed in a queue and are served in First In First Out (FIFO) order. The process
that arrives first gets executed first, ensuring fair and systematic processing.

g) What is AVL tree?

Year-2018 Q.b

h) What is the significance of hash function?

A hash function is used to map a key to a specific index (address) in a hash table. Its significance includes:

 Fast access: It allows quick insertion, deletion, and searching, usually in O(1) average time.

 Efficient data retrieval: Directly computes the storage location without searching the entire data set.

 Uniform distribution: A good hash function spreads keys evenly, reducing collisions.

 Better performance: Minimizes time complexity compared to linear or binary search.

 Memory optimization: Uses table space efficiently.

Year-2023(paper-C5 T)

1. What are non-recursive procedures?

Non-recursive procedures are procedures or functions that do not call themselves, either directly or indirectly,
during execution.

Instead of recursion, they use iterative control structures such as:

 for loops

 while loops

 do–while loops
and may use explicit data structures like stacks or queues to manage repetition.

Example (Non-Recursive Factorial in C):

int factorial(int n)
{
int fact = 1;
for(int i = 1; i <= n; i++)
 fact = fact * i;
return fact;
}

2. What are advantages of Insertion sort?

Advantages:

 Simple and easy to implement.

 Stable sorting algorithm.

 Efficient for small lists and nearly sorted lists.

 Space-efficient as it is an in-place algorithm.

 Adoptive. the number of inversions is directly proportional to number of swaps. For example, no swapping
happens for a sorted array and it takes O(n) time only.

3. State the principle of stack and give it's two applications.

The principle of a stack is LIFO (Last-In, First-Out),

Applications of stack are as follows :

1. Expression evaluation : Stack is used to evaluate prefix, postfix and infix expressions.
2. Expression conversion : An expression can be represented in prefix, postfix or infix notation. Stack can be used to
convert one form of expression to another.
3. Syntax parsing : Many compilers use a stack for parsing the syntax of expressions, program blocks etc. before
translating into low level code.
4. Parenthesis checking : Stack is used to check the proper opening and closing of parenthesis.

4. What are front and rear pointers of queue?

In a queue data structure, the front pointer (or head) indicates the position where elements are removed
(dequeued), while the rear pointer (or tail) points to the location where new elements are added
(enqueued), following the First-In, First-Out (FIFO) principle.

5. What is the need of garbage collection?

The purpose of garbage collection (GC) in computer programming is to automatically find and free up
memory occupied by objects that are no longer in use, preventing memory leaks and simplifying
development by removing the need for manual memory deallocation, thereby improving application
performance and stability.

6. How a heap can be created?

7. How a binary tree can be represented as array structure?

A binary tree can be efficiently represented as an array structure using the level-order traversal method,
provided the tree is a complete binary tree [1]. This representation stores nodes based on their position in
the tree, starting from the top and moving left to right across each level.

In this array representation:

  The root element is stored at index 0 [1].
 For any node at index i:
o Its left child is stored at index 2 * i + 1 .
o Its right child is stored at index 2 * i + 2 .
o Its parent (for any node except the root) is stored at index floor((i - 1) / 2) .

Example
Consider a simple complete binary tree:

0 1 2 3 4

A B C D E

8. What is traversal method of a threaded binary tree?

A threaded binary tree is a binary tree in which the NULL pointers of left or right child are replaced by threads that
point to the tree’s inorder predecessor or successor. This allows traversal without using recursion or a stack.
Traversal Method (Inorder Traversal)
The main traversal method used in a threaded binary tree is Inorder Traversal.
Steps for Inorder Traversal in a Threaded Binary Tree:
1. Start from the leftmost node of the tree.
2. Visit the current node (process its data).
3. If the right pointer is a thread, move directly to the inorder successor.
4. If the right pointer is a child, move to its leftmost node.
5. Repeat until all nodes are visited.

Year-2023(paper-CC4 T)

1. What is array?

Array is a linear data structure where all elements are arranged sequentially. It is a collection of elements
of same data type stored at contiguous memory locations.

Data stored in each position of an array is given a positive value called the index of the element. The index
helps in identifying the location of the elements in an array.
2. What do you mean by AVL tree?

Year-2018 Q.b

3. What is big oh notation?

Year-2015 Q.d

4. What are linear and nonlinear data structure?

Linear Data Structure:

Data structure where data elements are arranged sequentially or linearly where each and every element is
attached to its previous and next adjacent is called a linear data structure. In linear data structure, single
level is involved. Therefore, we can traverse all the elements in single run only. Its examples
are array, stack, queue, linked list, etc.

Non-linear Data Structure:

Data structures where data elements are not arranged sequentially or linearly are called non-linear data
structures. In a non-linear data structure, single level is not involved. Therefore, we can't traverse all the
elements in single run only. Its examples are trees and graphs.

5. What is meant by topological sorting?

Topological Sort is a linear ordering of the vertices in such a way that

if there is an edge in the DAG going from vertex ‘u’ to vertex ‘v’,

then ‘u’ comes before ‘v’ in the ordering.

It is important to note that-

 Topological Sorting is possible if and only if the graph is a Directed Acyclic Graph.
 There may exist multiple different topological orderings for a given directed acyclic graph.
 Topological Sort Example-

 Consider the following directed acyclic graph-


For this graph, following 4 different topological orderings are possible-

 123456
 123465
 132456
 132465

Applications of Topological Sort-

 Scheduling jobs from the given dependencies among jobs

 Instruction Scheduling
 Data Serialization

6. What is abstract data type?

Year-2015 Q.c

7. What do you mean by linear data structure?

Linear Data Structure:

Data structure where data elements are arranged sequentially or linearly where each and every element is
attached to its previous and next adjacent is called a linear data structure. In linear data structure, single
level is involved. Therefore, we can traverse all the elements in single run only. Its examples
are array, stack, queue, linked list, etc.

8. Define priority queue.

Year-2015 Q.e

YEAR-2015

2) 2+6+1+6
(a)What are the advantages of Array over linked list?

Advantages of Arrays over Linked List :

 Random Access. : We can access ith item in O(1) time (only some basic arithmetic required using base
address). In case of linked lists, it is O(n) operation due to sequential access.

 Cache Friendliness : Array items (Or item references) are stored at contiguous locations which makes
array cache friendly (Please refer Spatial locality of reference for more details)

 Easy to use : Arrays are relatively very easy to use and are available as core of programming languages

 Less Overhead : Unlike linked list, we do not have any extra references / pointers to be stored with every
item.

(b)Write down the algorithm deleting last node from a single linked list.
 Deletion at end :
Here START is a pointer variable which contains the address of first node. PTR is a pointer variable which contains
address of node to be deleted. PREV is a pointer variable which points to previous node. ITEM is the value to be
deleted.
1. If (START == NULL) Then [Check whether list is empty]
2. Print: Linked-List is empty.
3. Else
4. PTR = START, PREV = START
5. Repeat While (PTR -> LINK != NULL)
6. PREV = PTR [Assign PTR to PREV]
7. PTR = PTR -> LINK [Move PTR to next node]
[End of While Loop]
8. ITEM = PTR -> INFO [Assign INFO of last node to ITEM] 9. If (START -> LINK == NULL) Then
[If only one node is left]
10. START = NULL [Assign NULL to START]
11. Else
9. PREV -> LINK = NULL
[Assign NULL to link field of second last node] [End of Step 9 If]
10. Delete PTR
11. Print : ITEM deleted
[End of Step 1 If]
12. Exit

(c) Why is circular linked list needed over a single linked list?

A circular linked list is preferred over a singly linked list because the last node points to the first node instead
of NULL, allowing continuous traversal. It is useful for applications like circular queues and round-robin scheduling
where repeated access is required.

(d) Write down a C function to reverse a single linked list.

#include <stdio.h>

struct node {

int data;

struct node *next;

};

struct node* reverse(struct node *FIRST)

struct node *PTR, *PREV, *REV;

PTR = FIRST;

PREV = NULL;

while (PTR != NULL)

{
 REV = PREV;

PREV = PTR;

PTR = PTR->LINK;

PREV->LINK = REV;

FIRST = PREV;

return FIRST;

}
3) 6+5+3
(a) Write two functions to implement two basic operations of stack.

#include <stdio.h>

#define MAX 100

int STACK[MAX];

int TOP = -1;

/* Function to PUSH an element into stack */

void PUSH(int DATA) {

if (TOP == MAX - 1) {

printf("STACK OVERFLOW\n");

return;

TOP = TOP + 1;

STACK[TOP] = DATA;

printf("Element %d pushed successfully\n", DATA);

/* Function to POP an element from stack */

void POP() {

int ITEM;

if (TOP < 0) {

printf("STACK UNDERFLOW\n");
 return;

ITEM = STACK[TOP];

STACK[TOP] = 0; // optional

TOP = TOP - 1;

printf("Popped element is %d\n", ITEM);

}
(b) What is queue ?What are the various operation associated with queue?

Queue is a linear data structure that follows the FIFO (First In First Out) principle, where insertion is done at the
rear end and deletion is done from the front end.

The following are some fundamental operations that allow us to add, remove, and access elements efficiently.

 enqueue() - Insertion of elements to the queue.

 dequeue() - Removal of elements from the queue.

 getFront()- Acquires the data element available at the front node of the queue without deleting it.

 getRear() - This operation returns the element at the rear end without removing it.

 isEmpty() - Checks if the queue is empty.

 size() - This operation returns the size of the queue i.e. the total number of elements it contains.

(c)Convert postfix to infix:

4 2 $ 3* 3-84/11 + / +

Symbol Action Stack content

4 push 4
2 push 4, 2
$ pop 4,2 → (4$2) (4$2)
3 push (4$2), 3
* pop → ((4$2)*3) ((4$2)*3)
3 push ((4$2)*3), 3
- pop → (((4$2)*3)-3) (((4$2)*3)-3)
8 push (((4$2)*3)-3), 8
4 push (((4$2)*3)-3), 8, 4
/ pop → (8/4) (((4$2)*3)-3), (8/4)
1 push (((4$2)*3)-3), (8/4), 1
1 push (((4$2)*3)-3), (8/4), 1, 1
+ pop → (1+1) (((4$2)*3)-3), (8/4), (1+1)
/ pop → ((8/4)/(1+1)) (((4$2)*3)-3), ((8/4)/(1+1))
+ pop → final expression (((4$2)*3)-3)+((8/4)/(1+1))

4) 2+5+(2+3)+3
(a)Write down the disadvantages of binary search.
Disadvantages of Binary Search Tree (BST):

 Not self-balancing: Unbalanced BSTs can lead to poor performance

 Worst-case time complexity: In the worst case, BSTs can have a linear time complexity for searching and
insertion

 Memory overhead: BSTs require additional memory to store pointers to child nodes

 Not suitable for large datasets: BSTs can become inefficient for very large datasets

 Limited functionality: BSTs only support searching, insertion, and deletion operations

(b)Write down a function to insert node in a BST.

struct node {

int info;

struct node *left;

struct node *right;

};

struct node* insertBST(struct node *root, int item)

struct node *newnode, *parent = NULL, *current = root;

/* Step 1: Find location */

while (current != NULL)

parent = current;

if (item < current->info)

current = current->left;

else if (item > current->info)

current = current->right;

else

return root; // Item already exists

/* Step 2: Create new node */

newnode = (struct node *)malloc(sizeof(struct node));

 if (newnode == NULL)

printf("OVERFLOW\n");

return root;

newnode->info = item;

newnode->left = NULL;

newnode->right = NULL;

/* Step 3: Insert node */

if (parent == NULL)

root = newnode; // Tree was empty

else if (item < parent->info)

parent->left = newnode;

else

parent->right = newnode;

return root;
}

(c) What do you mean by Hash Function?Explain with some examples.

A hash function is a mathematical function or algorithm that simply takes a variable number of characters (called a
”message”) and converts it into a string with a fixed number of characters (called a hash value or simply, a hash).

Hash Function is a function that maps any big number or string to a small integer [Link] function takes the
data item as an Input and returns a small integer value as an output .The small integer value is called as a hash
value. Hash value of the data item is then used as an index for sorting it into the Hash table.

There are many hash functions that use numeric or alphanumeric keys. Somes are

Division Method.
Multiplication Method
 Mid-Square Method
Folding Method

a. Division method :
1. Choose a number m larger than the number n of key in K. (The number m is usually chosen to be a prime
number or a number without small divisors, since this frequently minimizes the number of collisions.)
2. The hash function H is defined by :

H(k) = k (mod m) or H(k) = k (mod m) + 1

3. Here k (mod m) denotes the remainder when k is divided by m.

4. The second formula is used when we want the hash addresses to range from 1 to m rather than from 0 to m
– 1.
b. Midsquare method :

1. The key k is squared.

2. The hash function H is defined by : H(k) = l where l is obtained by deleting digits from both end of k2.
3. We emphasize that the same positions of k2 must be used for all of the keys.

c. Folding method :
The key k is partitioned into a number of parts, k1, .... , kr, where each part, except possibly the last, has the same
number of digits as the required address.

Then the parts are added together, ignoring the last carry i.e.,
H(k) = k1 + k2 + .... + kr
where the leading-digit carries, if any, are ignored.

Now truncate the address upto the digit based on the size of hash table.

(d)Draw the expression tree for E=(3 x− y )∗¿

5)
(a) Write a function to display all the elements of a circular linked list.

void display(struct node *start)

struct node *temp;

if (start == NULL)

printf("List is empty");
 return;

temp = start;

do

printf("%d ", temp->data);

temp = temp->next;

while (temp != start);

}

(b)Write down the condition to check the overflow condition in a circular queue.

Overflow condition in a Circular Queue:

A circular queue is said to be full (overflow condition) when the next position of rear is the same as front.

Condition:

(rear +1) % ¿ front where,

rear → points to the last element

front → points to the first element

size → total capacity of the circular queue

(c) what is Deque? Give an example of a Deque.

A Deque is a linear data structure in which insertion and deletion of elements can be performed at both ends, i.e.,
front and rear.

(d)What is Priority Queue? Define a node in a Priority Queue using structure in C language.
 Year-2015 Q.e(Priority Queue)

 Define a node in a Priority Queue using structure in C language:

typedef struct Node {

int data;

int priority;

struct Node* next;

} Node;

6) 6+2+2+5
(a) Write down listing of nodes using in-order pre-order and post-order traversal on the following tree:

In-order Traversal (Left – Root – Right)

E, D, A, C, H, F, B, G

Pre-order Traversal (Root – Left – Right)

A, D, E, B, C, F, H, G

Post-order Traversal (Left – Right – Root)

E, D, H, F, C, G, B, A

(b)Why tree is called as a non-linear data structure?

A tree is called a non-linear data structure because its elements (nodes) are not stored sequentially in a single
line, but rather in a hierarchical, multi-level structure with parent-child relationships, unlike linear structures
(arrays, lists) where data flows one after another. This hierarchy allows for branching, where a single node can
connect to multiple other nodes (children) at different levels, creating a more complex, multi-dimensional
arrangement.

(c)What is AVL tree?

Year-2018 Q.b

(d)Write an algorithm to delete the maximum element from the list.

7) 2+6+4+3
(a) What are the basic differences of graph over tree?

Basic Differences Between Graph and Tree:

 Cycles: Graphs can contain cycles, while trees cannot.

 Connectivity: Graphs can be disconnected (i.e., have multiple components), while trees are always
connected.

 Hierarchy: Trees have a hierarchical structure, with one vertex designated as the root. Graphs do not have
this hierarchical structure.

 Applications: Graphs are used in a wide variety of applications, such as social networks, transportation
networks, and computer science. Trees are often used in hierarchical data structures, such as file systems
and XML documents.

(b)Write down the algorithm to implement Insertion sort.

INSERTION_SORT(A)
(A = array of elements)

1. for j ← 2 to length[A]

2. do key ← A[j] /*Insert A[j] into the sorted sequence A[1....j – 1].*/

3. i←j–1

4. while i > 0 and A[i] > key

5. do A[i + 1] ← A[i]

6. i←i–1

7. A[i + 1] ←key

(c) Why the time complexity of binary search is lower than Linear search?
(d) Define the following terms :

I. depth of a tree

II. full binary tree.

I. Depth of a Tree
The depth of a tree is the maximum number of levels (or edges) from the root node to the deepest leaf node.

Example:

Here, the longest path is A → B → D, so the depth of the tree = 3 levels.

II. Full binary tree

Year-2024 (Paper- MJ 3-T) Q.6

Year-2016

2)(a) How linked list over comes all the disadvantages of arry?3

Advantages of Linked List over arrays :

 Efficient insertion and deletion: Linked lists allow insertion and deletion in the middle in O(1) time, if we
have a pointer to the target position, as only a few pointer changes are needed. In contrast, arrays require
O(n) time for insertion or deletion in the middle due to element shifting.
  Implementation of Queue and Deque : Simple array implementation is not efficient at all. We must use
circular array to efficiently implement which is complex. But with linked list, it is easy and straightforward.
That is why most of the language libraries use Linked List internally to implement these data structures.

 Space Efficient in Some Cases : Linked List might turn out to be more space efficient compare to arrays in
cases where we cannot guess the number of elements in advance. In case of arrays, the whole memory for
items is allocated together. Even with dynamic sized arrays like vector in C++ or list in Python or ArrayList in
Java. the internal working involves de-allocation of whole memory and allocation of a bigger chunk when
insertions happen beyond the current capacity.

 Circular List with Deletion/Addition : Circular Linked Lists are useful to implement CPU round robin
scheduling or similar requirements in the real world because of the quick deletion/insertion in a circular
manner.

(b)Write an algorithm to add a new node after the specifiéd location of nodes in linked list. 3

(c) Write an algorithm to remove the specified node from the doubly linked list. 4

ii. Delete node at specific location :

1. IF HEAD = NULL then Write UNDERFLOW

Go to Step 9

[END OF IF]

2. SET TEMP = HEAD

3. Repeat Step 4 while TEMP -> DATA != ITEM

4. SET TEMP = TEMP -> NEXT

[END OF LOOP]

5. SET PTR = TEMP -> NEXT

6. SET TEMP -> NEXT = PTR -> NEXT

7. SET PTR -> NEXT -> PREV = TEMP

8. FREE PTR

9. EXIT

(d) How circular linked list over come the short comings of linear linked list ? 2

A circular linked list is a data structure where the last node points back to the first node, forming a closed loop.

 Structure: All nodes are connected in a circle, enabling continuous traversal without encountering NULL.

 Difference from Regular Linked List: In a regular linked list, the last node points to NULL, whereas in a circular
linked list, it points to the first node.
  Uses: Ideal for tasks like scheduling and managing playlists, where smooth and repeated.

(e)Write an algorithm to add a new element at the end of circular linked list. 3

1. If PTR = NULL

2. Write OVERFLOW

3. Go to Step 1

[END OF IF]

4. SET NEW_NODE = PTR

5. SET PTR = PTR -> NEXT

6. SET NEW_NODE -> DATA = VAL

7. SET NEW_NODE -> NEXT = HEAD

8. SET TEMP = HEAD

9. Repeat Step 10 while TEMP -> NEXT != HEAD

10. SET TEMP = TEMP -> NEXT

[END OF LOOP]

11. SET TEMP -> NEXT = NEW_NODE

12. EXIT

3.(a) How circular queues solve the limitations of a queue ?2

A circular queue solves the linear queue's memory wastage by connecting the end back to the start, allowing empty
spaces at the front (after dequeues) to be reused by new insertions, preventing the "full queue" issue prematurely
and ensuring efficient use of fixed-size arrays, making it ideal for buffer management where continuous data flow is
needed.

A circular queue is a linear data structure that overcomes the limitations of a simple queue. In a normal array
implementation, dequeue() can be O(n) or we may waste space. Using a circular array, both enqueue() and
dequeue() can be done in O(1).

(b) Write an algorithm to delete an element from circular queue. 3

DELETE_CQUEUE(CQ, FRONT, REAR, MAX)

1. If FRONT = -1 then

2. Print "QUEUE UNDERFLOW"

3. Exit

4. End If

5. ITEM ← CQ[FRONT]
6. If FRONT = REAR then

7. FRONT ← -1

8. REAR ← -1

9. Else

10. FRONT ← (FRONT + 1) mod MAX

11. End If

12. Print "Deleted element =", ITEM

(c)How to add an element to the queue which have some element using linked list ? 2

(d) Suppose the following sequences list the nodes of binary tree T in preorder and in-order respectively.

Preorder : A B D E G H C F

In-order : D B G E H A C F

Draw the binary tree. 4

Step 1: Root

 First element of Preorder is the root

Root = A

Step 2: Split Inorder using root

A
Inorder:
DBGEH|A|CF /\

 Left subtree (of A): D B G E H B C

 Right subtree (of A): C F /\ \

Step 3: Left Subtree of A D E F

Preorder (remaining): B D E G H C F /\

 Root of left subtree = B G H

Split inorder left part using B:

D|B|GEH

 Left child of B: D

 Right subtree of B: G E H

Step 4: Right Subtree of B

Preorder continues: D E G H ...

  Root = E

Split inorder G E H using E:

G|E|H

 Left child of E = G

 Right child of E = H

Step 5: Right Subtree of A

Inorder right part: C F

Preorder part: C F

 Root = C

 Right child = F

(e) What is Deque ? Why it is used ? How to Count total number of elements in deque ? 1+1+2

A Deque (Double Ended Queue) is a linear data structure in which insertion and deletion of elements can be
performed at both ends, i.e., front and rear.

Deque is used when elements need to be added or removed from both ends efficiently, such as in sliding window
problems, undo–redo operations, CPU scheduling, etc.

How to count total number of elements in a Deque? (2 marks)

Assume deque is implemented using circular array with size MAX.

 If FRONT = -1, then

→ Number of elements = 0

 If FRONT ≤ REAR, then

Number of elements=(REAR−FRONT +1)

 If FRONT > REAR, then

Number of elements=(MAX −FRONT )+(REAR+1)

4) (a) What is top in a Stack ? Write down the uses of top in a stack. 1+2

TOP is a variable that stores the position (index) of the topmost element of the stack.

Uses of TOP in a Stack :

1. Insertion (PUSH operation):

TOP is increased by 1 before inserting a new element at the top of the stack.

2. Deletion (POP operation):

The element at the position pointed by TOP is removed, and TOP is decreased by 1.

3. Overflow and Underflow checking:

o Overflow: When TOP = MAX – 1, stack is full.

o Underflow: When TOP = -1, stack is empty.

(b) There are changes in stack if an element pops from the stack which may be NULL or may not be NULL. Write an
algo of pop operation from a stack using as a linked list. 3
(c) Transform the following infix expression into equivalent postfix expression ;

Infix Expression : 4 $2 *3-3 + 8/4 *(1 + 1). 4

Characte Stack Postfix

r

4 — 4

$ $ 4

2 $ 42

* * 42$

3 * 42$3

− − 42$3*

3 − 42$3*3

+ + 42$3*3−

8 + 42$3*3−8

/ +/ 42$3*3−8

4 +/ 42$3*3−84

* +* 42$3*3−84/

( +*( 42$3*3−84/

1 +*( 42$3*3−84/1

+ + * ( + 42$3*3−84/1

1 + * ( + 42$3*3−84/11

) +* 42$3*3−84/11+

End — 42$3*3−84/11+*
+

So,postfix expression of the given infix expression is : 42$3*3−84/11+*+

(d)Write down two Applications of stacks. 2

 Expression evaluation and conversion

Stacks are used to evaluate postfix/prefix expressions and to convert infix expressions into postfix or prefix
form.
  Function calls and recursion
Stacks are used to manage function calls, local variables, and return addresses during recursion.

(e)What is the definition of degree of a node ? Give an example. 1+1

The degree of a node in a tree is the number of children (sub-nodes) directly connected to that node.

Example

Here, degree of node A is 2.

5)(a) What is a complete binary tree ? What is its depth ?Give an example.2+2

 A complete binary tree is a special type of binary tree where all the levels of the tree are filled completely
except the lowest level nodes which are filled from as left as possible.
Example:

Fig. – complete binary tree

i. Depth : The depth of binary tree is the maximum level of any leaf in the tree. This equals the length of the
longest path from the root to any leaf. Depth of below Fig. tree is 2.
A

B C

D E F

(b) Write an algorithm to traverse a binary search tree in in-order fashion. 3

Algorithm for inorder traversal :

Inorder (INFO, LEFT, RIGHT, ROOT)

1. [Push NULL onto STACK and initialize PTR]

Set TOP = 1, STACK[1] = NULL and PTR = ROOT

2. Repeat while PTRNULL

[Push leftmost path onto STACK]

a. Set TOP = TOP + 1 and

STACK [TOP] = PTR

b. Set PTR = LEFT [PTR]

End loop

3. Set PTR = STACK[TOP] and TOP = TOP – 1

4. Repeat steps 5 to 7 while PTR  NULL

5. Apply process to INFO[PTR]

6. [Right Child?] If RIGHT [PTR]  NULL

Then

a. Set PTR = RIGHT [PTR]

b. goto step 2

Endif

7. Set PTR = STACK[TOP] and TOP = TOP – 1

End of Step 4 Loop

[Link]

(c) Write down listing of nodes using preorder and post order traversal of the following binary tree. 2+2

Preorder Traversal (Root – Left – Right)

A , B , D, G , C , E , H , I , F
Postorder Traversal (Left – Right – Root)

G, D, B, H , I, E, F , C , A

(d)What is AVL Tree ? Is the following tree is AVL Tree or not ? Give explanation. 1+3

An AVL tree defined as a self-balancing Binary Search Tree (BST) where the difference between heights of left and
right subtrees for any node cannot be more than one.
Balance Factor = left subtree height - right subtree height
For a Balanced Tree(for every node): -1 ≤ Balance Factor ≤ 1
 Example of an AVL Tree:

6)(a) How linear search differ from Binary search method ?3

Linear Search Binary Search

In linear search input data need not to be in sorted. In binary search input data need to be in sorted order.

It is also called sequential search. It is also called half-interval search.

The time complexity of linear search O(n). The time complexity of binary search O(log n).

Multidimensional array can be used. Only single dimensional array is used.

Linear search performs equality comparisons. Binary search performs ordering comparisons.

It is less complex. It is more complex.

It is very slow process. It is very fast process.

(b)What is the difference between internal sorting and external sorting ? 3

Internal Sorting External Sorting

Sorting is performed completely in main memory Sorting is performed using secondary storage such as
(RAM). hard disk or tape.

Suitable when the entire dataset fits into memory. Suitable when the dataset is too large to fit into
memory.

Access speed is fast because RAM access is quick. Access speed is slower due to disk I/O operations.

Requires less I/O operations. Requires large number of I/O operations.

Implementation is simple. Implementation is complex.

Uses CPU time more than I/O time. Uses I/O time more than CPU time.

Temporary storage requirement is low. Requires large temporary storage.

 Performance mainly depends on CPU efficiency. Performance mainly depends on disk access speed.

Suitable for small to medium-sized data. Suitable for very large data files.

Examples: Bubble sort, Selection sort, Insertion sort, Examples: External merge sort, Balanced merge sort,
Quick sort, Heap sort. Polyphase merge sort.

(c)Consider list (50, 40, 20, 60, 80, 100, 45, 70, 105). What is sorted list it the list is sorted using quick sort
technique ? Explain every step. 9

7)(a) What is array ? Why it is used ? 1+2

An array can be defined as the collection of the sequential memory locations, which can be referred to
by a single name along with a number known as the index, to access a particular field or data.
The general form of declaration is : type variable-name [size];
For example, when we want to store 10 integer values, then we can use the following declaration, int A[10].

 Efficient and Fast Access: Arrays allow direct and efficient access to any element in the collection with
constant access time, as the data is stored in contiguous memory locations.

 Memory Efficiency: Arrays store elements in contiguous memory, allowing efficient allocation in a single
block and does not require extra storage for linking different blocks.

 Versatility: Arrays can be used to store a wide range of data types, including integers, floating-point numbers,
characters, and even complex data structures such as objects and pointers.

 Compatibility with hardware: The array data structure is compatible with most hardware architectures,
making it a versatile tool for programming in a wide range of environments.

(b)Write an algorithm of marge sort technique. 5

MERGE_SORT (a, p, r) :

1. if p < r

2. then q ← |_ (p + r)/2 _|

3. MERGE-SORT (A, p, q)

4. MERGE-SORT (A, q + 1, r)

5. MERGE (A, p, q, r)
MERGE (A, p, q, r) :
1. n1 = q – p + 1
 2. n2 = r – q
3. Create arrays L [1 .........n1 + 1] and R [1......n2 + 1]
4. for i = 1 to n1 do

L[i] = A [p + i – 1]
endfor
5. for j = 1 to n2 do

R[j] = A[q + j]
endfor
6. L[n1 + 1] = ∞, R[n2 + 1] = ∞
7. i = 1, j = 1

8. for k = p to r
do
if L[i] <= R[j]
then A[k] ← L[i]
i=i+1
else A[k] = R[j]

j=j+1

endif

endfor

9. exit

(c)Write a function of transpose of a matrix. 3

#include <stdio.h>

int main() {

int n = 3;

int a[3][3] = {

{1, 2, 3},

{4, 5, 6},

{7, 8, 9}

};

// Transpose in-place

for (int i = 0; i < n; i++) {

for (int j = i + 1; j < n; j++) {

int temp = a[i][j];

a[i][j] = a[j][i];
 a[j][i] = temp;

// Display transpose

printf("Transpose of the matrix:\n");

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

printf("%d ", a[i][j]);

printf("\n");

return 0;

(d)What is Array of pointers ? 2

An array of pointers is a collection of variables where each element of the array is a pointer, meaning it stores
the memory address of another data element rather than the data itself. This allows for managing multiple,
potentially non-contiguous, memory locations through a single array structure.

Syntax in C: pointer_type *array_name [array_size];

(e) What is the address of a [1] [3] element in Row major arrangement ? The array is a [4][3] and base address is 500
and data type of array is integer. 2

Row major order :

Address of A[I][J] = B + W * ((I – LR) * N + (J – LC))

I = Row Subset of an element whose address to be found,

J = Column Subset of an element whose address to be found,
B = Base address,
W = Storage size of one element store in an array(in byte),
LR = Lower Limit of row/start row index of the matrix(If not given assume it as zero),
LC = Lower Limit of column/start column index of the matrix(If not given assume it as zero),
N = Number of column given in the matrix.

Given

 Array = A[4][3]

 Element = A[1][3]

 Base address B=500

 Data type = integer → W =4 bytes

 Lower limit of row LR=0(not given, so assumed 0)

 Lower limit of column LC=0 (not given, so assumed 0)

 Number of columns N=3

Address=500+4×((1−0)×3+(3−0))

=500+4*(3+3)

=500+4*6

=524

Year-2017

2. (4+4)+7

(a) Implement typical stack operation when stacks are represented using (1) arrays and (2) using singly linked lists.

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. It can be implemented using an
array by treating the end of the array as the top of the stack.

A stack can be implemented using an array where we maintain:

 An integer array to store elements.

 A variable capacity to represent the maximum size of the stack.

 A variable top to track the index of the top element. Initially, top = -1 to indicate an empty stack.

Operations On Stack using array:

Push Operation:

Adds an item to the stack. If the stack is full, then it is said to be an Overflow condition.

 Before pushing the element to the stack, we check if the stack is full.

 If the stack is full (top == capacity-1) , then Stack Overflows and we cannot insert the element to the stack.

 Otherwise, we increment the value of top by 1 (top = top + 1) and the new value is inserted at top position .

 The elements can be pushed into the stack till we reach the capacity of the stack.
Pop Operation:

Removes an item from the stack. The items are popped in the reversed order in which they are pushed. If the stack is
empty, then it is said to be an Underflow condition.

 Before popping the element from the stack, we check if the stack is empty .

 If the stack is empty (top == -1), then Stack Underflows and we cannot remove any element from the stack.

 Otherwise, we store the value at top, decrement the value of top by 1 (top = top – 1) and return the stored
top value.
A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. It can be implemented using
a linked list, where each element of the stack is represented as a node. The head of the linked list acts as the top of
the stack.

Declaration of Stack using Linked List

A stack can be implemented using a linked list where we maintain:

 A Node structure/class that contains:

data → to store the element.
next → pointer/reference to the next node in the stack.

 A pointer/reference top that always points to the current top node of the stack.
Initially, top = null to represent an empty stack.

Operations on Stack using Linked List

Push Operation

Adds an item to the stack. Unlike array implementation, there is no fixed capacity in linked list. Overflow occurs only
when memory is exhausted.

 A new node is created with the given value.

 The new node’s next pointer is set to the current top.

 The top pointer is updated to point to this new node.

Pop Operation

Removes the top item from the stack. If the stack is empty, it is said to be an Underflow condition.

 Before deleting, we check if the stack is empty (top == NULL).

 If the stack is empty, underflow occurs and deletion is not possible.

 Otherwise, we store the current top node in a temporary pointer.

 Move the top pointer to the next node.

 Delete the temporary node to free memory.

(b) Define binary search tree. Write an algorithm to implement insertion operation.
A Binary Search Tree (BST) is a type of binary tree data structure in which each node contains a unique key and
satisfies a specific ordering property:

 All nodes in the left subtree of a node contain values strictly less than the node’s value.

 All nodes in the right subtree of a node contain values strictly greater than the node’s value.

Fig.-Binary search tree

3. 7+8

(a) Write an algorithm to convert INFIX expression into POSTFIX expression.

Polish (Q, P)

Let Q is an arithmetic expression written in infix notation. This algorithm finds the equivalent postfix expression P.

1. Push "("onto STACK, and add ")" to end of Q.

2. Scan Q from left to right and repeat steps 3 to 6 for each element of Q until the STACK is empty.
3. If an operand is encountered, add it to P.

If an operator ⦻ is encountered, then:

4. If a left parenthesis is encountered push it onto STACK.
5.

precedence as or higher precedence than ⦻.

a. Repeatedly pop from STACK and add to P each operator (on the top of STACK) which has the same

b. Add ⦻ to STACK.
[End if]
6. If a right parenthesis is encountered, then:
a. Repeatedly pop from STACK and add to P each operator (on the top of STACK) until a left parenthesis is
encountered.
b. Remove the left parenthesis [Do not add it to P]
[End if]
[End of step 2]

7. End.

(b) Define AVL tree? Construction AVL tree for following data: 1, 2, 3, 4, 8, 7, 6, 5, 11, 10, 12

An AVL tree defined as a self-balancing Binary Search Tree (BST) where the difference between heights of left and
right subtrees for any node cannot be more than one.
Balance Factor = left subtree height - right subtree height
For a Balanced Tree(for every node): -1 ≤ Balance Factor ≤ 1

Example of an AVL Tree:

4. 7+8

(a) Give an algorithm to reverse the elements of a single linked lists without using a temporary list.

To reverse a linear linked list, three pointer fields are used.

These are PREV, PTR, REV which hold the address of previous node current node and will maintain the linked list.

Algorithm:

7. PTR =FIRST
8. TPT=NULL
9. Repeat step 4 while PTR != NULL
10. REV = PREV
11. PREV = PTR
12. PTR PTR -> LINK
13. PREV -> LINK = REV
[End of while loop]
14. START = PREV
15. Exit

(b) Write algorithm to insert and delete elements from a doubly linked list.

5. 2+(2+2)+4

(a) Write down the merge sort algorithm.

Merge sort :
a. Merge sort is a sorting algorithm that uses the idea of divide and conquer.
b. This algorithm divides the array into two halves, sorts them separately and then merges them.
c. This procedure is recursive, with the base criteria that the number of elements in the array is not more than 1.
ALGORITHM:
MERGE_SORT (a, p, r) :

4. if p < r

5. then q ← |_ (p + r)/2 _|

6. MERGE-SORT (A, p, q)

4. MERGE-SORT (A, q + 1, r)

5. MERGE (A, p, q, r)
MERGE (A, p, q, r) :
10. n1 = q – p + 1
11. n2 = r – q
12. Create arrays L [1 .........n1 + 1] and R [1......n2 + 1]
13. for i = 1 to n1 do

L[i] = A [p + i – 1]
endfor
14. for j = 1 to n2 do

R[j] = A[q + j]
endfor
15. L[n1 + 1] = ∞, R[n2 + 1] = ∞
16. i = 1, j = 1

17. for k = p to r
do
if L[i] <= R[j]
then A[k] ← L[i]
i=i+1
else A[k] = R[j]

j=j+1

endif

endfor

18. exit

(b) What are the applications of hashing data structure ?

1. Hashing provides constant time search, insert and delete operations on average. This is why hashing is one of
the most used data structure, example problems are, distinct elements, counting frequencies of items,
finding duplicates, etc.

2. Database indexing: Hashing is used to index and retrieve data efficiently in databases and other data storage
systems.

3. Dictionaries : To implement a dictionary so that we can quickly search a word

4. Password storage: Hashing is used to store passwords securely by applying a hash function to the password
and storing the hashed result, rather than the plain text password.

5. Network Routing: Determining the best path for data packets

6. Bloom Filters : Bloom filter is a space optimized and probabilistic version of hashing and has huge
applications like spam filtering, recommendations.

7. Cryptography: Hashing is used in cryptography to generate digital signatures, message authentication codes
(MACs), and key derivation functions.

8. Load balancing: Hashing is used in load-balancing algorithms, such as consistent hashing, to distribute
requests to servers in a network.

(c) How does collision occur in hashing? Mention one solution to over come collision in hashing.

In Hashing, hash functions were used to generate hash values. The hash value is used to create an index for the
keys in the hash table. The hash function may return the same hash value for two or more keys. When two or
more keys have the same hash value, a collision happens. To handle this collision, we use Collision Resolution
Techniques.

There are two Collision Resolution Techniques:

Linear probing is a collision resolution technique used in open addressing hashing.

When two keys hash to the same index in a hash table, linear probing finds the next available empty slot by checking
the table sequentially.
Example, Using the hash function ‘key mod 7’, insert the following sequence of keys in the hash table-50, 700, 76, 85,
92, 73 and 101 Use linear probing technique for collision resolution.
Solution-

The given sequence of keys will be inserted in the hash table as-

Step-01:

 Draw an empty hash table.

 For the given hash function, the possible range of hash values is [0, 6].
 So, draw an empty hash table consisting of 7 buckets as-
Step-02:

 Insert the given keys in the hash table one by one.

 The first key to be inserted in the hash table = 50.
 Bucket of the hash table to which key 50 maps = 50 mod 7 = 1.
 So, key 50 will be inserted in bucket-1 of the hash table as-

Step-03:

 The next key to be inserted in the hash table = 700.

 Bucket of the hash table to which key 700 maps = 700 mod 7 = 0.
 So, key 700 will be inserted in bucket-0 of the hash table as-

Step-04:

 The next key to be inserted in the hash table = 76.

 Bucket of the hash table to which key 76 maps = 76 mod 7 = 6.
 So, key 76 will be inserted in bucket-6 of the hash table as-

Step-05:

 The next key to be inserted in the hash table = 85.

  Bucket of the hash table to which key 85 maps = 85 mod 7 = 1.
 Since bucket-1 is already occupied, so collision occurs.
 To handle the collision, linear probing technique keeps probing linearly until an empty bucket is found.
 The first empty bucket is bucket-2.
 So, key 85 will be inserted in bucket-2 of the hash table as-

Step-06:

 The next key to be inserted in the hash table = 92.

 Bucket of the hash table to which key 92 maps = 92 mod 7 = 1.
 Since bucket-1 is already occupied, so collision occurs.
 To handle the collision, linear probing technique keeps probing linearly until an empty bucket is found.
 The first empty bucket is bucket-3.
 So, key 92 will be inserted in bucket-3 of the hash table as-

Step-07:

 The next key to be inserted in the hash table = 73.

 Bucket of the hash table to which key 73 maps = 73 mod 7 = 3.
 Since bucket-3 is already occupied, so collision occurs.
 To handle the collision, linear probing technique keeps probing linearly until an empty bucket is found.
 The first empty bucket is bucket-4.
 So, key 73 will be inserted in bucket-4 of the hash table as-
Step-08:

 The next key to be inserted in the hash table = 101.

 Bucket of the hash table to which key 101 maps = 101 mod 7 = 3.
 Since bucket-3 is already occupied, so collision occurs.
 To handle the collision, linear probing technique keeps probing linearly until an empty bucket is found.
 The first empty bucket is bucket-5.
 So, key 101 will be inserted in bucket-5 of the hash table as-

(d) Write an algorithm to insert a node as the last node of a linked list.

1. Start
2. Create a new node NEW
3. Read DATA
4. Set NEW → DATA = DATA
5. Set NEW → NEXT = NULL
6. If HEAD == NULL then
a. Set HEAD = NEW
b. Go to Step 10
7. Set TEMP = HEAD
8. While TEMP → NEXT ≠ NULL
→ Set TEMP = TEMP → NEXT
9. Set TEMP → NEXT = NEW
10. Stop

6. 5+(6+2)+2

(a) Write down the relative advantages and disadvantages of array and linked list.

Advantages of Array Data Structure:

 Efficient and Fast Access: Arrays allow direct and efficient access to any element in the collection with
constant access time, as the data is stored in contiguous memory locations.
  Memory Efficiency: Arrays store elements in contiguous memory, allowing efficient allocation in a single
block and does not require extra storage for linking different blocks.

 Versatility: Arrays can be used to store a wide range of data types, including integers, floating-point numbers,
characters, and even complex data structures such as objects and pointers.

 Compatibility with hardware: The array data structure is compatible with most hardware architectures,
making it a versatile tool for programming in a wide range of environments.

Disadvantages of Array Data Structure:

 Fixed Size: Arrays have a fixed size set at creation. Expanding an array requires creating a new one and
copying elements, which is time-consuming and memory-intensive. Even dynamic sized arrays internally use
fixed sized memory allocation and de-allocation.

 Memory Allocation Issues: Allocating large arrays can cause memory exhaustion, leading to crashes,
especially on systems with limited resources.

 Insertion and Deletion Challenges: Adding or removing elements requires shifting subsequent elements,
making these operations inefficient.

Advantages Of Linked List:

 Dynamic data structure: A linked list is a dynamic arrangement so it can grow and shrink at runtime by
allocating and deallocating memory. So there is no need to give the initial size of the linked list.

 No memory wastage: In the Linked list, efficient memory utilization can be achieved since the size of the
linked list increase or decrease at run time so there is no memory wastage and there is no need to pre-
allocate the memory.

 Insertion and Deletion Operations: Insertion and deletion operations are quite easier in the linked list. There
is no need to shift elements after the insertion or deletion of an element only the address present in the next
pointer needs to be updated.

 Flexible: This is because the elements in Linked List are not stored in contiguous memory locations unlike the
array.

 Efficient for large data: When working with large datasets linked lists play a crucial role as it can grow and
shrink dynamically.

Disadvantages Of Linked List:

 Memory usage: More memory is required in the linked list as compared to an array. Because in a linked list,
a pointer is also required to store the address of the next element and it requires extra memory for itself.

 Traversal: In a Linked list traversal is more time-consuming as compared to an array. Direct access to an
element is not possible in a linked list as in an array by index. For example, for accessing a node at position n,
one has to traverse all the nodes before it.

 Reverse Traversing: In a singly linked list reverse traversing is not possible, but in the case of a doubly-linked
list, it can be possible as it contains a pointer to the previously connected nodes with each node. For
performing this extra memory is required for the back pointer hence, there is a wastage of memory.

 Lower efficiency at times: For certain operations, such as searching for an element or iterating through the
list, can be slower in a linked list.

 Not suited for small dataset: Cannot provide any significant benefits on small dataset compare to that of an
array.
(b) Write an algorithm to calculate average of a set of integers stored in a singly linked list. Explain if there will be any
improvement in time complexity of the algorithm if we use array to store the integers.

(c) Write an application where it is advantages to use doubly linked list instead of singly linked list.

Application where Doubly Linked List is more advantageous than Singly Linked List:

A Doubly Linked List(DLL) is a linear data structure that contains an extra pointer, typically called the previous pointer,
together with the next pointer and data which are there in a singly linked list.

Below are applications where using a doubly linked list is clearly more advantageous than a singly linked list:

1. Browser History (Back and Forward Navigation)

 Each visited webpage is stored as a node.

 The next pointer points to the next page.

 The previous pointer points to the previous page.

Why Doubly Linked List is Better:

 Enables backward traversal (Back button).

 Enables forward traversal (Forward button).

 Singly linked list cannot move backward without extra traversal.

Advantage: Fast navigation in both directions.

2. Undo and Redo Operations (Text Editors)

 Each user action is stored as a node.

 Previous pointer → Undo operation.

 Next pointer → Redo operation.

Why Doubly Linked List is Better:

 Supports both undo and redo efficiently.

 No need to traverse from the beginning.

✔ Advantage: Efficient action reversal.

3. Music / Video Playlist Navigation

 Each song or video is a node.

 User can move to next or previous media.

Why Doubly Linked List is Better:

 Direct backward movement is possible.

 Singly linked list supports only forward traversal.

✔ Advantage: Easy previous/next navigation.

7. Write short notes on any three of the following: 3x5

(a) Shortest path problem.

The shortest path algorithms are the ones that focuses on calculating the minimum travelling cost from source node
to destination node of a graph in optimal time and space complexities.

Types of Shortest Path Algorithms:

As we know there are various types of graphs (weighted, unweighted, negative, cyclic, etc.) therefore having a single
algorithm that handles all of them efficiently is not possible. In order to tackle different problems, we have different
shortest-path algorithms, which can be categorised into two categories:

Single Source Shortest Path Algorithms:

In this algorithm we determine the shortest path of all the nodes in the graph with respect to a single node i.e. we
have only one source node in this algorithms.

1. Depth-First Search (DFS)

2. Breadth-First Search (BFS)

3. Multi-Source BFS

4. Dijkstra's algorithm

5. Bellman-Ford algorithm

6. Topological Sort

7. A* search algorithm

All Pair Shortest Path Algorithms:

Contrary to the single source shortest path algorithm, in this algorithm we determine the shortest path between
every possible pair of nodes.

1. Floyd-Warshall algorithm

2. Johnson's algorithm

(b) Complexity of an algorithm.

Algorithm Complexity:

Suppose X is treated as an algorithm and N is treated as the size of input data, the time and space implemented by
the Algorithm X are the two main factors which determine the efficiency of X.

Time Factor − The time is calculated or measured by counting the number of key operations such as comparisons in
sorting algorithm.
Space Factor − The space is calculated or measured by counting the maximum memory space required by the
algorithm.

The complexity of an algorithm f(N) provides the running time and / or storage space needed by the algorithm with
respect of N as the size of input data.

Space Complexity:

Space complexity of an algorithm represents the amount of memory space needed the algorithm in its life cycle.

Space needed by an algorithm is equal to the sum of the following two components

A fixed part that is a space required to store certain data and variables (i.e. simple variables and constants, program
size etc.), that are not dependent of the size of the problem.

A variable part is a space required by variables, whose size is totally dependent on the size of the problem. For
example, recursion stack space, dynamic memory allocation etc.

Space complexity S(p) of any algorithm p is S(p) = A + Sp(I) Where A is treated as the fixed part and S(I) is treated as
the variable part of the algorithm which depends on instance characteristic I. Following is a simple example that tries
to explain the concept

Algorithm

SUM(P, Q)

Step 1 - START

Step 2 - R ← P + Q + 10

Step 3 - Stop

Here we have three variables P, Q and R and one constant. Hence S(p) = 1+3. Now space is dependent on data types
of given constant types and variables and it will be multiplied accordingly.

Time Complexity:

Time Complexity of an algorithm is the representation of the amount of time required by the algorithm to execute to
completion. Time requirements can be denoted or defined as a numerical function t(N), where t(N) can be measured
as the number of steps, provided each step takes constant time.

For example, in case of addition of two n-bit integers, N steps are taken. Consequently, the total computational time
is t(N) = c*n, where c is the time consumed for addition of two bits. Here, we observe that t(N) grows linearly as
input size increases.

(c) Euclid's algorithm.

(d) B-Tree

A B-Tree is a specialized m-way tree designed to optimize data access, especially on disk-based storage systems.
 In a B-Tree of order m, each node can have up to m children and m-1 keys, allowing it to efficiently manage
large datasets.
 The value of m is decided based on disk block and key sizes.
  One of the standout features of a B-Tree is its ability to store a significant number of keys within a single
node, including large key values. It significantly reduces the tree’s height, hence reducing costly disk
operations.
 B Trees allow faster data retrieval and updates, making them an ideal choice for systems requiring efficient
and scalable data management. By maintaining a balanced structure at all times,
 B-Trees deliver consistent and efficient performance for critical operations such as search, insertion, and
deletion.
Following is an example of a B-Tree of order 5 .

Properties of a B-Tree
A B Tree of order m can be defined as an m-way search tree which satisfies the following properties:
1. All leaf nodes of a B tree are at the same level, i.e. they have the same depth (height of the tree).
2. The keys of each node of a B tree (in case of multiple keys), should be stored in the ascending order.
3. In a B tree, all non-leaf nodes (except root node) should have at least m/2 children.
4. All nodes (except root node) should have at least m/2 - 1 keys.
5. If the root node is a leaf node (only node in the tree), then it will have no children and will have at least one
key. If the root node is a non-leaf node, then it will have at least 2 children and at least one key.
6. A non-leaf node with n-1 key values should have n non NULL children.
Application of B-tree : The main application of a B-tree is the organization of a huge collection of records into a file
structure. The organization should be in such a way that any record in it can be searched very efficiently i.e.,
insertion, deletion and modification operations can be carried out perfectly and efficiently.

Year-2018

15

2. Name one sorting technique that are recursive in nature and using this technique sort the following list. Clearly
show the algorithmic steps.

15 5 19 9 2 8 1 6 13 11

Compute the complexity of your algorithm.

3. 10 + (2 + 3)
(a) Write an algorithm to evaluate a postfix expression. Trace the same algorithm with stack contents for the
following expression:

ABC+*CBA-+* with A = 1 B = 3 C = 5

Algorithm to evaluate a postfix expression:

EVALUATE_POSTFIX(EXP)

1. Initialize an empty stack S

2. Scan the postfix expression EXP from left to right

3. For each symbol X in EXP:

a) If X is an operand

Push its value onto stack S

b) If X is an operator

i) Pop operand2 from stack S

ii) Pop operand1 from stack S

iii) Compute: RESULT = operand1 (X) operand2

iv) Push RESULT onto stack S

4. After scanning the complete expression,

the top of the stack contains the final result

5. Return top of stack

Ste Symbol Scanned Action Performed Stack Contents

p

1 A Push 1 1

2 B Push 3 1, 3

3 C Push 5 1, 3, 5

4 + Pop 5, 3 → 3+5=8 → Push 8 1, 8

5 * Pop 8, 1 → 1×8=8 → Push 8 8

6 C Push 5 8, 5

7 B Push 3 8, 5, 3

8 A Push 1 8, 5, 3, 1

9 - Pop 1, 3 → 3−1=2 → Push 2 8, 5, 2

10 + Pop 2, 5 → 5+2=7 → Push 7 8, 7

11 * Pop 7, 8 → 8×7=56 → Push 56 56

(b) What is sparse matrix ? How can be store sparse matrix in computer memory?
A sparse matrix in which most of its elements are zero. It is characterized by a small number of non-zero elements
compared to the total number of elements (mxn). In other words, a sparse matrix has a significant proportion of zero
values, often exceeding half of the total elements.

Given m and n, a sparse matrix of size mxn can be defined as follows:

 m: The number of rows

 n: The number of columns

For example, consider the following 4x4 matrix:

[ [0, 0, 7, 0],

[1, 0, 0, 0],

[2, 0, 5, 0],

[0, 8, 0, 4] ]

Sparse Matrix representations:

Representing a sparse matrix by a 2D array leads to wastage of lots of memory as zeroes in the matrix are of no use in
most of the cases. So, instead of storing zeroes with non-zero elements, we only store non-zero elements. This means
storing non-zero elements with triples- (Row, Column, value).

Sparse Matrix Representations can be done in many ways following are two common representations:

1. Array representation

2. Linked list representation

Method 1: Using Arrays:

2D array is used to represent a sparse matrix in which there are three rows named as

 Row: Index of row, where non-zero element is located

 Column: Index of column, where non-zero element is located

 Value: Value of the non zero element located at index - (row,column)

Method 2: Using Linked Lists

In linked list, each node has four fields. These four fields are defined as:

 Row: Index of row, where non-zero element is located

 Column: Index of column, where non-zero element is located

 Value: Value of the non-zero element located at index - (row,column)

 Next node: Address of the next node

4. 2+4+4+5

(a) What do you mean by a complete binary tree ?

Complete binary tree: A tree is called a complete binary tree if tree satisfies following conditions:

a. Each node has exactly two children except leaf node.

b. All leaf nodes are at same level.

c. If a binary tree contains m nodes at level l, it contains atmost 2m nodes at level l + 1.

Example:

Fig. – complete binary tree

(b) Explain the need of a height-balance tree ?

The above tree is a binary search tree and also a height-balanced tree.
Suppose we want to find the value 79 in the above tree. First, we compare the value of the root node. Since the value
of 79 is greater than 35, we move to its right child, i.e., 48. Since the value 79 is greater than 48, so we move to the
right child of 48. The value of the right child of node 48 is 79. The number of hops required to search the element 79
is 2.
Similarly, any element can be found with at most 2 jumps because the height of the tree is 2.
So it can be seen that any value in a balanced binary tree can be searched in O(logN) time where N is the number of
nodes in the tree. But if the tree is not height-balanced then in the worst case, a search operation can
take O(N) time.

(c) Write the recursive algorithm for post-order traversal of a binary tree.

Algorithm for postorder traversal :

Postorder (INFO, LEFT, RIGHT, ROOT)

1. [Push NULL onto STACK and initialize PTR]

Set TOP = 1, STACK[1] = NULL and PTR = ROOT

2. [Push leftmost path onto STACK]

Repeat steps 3 to 5 while PTR ≠ NULL

3. Set TOP = TOP + 1 and STACK [TOP] = PTR

[Pushes PTR on STACK]

4. If RIGHT [PTR] ≠NULL

Then

Set TOP = TOP + 1 and STACK [TOP] = RIGHT [PTR] Endif

5. Set PTR = LEFT [PTR]

End of step 2 loop

6. Set PTR = STACK [TOP] and TOP = TOP – 1

[Pops node from STACK]

7. Repeat while PTR > 0
a. Apply process to INFO [PTR]
b. Set PTR = STACK [TOP] and TOP = TOP – 1 End loop
8. If PTR < 0 Then
a. Set PTR = – PTR
b. goto step 2
Endif
9. Exit
(d) Write an algorithm to delete a node from a binary search tree.

DEL(INFO, LEFT, RIGHT, ROOT, AVAIL, ITEM)

A binary search tree T is in memory, and an ITEM of information is given.

This algorithm deletes ITEM from the tree.

1. [Find the locations of ITEM and its parent]

Call FIND(INFO, LEFT, RIGHT, ROOT, ITEM, LOC, PAR)
2. [ITEM in tree?]
If LOC = NULL, then write ITEM not in tree, and Exit.
3. [Delete node containing ITEM]
If RIGHT [LOC] ≠ NULL and LEFT[LOC] ≠ NULL, then :
Call CASEB(INFO, LEFT, RIGHT, ROOT, LOC, PAR)
Else:
Call CASEA(INFO, LEFT, RIGHT, ROOT, LOC, PAR)
[End of If structure]
4. [Return deleted node to the AVAIL list]
Set LEFT [LOC] := AVAIL and AVAIL := LOC
 5. Exit.

5. 5+6+4

(a) Explain the adjacency matrix representation of a graph with an example.

(b) Explain the BFS algorithm for graph traversal with an example.

Breadth First Search (BFS) :

The general idea behind a breadth first search beginning at a starting node A is as follows :
a. First we examine the starting node A.
b. Then, we examine all the neighbours of A, and so on.

c. We need to keep track of the neighbours of a node, and that no node is processed more than once.
d. This is accomplished by using a queue to hold nodes that are waiting to be processed, and by using a field
STATUS which tells us the current status of any node.
Algorithm : This algorithm executes a breadth first search on a graph G beginning at a starting node A.
i. Initialize all nodes to ready state (STATUS=1).

ii. Put the starting node A in queue and change its status to the waiting state (STATUS = 2).
iii. Repeat steps (iv) and (v) until queue is empty.
iv. Remove the front node N of queue. Process N and change the status of N to the processed state (STATUS = 3).
v. Add to the rear of queue all the neighbours of N that are in the ready state (STATUS=1) and change their status to
the waiting state (STATUS = 2).
[End of loop]
vi. End.
(c) What do you mean by B-tree ?

A B-Tree is a specialized m-way tree designed to optimize data access, especially on disk-based storage systems.
 In a B-Tree of order m, each node can have up to m children and m-1 keys, allowing it to efficiently manage
large datasets.
 The value of m is decided based on disk block and key sizes.
 One of the standout features of a B-Tree is its ability to store a significant number of keys within a single
node, including large key values. It significantly reduces the tree’s height, hence reducing costly disk
operations.
 B Trees allow faster data retrieval and updates, making them an ideal choice for systems requiring efficient
and scalable data management. By maintaining a balanced structure at all times,
 B-Trees deliver consistent and efficient performance for critical operations such as search, insertion, and
deletion.
Following is an example of a B-Tree of order 5 .

Properties of a B-Tree
A B Tree of order m can be defined as an m-way search tree which satisfies the following properties:
7. All leaf nodes of a B tree are at the same level, i.e. they have the same depth (height of the tree).
8. The keys of each node of a B tree (in case of multiple keys), should be stored in the ascending order.
 9. In a B tree, all non-leaf nodes (except root node) should have at least m/2 children.
10. All nodes (except root node) should have at least m/2 - 1 keys.
11. If the root node is a leaf node (only node in the tree), then it will have no children and will have at least one
key. If the root node is a non-leaf node, then it will have at least 2 children and at least one key.
12. A non-leaf node with n-1 key values should have n non NULL children.
Application of B-tree : The main application of a B-tree is the organization of a huge collection of records into a file
structure. The organization should be in such a way that any record in it can be searched very efficiently i.e.,
insertion, deletion and modification operations can be carried out perfectly and efficiently.
6. 4+6+3+2

(a) How can we represent a polynomial ?

(b) Show the implementation of a queue using stack(s).

(c) When do we call a binary tree as AVL tree?

A binary tree is called an AVL tree when it satisfies both of the following conditions:

1. It is a Binary Search Tree (BST)

For every node:

 All keys in the left subtree are smaller than the node’s key

 All keys in the right subtree are greater than the node’s key

2. It is Height Balanced

For every node in the tree, the balance factor(Balance Factor=Height of Left Subtree−Height of Right Subtree) is −1,
0, or +1

(d) Give an example of AVL tree of height three.

An AVL tree of height three is a balanced binary search tree where the longest path from the root to any leaf has
three edges (or four levels), with the key property that the height difference between any node's left and right
subtrees is at most one (-1, 0, or 1)
7. (2+3)+3+7

(a) Define Stack. How is it different from Queue?

Stack is a linear data structure that follows LIFO(Last in first out) principle i.e., entering and retrieving data is possible
from only one end. The entering and retrieving of data is also called push and pop operation in a stack.

Applications of Stack

Different applications of Stack are as follows:

 The stack data structure is used in the evaluation and conversion of arithmetic expressions.

 It is used for parenthesis checking and string reversal.

Topic Stack Queue

Definition A linear data structure that follows the Last A linear data structure that follows the First
In First Out (LIFO) principle. In First Out (FIFO) principle.

Primary Push (add an item), Pop (remove an item), Enqueue (add an item), Dequeue (remove
Operations Peek (view the top item) an item), Front (view the first item), Rear
(view the last item)

Insertion/Removal Elements are added and removed from the Elements are added at the rear and removed
same end (the top). from the front.
 Use Cases Function call management (call stack), Scheduling processes in operating systems,
expression evaluation and syntax parsing, managing requests in a printer queue,
undo mechanisms in text editors. breadth-first search in graphs.

Examples Browser history (back button), reversing a Customer service lines, CPU task scheduling.
word.

(b) What is a Priority Queue?

A priority queue is a data structure in which each element has been assigned a value called the priority of the
element and an element can be inserted or deleted not only at the ends but at any position on the queue.
A priority queue is a collection of elements such that each element has been assigned an explicit or implicit priority
and such that the order in which elements are deleted and processed comes from the following rules :
a. An element of higher priority is processed before any element of lower priority.
b. Two elements with the same priority are processed to the order in which they were inserted to the queue.
Types of priority queues are :

1. Ascending priority queue : In ascending priority queue, elements can be inserted in an order. But, while deleting
elements from the queue, always a small element to be deleted first.
2. Descending priority queue : In descending priority queue, elements are inserted in any order but while deleting
elements from the queue always a largest element to be deleted first.
Applications of priority queue :

1. The typical example of priority queue is scheduling the jobs in operating system. Typically operating system
allocates priority to jobs. The jobs are placed in the queue and position 1 of the job in priority queue determines
their priority.
2. In network communication, to manage limited bandwidth for transmission, the priority queue is used.
In simulation modelling, to manage the discrete events the priority queue is used.

(c) Write an algorithm to concatenate two singly linked lists.

1. Start
2. If HEAD1 == NULL, then
→ Set HEAD1 = HEAD2 and go to Step 7
3. If HEAD2 == NULL, then
→ List remains unchanged, go to Step 7
4. Set TEMP = HEAD1
5. Traverse the first list until the last node:
While (TEMP →NEXT != NULL)
→ Set TEMP = TEMP → NEXT
6. Set TEMP → NEXT = HEAD2
7. Stop

8. Write short notes (any three): 3x5

(a) Degree.

Degree-

 Degree of a node is the total number of children of that node.

 Degree of a tree is the highest degree of a node among all the nodes in the tree.
Example-

Here,

 Degree of node A = 2

 Degree of node B = 3

 Degree of node C = 2

 Degree of node D = 0

 Degree of node E = 2

 Degree of node F = 0

 Degree of node G = 1

 Degree of node H = 0

 Degree of node I = 0

 Degree of node J = 0

 Degree of node K = 0

(b) Circular linked list.

A circular linked list is a data structure where the last node points back to the first node, forming a closed loop.

 Structure: All nodes are connected in a circle, enabling continuous traversal without encountering NULL.

 Difference from Regular Linked List: In a regular linked list, the last node points to NULL, whereas in a circular
linked list, it points to the first node.

 Uses: Ideal for tasks like scheduling and managing playlists, where smooth and repeated.

Types of Circular Linked Lists

We can create a circular linked list from both singly linked lists and doubly linked lists. So, circular linked lists are
basically of two types:

1. Circular Singly Linked List

In Circular Singly Linked List, each node has just one pointer called the "next" pointer. The next pointer of the last
node points back to the first node and this results in forming a circle. In this type of Linked list, we can only move
through the list in one direction.
2. Circular Doubly Linked List:

In circular doubly linked list, each node has two pointers prev and next, similar to doubly linked list. The prev pointer
points to the previous node and the next points to the next node. Here, in addition to the last node storing the
address of the first node, the first node will also store the address of the last node.

(c) One Technique for collision handling.

Collision Resolution Techniques-

In Hashing, collision resolution techniques are classified as-

Linear probing is a collision resolution technique used in open addressing hashing.

When two keys hash to the same index in a hash table, linear probing finds the next available empty slot by checking
the table sequentially.
Example, Using the hash function ‘key mod 7’, insert the following sequence of keys in the hash table-50, 700, 76, 85,
92, 73 and 101 Use linear probing technique for collision resolution.
Solution-

The given sequence of keys will be inserted in the hash table as-

Step-01:

 Draw an empty hash table.

 For the given hash function, the possible range of hash values is [0, 6].
 So, draw an empty hash table consisting of 7 buckets as-
Step-02:

 Insert the given keys in the hash table one by one.

 The first key to be inserted in the hash table = 50.
 Bucket of the hash table to which key 50 maps = 50 mod 7 = 1.
 So, key 50 will be inserted in bucket-1 of the hash table as-

Step-03:

 The next key to be inserted in the hash table = 700.

 Bucket of the hash table to which key 700 maps = 700 mod 7 = 0.
 So, key 700 will be inserted in bucket-0 of the hash table as-

Step-04:

 The next key to be inserted in the hash table = 76.

 Bucket of the hash table to which key 76 maps = 76 mod 7 = 6.
 So, key 76 will be inserted in bucket-6 of the hash table as-
Step-05:

 The next key to be inserted in the hash table = 85.

 Bucket of the hash table to which key 85 maps = 85 mod 7 = 1.
 Since bucket-1 is already occupied, so collision occurs.
 To handle the collision, linear probing technique keeps probing linearly until an empty bucket is found.
 The first empty bucket is bucket-2.
 So, key 85 will be inserted in bucket-2 of the hash table as-

Step-06:

 The next key to be inserted in the hash table = 92.

 Bucket of the hash table to which key 92 maps = 92 mod 7 = 1.
 Since bucket-1 is already occupied, so collision occurs.
 To handle the collision, linear probing technique keeps probing linearly until an empty bucket is found.
 The first empty bucket is bucket-3.
 So, key 92 will be inserted in bucket-3 of the hash table as-

Step-07:

 The next key to be inserted in the hash table = 73.

 Bucket of the hash table to which key 73 maps = 73 mod 7 = 3.
 Since bucket-3 is already occupied, so collision occurs.
  To handle the collision, linear probing technique keeps probing linearly until an empty bucket is found.
 The first empty bucket is bucket-4.
 So, key 73 will be inserted in bucket-4 of the hash table as-

Step-08:

 The next key to be inserted in the hash table = 101.

 Bucket of the hash table to which key 101 maps = 101 mod 7 = 3.
 Since bucket-3 is already occupied, so collision occurs.
 To handle the collision, linear probing technique keeps probing linearly until an empty bucket is found.
 The first empty bucket is bucket-5.
 So, key 101 will be inserted in bucket-5 of the hash table as-

(d) B+ tree.

A B+ Tree is an advanced data structure used in database systems and file systems to maintain sorted data for fast
retrieval, especially from disk. It is an extended version of the B Tree, where all actual data is stored only in the leaf
nodes, while internal nodes contain only keys for navigation.

Components of B+ Tree

 Leaf nodes store all the key values and pointers to the actual data.

 Internal nodes store only the keys that guide searches.

 All leaf nodes are linked together, supporting efficient sequential and range queries.

This structure makes the B+ Tree balanced, disk-efficient, and ideal for database indexing.

Features of B+ Trees

 Balanced: Auto-adjusts when data is added or removed, keeping search time efficient.
  Multi-level: Has a root, internal nodes, and leaf nodes (which store the data).

 Ordered: Maintains sorted keys, making range queries easy.

 High Fan-out: Each node has many children, keeping the tree short and fast.

 Cache-friendly: Works well with memory caches for better speed.

 Disk-efficient: Ideal for disk storage due to fast data access.

How B+ Trees Work

The Structure of the Internal Nodes of a B+ Tree of Order 'a' is as Follows

 Each internal node is of the form: <P1, K1, P2, K2, ....., Pc-1, Kc-1, Pc> where c <= a and each Pi is a tree pointer
(i.e points to another node of the tree) and, each Ki is a key-value (see diagram-I for reference).

 Every internal node has :K1 < K2< .... < Kc-1

 For each search field value 'X' in the sub-tree pointed at by Pi, the following condition holds: K i-1 < X <= Ki, for
1 < I < c and, Ki-1 < X, for i = c (See diagram I for reference)

 Each internal node has at most 'aa tree pointers.

 The root node has, at least two tree pointers, while the other internal nodes have at least \ceil(a/2) tree
pointers each.

 If an internal node has 'c' pointers, c <= a, then it has 'c - 1' key values.

Structure of Internal Node

The Structure of the Leaf Nodes of a B+ Tree of Order 'b' is as Follows

 Each leaf node is of the form: <<K1, D1>, <K2, D2>, ....., <Kc-1, Dc-1>, Pnext> where c <= b and each Di is a data
pointer (i.e points to actual record in the disk whose key value is Ki or to a disk file block containing that
record) and, each K1 is a key value and, Pnext points to next leaf node in the B+ tree (see diagram II for
reference).

 Every leaf node has : K1 < K2< .... < Kc-1, c <= b

 Each leaf node has at least \ceil(b/2) values.

 All leaf nodes are at the same level.

In the below diagram, we can see that using the Pnext pointer it is viable to traverse all the leaf nodes, just like a linked
list, thereby achieving ordered access to the records stored in the disk.

Year-2019

Group-B

2. (a) Write an algorithm to reverse a single linked list. 5

1. To reverse a linear or single linked list, three pointer fields are used.
2. These are PREV, PTR, REV which hold the address of previous node, current node and will maintain the linked
list.

Algorithm :

1. PTR = FIRST

2. TPT = NULL

3. Repeat step 4 while PTR != NULL

4. REV = PREV

5. PREV = PTR

6. PTR = PTR LINK

7. PREV  LINK = REV

[End of while loop]

8. START = PREV

9. Exit

(b)Suppose, we use linked list to represent a polynomial . Show how do we represent the following polynomial:
10x7+5x4+3x2+6. 4

(c) Show how can we represent the following sparse matrix ? 6

10001

0 1 01 0

00001

00110

10010

3)(a)Show both adjacency matrix representation and adjacency list representation of the following graph. 3+3
 c
From the given figure, the graph is an undirected graph with vertices:
V = {A, B, C, D, E}
Edges observed from the graph
 A—B
 A—E
 A—C
 B—C
 C—D
 E—D
Adjacency Matrix Representation :
Let us take the vertex order as:
A, B, C, D, E
For an undirected graph:
 Write 1 if there is an edge between two vertices
 Write 0 otherwise
A B C D E
A 0 1 1 0 1
B 1 0 1 0 0
C 1 1 0 1 0
D 0 0 1 0 1
E 1 0 0 1 0

Adjacency List Representation :

Each vertex stores a list of its adjacent vertices.
 A→B→C→E
 B→A→C
 C→A→B→D
 D→C→E
 E→A→D

(b) Consider the following graph :

 G
Show the order of node traversals if you use BFS graph traversal technique and start from vertex A. Show
the content of queue in every step. 5

Graph (Adjacency)
 A→B
 B → A, C, D
 C → B, D, E
 D → B, C, E, F
 E → C, D, F
 F → D, E, G
 G→F
We will apply BFS (Breadth First Search) starting from vertex A.
Rule:
 Visit a node
 Enqueue all its unvisited adjacent nodes
 Process queue FIFO
Step 1
Start from A
 Visit: A
 Queue: [A]

Step 2
Dequeue A
 Visit adjacent node: B
 Queue: [B]
Traversal so far: A

Step 3
Dequeue B
 Adjacent nodes: A (visited), C, D
 Enqueue C, D
 Queue: [C, D]
Traversal so far: A, B

Step 4
Dequeue C
 Adjacent nodes: B (visited), D (already in queue), E
 Enqueue E
 Queue: [D, E]
Traversal so far: A, B, C
Step 5
Dequeue D
 Adjacent nodes: B, C (visited), E (already in queue), F
 Enqueue F
 Queue: [E, F]
Traversal so far: A, B, C, D

Step 6
Dequeue E
 Adjacent nodes: C, D (visited), F (already in queue)
 Queue: [F]
Traversal so far: A, B, C, D, E
Step 7
Dequeue F
 Adjacent nodes: D, E (visited), G
 Enqueue G
 Queue: [G]
Traversal so far: A, B, C, D, E, F

Step 8
Dequeue G
 Adjacent node: F (visited)
 Queue: [ ] (empty)
Traversal so far: A, B, C, D, E, F, G

So, the sequence is A → B → C → D → E → F → G

(c) Write recursive Binary search algorithm. 4

Binary search works on a sorted array.
Binary_Search(A, LB, UB, KEY)

1. if (LB > UB)

return -1;

2. MID = (LB + UB) / 2;

3. if (A[MID] == KEY)
return MID;
4. else if (KEY < A[MID])
return Binary_Search(A, LB, MID - 1, KEY);
5. else
return Binary_Search(A, MID + 1, UB, KEY);

4)(a) Show the every step of constructing binary search tree if you are given the following list of nodes : 5 16, 7, 15,
20, 9, 2, 6

Step 1: Insert 5

Step 2: Insert 16 (16>5,right of 5)

Step 3: Insert 7 (7 > 5 → go right, 7 < 16 → left of 16)
Step 4: Insert 15(15 > 5 → right, 15 < 16 → left, 15 > 7 → right of 7)
Step 5: Insert 20(20 > 5 → right, 20 > 16 → right of 16)
Step 6: Insert 9(9 > 5 → right, 9 < 16 → left, 9 > 7 → right, 9 < 15 → left of 15)
Step 7: Insert 2(2 < 5 → left of 5)
Step 8: Insert 6(6 > 5 → right, 6 < 16 → left, 6 < 7 → left of 7)

(b)Show the post-order traversal order of nodes in the binary search tree obtained in above question
4(a). 4
Ans: 2, 6, 9, 15, 7, 20, 16, 5
(c)Give algorithm Bar in-order binary tree traversal. 5
Algorithm for inorder traversal :
Inorder (INFO, LEFT, RIGHT, ROOT)
1. [Push NULL onto STACK and initialize PTR]
Set TOP = 1, STACK[1] = NULL and PTR = ROOT
2. Repeat while PTRNULL
[Push leftmost path onto STACK]
a. Set TOP = TOP + 1 and STACK [TOP] = PTR
b. Set PTR = LEFT [PTR]
End loop
3. Set PTR = STACK[TOP] and TOP = TOP – 1
4. Repeat steps 5 to 7 while PTR  NULL
5. Apply process to INFO[PTR]
6. [Right Child?] If RIGHT [PTR]  NULL Then a. Set PTR = RIGHT [PTR] b. goto step 2 Endif
7. Set PTR = STACK[TOP] and TOP=TOP-1
End of Step 4 loop
[Link]

(d)Define binary tree. 1

A Binary Tree Data Structure is a hierarchical data structure in which each node has at most two children,
referred to as the left child and the right child.

5 (a) Write the algorithm of insertion sort. 5

INSERTION_SORT(A)
(A = array of elements)

1. for j ← 2 to length[A]

2. do key ← A[j] /*Insert A[j] into the sorted sequence A[1....j – 1].*/

3. i←j–1

4. while i > 0 and A[i] > key

5. do A[i + 1] ← A[i]

6. i←i–1

7. A[i + 1] ←key

(b) What is linear probing in Hashing ? 3

Linear probing is a collision resolution technique used in open addressing hashing.
When two keys hash to the same index in a hash table, linear probing finds the next available empty slot by checking
the table sequentially.
Example, Using the hash function ‘key mod 7’, insert the following sequence of keys in the hash table-50, 700, 76, 85,
92, 73 and 101 Use linear probing technique for collision resolution.
Solution-

The given sequence of keys will be inserted in the hash table as-

Step-01:

 Draw an empty hash table.

 For the given hash function, the possible range of hash values is [0, 6].
 So, draw an empty hash table consisting of 7 buckets as-

Step-02:

 Insert the given keys in the hash table one by one.

 The first key to be inserted in the hash table = 50.
 Bucket of the hash table to which key 50 maps = 50 mod 7 = 1.
 So, key 50 will be inserted in bucket-1 of the hash table as-

Step-03:

 The next key to be inserted in the hash table = 700.

 Bucket of the hash table to which key 700 maps = 700 mod 7 = 0.
 So, key 700 will be inserted in bucket-0 of the hash table as-
Step-04:

 The next key to be inserted in the hash table = 76.

 Bucket of the hash table to which key 76 maps = 76 mod 7 = 6.
 So, key 76 will be inserted in bucket-6 of the hash table as-

Step-05:

 The next key to be inserted in the hash table = 85.

 Bucket of the hash table to which key 85 maps = 85 mod 7 = 1.
 Since bucket-1 is already occupied, so collision occurs.
 To handle the collision, linear probing technique keeps probing linearly until an empty bucket is found.
 The first empty bucket is bucket-2.
 So, key 85 will be inserted in bucket-2 of the hash table as-

Step-06:

 The next key to be inserted in the hash table = 92.

 Bucket of the hash table to which key 92 maps = 92 mod 7 = 1.
 Since bucket-1 is already occupied, so collision occurs.
 To handle the collision, linear probing technique keeps probing linearly until an empty bucket is found.
 The first empty bucket is bucket-3.
  So, key 92 will be inserted in bucket-3 of the hash table as-

Step-07:

 The next key to be inserted in the hash table = 73.

 Bucket of the hash table to which key 73 maps = 73 mod 7 = 3.
 Since bucket-3 is already occupied, so collision occurs.
 To handle the collision, linear probing technique keeps probing linearly until an empty bucket is found.
 The first empty bucket is bucket-4.
 So, key 73 will be inserted in bucket-4 of the hash table as-

Step-08:

 The next key to be inserted in the hash table = 101.

 Bucket of the hash table to which key 101 maps = 101 mod 7 = 3.
 Since bucket-3 is already occupied, so collision occurs.
 To handle the collision, linear probing technique keeps probing linearly until an empty bucket is found.
 The first empty bucket is bucket-5.
 So, key 101 will be inserted in bucket-5 of the hash table as-

(c)Write an algorithm of linear search technique. 4

Algorithm: Linear Search Technique
LINEAR(DATA, N, ITEM, LOC)

Here DATA is a linear array with N elements, and ITEM is a given item of information. This algorithm finds the location
LOC of ITEM in DATA, or sets LOC := 0 if the search is unsuccessful.

1. [Insert ITEM at the end of DATA] Set DATA[N + 1] := ITEM

2. [Initialize counter] Set LOC := 1

3. [Search for ITEM]

Repeat while DATA[LOC] ≠ ITEM Set LOC := LOC + 1

[End of loop]

4. [Successful?] If LOC = N + 1, then : Set LOC := 0

5. Exit
(d) Discuss applications of Hashing data structure. 3
1. Hashing provides constant time search, insert and delete operations on average. This is why hashing is one of
the most used data structure, example problems are, distinct elements, counting frequencies of items,
finding duplicates, etc.
2. Database indexing: Hashing is used to index and retrieve data efficiently in databases and other data storage
systems.
3. Dictionaries : To implement a dictionary so that we can quickly search a word
4. Password storage: Hashing is used to store passwords securely by applying a hash function to the password
and storing the hashed result, rather than the plain text password.
5. Network Routing: Determining the best path for data packets
6. Bloom Filters : Bloom filter is a space optimized and probabilistic version of hashing and has huge
applications like spam filtering, recommendations.
7. Cryptography: Hashing is used in cryptography to generate digital signatures, message authentication codes
(MACs), and key derivation functions.
8. Load balancing: Hashing is used in load-balancing algorithms, such as consistent hashing, to distribute
requests to servers in a network.
9. Blockchain: Hashing is used in blockchain technology, such as the proof-of-work algorithm, to secure the
integrity and consensus of the blockchain.
10. Image processing: Hashing is used in image processing applications, such as perceptual hashing, to detect
and prevent image duplicates and modifications.

6)(a) How do we represent queue data structure ? 3

A queue is a linear data structure that follows the principle FIFO (First In First Out), where the element inserted first
is removed first.
A queue can be represented in the following two ways:

1. Array Representation
 The queue is represented using a linear array.
 Two variables are used:
o FRONT – points to the first element of the queue.
o REAR – points to the last element of the queue.
 Insertion (enqueue) is done at the REAR end.
 Deletion (dequeue) is done from the FRONT end.
 This representation is simple but may cause wastage of memory when elements are deleted (unless circular
queue is used).
2. Linked List Representation
 The queue is represented using a linked list.
 FRONT points to the first node and REAR points to the last node.
 Insertion is done at the REAR by adding a new node.
 Deletion is done from the FRONT by removing the first node.
 This representation allows dynamic memory allocation and avoids memory wastage.

(b)How do we detect if a queue is empty for a non-circular queue ? 3

In a non-circular queue, emptiness is detected using the FRONT and REAR pointers (or indices).
Condition for Empty Queue:
 The queue is said to be empty when
FRONT = –1
(or when FRONT > REAR in some implementations).
Explanation:
 Initially, when the queue is created, both FRONT and REAR are set to –1, indicating that no elements are
present.
 When elements are inserted, REAR moves forward and FRONT is set to 0.
 As elements are deleted, FRONT increases.
 If all elements are removed, FRONT becomes greater than REAR, or both are reset to –1, which indicates that
the queue is empty.
Example:
 Initial state: FRONT = -1, REAR = -1 → Queue is empty
 After deletions: FRONT > REAR → Queue is empty

(c)Write the pop operation algorithm of a stack. 3

POP operation: In pop operation, we remove an element from stack. After every pop operation top of stack is
decremented by 1.

Algorithm:

POP (STACK, TOP, ITEM)

1. If TOP < 0 then write "STACK UNDERFLOW and STOP"

2. STACK [TOP] ← NULL

3. TOP TOP-1

4. STOP

(d)Define B-tree. 3
A B-Tree is a specialized m-way tree designed to optimize data access, especially on disk-based storage systems.
 In a B-Tree of order m, each node can have up to m children and m-1 keys, allowing it to efficiently manage
large datasets.
 The value of m is decided based on disk block and key sizes.
 One of the standout features of a B-Tree is its ability to store a significant number of keys within a single
node, including large key values. It significantly reduces the tree’s height, hence reducing costly disk
operations.
 B Trees allow faster data retrieval and updates, making them an ideal choice for systems requiring efficient
and scalable data management. By maintaining a balanced structure at all times,
 B-Trees deliver consistent and efficient performance for critical operations such as search, insertion, and
deletion.
Following is an example of a B-Tree of order 5 .

Properties of a B-Tree
A B Tree of order m can be defined as an m-way search tree which satisfies the following properties:
13. All leaf nodes of a B tree are at the same level, i.e. they have the same depth (height of the tree).
14. The keys of each node of a B tree (in case of multiple keys), should be stored in the ascending order.
15. In a B tree, all non-leaf nodes (except root node) should have at least m/2 children.
16. All nodes (except root node) should have at least m/2 - 1 keys.
17. If the root node is a leaf node (only node in the tree), then it will have no children and will have at least one
key. If the root node is a non-leaf node, then it will have at least 2 children and at least one key.
18. A non-leaf node with n-1 key values should have n non NULL children.
Application of B-tree : The main application of a B-tree is the organization of a huge collection of records into a file
structure. The organization should be in such a way that any record in it can be searched very efficiently i.e.,
insertion, deletion and modification operations can be carried out perfectly and efficiently.

(e)What do you mean by complete binary tree? Give example. 2+1

 Complete binary tree: A tree is called a complete binary tree if tree satisfies following conditions:

a. Each node has exactly two children except leaf node.

b. All leaf nodes are at same level.

c. If a binary tree contains m nodes at level l, it contains atmost 2m nodes at level l + 1.

 Fig.-Complete Binary Tree

7) (a) Write the Dijkstra's algorithm to find shortest path between two vertices in a graph. Show an example.
5+3

graph G = (V, E) with non-negative edge weights, i.e., we assume that w(u, v) ≥ 0 each edge (u, v) ∈ E.
a. Dijkstra’s algorithm, is a greedy algorithm that solves the single-source shortest path problem for a directed

b. Dijkstra’s algorithm maintains a set S of vertices whose final shortestpath weights from the source s have already
been determined.
c. That is, for all vertices v  S, we have d[v] = δ (s, v).

d. The algorithm repeatedly selects the vertex u ∈ V – S with the minimum shortest-path estimate, inserts u into S,
and relaxes all edges leaving u.
e. We maintain a priority queue Q that contains all the vertices in v – s, keyed by their d values.
f. Graph G is represented by adjacency list.

g. Dijkstra’s always chooses the “lightest or “closest” vertex in V – S to insert into set S, that it uses as a greedy
strategy.
DIJKSTRA (G, w, s)

1. INITIALIZE-SINGLE-SOURCE (G, s)
2. S φ

3. Q V[G]

4. while Q  φ

5. do u  EXTRACT-MIN (Q)

6. S  S U {u}

7. for each vertex v ∈ Adj [u]

8. do RELAX (u, v, w)

(b)Write an algorithm to delete a node from a single linked-list. 5

Delete a node from the end

Here START is a pointer variable which contains the address of first node. PTR is a pointer variable which contains
address of node to be deleted. PREV is a pointer variable which points to previous node. ITEM is the value to be
deleted.
1. If (START == NULL) Then [Check whether list is empty] 2. Print: Linked-List is empty.

3. Else

4. PTR = START, PREV = START

5. Repeat While (PTR -> LINK != NULL)

6. PREV = PTR [Assign PTR to PREV]

7. PTR = PTR -> LINK [Move PTR to next node]

 [End of While Loop]

8. ITEM = PTR -> INFO [Assign INFO of last node to ITEM] 9. If (START -> LINK == NULL) Then

[If only one node is left]

10. START = NULL [Assign NULL to START]

11. Else

9. PREV -> LINK = NULL

[Assign NULL to link field of second last node] [End of Step 9 If]
10. Delete PTR

11. Print : ITEM deleted

[End of Step 1 If]

12. Exit

(c)Write one advantage and disadvantage of array over linked list. 2

Advantages of Arrays over Linked List :

 Random Access. : We can access ith item in O(1) time (only some basic arithmetic required using base
address). In case of linked lists, it is O(n) operation due to sequential access.
Disadvantages of Arrays over Linked List :
 Fixed size – Array size must be declared in advance and cannot be changed dynamically, which may lead to
memory wastage or overflow.
8) Write short notes on any three : 5*3
(a) Priority queue

2. A priority queue is a data structure in which each element has been assigned a value called the priority of the
element and an element can be inserted or deleted not only at the ends but at any position on the queue.
3. A priority queue is a collection of elements such that each element has been assigned an explicit or implicit
priority and such that the order in which elements are deleted and processed comes from the following rules :
a. An element of higher priority is processed before any element of lower priority.
b. Two elements with the same priority are processed to the order in which they were inserted to the queue.
Types of priority queues are :

3. Ascending priority queue : In ascending priority queue, elements can be inserted in an order. But, while deleting
elements from the queue, always a small element to be deleted first.
4. Descending priority queue : In descending priority queue, elements are inserted in any order but while deleting
elements from the queue always a largest element to be deleted first.
Applications of priority queue :

3. The typical example of priority queue is scheduling the jobs in operating system. Typically operating system
allocates priority to jobs. The jobs are placed in the queue and position 1 of the job in priority queue determines
their priority.
4. In network communication, to manage limited bandwidth for transmission, the priority queue is used.
In simulation modelling, to manage the discrete events the priority queue is used.

(b)Merge sort
Merge sort :
a. Merge sort is a sorting algorithm that uses the idea of divide and conquer.
b. This algorithm divides the array into two halves, sorts them separately and then merges them.
c. This procedure is recursive, with the base criteria that the number of elements in the array is not more than 1.
ALGORITHM:
MERGE_SORT (a, p, r) :

7. if p < r

8. then q ← |_ (p + r)/2 _|

9. MERGE-SORT (A, p, q)

4. MERGE-SORT (A, q + 1, r)

5. MERGE (A, p, q, r)
MERGE (A, p, q, r) :
19. n1 = q – p + 1
20. n2 = r – q
21. Create arrays L [1 .........n1 + 1] and R [1......n2 + 1]
22. for i = 1 to n1 do

L[i] = A [p + i – 1]
endfor
23. for j = 1 to n2 do

R[j] = A[q + j]
endfor
24. L[n1 + 1] = ∞, R[n2 + 1] = ∞
25. i = 1, j = 1

26. for k = p to r
do
if L[i] <= R[j]
then A[k] ← L[i]
i=i+1
else A[k] = R[j]

j=j+1

endif

endfor

27. exit

Complexity of merge sort algorithm :

1. Let f(n) denote the number of comparisons needed to sort an n-element array A using the merge sort algorithm.
2. The algorithm requires at most log n passes.
3. Moreover, each pass merges a total of n elements, and by the discussion on the complexity of merging, each pass
will require at most n comparisons.
4. Accordingly, for both the worst case and average case, f(n)  n log n
5. This algorithm has the same order as heap sort and the same average order as quick sort.
6. The main drawback of merge sort is that it requires an auxiliary array with n elements.
7. Each of the other sorting algorithms requires only a finite number of extra locations, which is independent of n.
8. The results are summarized in the following table :
(c)Collision resolve techniques in Hashing
Collision resolution technique :
 Hashing with open addressing :
1. In open addressing, all elements are stored in the hash table itself.
2. While searching for an element, we systematically examine table slots until the desired element is found or it is
clear that the element is not in the table.
3. Thus, in open addressing, the load factor  can never exceed 1.
4. The process of examining the locations in the hash table is called probing.
5. Following are techniques of collision resolution by open addressing :
a. Linear probing :
i. Given an ordinary hash function h : U [0, 1, ....., m – 1], the method of linear probing uses the hash function.
h (k, i) = (h (k) + i) mod m
where ‘m’ is the size of the hash table and h (k) = k mod m (basic hash function).
b. Quadratic probing:
i. Suppose a record R with key k has the address H(k) = h then instead of searching the locations with address h, h +
1, h + 2, ....., we linearly search the locations with addresses h, h + 1, h + 4, h + 9, ......., h + i2 .
ii. Quadratic probing uses a hash function of the form
h (k, i) = (h (k) + c 1i + c 2 i 2) mod m
where (as in linear probing) h is an auxiliary hash function, c1 and c2  0 are auxiliary constants, and i = 0, 1, ....., m –
1.
c. Double hashing :
i. Double hashing is one of the best methods available for open addressing because the permutations produced have
many of the characteristics of randomly chosen permutations.
ii. Double hashing uses a hash function of the form :
h(k, i) = (h1 (k) + ih2 (k)) mod m
where h1 and h2 are auxiliary hash functions and m is the size of the hash table.
 Hashing with separate chaining :
1. This method maintains the chain of elements which have same hash address.
2. We can take the hash table as an array of pointers.
3. Size of hash table can be number of records.
4. Here each pointer will point to one linked list and the elements which have same hash address will be maintained
in the linked list.
5. We can maintain the linked list in sorted order and each elements of linked list will contain the whole record with
key.
6. For inserting one element, first we have to get the hash value through hash function which will map in the hash
table, then that element will be inserted in the linked list.
7. Searching a key is also same, first we will get the hash key value in hash table through hash function, then we will
search the element in corresponding linked list.
8. Deletion of a key contains first search operation then same as delete operation of linked list.
(d) Bi-connected graph
An undirected graph is called Biconnected if there are two vertex-disjoint paths between any two vertices. In a
Biconnected Graph, there is a simple cycle through any two vertices.
Or in other words:
A graph is said to be Biconnected if:
1. It is connected, i.e. it is possible to reach every vertex from every other vertex, by a simple path.
2. Even after removing any vertex the graph remains connected.
Examples:

Important points:
 No vertex exists whose removal disconnects the graph.
 Minimum number of vertices in a biconnected graph is 2.
 A graph with an articulation point is not biconnected.
 A tree is never biconnected because every internal node is an articulation point.

Year-2022(C 5-T)

Group - B
2. Answer any four questions: 5×4=20

(a) Differentiate between linked list and array. Write a routine to push an element into a stack. 2+3

S. Array Linked list

No
.
1. An array is a list of finite number of elements A linked list is a linear collection of data
of same data type i.e., integer, real or string elements called nodes which are connected
etc. by links.
2. Elements can be accessed randomly. Elements cannot be accessed randomly. It
can be accessed only sequentially.
3. Array is classified as : a. 1-D array A linked list can be linear, doubly or circular
b. 2-D array linked list.
c. n-D array
4. Each array element is independent and does Location or address of element is stored in
not have a connection with previous element the link part of previous element or node.
or with its location.
5. Array elements cannot be added, deleted The nodes in the linked list can be added and
once it is declared. deleted from the list.
6. In array, elements can be modified easily by In linked list, modifying the node is a complex
identifying the index value. process.
7. Pointer cannot be used in array. Pointers are used in linked list.

(b) What is recursive function? How can we calculate factorial of a number using recursion? 2+3

A recursive function is a function that calls itself directly or indirectly to solve a problem by breaking it into smaller
subproblems.
Every recursive function must have:

1. Base condition – stops the recursion

2. Recursive case – function calls itself

Factorial of a Number Using Recursion (3 marks)

Definition:
Factorial of a number n is:n !=n ×(n−1)×(n−2)× ⋯× 1 With 0 !=1

Algorithm:

FACT(n)

1. If n = 0 then

2. return 1

3. Else

4. return n × FACT(n − 1)

Example: 5! = 5 × 4 × 3 × 2 × 1 = 120

(c) Explain the concept of priority queue with suitable example. 5

A priority queue is a data structure in which each element has been assigned a value called the priority of the
element and an element can be inserted or deleted not only at the ends but at any position on the queue.
A priority queue is a collection of elements such that each element has been assigned an explicit or implicit priority
and such that the order in which elements are deleted and processed comes from the following rules :
c. An element of higher priority is processed before any element of lower priority.
d. Two elements with the same priority are processed to the order in which they were inserted to the queue.
Types of priority queues are :

1. Ascending priority queue : In ascending priority queue, elements can be inserted in an order. But, while deleting
elements from the queue, always a small element to be deleted first.
2. Descending priority queue : In descending priority queue, elements are inserted in any order but while deleting
elements from the queue always a largest element to be deleted first.
Applications of priority queue :

1. The typical example of priority queue is scheduling the jobs in operating system. Typically operating system
allocates priority to jobs. The jobs are placed in the queue and position 1 of the job in priority queue determines
their priority.
2. In network communication, to manage limited bandwidth for transmission, the priority queue is used.
In simulation modelling, to manage the discrete events the priority queue is used.

(d) How will be your programming approach to delete a specific element from any array? You may write a C program
to describe. 1+4

(e) Convert infix expression to postfix expression. (a + b * c ^ d) * ( e + f / g ). 5

Characte Stack Postfix

r

( ( —

a ( a

+ (+ a

b (+ ab

* (+* ab

c (+* abc

^ ( + * ^ abc

d ( + * ^ abcd

) — abcd^*+

* * abcd^*+

( *( abcd^*+

e *( abcd^*+e

+ *(+ abcd^*+e

f *(+ abcd^*+ef
 / *(+/ abcd^*+ef

g *(+/ abcd^*+efg

) * abcd^*+efg/+

End — abcd^*+efg/
+

So, the postfix expression of the given infix expression is: abcd^*+efg/*

(f) Explain binary search technique with an example. 5

For a binary search to work, it is mandatory for the target array to be sorted. The following is our sorted array and let
us assume that we need to search the location of value 31 using binary search.

First, we shall determine half of the array by using this formula −

mid = low + (high - low) / 2

Here it is, 0 + (9 - 0) / 2 = 4 (integer value of 4.5). So, 4 is the mid of the array.

Now we compare the value stored at location 4, with the value being searched, i.e. 31. We find that the value at
location 4 is 27, which is not a match. As the value is greater than 27 and we have a sorted array, so we also know
that the target value must be in the upper portion of the array.

We change our low to mid + 1 and find the new mid value again.

low = mid + 1

mid = low + (high - low) / 2

Our new mid is 7 now. We compare the value stored at location 7 with our target value 31.
The value stored at location 7 is not a match, rather it is less than what we are looking for. So, the value must be in
the lower part from this location.

Hence, we calculate the mid again. This time it is 5.

We compare the value stored at location 5 with our target value. We find that it is a match.

We conclude that the target value 31 is stored at location 5.

Group - C

3. Answer any one question: 10×1=10

(a) What is linked list? What is the advantage of it? How can we reverse a singly linked list? 2+3+5

Linked List:

A Linked list is a dynamic arrangement that contains a “link” to the structure containing the subsequent items. It's a
set of structures ordered not by their physical placement in memory (like an array) but by logical links that are stored
as a part of the info within the structure itself.

A linked list is another way to collect similar data. However, unlike an array, elements during a linked list aren't in
consecutive memory locations. A linked list consists of nodes that are connected with one another using pointers.
The figure illustrates a linked list.

Advantages Of Linked List:

 Dynamic data structure: A linked list is a dynamic arrangement so it can grow and shrink at runtime by
allocating and deallocating memory. So there is no need to give the initial size of the linked list.

 No memory wastage: In the Linked list, efficient memory utilization can be achieved since the size of the
linked list increase or decrease at run time so there is no memory wastage and there is no need to pre-
allocate the memory.
  Implementation: Linear data structures like stacks and queues are often easily implemented using a linked
list.

 Insertion and Deletion Operations: Insertion and deletion operations are quite easier in the linked list. There
is no need to shift elements after the insertion or deletion of an element only the address present in the next
pointer needs to be updated.

 Flexible: This is because the elements in Linked List are not stored in contiguous memory locations unlike
the array.

 Efficient for large data: When working with large datasets linked lists play a crucial role as it can grow and
shrink dynamically.

 Scalability: Contains the ability to add or remove elements at any position.

Reverse a single linked list:

[Link] reverse a linear or single linked list, three pointer fields are used.

[Link] are PREV, PTR, REV which hold the address of previous node, current node and will maintain the linked list.

Algorithm :

1. PTR = FIRST

2. TPT = NULL

3. Repeat step 4 while PTR != NULL

4. REV = PREV

5. PREV = PTR

6. PTR = PTR LINK

7. PREV LINK = REV

[End of while loop]

8. START = PREV

9. Exit

(b) Write short notes on the following topics (any two): 5+5

(i) BFS

Breadth First Search (BFS) :

The general idea behind a breadth first search beginning at a starting node A is as follows :
a. First we examine the starting node A.
e. Then, we examine all the neighbours of A, and so on.

f. We need to keep track of the neighbours of a node, and that no node is processed more than once.
g. This is accomplished by using a queue to hold nodes that are waiting to be processed, and by using a field
STATUS which tells us the current status of any node.
Algorithm : This algorithm executes a breadth first search on a graph G beginning at a starting node A.
iv. Initialize all nodes to ready state (STATUS=1).

v. Put the starting node A in queue and change its status to the waiting state (STATUS = 2).
vi. Repeat steps (iv) and (v) until queue is empty.
iv. Remove the front node N of queue. Process N and change the status of N to the processed state (STATUS = 3).
v. Add to the rear of queue all the neighbours of N that are in the ready state (STATUS=1) and change their status to
the waiting state (STATUS = 2).
[End of loop]
vi. End.

(ii) Topological sorting

Topological Sort is a linear ordering of the vertices in such a way that

if there is an edge in the DAG going from vertex ‘u’ to vertex ‘v’,

then ‘u’ comes before ‘v’ in the ordering.

It is important to note that-

 Topological Sorting is possible if and only if the graph is a Directed Acyclic Graph.

 There may exist multiple different topological orderings for a given directed acyclic graph.

Topological Sort Example-

Find the number of different topological orderings possible for the given graph-

Solution-

The topological orderings of the above graph are found in the following steps-

Step-01:

Write in-degree of each vertex-

Step-02:
  Vertex-A has the least in-degree.

 So, remove vertex-A and its associated edges.

 Now, update the in-degree of other vertices.

Step-03:

 Vertex-B has the least in-degree.

 So, remove vertex-B and its associated edges.

 Now, update the in-degree of other vertices.

Step-04:

There are two vertices with the least in-degree. So, following 2 cases are possible-

In case-01,

 Remove vertex-C and its associated edges.

 Then, update the in-degree of other vertices.

In case-02,

 Remove vertex-D and its associated edges.

 Then, update the in-degree of other vertices.

Step-05:

Now, the above two cases are continued separately in the similar manner.

In case-01,

 Remove vertex-D since it has the least in-degree.

 Then, remove the remaining vertex-E.

In case-02,

 Remove vertex-C since it has the least in-degree.

 Then, remove the remaining vertex-E.

Conclusion-

For the given graph, following 2 different topological orderings are possible-

 ABCDE

 ABDCE

(iii) B-Tree

A B-Tree is a specialized m-way tree designed to optimize data access, especially on disk-based storage systems.
 In a B-Tree of order m, each node can have up to m children and m-1 keys, allowing it to efficiently manage
large datasets.
 The value of m is decided based on disk block and key sizes.
 One of the standout features of a B-Tree is its ability to store a significant number of keys within a single
node, including large key values. It significantly reduces the tree’s height, hence reducing costly disk
operations.
 B Trees allow faster data retrieval and updates, making them an ideal choice for systems requiring efficient
and scalable data management. By maintaining a balanced structure at all times,
 B-Trees deliver consistent and efficient performance for critical operations such as search, insertion, and
deletion.
Following is an example of a B-Tree of order 5 .

Properties of a B-Tree
A B Tree of order m can be defined as an m-way search tree which satisfies the following properties:
19. All leaf nodes of a B tree are at the same level, i.e. they have the same depth (height of the tree).
20. The keys of each node of a B tree (in case of multiple keys), should be stored in the ascending order.
21. In a B tree, all non-leaf nodes (except root node) should have at least m/2 children.
22. All nodes (except root node) should have at least m/2 - 1 keys.
23. If the root node is a leaf node (only node in the tree), then it will have no children and will have at least one
key. If the root node is a non-leaf node, then it will have at least 2 children and at least one key.
24. A non-leaf node with n-1 key values should have n non NULL children.
Application of B-tree : The main application of a B-tree is the organization of a huge collection of records into a file
structure. The organization should be in such a way that any record in it can be searched very efficiently i.e.,
insertion, deletion and modification operations can be carried out perfectly and efficiently.

Year-2023(Paper - C5-T)

Group - B

Answer any four questions : 5×4-20

9. Explain the Bubble sorting algorithm.

1. Bubble sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent element if they are
in wrong order.
2. Bubble sort procedure is based on following idea :

a. Suppose if the array contains n elements, then (n – 1) iterations are required to sort this array.
b. The set of items in the array are scanned again and again and if any two adjacent items are found to be out
of order, they are reversed.
c. At the end of the first iteration, the lowest value is placed in the first position.
d. At the end of the second iteration, the next lowest value is placed in the second position and so on.
3. It is very efficient in large sorting jobs. For n data items, this method requires n(n – 1)/2 comparisons.
Bubble-sort (A) :

1. for i 1 to length [A]

2. for j  length[A] down to i + 1

3. if A[j] < A[j – 1]

4. exchange(A[j], A[j – 1])

10. Explain Row major implementation and column major implementation of an array.

Row Major :
1. In row major order, the element of an array is stored in computer memory as row-by-row.
2. Under row major representation, the first row of the array occupies the first set of memory locations reserved for
the array, the second row occupies the next set, and so forth.
3. In row major order, elements of a two-dimensional array are ordered as :
A11, A12, A13, A14, A15, A16, A21, A22, A23, A24, A25, A26, A31, ....., A46, A51, A52, ......, A 56

Example :

Let us consider the following two-dimensional array :

a. Move the elements of the second row starting from the first element to the memory location adjacent to the
last element of the first row.
b. When this step is applied to all the rows except for the first row, we have a single row of elements. This is the
row major representation.
c. By application of above mentioned process, we get
{a, b, c, d, e, f, g, h, i, j, k, l}
Column Major:
1. In column major order the elements of an array is stored as column-bycolumn, it is called column major order.
2. Under column major representation, the first column of the array occupies the first set of memory locations
reserved for the array, the second column occupies the next set, and so forth.
3. In column major order, elements are ordered as :
A11, A21, A31, A41, A51, A12, A22, A32, A42, A52, A13, ....., A55, A16, A26, ......., A56.
Example : Consider the following two-dimensional array :
 a. Transpose the elements of the array. Then, the representation will be same as that of the row major
representation.
b. Then perform the process of row-major representation.
c. By application of above mentioned process, we get
{a, e, i, b, f, j, c, g, k, d, h, l}.

11. Write an algorithm to evaluate a postfix expression using stack.

This algorithm finds the value of an arithmetic expression P written in postfix notation.
1. Add a right parenthesis “)” to P.

[This acts as a sentinel]

2. Scan P from left to right and repeat step 3 and 4 for each element of P until the sentinel “)” is encountered.
If an operand is encountered, put it on STACK.
If an operator ⊕ is encountered then :
3.

4.

Evaluate B ⊕ A.
a. Remove the top two elements of STACK, where A is the top element and B is the next-to-top element.
b.

c. Place the result of (b) back on STACK.

[End of if structure]

[End of step 2 loop]

5. Set value equal to top element on STACK.
6. End.
12. Discuss the technique of Binary search algorithm with suitable example.

For a binary search to work, it is mandatory for the target array to be sorted. The following is our sorted array and let
us assume that we need to search the location of value 31 using binary search.

First, we shall determine half of the array by using this formula −

mid = low + (high - low) / 2

Here it is, 0 + (9 - 0) / 2 = 4 (integer value of 4.5). So, 4 is the mid of the array.

Now we compare the value stored at location 4, with the value being searched, i.e. 31. We find that the value at
location 4 is 27, which is not a match. As the value is greater than 27 and we have a sorted array, so we also know
that the target value must be in the upper portion of the array.
We change our low to mid + 1 and find the new mid value again.

low = mid + 1

mid = low + (high - low) / 2

Our new mid is 7 now. We compare the value stored at location 7 with our target value 31.

The value stored at location 7 is not a match, rather it is less than what we are looking for. So, the value must be in
the lower part from this location.

Hence, we calculate the mid again. This time it is 5.

We compare the value stored at location 5 with our target value. We find that it is a match.

We conclude that the target value 31 is stored at location 5.

13. Write an algorithm to delete any element from any position of link list.

1. Delete node at specified position : Here START is a pointer variable which contains the address of first node.
PTR is a pointer variable which contains address of node to be deleted. PREV is a pointer variable which
points to previous node. ITEM is the value to be deleted.
1. If (START == NULL) Then [Check whether list is empty]

2. Print: Linked-List is empty.

3. Else If (START -> INFO == ITEM) Then

 [Check if ITEM is in 1st node]

4. PTR = START

5. START = START -> LINK [START now points to 2nd node]

6. Delete PTR

7. Else

8. PTR = START, PREV = START

9. Repeat While (PTR != NULL)

10. If (PTR -> INFO == ITEM) Then

[If ITEM matches with PTR->INFO]

11. PREV -> LINK = PTR -> LINK[Assign LINK field of PTR to PREV]

12. Delete PTR

13. Else

14. PREV = PTR [Assign PTR to PREV]

15. PTR = PTR -> LINK [Move PTR to next node]

[End of Step 10 If]

[End of While Loop]

16. Print: ITEM deleted

[End of Step 1 If]

17. Exit

14. Write an algorithm for post order traversal in tree.

Algorithm for postorder traversal :

Postorder (INFO, LEFT, RIGHT, ROOT)

8. [Push NULL onto STACK and initialize PTR]

Set TOP = 1, STACK[1] = NULL and PTR = ROOT

9. [Push leftmost path onto STACK]

Repeat steps 3 to 5 while PTR ≠ NULL

10. Set TOP = TOP + 1 and STACK [TOP] = PTR

[Pushes PTR on STACK]

11. If RIGHT [PTR] ≠NULL

Then

Set TOP = TOP + 1 and STACK [TOP] = RIGHT [PTR]

Endif
12. Set PTR = LEFT [PTR]

End of step 2 loop

13. Set PTR = STACK [TOP] and TOP = TOP – 1
 [Pops node from STACK]
14. Repeat while PTR > 0
c. Apply process to INFO [PTR]
d. Set PTR = STACK [TOP] and TOP = TOP – 1 End loop
8. If PTR < 0 Then
c. Set PTR = – PTR
d. goto step 2
Endif
9. Exit

Group - C

Answer any one question: 10×1=10

15. What is data structure? Write down the application of Data Structure. Write an algorithm for POP and PUSH
operation of stack data structure. 2+2+6

A data structure is a way of organizing all data items that considers not only the elements stored but also their
relationship to each [Link] structure is the representation of the logical relationship existing between individual
elements of [Link] structure is define as a mathematical or logical model of particular organization of data items.
Data structure is needed because :
1. It helps to understand the relationship of one element with the other.
2. It helps in the organization of all data items within the memory.
Application of Data Structure:

 Operating Systems: Managing system resources like memory allocation, file systems (which often use trees),
and process scheduling (using queues and priority queues).

 Databases: Rely heavily on data structures like B-trees and hash tables to ensure efficient indexing, storage,
and retrieval of vast amounts of data.

 Networking: Graphs are essential for representing network topologies and implementing routing algorithms
(like Dijkstra's shortest path) in GPS and network routers.

 Artificial Intelligence and Machine Learning: Data structures are crucial for organizing and processing large
datasets for tasks such as pattern recognition, classification, and decision-making.

PUSH operation: In push operation, we insert an element onto stack. Before inserting, first we increase the top
pointer and then insert the element.

Algorithm:

PUSH (STACK, TOP, MAX, DATA)

1. If TOP MAX-1 then write "STACK OVERFLOW and STOP"

2. READ DATA

3. TOP TOP + 1

4. STACK [TOP] - DATA

5. STOP

POP operation: In pop operation, we remove an element from stack. After every pop operation top of stack is
decremented by 1.

Algorithm:
POP (STACK, TOP, ITEM)

1. If TOP < 0 then write "STACK UNDERFLOW and STOP"

2. STACK [TOP] ← NULL

3. TOP TOP-1

4. STOP

16. What is the Binary Search Tree (BST)? What is the complete binary tree? Construct BST tree for the following data
21, 26, 30, 9, 4, 14, 28, 18, 15, 10, 2, 3, 7. 2+2+6

A Binary Search Tree (BST) is a type of binary tree data structure in which each node contains a unique key and
satisfies a specific ordering property:

 All nodes in the left subtree of a node contain values strictly less than the node’s value.

 All nodes in the right subtree of a node contain values strictly greater than the node’s value.

Fig.-Binary search tree

Complete binary tree:

A tree is called a complete binary tree if tree satisfies following conditions:

a. Each node has exactly two children except leaf node.

b. All leaf nodes are at same level.

c. If a binary tree contains m nodes at level l, it contains atmost 2m nodes at level l + 1.

Fig.-Complete Binary Tree

Year-2023(Paper-CC4T)

GROUP-B

2. Answer any four questions: 5×4=20

(a) Define searching. Differentiate between internal sorting and external sorting. 2+3

Searching is the process of finding the location of given element in the linear array.
The search is said to be successful if the given element is found, i.e., the element does exists in the array;
otherwise unsuccessful.
There are two searching techniques :

a. Linear search (sequential) b. Binary search

The algorithm which we choose depends on organization of the array elements.

If the elements are in random order, then we have to use linear search technique, and if the array elements are
sorted, then it is preferable to use binary search.
Internal Sorting External Sorting

Sorting is performed completely in main memory Sorting is performed using secondary storage such as
(RAM). hard disk or tape.

Suitable when the entire dataset fits into memory. Suitable when the dataset is too large to fit into
memory.

Access speed is fast because RAM access is quick. Access speed is slower due to disk I/O operations.

Requires less I/O operations. Requires large number of I/O operations.

Implementation is simple. Implementation is complex.

Uses CPU time more than I/O time. Uses I/O time more than CPU time.

Temporary storage requirement is low. Requires large temporary storage.

Performance mainly depends on CPU efficiency. Performance mainly depends on disk access speed.

Suitable for small to medium-sized data. Suitable for very large data files.

Examples: Bubble sort, Selection sort, Insertion sort, Examples: External merge sort, Balanced merge sort,
Quick sort, Heap sort. Polyphase merge sort.

(b) What is the disadvantage of array over linked list? What do you mean by doubly linked list? 2+3

Disadvantage of array over linked list:

 Efficient insertion and deletion: Linked lists allow insertion and deletion in the middle in O(1) time, if we
have a pointer to the target position, as only a few pointer changes are needed. In contrast, arrays require
O(n) time for insertion or deletion in the middle due to element shifting.

 Implementation of Queue and Deque : Simple array implementation is not efficient at all. We must use
circular array to efficiently implement which is complex. But with linked list, it is easy and straightforward.
That is why most of the language libraries use Linked List internally to implement these data structures.

 Space Efficient in Some Cases : Linked List might turn out to be more space efficient compare to arrays in
cases where we cannot guess the number of elements in advance. In case of arrays, the whole memory for
items is allocated together. Even with dynamic sized arrays like vector in C++ or list in Python or ArrayList in
Java. the internal working involves de-allocation of whole memory and allocation of a bigger chunk when
insertions happen beyond the current capacity.

 Circular List with Deletion/Addition : Circular Linked Lists are useful to implement CPU round robin
scheduling or similar requirements in the real world because of the quick deletion/insertion in a circular
manner.

Doubly linked list:

1. The doubly or two-way linked list uses double set of pointers, one pointing to the next node and the other
pointing to the preceding node.
2. In doubly linked list, all nodes are linked together by multiple links which help in accessing both the successor
and predecessor node for any arbitrary node within the list.
3. Every node in the doubly linked list has three fields :

LPT INFO RPT

4. LPT will point to the node in the left side (or previous node) i.e., LPT will hold the address of the previous node,
RPT will point to the node in the right side (or next node) i.e., RPT will hold the address of the next node.
5. INFO field store the information of the node.
6. A doubly linked list can be shown as follows :

LPT RPT

NULL INFO INFO INFO INFO NULL

Fig. Doubly
linked list.
7. The structure defined for doubly linked list is:

struct node

{ int info;
struct node *rpt;
struct node *lpt;

} node;
(c) Define a binary tree. What do you mean by tree traversal? 3+2

A Binary Tree Data Structure is a hierarchical data structure in which each node has at most two children,
referred to as the left child and the right child.

Tree traversal refers to the process of visiting or accessing each node of a tree exactly once in a specific order. Unlike
linear data structures such as arrays, linked lists, or queues (which have only one logical way of traversal), trees offer
multiple ways to traverse their nodes.

Tree traversals are broadly classified into two categories:

Depth-First Traversal (DFT)

 Explores as far as possible along a branch before exploring the next branch.

 Types: Inorder, Preorder, Postorder

Breadth-First Traversal (BFT)

 Explores nodes level by level from top to bottom.

 Type: Level Order Traversal.

 The level order traversal of the above tree is 1, 2, 3, 4, 5, 6, and 7.

(d) Illustrate the construction of a binary tree given its in-order and post-order traversal. 5

IN-ORDER : HDIJEKBALFMCNGO

POST-ORDER : HIDJKEBLMFNOGCA

Step 1: Find Root

 Last element of Post-order = A

 So, A is the root

Step 2: Split In-order by Root (A)

In-order:
HDIJEKB|A|LFMCNGO

 Left In-order: H D I J E K B

 Right In-order: L F M C N G O

Step 3: Left Subtree of A

Post-order corresponding to left subtree:

HIDJKEB

 Root = B

Split In-order around B:

HDIJEK|B
Step 4: Left Subtree of B

Post-order: H I D J K E
Root = E

Split In-order:
HDIJ|E|K

Step 5: Subtree of E

 Left In-order: H D I J

 Right In-order: K

Right child of E = K

Post-order left part: H I D J

Root = J

Split In-order:
HDI|J

Step 6: Subtree of J

Post-order: H I D
Root = D

Split In-order:
H|D|I

Step 7: Right Subtree of A

Post-order: L M F N O G C
Root = C

Split In-order:
LFM|C|NGO

Step 8: Left Subtree of C

Post-order: L M F
Root = F

Split In-order:
L|F|M

Step 9: Right Subtree of C

Post-order: N O G
Root = G

Split In-order:
N|G|O

(e) Describe bubble sort algorithm and find its complexity. 5

Bubble sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent element if they are in
wrong order.
Bubble sort procedure is based on following idea :

a. Suppose if the array contains n elements, then (n – 1) iterations are required to sort this array.
b. The set of items in the array are scanned again and again and if any two adjacent items are found to be out
of order, they are reversed.
 c. At the end of the first iteration, the lowest value is placed in the first position.
d. At the end of the second iteration, the next lowest value is placed in the second position and so on.
It is very efficient in large sorting jobs. For n data items, this method requires n(n – 1)/2 comparisons.
Bubble-sort (A) :

2. for i  1 to length [A]

3. for j length[A] down to i + 1

4. if A[j] < A[j – 1]

5. exchange(A[j], A[j – 1])

Analysis of bubble sort :

Complexity of best case is Ω(n).

Complexity of worst case is O(n 2 ).

Complexity of average case is θ (n 2 )

(f) Write a short note on post-order traversal. 5

Postorder Traversal

Postorder traversal visits the node in the order: Left -> Right -> Root

Algorithm for Postorder Traversal:

Postorder(tree)

●Traverse the left subtree, i.e., call Postorder(left->subtree)

● Traverse the right subtree, i.e., call Postorder(right->subtree)
● Visit the root
 GROUP-C

3. Answer any two questions: 10×2=20

(a) What is linked list? Write and explain the algorithm to create and traverse operations in single linked list with an
example. 2+8=10

Linked List:

A Linked list is a dynamic arrangement that contains a “link” to the structure containing the subsequent items. It's a
set of structures ordered not by their physical placement in memory (like an array) but by logical links that are stored
as a part of the info within the structure itself.

A linked list is another way to collect similar data. However, unlike an array, elements during a linked list aren't in
consecutive memory locations. A linked list consists of nodes that are connected with one another using pointers.
The figure illustrates a linked list.

Algorithm to create a singly linked list:

1. Start
2. Set HEAD ← NULL
3. Read N (number of nodes)
4. For i = 1 to N, repeat:
5. Create a new node NEW
6. Read DATA
7. Set NEW → DATA = DATA
8. Set NEW → NEXT = NULL
9. If HEAD == NULL then
a. Set HEAD = NEW
b. Set TEMP = NEW
10. Else
a. Set TEMP → NEXT = NEW
b. Set TEMP = NEW
11. Stop

Traversing a linked list : Let LIST be a linked list in memory. This algorithm traverses LIST, applying an operation
PROCESS to each element of LIST. The variable PTR points to the node currently being processed.
1. Set PTR := START [Initializes pointer PTR]

2. Repeat Steps 3 and 4 while PTR != NULL

3. Apply PROCESS to PTR -> INFO

4. Set PTR := PTR -> LINK

[PTR now points to the next node] [End of Step 2 loop]
5. Exit

(b) What is hashing? Describe different types of hash functions. What is collision resolution technique in hashing?
2+5+3=10

 Hashing:
In data structures, hashing is a well-known technique to search any particular element among several elements. It
minimizes the number of comparisons while performing the search. Hashing is extremely efficient. The time taken by
it to perform the search does not depend upon the total number of elements .

It completes the search with constant time complexity O(1).

 Types of Hash Functions:
There are many hash functions that use numeric or alphanumeric keys. Somes are

Division Method.
Multiplication Method
Mid-Square Method
Folding Method

a. Division method :
5. Choose a number m larger than the number n of key in K. (The number m is usually chosen to be a prime
number or a number without small divisors, since this frequently minimizes the number of collisions.)
6. The hash function H is defined by :

H(k) = k (mod m) or H(k) = k (mod m) + 1

7. Here k (mod m) denotes the remainder when k is divided by m.

8. The second formula is used when we want the hash addresses to range from 1 to m rather than from 0 to m
– 1.
d. Midsquare method :

1. The key k is squared.

2. The hash function H is defined by : H(k) = l where l is obtained by deleting digits from both end of k2.
3. We emphasize that the same positions of k2 must be used for all of the keys.

e. Folding method :
The key k is partitioned into a number of parts, k1, .... , kr, where each part, except possibly the last, has the same
number of digits as the required address.

Then the parts are added together, ignoring the last carry i.e.,
H(k) = k1 + k2 + .... + kr
where the leading-digit carries, if any, are ignored.

Now truncate the address upto the digit based on the size of hash table.

 Collision resolution technique :

 Hashing with open addressing :
1. In open addressing, all elements are stored in the hash table itself.
2. While searching for an element, we systematically examine table slots until the desired element is found or it is
clear that the element is not in the table.
3. Thus, in open addressing, the load factor  can never exceed 1.
4. The process of examining the locations in the hash table is called probing.
5. Following are techniques of collision resolution by open addressing :
a. Linear probing :
i. Given an ordinary hash function h : U [0, 1, ....., m – 1], the method of linear probing uses the hash function.
h (k, i) = (h (k) + i) mod m
where ‘m’ is the size of the hash table and h (k) = k mod m (basic hash function).
b. Quadratic probing:
i. Suppose a record R with key k has the address H(k) = h then instead of searching the locations with address h, h +
1, h + 2, ....., we linearly search the locations with addresses h, h + 1, h + 4, h + 9, ......., h + i2 .
ii. Quadratic probing uses a hash function of the form
h (k, i) = (h (k) + c 1i + c 2 i 2) mod m
where (as in linear probing) h is an auxiliary hash function, c1 and c2  0 are auxiliary constants, and i = 0, 1, ....., m –
1.
c. Double hashing :
i. Double hashing is one of the best methods available for open addressing because the permutations produced have
many of the characteristics of randomly chosen permutations.
ii. Double hashing uses a hash function of the form :
h(k, i) = (h1 (k) + ih2 (k)) mod m
where h1 and h2 are auxiliary hash functions and m is the size of the hash table.
 Hashing with separate chaining :
1. This method maintains the chain of elements which have same hash address.
2. We can take the hash table as an array of pointers.
3. Size of hash table can be number of records.
4. Here each pointer will point to one linked list and the elements which have same hash address will be maintained
in the linked list.
5. We can maintain the linked list in sorted order and each elements of linked list will contain the whole record with
key.
6. For inserting one element, first we have to get the hash value through hash function which will map in the hash
table, then that element will be inserted in the linked list.
7. Searching a key is also same, first we will get the hash key value in hash table through hash function, then we will
search the element in corresponding linked list.
8. Deletion of a key contains first search operation then same as delete operation of linked list.

(c) Define stack. How is it different from queue? Show implementation of a queue. 2+2+6=10

A stack is a linear data structure that stores elements in a sequential manner. In a stack, all insertions and deletions
are performed only at one end, which is known as the TOP of the stack. The stack follows the principle of LIFO (Last
In, First Out). This means that the element which is inserted last into the stack will be the first one to be removed.
The order may be LIFO(Last In First Out) or FILO(First In Last Out). LIFO implies that the element that is inserted last,
comes out first and FILO implies that the element that is inserted first, comes out last.

A stack can be implemented using an array or a linked list.

Feature Stack Queue

Definition A linear data structure that follows A linear data structure that follows the First In First Out
 the Last In First Out (FIFO) principle.
(LIFO) principle.

Primary Push (add an item), Pop (remove Enqueue (add an item), Dequeue (remove an item),
Operations an item), Peek (view the top item) Front (view the first item), Rear (view the last item)

Insertion/Removal Elements are added and removed Elements are added at the rear and removed from the
from the same end (the top). front.

Use Cases Function call management (call Scheduling processes in operating systems, managing
stack), expression evaluation and requests in a printer queue, breadth-first search in
syntax parsing, undo mechanisms graphs.
in text editors.

Examples Browser history (back button), Customer service lines, CPU task scheduling.
reversing a word.

Real-World A stack of plates: you add and A queue at a ticket counter: the first person in line is
Analogy remove plates from the top. the first to be served.

Complexity Push: O(1), Pop: O(1), Peek: O(1) Enqueue: O(1), Dequeue: O(1), Front: O(1), Rear: O(1)
(Amortized)

Memory Structure Typically uses a contiguous block Typically uses a circular buffer or linked list.
of memory or linked list.

Implementation Can be implemented using arrays Can be implemented using arrays, linked lists, or
or linked lists. circular buffers.

Implement a queue using stacks:

(d)Write short notes on any two of the following: 5×2=10

(i) Threaded binary trees

Threaded binary tree is a binary tree in which all left child pointers that are NULL points to its inorder predecessor
and all right child pointers that are NULL points to its inorder successor.
Advantages of using threaded binary tree :
1. In threaded binary tree the traversal operations are very fast.

2. In threaded binary tree, we do not require stack to determine the predecessor and successor node.
3. In a threaded binary tree, one can move in any direction i.e., upward or downward because nodes are circularly
linked.
4. Insertion into and deletions from a threaded tree are all although time consuming operations but these are very
easy to implement.
(ii) Dequeue

1. In a dequeue, both insertion and deletion operations are performed at either end of the queues. That is, we can
insert an element from the rear end or the front end. Also deletion is possible from either end.

Fig.- Structure of dequeue

2. This dequeue can be used both as a stack and as a queue.
3. There are various ways by which this dequeue can be represented. The most common ways of representing this
type of dequeue are :

a. Using a doubly linked list

b. Using a circular array

Types of dequeue :
1. Input-restricted dequeue : In input-restricted dequeue, element can be added at only one end but we can delete
the element from both ends.
2. Output-restricted dequeue : An output-restricted dequeue is a dequeue where deletions take place at only one
end but allows insertion at both ends.

(iii) Heap sort technique

Heap Sort is a comparison-based sorting algorithm based on the Binary Heap data structure.

 It is an optimized version of selection sort.

 The algorithm repeatedly finds the maximum (or minimum) element and swaps it with the last (or first)
element.

 Using a binary heap allows efficient access to the max (or min) element in O(log n) time instead of O(n).

 The process is repeated for the remaining elements until the array is sorted.

 Overall, Heap Sort achieves a time complexity of O(n log n).

Analysis of heap sort :

Complexity of heap sort for all cases is O(n log2 n).

MAX-HEAPIFY (A, i) :

1. i left [i]

2. r  right [i]

3. if l ≤ heap-size [A] and A[l] > A[i]

4. then largest  l

5. else largest  i

6. if r ≤ heap-size [A] and A[r] > A [largest]

7. then largest  r

8. if largest ≠ i

9. then exchange A[i]  A[largest]

10. MAX-HEAPIFY [A, largest]

HEAP-SORT(A) :
1. BUILD-MAX-HEAP (A)

2. for i  length [A] down to 2

3. do exchange A[1]  A[i]

4. heap-size [A]  heap-size [A] – 1

5. MAX-HEAPIFY (A, 1)
Advantages of Heap Data Structure

1. Time Efficient: Heaps have an average time complexity of O(log n) for inserting and deleting elements,
making them efficient for large datasets. We can convert any array to a heap in O(n) time. The most
important thing is, we can get the min or max in O(1) time

2. Space Efficient : A Heap tree is a complete binary tree, therefore can be stored in an array without wastage
of space.

3. In-place: Most of the applications of heap require in-place rearrangements of elements. For example
HeapSort.

Disadvantages of Heap Data Structure:

 Lack of flexibility: The heap data structure is not very flexible, as it is designed to maintain a specific order of
elements. This means that it may not be suitable for some applications that require more flexible data
structures.

 Not ideal for searching: While the heap data structure allows efficient access to the top element, it is not
ideal for searching for a specific element in the heap. Searching for an element in a heap requires traversing
the entire tree, which has a time complexity of O(n).

(iv) Circular linked list

A circular linked list is a data structure where the last node points back to the first node, forming a closed loop.

 Structure: All nodes are connected in a circle, enabling continuous traversal without encountering NULL.

 Difference from Regular Linked List: In a regular linked list, the last node points to NULL, whereas in a circular
linked list, it points to the first node.

 Uses: Ideal for tasks like scheduling and managing playlists, where smooth and repeated.

Types of Circular Linked Lists

We can create a circular linked list from both singly linked lists and doubly linked lists. So, circular linked lists are
basically of two types:

1. Circular Singly Linked List

In Circular Singly Linked List, each node has just one pointer called the "next" pointer. The next pointer of the last
node points back to the first node and this results in forming a circle. In this type of Linked list, we can only move
through the list in one direction.

2. Circular Doubly Linked List:

In circular doubly linked list, each node has two pointers prev and next, similar to doubly linked list. The prev pointer
points to the previous node and the next points to the next node. Here, in addition to the last node storing the
address of the first node, the first node will also store the address of the last node.
 Year-2024 (Paper- MI 3T)

Group - B

Answer any four of the following questions: 5×4=20

9. Write an algorithm to insert an element at the end of a circular linked list.

Insertion in circular linked list at the end:

1. If PTR = NULL

2. Write OVERFLOW

3. Go to Step 1

[END OF IF]

4. SET NEW_NODE = PTR

5. SET PTR = PTR -> NEXT

6. SET NEW_NODE -> DATA = VAL

7. SET NEW_NODE -> NEXT HEAD

8. SET TEMP = HEAD

9. Repeat Step 10 while TEMP -> NEXT != HEAD

10. SET TEMP TEMP -> NEXT

[END OF LOOP]

11. SET TEMP -> NEXT = NEW_NODE

12. EXIT

10. Explain the working method of merge sort with the following data items: 10,15,0,17,20,30,70,6.

Merge sort follows the Divide and Conquer technique:

 1. Divide the list into two halves repeatedly until each sublist has one element.

2. Conquer (Merge) the sublists by comparing elements and sorting them.

Step-1: Divide

[10, 15, 0, 17, 20, 30, 70, 6]

[10, 15, 0, 17] [20, 30, 70, 6]

↓ ↓

[10, 15] [0, 17] [20, 30] [70, 6]

↓ ↓ ↓ ↓

[10] [15] [0] [17] [20] [30] [70] [6]

Step-2:Merge

Merge and sort step by step:

 Merge [10] and [15] → [10, 15]

 Merge [0] and [17] → [0, 17]

 Merge [20] and [30] → [20, 30]

 Merge [70] and [6] → [6, 70]

Now merge larger sublists:

 Merge [10, 15] and [0, 17]

→ [0, 10, 15, 17]

 Merge [20, 30] and [6, 70]

→ [6, 20, 30, 70]

Final merge:

 Merge [0, 10, 15, 17] and [6, 20, 30, 70]
→ [0, 6, 10, 15, 17, 20, 30, 70]

So, the sorted elements are : 0, 6, 10, 15, 17, 20, 30, 70

11. Write an algorithm to perform binary search algorithm using divide and conquer approach.

Binary search works on a sorted array.

Where A is the sorted array, LB = lower bound, UB = upper bound, and KEY is the element to be searched.
Binary_Search(A, LB, UB, KEY)
{
if (LB > UB)
return -1;

MID = (LB + UB) / 2;

if (A[MID] == KEY)
return MID;
else if (KEY < A[MID])
return Binary_Search(A, LB, MID - 1, KEY);
else
 return Binary_Search(A, MID + 1, UB, KEY);
}
12. (a) Evaluate the following postfix expression using stack: 8 2 4 - * 1 2 7 / +

(b) The following sequence of operations is performed on a stack push(1) push(3), pop, push(2), push(5), pop, pop,
pop, push(6), pop. What will be the sequence of popped out values? 4+1

Ste Operation Stack (Bottom → Top) Popped value

p

1 push(1) 1 —

2 push(3) 1, 3 —

3 pop 1 3

4 push(2) 1, 2 —

5 push(5) 1, 2, 5 —

6 pop 1, 2 5

7 pop 1 2

8 pop — (empty) 1

9 push(6) 6 —

10 pop — (empty) 6

Sequence of popped out values : 3,5,2,1,6

13. Write an algorithm for finding the shortest path using Dijkstra's algorithm.

graph G = (V, E) with non-negative edge weights, i.e., we assume that w(u, v) ≥ 0 each edge (u, v) ∈ E.
h. Dijkstra’s algorithm, is a greedy algorithm that solves the single-source shortest path problem for a directed

i. Dijkstra’s algorithm maintains a set S of vertices whose final shortestpath weights from the source s have already
been determined.
j. That is, for all vertices v  S, we have d[v] = δ (s, v).

k. The algorithm repeatedly selects the vertex u ∈ V – S with the minimum shortest-path estimate, inserts u into S,
and relaxes all edges leaving u.
l. We maintain a priority queue Q that contains all the vertices in v – s, keyed by their d values.
m. Graph G is represented by adjacency list.

n. Dijkstra’s always chooses the “lightest or “closest” vertex in V – S to insert into set S, that it uses as a greedy
strategy.
DIJKSTRA (G, w, s)

1. INITIALIZE-SINGLE-SOURCE (G, s)
2. S φ

3. Q V[G]

4. while Q  φ
 5. do u  EXTRACT-MIN (Q)

6. S  S U {u}

7. for each vertex v ∈ Adj [u]

8. do RELAX (u, v, w)
14. What is sparse matrix? How can we represent sparse matrix using array? 2+3

A sparse matrix in which most of its elements are zero. It is characterized by a small number of non-zero elements
compared to the total number of elements (mxn). In other words, a sparse matrix has a significant proportion of zero
values, often exceeding half of the total elements.

Given m and n, a sparse matrix of size mxn can be defined as follows:

 m: The number of rows

 n: The number of columns

For example, consider the following 4x4 matrix:

[ [0, 0, 7, 0],

[1, 0, 0, 0],

[2, 0, 5, 0],

[0, 8, 0, 4] ]

Representing a sparse matrix by a 2D array leads to wastage of lots of memory as zeroes in the matrix are of no use in
most of the cases. So, instead of storing zeroes with non-zero elements, we only store non-zero elements. This means
storing non-zero elements with triples- (Row, Column, value).

Sparse Matrix Representations can be done in many ways following are two common representations:

3. Array representation

4. Linked list representation

Method 1: Using Arrays:

2D array is used to represent a sparse matrix in which there are three rows named as

 Row: Index of row, where non-zero element is located

 Column: Index of column, where non-zero element is located

 Value: Value of the non zero element located at index - (row,column)

Group - C

Answer any one of the following questions: 10×1=10

15. (a) What is a binary search tree (BST)? 2+3+5

A Binary Search Tree (BST) is a type of binary tree data structure in which each node contains a unique key and
satisfies a specific ordering property:

 All nodes in the left subtree of a node contain values strictly less than the node’s value.

 All nodes in the right subtree of a node contain values strictly greater than the node’s value.

Fig.-Binary search tree

(b) Construct a BST using the following elements: 50, 30, 20, 40, 70, 60, 80

1. Insert 50
→ 50 becomes the root
2. Insert 30
30 < 50 → goes to left of 50
3. Insert 20
20 < 50 → left
20 < 30 → left of 30
4. Insert 40
40 < 50 → left
40 > 30 → right of 30
5. Insert 70
70 > 50 → right of 50
6. Insert 60
60 > 50 → right
60 < 70 → left of 70
7. Insert 80
80 > 50 → right
80 > 70 → right of 70

(c) Perform inorder, preorder, and postorder traversals on the constructed BST.

1. Inorder Traversal (Left → Root → Right)

 Left subtree of 50 → (20, 30, 40)

 Root → 50

 Right subtree of 50 → (60, 70, 80)

Inorder sequence:
20, 30, 40, 50, 60, 70, 80

2. Preorder Traversal (Root → Left → Right)

 Root → 50

 Left subtree → (30, 20, 40)

  Right subtree → (70, 60, 80)

Preorder sequence:
50, 30, 20, 40, 70, 60, 80

3. Postorder Traversal (Left → Right → Root)

 Left subtree → (20, 40, 30)

 Right subtree → (60, 80, 70)

 Root → 50

Postorder sequence:
20, 40, 30, 60, 80, 70, 50

16. Find the minimum cost spanning tree of the following graph (Figure 1) using Prim's algorithm by following the
steps. Also analyse the complexity of the algorithm. 7+3

Year-2024(Paper- MJ 3T)

Group-B

Answer any four questions of the following: 5×4-20

9. Write an algorithm to check whether a matrix is upper triangular matrix or not. Calculate time complexity of your
algorithm. 4+1

Algorithm: Check Whether a Matrix is an Upper Triangular Matrix

An upper triangular matrix is a square matrix in which all elements below the main diagonal are zero, i.e.,
for all i > j, A[i][j] = 0.

Algorithm: UPPER_TRIANGULAR (A, n)

1. For i = 1 to n

2. For j = 1 to n

3. If i > j and A[i][j] ≠ 0

4. Print “Not an Upper Triangular Matrix”

5. Exit.
 6. End For

7. End For

8. Print “Upper Triangular Matrix”

9. End

Time Complexity :

 The algorithm uses two nested loops, each running n times.

 Total number of comparisons = n × n = n²

 Therefore, Time Complexity = O(n²)

10. Write an algorithm to insert and delete in a circular queue using array. 21/2+21/2

(a) Algorithm to INSERT an element in a Circular Queue (Using Array)

INSERT_CQ (CQ, FRONT, REAR, MAX, ITEM)

1. Check overflow condition:

If (REAR + 1) % MAX = FRONT

Print “CIRCULAR QUEUE OVERFLOW”

Exit.

2. If queue is empty (FRONT = −1)

Set FRONT ← 0

Set REAR ← 0

3. Else

REAR ← (REAR + 1) % MAX

4. Insert the element:

CQ[REAR] ← ITEM

5. End

(b) Algorithm to DELETE an element from a Circular Queue (Using Array)

DELETE_CQ (CQ, FRONT, REAR, MAX)

1. Check underflow condition:

If FRONT = −1

Print “CIRCULAR QUEUE UNDERFLOW”

Exit.

2. Delete the element:

ITEM ← CQ[FRONT]

3. If only one element is present (FRONT = REAR)

Set FRONT ← −1

Set REAR ← −1

4. Else
 FRONT ← (FRONT + 1) % MAX

5. End

[Link] an algorithm to check whether a given string is palindrome or not using stack.

Algorithm: Check Palindrome Using Stack

PALINDROME (STR)

1. Initialize an empty stack S.

2. Find the length of the string STR and store it in N.

3. Push each character of STR into the stack S

o For i = 0 to N − 1, push STR[i] into S.

4. Compare characters:

o For i = 0 to N − 1

 Pop the top character from stack S and store it in CH.

 If CH ≠ STR[i], then

 Print “Not a Palindrome”

 Stop.

5. If all characters match, print “Palindrome”.

6. End

12. Write an algorithm in recursive way to search an element in binary search tree of integer numbers.

Binary search works on a sorted array.

Binary_Search (A, LB, UB, KEY)
Where A is the sorted array, LB = lower bound, UB = upper bound, and KEY is the element to be searched.
1. If LB > UB then
Print “Element not found” and RETURN
2. Set MID = (LB + UB) / 2
3. If A[MID] == KEY then
Print “Element found at position ” MID + 1 and RETURN
4. Else if KEY < A[MID] then
Call Binary_Search(A, LB, MID – 1, KEY)
5. Else
Call Binary_Search(A, MID + 1, UB, KEY)
END
[Link] is a stack? Explain the push operation of a stack. 2+3

A stack is a linear data structure that stores elements in a sequential manner. In a stack, all insertions and deletions
are performed only at one end, which is known as the TOP of the stack. The stack follows the principle of LIFO (Last
In, First Out). This means that the element which is inserted last into the stack will be the first one to be removed.
The order may be LIFO(Last In First Out) or FILO(First In Last Out). LIFO implies that the element that is inserted last,
comes out first and FILO implies that the element that is inserted first, comes out last.

A stack can be implemented using an array or a linked list.

Push Operation :

1. Check overflow condition:

If TOP = MAX − 1, the stack is full and insertion is not possible.

2. Increment TOP:
If the stack is not full, increase the value of TOP by 1.

3. Insert the element:

Store the new element at STACK[TOP].

PUSH operation: In push operation, we insert an element onto stack. Before inserting, first we increase the top
pointer and then insert the element.

Algorithm:

PUSH (STACK, TOP, MAX, DATA)

1. If TOP MAX-1 then write "STACK OVERFLOW and STOP"

2. READ DATA

3. TOP TOP + 1

4. STACK [TOP] - DATA

5. STOP

[Link] the infix expression to prefix and postfix ((A+((B^C)-D))*(E-(A/C)))

Infix to prefix:

((A+((B^C)-D))*(E-(A/C)))

=((A+(^BC)-D)*(E-(/AC))

=((A+(-^BCD)*(-E/AC))

=((+A-^BCD)*(-E/AC))

=*+A-^BCD-E/AC

Infix to pOSTfix:

((A+((B^C)-D))*(E-(A/C)))

=((A+((BC^)-D))*(E-(AC/)))

=((A+(BC^D-)*(EAC/-))

=(ABC^D-+)*(EAC/-)
=ABC^D-+EAC/-*

Group - C

Answer any one questions of the following: 10×1=10

(15) What is AVL tree? Construct an AVL tree using following sequence of data.

16, 27, 9, 11, 36, 54, 61, 83, 72

An AVL tree defined as a self-balancing Binary Search Tree (BST) where the difference between heights of
left and right subtrees for any node cannot be more than one.
Balance Factor = left subtree height - right subtree height
For a Balanced Tree(for every node): -1 ≤ Balance Factor ≤ 1

Example of an AVL Tree:

(16) Write an algorithm to perform the "merge sort" and explain its time complexity. Discuss the advantages and
disadvantages of merge sort compared to other sorting algorithms. 8+2

Merge sort :
a. Merge sort is a sorting algorithm that uses the idea of divide and conquer.
b. This algorithm divides the array into two halves, sorts them separately and then merges them.
c. This procedure is recursive, with the base criteria that the number of elements in the array is not more than 1.
ALGORITHM:
MERGE_SORT (a, p, r) :

10. if p < r

11. then q ← |_ (p + r)/2 _|

12. MERGE-SORT (A, p, q)

4. MERGE-SORT (A, q + 1, r)

5. MERGE (A, p, q, r)
MERGE (A, p, q, r) :
28. n1 = q – p + 1
29. n2 = r – q
30. Create arrays L [1 .........n1 + 1] and R [1......n2 + 1]
31. for i = 1 to n1 do

L[i] = A [p + i – 1]
endfor
32. for j = 1 to n2 do

R[j] = A[q + j]
endfor
33. L[n1 + 1] = ∞, R[n2 + 1] = ∞
34. i = 1, j = 1

35. for k = p to r
do
if L[i] <= R[j]
then A[k] ← L[i]
i=i+1
else A[k] = R[j]

j=j+1

endif

endfor

36. exit

1. Let f(n) denote the number of comparisons needed to sort an n-element array A using the merge sort algorithm.
2. The algorithm requires at most log n passes.
3. Moreover, each pass merges a total of n elements, and by the discussion on the complexity of merging, each pass
will require at most n comparisons.
4. Accordingly, for both the worst case and average case, f(n)  n log n
5. This algorithm has the same order as heap sort and the same average order as quick sort.
6. The main drawback of merge sort is that it requires an auxiliary array with n elements.
7. Each of the other sorting algorithms requires only a finite number of extra locations, which is independent of n.
8. The results are summarized in the following table :
Advantages and Disadvantages of Merge Sort

Advantages

 Stability : Merge sort is a stable sorting algorithm, which means it maintains the relative order of equal
elements in the input array.

 Guaranteed worst-case performance: Merge sort has a worst-case time complexity of O(N logN) , which
means it performs well even on large datasets.

 Simple to implement: The divide-and-conquer approach is straightforward.

 Naturally Parallel : We independently merge subarrays that makes it suitable for parallel processing.

Disadvantages

 Space complexity: Merge sort requires additional memory to store the merged sub-arrays during the sorting
process.

 Not in-place: Merge sort is not an in-place sorting algorithm, which means it requires additional memory to
store the sorted data. This can be a disadvantage in applications where memory usage is a concern.

 Merge Sort is Slower than QuickSort in general as QuickSort is more cache friendly because it works in-
place.

Year-2022 (VU-BCA)

Group - A

Answer any four questions. 4x15

1. (a) What do you mean by algorithmic complexity? Explain Time complexity and space complexity in brief. 2+6

Algorithm Complexity:

Suppose X is treated as an algorithm and N is treated as the size of input data, the time and space implemented by
the Algorithm X are the two main factors which determine the efficiency of X.

Time Factor − The time is calculated or measured by counting the number of key operations such as comparisons in
sorting algorithm.

Space Factor − The space is calculated or measured by counting the maximum memory space required by the
algorithm.

The complexity of an algorithm f(N) provides the running time and / or storage space needed by the algorithm with
respect of N as the size of input data.

Space Complexity:
Space complexity of an algorithm represents the amount of memory space needed the algorithm in its life cycle.

Space needed by an algorithm is equal to the sum of the following two components

A fixed part that is a space required to store certain data and variables (i.e. simple variables and constants, program
size etc.), that are not dependent of the size of the problem.

A variable part is a space required by variables, whose size is totally dependent on the size of the problem. For
example, recursion stack space, dynamic memory allocation etc.

Space complexity S(p) of any algorithm p is S(p) = A + Sp(I) Where A is treated as the fixed part and S(I) is treated as
the variable part of the algorithm which depends on instance characteristic I. Following is a simple example that tries
to explain the concept

Algorithm

SUM(P, Q)

Step 1 - START

Step 2 - R ← P + Q + 10

Step 3 - Stop

Here we have three variables P, Q and R and one constant. Hence S(p) = 1+3. Now space is dependent on data types
of given constant types and variables and it will be multiplied accordingly.

Time Complexity:

Time Complexity of an algorithm is the representation of the amount of time required by the algorithm to execute to
completion. Time requirements can be denoted or defined as a numerical function t(N), where t(N) can be measured
as the number of steps, provided each step takes constant time.

For example, in case of addition of two n-bit integers, N steps are taken. Consequently, the total computational time
is t(N) = c*n, where c is the time consumed for addition of two bits. Here, we observe that t(N) grows linearly as
input size increases.

(b) What is Data structure? Write a brief note on classification of data structure. 2+5

A data structure is a storage that is used to store and organize data. It is a way of arranging data on a computer so
that it can be accessed and updated efficiently. Data structure is the representation of the logical relationship existing
between individual elements of data. Data structure is define as a mathematical or logical model of particular
organization of data items.

A data structure organizes, processes, retrieves, and stores data, making it essential for nearly every program or
software system.

Classification of Data Structure

There are many different data structures that are used to solve different mathematical and logical problems. By using
data structure, one can organize and process a very large amount of data in a relatively short period.
  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: array, stack, queue, linked list, etc.

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

o Dynamic data structure: In the 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: stack and queue data structures.

 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.
Examples: tree and graph data structures.

Arrays Data Structure

An array is a linear data structure and it is a collection of element of same data type stored at contiguous memory
locations.

Different applications of an array are as follows:

Arrays efficiently manage and store database records.

 It helps in implementing sorting algorithm.

  It is also used to implement other data structures like Stacks, Queues, Heaps, Hash tables, etc.

 An array can be used for CPU scheduling.

Linked list Data Structure

A linked list is a linear data structure in which elements are not stored at contiguous memory locations. The elements
in a linked list are linked using pointers as shown in the below image.

Applications of the Linked list

 Linked lists are used to implement other data structures like stacks, queues, etc.

 It is used for the representation of sparse matrices.

 It is used in the linked allocation of files.

 Linked lists are used to display image containers. Users can visit past, current, and next images.

 They are used to perform undo operations.

Stack Data Structure

Stack is a linear data structure that follows LIFO(Last in first out) principle i.e., entering and retrieving data is possible
from only one end. The entering and retrieving of data is also called push and pop operation in a stack.

Applications of Stack

Different applications of Stack are as follows:

 The stack data structure is used in the evaluation and conversion of arithmetic expressions.

 It is used for parenthesis checking and string reversal.

 A memory stack is also used for processing function calls.

 The stack is used in virtual machines like JVM.

Queue Data Structure

Queue is a linear data structure that follows First In First Out(FIFO) principle i.e. the data item stored first will be
accessed first. In this, entering is done from one end and retrieving data is done from other end. An example of a
queue is any queue of consumers for a resource where the consumer that came first is served first.

Applications of Queue:

Different applications of Queue are as follows:

 Queue is used for handling website traffic.

 It helps to maintain the playlist in media players.

 It helps in serving requests on a single shared resource, like a printer, CPU task scheduling, etc.

 Queues are used for job scheduling in the operating system.

Tree Data Structure

A tree is a non-linear and hierarchical data structure where the elements are arranged in a tree-like structure. In a
tree, the topmost node is called the root node. Each node contains some data, and data can be of any type. It
consists of a central node, structural nodes, and sub-nodes which are connected via edges. Different tree data
structures allow quicker and easier access to the data as it is a non-linear data structure.

Applications of Tree:

 Heap is a tree data structure that is implemented using arrays and used to implement priority queues.

 B-Tree and B+ Tree are used to implement indexing in databases.

  Syntax Tree helps in scanning, parsing, generation of code, and evaluation of arithmetic expressions in
Compiler design.

 Spanning trees are used in routers in computer networks.

 Domain Name Server also uses a tree data structure.

Graph Data Structure

A graph is a non-linear data structure that consists of vertices (or nodes) and edges. It consists of a finite set of
vertices and set of edges that connect a pair of nodes. The graph is used to solve the most challenging and complex
programming problems. It has different terminologies which are Path, Degree, Adjacent vertices, Connected
components, etc.

Applications of Graph:

 The operating system uses Resource Allocation Graph.

 Also used in the World Wide Web where the web pages represent the nodes.

 One of the most common real-world examples of a graph is Google Maps where cities are located as vertices
and paths connecting those vertices are located as edges of the graph.

 A social network is also one real-world example of a graph where every person on the network is a node, and
all of their friendships on the network are the edges of the graph.

2. 8+6+1

(a) Define AVL tree. Construct AVL tree for following data: 1, 2, 3, 4, 8, 7, 6, 5, 11, 10, 12

An AVL tree defined as a self-balancing Binary Search Tree (BST) where the difference between heights of left and
right subtrees for any node cannot be more than one.
Balance Factor = left subtree height - right subtree height
For a Balanced Tree(for every node): -1 ≤ Balance Factor ≤ 1

Example of an AVL Tree:

(b) Write two functions to implement two basic operations of stack.

#include <stdio.h>

#define MAX 100

int STACK[MAX];

int TOP = -1;

/* Function to PUSH an element into stack */

void PUSH(int DATA) {

if (TOP == MAX - 1) {

printf("STACK OVERFLOW\n");

return;

TOP = TOP + 1;

STACK[TOP] = DATA;

printf("Element %d pushed successfully\n", DATA);

/* Function to POP an element from stack */

void POP() {

int ITEM;

if (TOP < 0) {

printf("STACK UNDERFLOW\n");

return;

ITEM = STACK[TOP];

STACK[TOP] = 0; // optional

TOP = TOP - 1;

printf("Popped element is %d\n", ITEM);

(c) Why is circular linked list needed over single linked list?
 A circular linked list is preferred over a singly linked list because the last node points to the first node instead
of NULL, allowing continuous traversal. It is useful for applications like circular queues and round-robin scheduling
where repeated access is required.

3. 6+5+4

(a) Explain the BFS algorithm for graph traversal with an example.

Breadth First Search (BFS) :

The general idea behind a breadth first search beginning at a starting node A is as follows :
a. First we examine the starting node A.
h. Then, we examine all the neighbours of A, and so on.

i. We need to keep track of the neighbours of a node, and that no node is processed more than once.
j. This is accomplished by using a queue to hold nodes that are waiting to be processed, and by using a field
STATUS which tells us the current status of any node.
Algorithm : This algorithm executes a breadth first search on a graph G beginning at a starting node A.
vii. Initialize all nodes to ready state (STATUS=1).

[Link] the starting node A in queue and change its status to the waiting state (STATUS = 2).
ix. Repeat steps (iv) and (v) until queue is empty.
iv. Remove the front node N of queue. Process N and change the status of N to the processed state (STATUS = 3).
v. Add to the rear of queue all the neighbours of N that are in the ready state (STATUS=1) and change their status to
the waiting state (STATUS = 2).
[End of loop]
vi. End.
(b) Show every step of constructing binary search tree using the following list of nodes: 16, 7, 15, 20, 9, 2, 6.

(c) Write down the pre-order, post-order and in-order traversal order of nodes of the binary search tree obtained in
the above questions.

4. 5+2+3+5

(a) Write down a function to insert nodes in a BST.

#include <stdio.h>

#include <stdlib.h>

/* Definition of BST node */

struct node {
 int data;

struct node *left;

struct node *right;

};

/* Function to create a new node */

struct node* createNode(int item) {

struct node* temp = (struct node*)malloc(sizeof(struct node));

temp->data = item;

temp->left = NULL;

temp->right = NULL;

return temp;

/* Function to insert a node in BST */

struct node* insertBST(struct node* root, int key) {

/* If tree is empty, return new node */

if (root == NULL) {

return createNode(key);

/* Otherwise, recur down the tree */

if (key < root->data) {

root->left = insertBST(root->left, key);

else if (key > root->data) {

root->right = insertBST(root->right, key);

/* Return unchanged root pointer */

return root;

(b) What is deque?

Deque or Double Ended Queue is a generalized version of Queue data structure that allows insert and
delete at both ends. Below is an example program of deque
(c) What is linear probing in hashing?

Linear probing is a collision resolution technique used in open addressing hashing.

When two keys hash to the same index in a hash table, linear probing finds the next available empty slot by checking
the table sequentially.
Example, Using the hash function ‘key mod 7’, insert the following sequence of keys in the hash table-50, 700, 76, 85,
92, 73 and 101 Use linear probing technique for collision resolution.
Solution-

The given sequence of keys will be inserted in the hash table as-

Step-01:

 Draw an empty hash table.

 For the given hash function, the possible range of hash values is [0, 6].
 So, draw an empty hash table consisting of 7 buckets as-

Step-02:

 Insert the given keys in the hash table one by one.

 The first key to be inserted in the hash table = 50.
 Bucket of the hash table to which key 50 maps = 50 mod 7 = 1.
 So, key 50 will be inserted in bucket-1 of the hash table as-
Step-03:

 The next key to be inserted in the hash table = 700.

 Bucket of the hash table to which key 700 maps = 700 mod 7 = 0.
 So, key 700 will be inserted in bucket-0 of the hash table as-

Step-04:

 The next key to be inserted in the hash table = 76.

 Bucket of the hash table to which key 76 maps = 76 mod 7 = 6.
 So, key 76 will be inserted in bucket-6 of the hash table as-

Step-05:

 The next key to be inserted in the hash table = 85.

 Bucket of the hash table to which key 85 maps = 85 mod 7 = 1.
 Since bucket-1 is already occupied, so collision occurs.
 To handle the collision, linear probing technique keeps probing linearly until an empty bucket is found.
 The first empty bucket is bucket-2.
 So, key 85 will be inserted in bucket-2 of the hash table as-
Step-06:

 The next key to be inserted in the hash table = 92.

 Bucket of the hash table to which key 92 maps = 92 mod 7 = 1.
 Since bucket-1 is already occupied, so collision occurs.
 To handle the collision, linear probing technique keeps probing linearly until an empty bucket is found.
 The first empty bucket is bucket-3.
 So, key 92 will be inserted in bucket-3 of the hash table as-

Step-07:

 The next key to be inserted in the hash table = 73.

 Bucket of the hash table to which key 73 maps = 73 mod 7 = 3.
 Since bucket-3 is already occupied, so collision occurs.
 To handle the collision, linear probing technique keeps probing linearly until an empty bucket is found.
 The first empty bucket is bucket-4.
 So, key 73 will be inserted in bucket-4 of the hash table as-

Step-08:

 The next key to be inserted in the hash table = 101.

 Bucket of the hash table to which key 101 maps = 101 mod 7 = 3.
  Since bucket-3 is already occupied, so collision occurs.
 To handle the collision, linear probing technique keeps probing linearly until an empty bucket is found.
 The first empty bucket is bucket-5.
 So, key 101 will be inserted in bucket-5 of the hash table as-

(d) Write down the relative advantages and disadvantages of array and linked list.

Advantages of Array Data Structure:

 Efficient and Fast Access: Arrays allow direct and efficient access to any element in the collection with
constant access time, as the data is stored in contiguous memory locations.

 Memory Efficiency: Arrays store elements in contiguous memory, allowing efficient allocation in a single
block and does not require extra storage for linking different blocks.

 Versatility: Arrays can be used to store a wide range of data types, including integers, floating-point numbers,
characters, and even complex data structures such as objects and pointers.

 Compatibility with hardware: The array data structure is compatible with most hardware architectures,
making it a versatile tool for programming in a wide range of environments.

Disadvantages of Array Data Structure:

 Fixed Size: Arrays have a fixed size set at creation. Expanding an array requires creating a new one and
copying elements, which is time-consuming and memory-intensive. Even dynamic sized arrays internally use
fixed sized memory allocation and de-allocation.

 Memory Allocation Issues: Allocating large arrays can cause memory exhaustion, leading to crashes,
especially on systems with limited resources.

 Insertion and Deletion Challenges: Adding or removing elements requires shifting subsequent elements,
making these operations inefficient.

Advantages Of Linked List:

 Dynamic data structure: A linked list is a dynamic arrangement so it can grow and shrink at runtime by
allocating and deallocating memory. So there is no need to give the initial size of the linked list.

 No memory wastage: In the Linked list, efficient memory utilization can be achieved since the size of the
linked list increase or decrease at run time so there is no memory wastage and there is no need to pre-
allocate the memory.
  Insertion and Deletion Operations: Insertion and deletion operations are quite easier in the linked list. There
is no need to shift elements after the insertion or deletion of an element only the address present in the next
pointer needs to be updated.

 Flexible: This is because the elements in Linked List are not stored in contiguous memory locations unlike the
array.

 Efficient for large data: When working with large datasets linked lists play a crucial role as it can grow and
shrink dynamically.

Disadvantages Of Linked List:

 Memory usage: More memory is required in the linked list as compared to an array. Because in a linked list,
a pointer is also required to store the address of the next element and it requires extra memory for itself.

 Traversal: In a Linked list traversal is more time-consuming as compared to an array. Direct access to an
element is not possible in a linked list as in an array by index. For example, for accessing a node at position n,
one has to traverse all the nodes before it.

 Reverse Traversing: In a singly linked list reverse traversing is not possible, but in the case of a doubly-linked
list, it can be possible as it contains a pointer to the previously connected nodes with each node. For
performing this extra memory is required for the back pointer hence, there is a wastage of memory.

 Lower efficiency at times: For certain operations, such as searching for an element or iterating through the
list, can be slower in a linked list.

 Not suited for small dataset: Cannot provide any significant benefits on small dataset compare to that of an
array.

5. (a) Convert the following infix expression into equivalent postfix expression: 4$2*3-3+8/4*(1+1)

Characte Stack Postfix

r

4 — 4

$ $ 4

2 $ 42

* * 42$

3 * 42$3

− − 42$3*

3 − 42$3*3

+ + 42$3*3−

8 + 42$3*3−8

/ +/ 42$3*3−8

4 +/ 42$3*3−84

* +* 42$3*3−84/

( +*( 42$3*3−84/

1 +*( 42$3*3−84/1

+ + * ( + 42$3*3−84/1
 1 + * ( + 42$3*3−84/11

) +* 42$3*3−84/11+

End — 42$3*3−84/11+*
+

So,postfix expression of the given infix expression is : 42$3*3−84/11+*+

(b) Write an algorithm to implement merge sort.

Merge sort :
a. Merge sort is a sorting algorithm that uses the idea of divide and conquer.
b. This algorithm divides the array into two halves, sorts them separately and then merges them.
c. This procedure is recursive, with the base criteria that the number of elements in the array is not more than 1.
ALGORITHM:
MERGE_SORT (a, p, r) :

13. if p < r

14. then q ← |_ (p + r)/2 _|

15. MERGE-SORT (A, p, q)

4. MERGE-SORT (A, q + 1, r)

5. MERGE (A, p, q, r)
MERGE (A, p, q, r) :
37. n1 = q – p + 1
38. n2 = r – q
39. Create arrays L [1 .........n1 + 1] and R [1......n2 + 1]
40. for i = 1 to n1 do

L[i] = A [p + i – 1]
endfor
41. for j = 1 to n2 do

R[j] = A[q + j]
endfor
42. L[n1 + 1] = ∞, R[n2 + 1] = ∞
43. i = 1, j = 1

44. for k = p to r
do
if L[i] <= R[j]
then A[k] ← L[i]
i=i+1
else A[k] = R[j]

j=j+1

endif

endfor

45. exit

(c) What is a complete binary tree? What is its depth? Give an example.
Complete binary tree: A tree is called a complete binary tree if tree satisfies following conditions:

a. Each node has exactly two children except leaf node.

b. All leaf nodes are at same level.

c. If a binary tree contains m nodes at level l, it contains atmost 2m nodes at level l + 1.

Fig. – complete binary tree

ii. Depth : The depth of binary tree is the maximum level of any leaf in the tree. This equals the length of the
longest path from the root to any leaf. Depth of below Fig. tree is 2.
A

B C

D E F

(d) Write an algorithm to traverse a binary search tree in pre-order fashion.

6. (2+3)+3+7

(a) Define stack. How is it different from Queue?

Stack is a linear data structure that follows LIFO(Last in first out) principle i.e., entering and retrieving data is possible
from only one end. The entering and retrieving of data is also called push and pop operation in a stack.

Applications of Stack

Different applications of Stack are as follows:

 The stack data structure is used in the evaluation and conversion of arithmetic expressions.

 It is used for parenthesis checking and string reversal.

 Topic Stack Queue

Definition A linear data structure that follows A linear data structure that follows the First In First Out
the Last In First Out (FIFO) principle.
(LIFO) principle.

Primary Push (add an item), Pop (remove Enqueue (add an item), Dequeue (remove an item),
Operations an item), Peek (view the top item) Front (view the first item), Rear (view the last item)

Insertion/Removal Elements are added and removed Elements are added at the rear and removed from the
from the same end (the top). front.

Use Cases Function call management (call Scheduling processes in operating systems, managing
stack), expression evaluation and requests in a printer queue, breadth-first search in
syntax parsing, undo mechanisms graphs.
in text editors.

Examples Browser history (back button), Customer service lines, CPU task scheduling.
reversing a word.

Real-World A stack of plates: you add and A queue at a ticket counter: the first person in line is
Analogy remove plates from the top. the first to be served.

Complexity Push: O(1), Pop: O(1), Peek: O(1) Enqueue: O(1), Dequeue: O(1), Front: O(1), Rear: O(1)
(Amortized)

Memory Structure Typically uses a contiguous block Typically uses a circular buffer or linked list.
of memory or linked list.

Implementation Can be implemented using arrays Can be implemented using arrays, linked lists, or
or linked lists. circular buffers.

(b) What is Priority Queue?

A priority queue is a data structure in which each element has been assigned a value called the priority of the
element and an element can be inserted or deleted not only at the ends but at any position on the queue.

A priority queue is a collection of elements such that each element has been assigned an explicit or implicit priority
and such that the order in which elements are deleted and processed comes from the following rules:

a. An element of higher priority is processed before any element of lower priority.

b. Two elements with the same priority are processed to the order in which they were inserted to the queue.

Types of priority queues are:

1. Ascending priority queue: In ascending priority queue, elements can be inserted in an order. But, while deleting
elements from the queue, always a small element to be deleted first.

2. Descending priority queue: In descending priority queue, elements are inserted in any order but while deleting
elements from the queue always a largest element to be deleted first.

Applications of priority queue :

1. The typical example of priority queue is scheduling the jobs in operating system. Typically operating system
allocates priority to jobs. The jobs are placed in the queue and position 1 of the job in priority queue determines
their priority.

2. In network communication, to manage limited bandwidth for transmission, the priority queue is used.
3. In simulation modelling, to manage the discrete events the priority queue is used.

(c) Write an algorithm to concatenate Number of nodes to a linked list, Where N is given by user.

7. 2+6+4+3

(a) What are the basic differences of graph over tree?

Feature Graph Tree

Definition A collection of nodes (vertices) and A hierarchical data structure consisting of nodes
edges, where edges connect nodes. connected by edges with a single root node.

Structure Can have cycles (loops) and No cycles; connected structure with exactly one path
disconnected components. between any two nodes.

Root Node No root node; nodes may have Has a designated root node that has no parent.
multiple parents or no parents at all.

Node Relationships between nodes are Parent-child relationship; each node (except the root)
Relationship arbitrary. has exactly one parent.

Edges Each node can have any number of If there is n nodes then there would be n-1 number of
edges. edges

Traversal Traversal can be complex due to Traversal is straightforward and can be done in linear
Complexity cycles and disconnected components. time.

Application Used in various scenarios like social Commonly used for hierarchical data representation
networks, maps, network like file systems, organization charts, HTML DOM, XML
optimization, etc. documents, etc.

Examples Social networks, road networks, File systems, family trees, HTML DOM structure.
computer networks.

(b) Write down the algorithm to implement insertion sort.

INSERTION_SORT(A)
(A = array of elements)

8. for j ← 2 to length[A]

9. do key ← A[j] /*Insert A[j] into the sorted sequence A[1....j – 1].*/

10. i←j–1

11. while i > 0 and A[i] > key

12. do A[i + 1] ← A[i]

13. i←i–1
 14. A[i + 1] ←key

(c) Why the time complexity of binary search is lower than liner search?

(d) Define the following terms:

I. depth of a tree

Depth : The depth of binary tree is the maximum level of any leaf in the tree. This equals the length of the longest
path from the root to any leaf. Depth of below Fig. tree is 2.
A

B C

D E F

II. Full binary tree.

A full binary tree is a binary tree with either zero or two child nodes for each node.

A full Binary tree is a special type of binary tree in which every parent node/internal node has either two or no
children. It is also known as a proper binary tree.

8. Write short notes on any three of the following: 3x5

(a) DFS

1. Depth First Search (DFS):

The general idea behind a depth first search beginning at a starting node A is as follows:

a. First, we examine the starting node A.

b. Then, we examine each node N along a path P which begins at A; that is, we process neighbour of A, then a
neighbour of neighbour of A, and so on.

c. This algorithm uses a stack instead of queue.

Algorithm:
i. Initialize all nodes to ready state (STATUS = 1).

ii. Push the starting node A onto stack and change its status to the waiting state (STATUS = 2).

iii. Repeat steps (iv) and (v) until queue is empty.

iv. Pop the top node N of stack, process N and change its status to the processed state (STATUS = 3).

v. Push onto stack all the neighbours of N that are still in the ready state (STATUS = 1) and change their status to the
waiting state (STATUS = 2).

[End of loop]

vi. End.

Importance of DFS : DFS is very important algorithm as based upon DFS, there are O(V + E)-time algorithms for the
following problems :
1. Testing whether graph is connected.

2. Computing a spanning forest of G.

3. Computing the connected components of G.

4. Computing a path between two vertices of G or reporting that no such path exists.
5. Computing a cycle in G or reporting that no such cycle exists.
Application of DFS : Algorithms that use depth first search as a building block include :
1. Finding connected components.

2. Topological sorting.

3. Finding 2- (edge or vertex)-connected components.

4. Finding 3- (edge or vertex)-connected components.

5. Finding the bridges of a graph.

6. Generating words in order to plot the limit set of a group.

7. Finding strongly connected components.

(b) Bi connected

An undirected graph is called Biconnected if there are two vertex-disjoint paths between any two vertices. In a
Biconnected Graph, there is a simple cycle through any two vertices.
Or in other words:
A graph is said to be Biconnected if:
3. It is connected, i.e. it is possible to reach every vertex from every other vertex, by a simple path.
4. Even after removing any vertex the graph remains connected.
Examples:

Important points:
  No vertex exists whose removal disconnects the graph.
 Minimum number of vertices in a biconnected graph is 2.
 A graph with an articulation point is not biconnected.
 A tree is never biconnected because every internal node is an articulation point.

(c) Recursion

Recursion is a process of expressing a function that calls itself to perform specific [Link] recursion occurs
when one function calls another function that then calls the first [Link] P is a procedure containing either
a call statement to itself or a call statement to a second procedure that may eventually result in a call statement back
to the original procedure [Link] P is called recursive procedure. So the program will not continue to run indefinitely.

A recursive procedure must have the following two properties:

a. There must be certain criteria, called base criteria, for which the procedure does not call itself.

b. Each time the procedure does call itself, it must be closer to the criteria.

A recursive procedure with these two properties is said to be [Link], a function is said to be
recursively defined if the function definition refers to [Link], in order for the definition not to be circular, it must
have the following two properties:

a. There must be certain arguments, called base values, for which the function does not refer to itself.

[Link] time the function does refer to itself, the argument of the function must be closer to a base value.

Types of recursion :

a. Direct recursion: A function is directly recursive if it contains an explicit call to itself.

For example:

int foo (int x)

{ if (x <= 0)

return x;

return foo (x-1);

b. Indirect recursion: A function is indirectly recursive if it contains a call to another function.

For example:

int foo (int x)

{ if (x <= 0)

return bar (x);

return x; }

int bar (int y)

{return foo (y-1);}

c. Tail recursion:
Tail recursion (or tail-end recursion) is a special case of recursion in which the last operation of the function, the tail
call is a recursive call. Such recursions can be easily transformed to iterations.

For example:

Consider this recursive definition of the factorial function in C:

factorial (n)

if(n == 0)

return 1;

return n* factorial (n - 1);

d. Linear and tree recursive:

A recursive function is said to be linearly recursive when no pending operation involves another recursive call to the
function.A recursive function is said to be tree recursive (or non-linearly recursive) when the pending operation does
involve another recursive call to the function.

The Fibonacci function fib provides a classic example of tree recursion. The Fibonacci numbers can be defined by the
rule:

int fib (int n)

{/* n >= 0 */

if (n == 0)

return 0;

if (n == 1)

return 1;

return fib (n-1)+fib(n-2);

The pending operation for the recursive call is another call to fib. Therefore, fib is tree recursive.

(d) Circular Linked list

A circular linked list is a data structure where the last node points back to the first node, forming a closed loop.

 Structure: All nodes are connected in a circle, enabling continuous traversal without encountering NULL.

 Difference from Regular Linked List: In a regular linked list, the last node points to NULL, whereas in a circular
linked list, it points to the first node.

 Uses: Ideal for tasks like scheduling and managing playlists, where smooth and repeated.

Types of Circular Linked Lists

We can create a circular linked list from both singly linked lists and doubly linked lists. So, circular linked lists are
basically of two types:

1. Circular Singly Linked List

In Circular Singly Linked List, each node has just one pointer called the "next" pointer. The next pointer of the last
node points back to the first node and this results in forming a circle. In this type of Linked list, we can only move
through the list in one direction.

2. Circular Doubly Linked List:

In circular doubly linked list, each node has two pointers prev and next, similar to doubly linked list. The prev pointer
points to the previous node and the next points to the next node. Here, in addition to the last node storing the
address of the first node, the first node will also store the address of the last node.

(c) Euclid's algorithm.

Group - B

Answer any one question. 1×10

9.

(a) What do you mean by sparse matrix? What is collision in hashing? 2+2

A sparse matrix in which most of its elements are zero. It is characterized by a small number of non-zero elements
compared to the total number of elements (mxn). In other words, a sparse matrix has a significant proportion of zero
values, often exceeding half of the total elements.

Given m and n, a sparse matrix of size mxn can be defined as follows:

 m: The number of rows

 n: The number of columns

For example, consider the following 4x4 matrix:

[ [0, 0, 7, 0],

[1, 0, 0, 0],

[2, 0, 5, 0],

[0, 8, 0, 4] ]

Collision in hashing:

Hashing is a data structure that uses a hash function to map data to a location in the data structure. The hash
function takes the data as input and returns an index in the data structure where the data should be stored.
However, there can be cases where two different data elements map to the same index in the data structure. This is
known as a collision.
For example,

(b) Write the difference between B tree and B++ tree. 6

Basis of B tree B+ tree

Comparison

Pointers All internal and leaf nodes have data pointers Only leaf nodes have data pointers

Search Since all keys are not available at leaf, search often All keys are at leaf nodes, hence search
takes more time. is faster and more accurate.

Redundant No duplicate of keys is maintained in the tree. Duplicate of keys are maintained and
Keys all nodes are present at the leaf.

Insertion Insertion takes more time and it is not predictable Insertion is easier and the results are
sometimes. always the same.

Deletion Deletion of the internal node is very complex and the Deletion of any node is easy because
tree has to undergo a lot of transformations. all node are found at leaf.

Leaf Nodes Leaf nodes are not stored as structural linked list. Leaf nodes are stored as structural
linked list.

Access Sequential access to nodes is not possible Sequential access is possible just like
linked list

Height For a particular number nodes height is larger Height is lesser than B tree for the
same number of nodes

Application B-Trees used in Databases, Search engines B+ Trees used in Multilevel Indexing,
Database indexing

Number of Number of nodes at any intermediary level ‘l’ is 2l. Each intermediary node can have n/2
Nodes to n children.

10. 6+4

(a) Explain quicksort algorithm with a suitable example.

Recursive quick sort algorithm:

QUICK-SORT (A, p, r):

1. If p < r then

2. q← PARTITION (A, p, r)

3. QUICK-SORT (A, p, q-1)

4. QUICK-SORT (A, q + 1, r)

PARTITION (A, p, r) :

1. x ← A[r]

2. I ← p-1

3. for jp to r-1

4. do if A[j] ≤ x

5. then i  i+1

6. exchange A[i] A[j]

7. exchange A[i + 1] A[r]

8. return i + 1

Quick sort: This algorithm sorts an array A with N elements.

1. [Initialize] Top := NULL

2. [PUSH boundary values of A onto stack when A has 2 or more elements] If N > 1, then: TOP : TOP + 1, LOWER [1] :=
1, UPPER [1] := N

3. Repeat steps 4 to 7 while TOP ≠ NULL

4. [POP sublist from stacks]

Set BEG := LOWER [TOP], END := UPPER [TOP],

TOP TOP-1

5. Call Quick (A, N, BEG, END, LOC)

6. [PUSH left sublist onto stack when it has 2 or more elements]

If BEG < LOC-1 then :

TOP : TOP + 1, LOWER [TOP] := BEG,

UPPER [TOP] = LOC-1

[End of if structure]

7. [PUSH right sublist onto stack when it has 2 or more elements]

If LOC + 1 < END, then:

TOP := TOP + 1, LOWER [TOP] := LOC + 1

UPPER [TOP] := END

[END of if structure]

[END of step 3 loop]

8. Exit

Example:

(b) Differentiate between array of pointers and pointer to an array with proper example.

Feature Array of Pointers Pointer to an Array

Definition An array whose elements are pointers A pointer that points to an entire array

Declaration int *arr[3]; int (*ptr)[3];

What it stores Addresses of variables Address of the whole array

Number of Pointers Multiple pointers Single pointer

Memory Allocation Memory for multiple pointers Memory for one pointer

Accessing Elements *arr[i] (*ptr)[i]

Flexibility Each pointer can point anywhere Fixed to one array

Common Use Array of strings Passing arrays to functions

Complexity Easier to understand Slightly complex syntax

Example of array of pointers: Example of pointer to an array:

#include <stdio.h> #include <stdio.h>

int main() { int main() {

int a = 10, b = 20, c = 30; int arr[3] = {10, 20, 30};

int *arr[3]; int (*ptr)[3];

ptr = &arr;
arr[0] = &a; for(int i = 0; i < 3; i++) {