1.What is a Data Structure?
A data structure is a particular way of organizing, storing, and managing data so that it can be
accessed and modified efficiently. Data structures are essential in computer science and
software engineering because they help to optimize algorithms.
1. Primitive Data Structures
These are the basic data types provided by most programming languages. They serve as the
building blocks for more complex data structures
2. Non-Primitive Data Structures
These structures are derived from primitive data types and are categorized into two
subtypes:
A. Linear Data Structures
B. Non-Linear Data Structures
2.What do you mean by Space Complexity and time complexity of an algorithm
?. write an algorithm Ipseudo Code for Binary Search and mention the best
Case and worst case time Complexity of Binary search.
Time and Space Complexity
Time Complexity: Measures how much time an algorithm takes based on input size n.
Space Complexity: Measures how much memory an algorithm uses during execution.
Complexities:
Best Case: O(1) – Target found at middle.
Worst Case: O(log n) – Target found after multiple halving steps.
Space Complexity: O(1) for iterative version.
3.How array i's implemented i'n memory and how the address of an
Element Can be calculated in one and two dimensional array
Array Implementation in Memory:
Arrays are stored in contiguous memory locations.
Each element occupies equal space (e.g., w bytes).
The base address is the memory location of the first element.
Address Calculation:
1. One-Dimensional Array:
Formula:
Address(A[i]) = Base_Address + i × w
2. Two-Dimensional Array (Row-Major):
Formula:
Address(A[i][j]) = Base_Address + ((i × n) + j) × w
where n = number of columns
This helps the system locate any element in constant time using its index.
4.what do you mean by stack 2. write an algorithm for stack push and pop
operation
A stack is a linear data structure that works on the LIFO (Last In, First Out) principle.
Last inserted element is removed first.
Main operations: Push (insert), Pop (delete)
2. Algorithms
Push(stack, top, max, item):
Pop(stack, top)
5.Write the Prefix and Postfix form of Each of the following infix notation:-
a) A-B+(M$N)* (O+P)-Q/R^S*T+Z b) K+L-M*N+O^p) * W/U/V *T+Q
a) Infix:
A - B + (M $ N) * (O + P) - Q / R ^ S * T + Z
Prefix: + - + - A B * $ M N + O P / Q * ^ R S T Z
Postfix: A B - M N $ O P + * + Q R S ^ / T * - Z +
b) Infix:
K+L-M*N+O^P*W/U/V*T+Q
Prefix: + - + K L * M N * ^ O P / / W U V * T Q
Postfix: K L + M N * - O P ^ W * U / V / T * + Q +
6.what i's ment by Circular queue and Priority queve write a function to
insert and delete an element from a Circular queue.
Circular Queue:
A linear data structure where the last position connects back to the first, forming a circle. It
avoids wasted space in a regular queue.
Priority Queue:
A queue where each element has a priority. Elements with higher priority are served before
others.
Circular Queue Operations (Pseudocode):
Insert:
Delete:
7.Define sential a recur cursive function. What are the mditions to be
satisfied by ve function.
Definition of a Recursive Function:
A recursive function is a function that calls itself to solve a problem. It breaks down a
problem into smaller subproblems of the same type.
Conditions for a Recursive Function:
1. Base Case – A condition to stop recursion.
2. Recursive Case – The function must call itself with a smaller/simpler input.
3. Progress toward Base Case – Each recursive call should move closer to the base case to
avoid infinite recursion.
Example:
factorial(n):
if n == 0: return 1
else: return n * factorial(n - 1)
8.what do you mean by LinkedList ?. Explain Different types of Linked List.
Describe the functional Code for inserting and deleting a desired node i'n
singly Linked List
Definition of a Recursive Function:
A recursive function is a function that calls itself to solve a problem. It breaks down a
problem into smaller subproblems of the same type.
Conditions for a Recursive Function:
1. Base Case – A condition to stop recursion.
2. Recursive Case – The function must call itself with a smaller/simpler input.
3. Progress toward Base Case – Each recursive call should move closer to the base case to
avoid infinite recursion.
9.what i's B-tree?. Generate a B-tree of order 5 with the alphabets arrive
i'n the sequence as: a, g, b, k, d, h, m, jie, s, i, r, x, c, d,n,t,u,p
B-Tree?
A B-Tree is a self-balancing search tree used to store large amounts of sorted data.
Each node can have multiple keys and children.
Keeps data sorted and balanced for fast insertion, deletion, and search.
Used in databases and file systems.
B-Tree of Order 5:
Max 4 keys per node.
Min ⌈5/2⌉ = 3 children per internal node (except root).
Insertion Sequence:
a, g, b, k, d, h, m, j, e, s, i, r, x, c, d, n, t, u, p
Final Tree (Simplified):
less
CopyEdit
[d, j, r]
/ | \ \
[a, b, c] [e, g, h, i] [k, m, n, p] [s, t, u, x]
Tree remains balanced after all insertions.
Follows B-tree rules of order 5.
10.Describe Sorting and types. write an algorithm for insertion sort and
quick sort
Sorting is the process of arranging data in a specific order, usually ascending or descending.
Types of Sorting:
1. Bubble Sort – Repeatedly swaps adjacent elements.
2. Selection Sort – Selects the smallest/largest and places it correctly.
3. Insertion Sort – Inserts elements in the correct position one by one.
4. Merge Sort – Divide and conquer method that merges sorted halves.
5. Quick Sort – Divide and conquer using a pivot for partitioning.
11.write Kruskal's and Prim's algorithm and Explain with Example
Steps:
1. Sort all edges in ascending order of weights.
2. Pick the smallest edge.
3. Add it to the MST if it doesn't form a cycle.
4. Repeat until MST has (V - 1) edges.
Prim's Algorithm
Steps:
1. Start from any node.
2. Select the smallest edge from the current tree to a new vertex.
3. Add it to the MST.
4. Repeat until all vertices are included.
12.Explain the following. a) BFS and DFS b) AVL tree C) hash function d)
BST
a) BFS and DFS
BFS (Breadth-First Search):
Traverses a graph level by level using a queue.
Example order: A → B → C → D...
DFS (Depth-First Search):
Explores as deep as possible along each path using a stack or recursion.
Example order: A → B → D → C...
b) AVL Tree
An AVL tree is a self-balancing binary search tree.
Balance factor (left height − right height) is −1, 0, or 1.
Rotations are used to rebalance the tree after insertions or deletions.
c) Hash Function
A hash function maps a key to an index in a hash table.
Used in hashing for fast data retrieval.
Good hash functions minimize collisions.
d) BST (Binary Search Tree)
A Binary Search Tree is a binary tree where:
Left child < root < right child
Allows fast search, insert, delete (average case: O(log n))
