CIA 1

PART A (10 x 2 = 20 Marks)

Answer any TEN questions

1. List out the types of Linked List.

2. How do you declare an Array?

3. Write the Operations performed on the Stack

4. Any two Applications of Array.

5. What is Circular Linked List?

6. What is node?

7. Define PEEK

8. What is Underflow?

9. Define Binary Tree.

10. List out the Types of traversal in Binary Tree.

11. Define the term ENQUEUE & DEQUEUE.

12. What is root node?

PART B-(5 x 5 = 25 Marks) Answer any FIVE questions

13. Differentiate between Linear and Non-Linear Data structure.

14. List out any 5 Applications of Data Structure.

15. Write short notes on Doubly Linked List.

16. How to Insert and Delete an Element in the Circular Linked List.

17. Briefly discuss about tree Traversal.

18. List out Any 5 Application of Queue.

19. Write about Representation of Trees.

PART C- (3 x 10 = 30 Marks) Answer ANY THREE questions

20. Explain in detail about Singly Linked List.

21. Discuss in detail about the Stack & its Operation.

22. Explain about Conversion from Infix to Postfix Expression.

23. Discuss in detail about the Queue & its Operation.

24. Write in detail about the Representation of Binary Tree.

ANSWERS:

1. Types of Linked List

● Singly Linked List

 ● Doubly Linked List
● Circular Linked List
● Doubly Circular Linked List

2. How do you declare an Array?

data_type array_name[size];

Example:

int arr[10];

3. Operations performed on the Stack

● Push: Add an element to the top of the stack.

● Pop: Remove an element from the top of the stack.
● Peek/Top: Retrieve the top element without removing it.
● IsEmpty: Check if the stack is empty.
● IsFull: Check if the stack is full.

4. Applications of Array

● Used for storing and manipulating data in sorting and searching algorithms.
● Used to implement data structures like stacks, queues, and hash tables.

5. What is Circular Linked List?

A Circular Linked List is a linked list where the last node is connected back to the first node,
forming a circle. This can be implemented for both singly and doubly linked lists.

6. What is a Node?

A node is a fundamental unit of a data structure (like a linked list or tree) that contains:

● Data: The value stored in the node.

● Pointer: A reference to the next node (or previous node in a doubly linked list).
7. Define PEEK

PEEK is an operation in a stack that retrieves the top element without removing it from the
stack.

8. What is Underflow?

Underflow occurs when an attempt is made to remove an element from an empty data
structure (e.g., popping from an empty stack).

9. Define Binary Tree

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

10. Types of Traversal in Binary Tree

● Inorder Traversal (Left → Root → Right)

● Preorder Traversal (Root → Left → Right)
● Postorder Traversal (Left → Right → Root)
● Level-order Traversal (Breadth-first)

11. Define the term ENQUEUE & DEQUEUE

● ENQUEUE: Adding an element to the rear of the queue.

● DEQUEUE: Removing an element from the front of the queue.

12. What is a Root Node?

The root node is the topmost node in a tree data structure from which all other nodes
descend. It has no parent.

13. Differentiate between Linear and Non-Linear Data Structure

 Aspect Linear Data Structure Non-Linear Data Structure

Structure Data elements are arranged Data elements are arranged

sequentially. hierarchically.

Examples Array, Stack, Queue, Linked List Tree, Graph

Traversal Traversed in a single run (start to Traversal can involve multiple

end). paths.

Complexity Simpler to implement and understand. More complex due to hierarchical

nature.

Relationship Each element has a single Elements can have multiple

s predecessor and successor (except predecessors or successors.
ends).

14. Applications of Data Structure

1. Implementing databases.
2. Handling large datasets in machine learning algorithms.
3. Storing and organizing web browser history.
4. Optimizing routing in network systems.
5. Managing memory in operating systems.

15. Short Notes on Doubly Linked List

A Doubly Linked List is a type of linked list where each node contains:

● Data: The value of the node.

● Pointer to Next Node: Link to the next node in the sequence.
● Pointer to Previous Node: Link to the previous node in the sequence.

Advantages:

● Can be traversed in both forward and backward directions.

● Easier to delete nodes compared to singly linked lists.
16. Insert and Delete an Element in a Circular Linked List

Insertion:

1. At the Beginning:

○ Create a new node.

○ Point the new node’s next to the head.
○ Traverse to the last node and update its next to the new node.
○ Update the head to the new node.
2. At the End:

○ Create a new node.

○ Traverse to the last node.
○ Update the last node’s next to the new node.
○ Set the new node’s next to the head.

Deletion:

1. At the Beginning:

○ Traverse to the last node.

○ Update the last node’s next to the head’s next.
○ Update the head to the next node.
2. At the End:

○ Traverse to the second last node.

○ Update its next to the head.

17. Tree Traversal

Tree traversal is the process of visiting all nodes in a tree in a specific order. The main types
of traversal are:

1. Inorder (Left → Root → Right): Used in binary search trees for sorted output.
 2. Preorder (Root → Left → Right): Used for creating copies of trees.
3. Postorder (Left → Right → Root): Used in deleting a tree.
4. Level Order (Breadth-first): Visits nodes level by level, starting from the root.

18. Applications of Queue

1. Managing tasks in an operating system (e.g., CPU scheduling).

2. Handling requests in web servers (e.g., printing jobs).
3. Implementing BFS in graph traversal.
4. Traffic management systems (e.g., cars in toll booths).
5. Message queues in communication systems.

19. Representation of Trees (5 Marks)

Trees can be represented in the following ways:

1. Linked Representation:

○ Each node contains:

■ Data.
■ Pointer to the left child.
■ Pointer to the right child.

Example:
struct Node {
int data;
struct Node* left;
struct Node* right;
};

○
2. Array Representation:

○ For a node at index i:

■ Left child is at 2i + 1.
 ■ Right child is at 2i + 2.
○ The root node is at index 0.
○ Suitable for complete binary trees.
3. Adjacency List Representation (For general trees):

○Represented as a list of lists, where each list corresponds to a node and its
children.
4. Parent Array Representation:

○ Each element in the array represents the parent of the corresponding node.

These representations help in implementing and visualizing trees effectively.

20. Singly Linked List

A Singly Linked List is a linear data structure where each element (node) is connected to
the next by a pointer. It consists of nodes, and each node has two parts:

1. Data: Stores the value of the node.

2. Pointer (Next): Stores the address of the next node in the list.

Features:

● Dynamic Size: Can grow or shrink at runtime.

● Efficient Memory Use: Allocates memory as needed, unlike arrays.

Operations:

1. Insertion:

○ At the beginning: Update the new node's pointer to point to the head, then
update the head to the new node.
○ At the end: Traverse to the last node, update its pointer to the new node.
○ At a specific position: Adjust the pointers of adjacent nodes to insert the new
node.
 2. Deletion:

○ At the beginning: Update the head to point to the second node.

○ At the end: Traverse to the second last node, update its pointer to NULL.
○ At a specific position: Adjust the pointers to skip the node to be deleted.
3. Traversal:
Start from the head and follow the pointers to visit each node until NULL is
encountered.

Advantages:

● Efficient for insertion and deletion at the beginning.

● No need to define size in advance.

Disadvantages:

● Sequential access only (no direct access like arrays).

● Extra memory for storing pointers.

21. Stack & its Operations

A Stack is a linear data structure that follows the LIFO (Last In, First Out) principle. The
last element added is the first one to be removed.

Representation:

● Array-Based Implementation: Uses an array to store elements and a variable (top)

to track the index of the top element.
● Linked List Implementation: Uses a linked list where the top of the stack is the
head of the list.

Operations:
Push: Adds an element to the top of the stack.
Example:

stack[++top] = element;
 1.

Pop: Removes the top element of the stack.

Example:

element = stack[top--];

2.
3. Peek/Top: Retrieves the top element without removing it.

4. IsEmpty: Checks if the stack is empty.

5. IsFull: Checks if the stack has reached its capacity.

Applications:

● Expression evaluation and conversion (e.g., infix to postfix).

● Backtracking algorithms (e.g., maze solving).
● Function call management in recursion.

22. Conversion from Infix to Postfix Expression

Steps:

1. Initialize:

○ Create an empty stack for operators.

○ Create an output list for the postfix expression.
2. Scan the Infix Expression:

○ Operand: Directly add to the output list.

○ Operator:
■ If the stack is empty, push it.
■ Else, pop operators from the stack to the output until the stack is
empty or a lower precedence operator is found. Then, push the
current operator.
 ○ Left Parenthesis ((): Push to the stack.
○ Right Parenthesis ()): Pop and add to the output until a left parenthesis is
encountered. Discard the left parenthesis.
3. After Scanning:
Pop any remaining operators from the stack to the output.

Example:

Infix: (A + B) * C
Postfix: A B + C *

Applications:

● Evaluating mathematical expressions.

● Parsing expressions in compilers.

23. Queue & its Operations

A Queue is a linear data structure that follows the FIFO (First In, First Out) principle. The
first element added is the first one to be removed.

Representation:

● Array-Based Implementation: Fixed size; uses two pointers (front and rear).
● Linked List Implementation: Dynamic size; uses nodes with pointers for front and
rear.

Operations:
Enqueue: Adds an element to the rear of the queue.
Example:

queue[rear++] = element;

1.
Dequeue: Removes an element from the front of the queue.
Example:

element = queue[front++];

2.
3. IsEmpty: Checks if the queue is empty.

4. IsFull: Checks if the queue is full (in the case of an array implementation).

Types:

● Circular Queue: Rear connects to the front when the end is reached.
● Priority Queue: Elements are dequeued based on priority.
● Double-Ended Queue (Deque): Insertions and deletions can occur at both ends.

Applications:

● Task scheduling in operating systems.

● Breadth-First Search (BFS) in graphs.
● Call handling in customer support.

24. Representation of Binary Tree

A Binary Tree is a hierarchical data structure where each node has at most two children.

1. Array Representation:

● Each node is assigned an index in an array.

● For a node at index i:
○ Left child is at 2i + 1.
○ Right child is at 2i + 2.
● Root is at index 0.
Example:
For the tree:
 A
/\
B C

Array: [A, B, C]

2. Linked Representation:

● Each node has:

○ Data.
○ Pointer to the left child.
○ Pointer to the right child.
Example (in C):

struct Node {
int data;
struct Node* left;
struct Node* right;
};

3. Parent Array Representation:

● An array where each element represents the parent of the corresponding node.
Example:
For the tree:

A
/\
B C

Parent Array: [-1, 0, 0] (-1 indicates the root).

Applications:

● Used in binary search trees for efficient searching.

● Implementing heaps for priority queues.
● Representing hierarchical structures like file systems.
CIA 2

1. What is Sparse Matrix?

2. Define Data Structure.

3. What is circular linked List.

4. Write the basic purpose of header in the linked list.

5. Define Binary tree?

6. What is Tree Traversal?

7. Define the term Node.

8. What is a balance factor in AVL Tree?

9. What is directed graph?

10. Write down the basic operations of graph

11. What do you mean by kruskal's algorithm.

12. Write about Breath first search.

PART B-(5 x 5 = 25 Marks)

Answer any FIVE questions

13. Write short notes on types on types of arrays in dataStructures.

14. Explain the steps involved in conversion of infix to postfix.

15. Write about circular linked list.

16. Explain about representation of Queue.

17. Discuss in detail about types of graphs.

18. Write short notes on Graph traversal techniques.

19. Discuss about levels of Graph.

PART C (3 x 10 = 30 Marks)

Answer ANY THREE questions

20. Write in detail about Applications of Data Structures.

21. Explain stack & its Operations in detail

22. Explain in detail tree traversal techniques.

23. Discuss in detail on AVL Tree?

24. Write in detail about Dijikstra's Algorithm.

ANSWERS:

1. What is Sparse Matrix?

A sparse matrix is a matrix in which most of the elements are zero. It is typically stored
using efficient data structures to save space, such as arrays or linked lists for non-zero
elements.
2. Define Data Structure.

A data structure is a way of organizing and storing data in a computer so that it can be
accessed and used efficiently. Examples include arrays, linked lists, stacks, queues, trees,
and graphs.

3. What is Circular Linked List?

A circular linked list is a type of linked list where the last node points back to the first node,
forming a circle. It can be singly or doubly linked.

4. Write the basic purpose of the header in the linked list.

The header in a linked list is a special node at the beginning of the list. It often contains
metadata like the size of the list or serves as a starting point for traversal.

5. Define Binary Tree.

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

6. What is Tree Traversal?

Tree traversal is the process of visiting all the nodes in a tree in a specific order. The main
types are:

● Inorder (Left → Root → Right)

● Preorder (Root → Left → Right)
● Postorder (Left → Right → Root)
● Level-order (Breadth-first)
7. Define the term Node.

A node is a fundamental unit of a data structure, such as a tree or linked list. It contains:

● Data: The value stored in the node.

● Pointers/Links: References to other nodes.

8. What is a balance factor in AVL Tree?

The balance factor of a node in an AVL tree is the difference between the heights of its left
and right subtrees.
Balance Factor=Height of Left Subtree−Height of Right Subtree\text{Balance Factor} =
\text{Height of Left Subtree} - \text{Height of Right Subtree}
It ensures that the tree remains balanced.

9. What is Directed Graph?

A directed graph (digraph) is a graph where each edge has a direction, going from one
vertex to another. Edges are represented as ordered pairs of vertices.

10. Write down the basic operations of graph.

1. Add Vertex: Add a node to the graph.

2. Add Edge: Connect two vertices with an edge.
3. Remove Vertex: Delete a node and its associated edges.
4. Remove Edge: Delete a connection between two vertices.
5. Traversal: Visit nodes using algorithms like BFS or DFS.

11. What do you mean by Kruskal's Algorithm?

Kruskal's Algorithm is a greedy algorithm used to find the minimum spanning tree (MST) of
a graph. It works by:

1. Sorting all edges by weight.

2. Adding the smallest edge to the MST, ensuring no cycles are formed.
3. Repeating until all vertices are included in the MST.

12. Write about Breadth First Search (BFS).

Breadth First Search (BFS) is a graph traversal algorithm that explores all neighbors of a
node before moving to the next level.

● Uses a queue to keep track of nodes to visit.

● Useful for finding the shortest path in an unweighted graph.

13. Short Notes on Types of Arrays in Data Structures

1. One-Dimensional Array:

○ A linear arrangement of elements stored in contiguous memory locations.

○ Accessed using a single index.
○ Example: arr[5].
2. Two-Dimensional Array:

○ Represents a table or matrix with rows and columns.

○ Accessed using two indices.
○ Example: arr[3][4].
3. Multi-Dimensional Array:

○ An extension of two-dimensional arrays for higher dimensions.

○ Example: arr[3][4][2].
 4. Dynamic Array:

○ Can change size during runtime.

○ Example: Implemented using data structures like vector in C++.
5. Jagged Array:

○ An array where rows can have a variable number of columns.

14. Steps in Conversion of Infix to Postfix

1. Initialize an empty stack for operators and an empty string for the output.
2. Scan the infix expression from left to right.
3. For each character:
○ If it’s an operand, add it to the output string.
○ If it’s an operator:
■ Pop operators from the stack to the output until the stack is empty or
an operator of lower precedence is found.
■ Push the current operator onto the stack.
○ If it’s a left parenthesis, push it onto the stack.
○ If it’s a right parenthesis, pop and add to the output until a left parenthesis is
encountered, then discard the parenthesis.
4. After scanning, pop all remaining operators from the stack to the output.

15. Circular Linked List

A Circular Linked List is a type of linked list where:

● The last node points back to the first node, forming a loop.
● It can be either singly or doubly linked.

Advantages:

1. Traversal can continue indefinitely without reaching NULL.

2. Efficient for applications requiring a circular structure, such as round-robin
scheduling.
Operations:

1. Insertion: Adjust pointers of the last and new nodes to maintain the circular nature.
2. Deletion: Adjust pointers to bypass the deleted node.

16. Representation of Queue

1. Array Representation:

○ Uses a fixed-size array.

○ Two indices: front (to remove elements) and rear (to add elements).
○ Limitation: Wastage of space when elements are dequeued unless
implemented as a circular queue.
2. Linked List Representation:

○ Dynamic size.
○ Each node contains:
■ Data.
■ A pointer to the next node.
○ Front and Rear pointers are used to track the first and last nodes.
3. Circular Queue Representation:

○ An array implementation where rear wraps around to the beginning when

the end is reached.
○ Prevents wastage of space.

17. Types of Graphs

1. Undirected Graph:

○ Edges have no direction.

○ Example: (A-B) means two-way connectivity between A and B.
2. Directed Graph (Digraph):
 ○ Edges have a specific direction.
○ Example: (A → B) means one-way connectivity from A to B.
3. Weighted Graph:

○ Edges have weights or costs.

○ Example: (A-B: 5) indicates a weight of 5.
4. Unweighted Graph:

○ Edges have no weights.

5. Cyclic Graph:

○ Contains at least one cycle (a closed path).

6. Acyclic Graph:

○ Contains no cycles.
7. Connected Graph:

○ All vertices are reachable from each other.

8. Disconnected Graph:

○ Some vertices are not reachable from others.

18. Short Notes on Graph Traversal Techniques

1. Depth First Search (DFS):

○ Explores as far as possible along a branch before backtracking.

○ Uses a stack (implicit or explicit).
○ Example: Navigating a maze.
2. Breadth First Search (BFS):

○ Explores all neighbors of a node before moving to the next level.

○ Uses a queue.
○ Example: Finding the shortest path in an unweighted graph.

Applications:
 ● BFS: Used in shortest path algorithms.
● DFS: Used in cycle detection and topological sorting.

19. Levels of Graph

In graph theory, levels often refer to the distance from a starting node during traversal,
especially in BFS:

1. Level 0: Contains the starting node.

2. Level 1: Contains nodes directly connected to the starting node.
3. Level 2: Contains nodes connected to nodes in Level 1, and so on.

Example:

For BFS traversal of a graph starting at A:

● Level 0: A.
● Level 1: Neighbors of A.
● Level 2: Neighbors of Level 1 nodes.

Levels are critical in algorithms like BFS and shortest path finding in unweighted graphs.

20. Applications of Data Structures

Data structures are essential in various fields of computer science and software
development. Here are some key applications:

1. Arrays:

○ Used in matrix operations, image processing, and as building blocks for more
complex data structures like heaps and hash tables.
○ Examples: Storing game boards, database records.
 2. Linked Lists:

○ Used in dynamic memory allocation, implementation of stacks, queues, and

adjacency lists for graphs.
○ Examples: Music playlists, undo operations in text editors.
3. Stacks:

○Used in expression evaluation, backtracking algorithms, and recursive

function management.
○ Examples: Syntax parsing, browser history.
4. Queues:

○ Used in scheduling algorithms, managing requests in printers, and BFS in

graphs.
○ Examples: CPU task scheduling, customer service systems.
5. Trees:

○ Used in hierarchical data representation, search operations, and expression

parsing.
○ Examples: File systems, XML/JSON parsing, decision trees.
6. Graphs:

○ Used in modeling networks (social, transport), shortest path algorithms, and

dependency resolution.
○ Examples: Google Maps, LinkedIn connections.
7. Hash Tables:

○ Used for fast data retrieval.

○ Examples: Caches, dictionaries, database indexing.
8. Heaps:

○ Used in priority queue implementations, graph algorithms, and memory

management.
○ Examples: Heap sort, task scheduling.

21. Stack & its Operations

A stack is a linear data structure that follows the LIFO (Last In, First Out) principle.

Characteristics:

1. Insertions and deletions occur only at one end called the top.
2. Useful for tasks where data must be reversed or backtracked.

Operations:

1. Push: Adds an element to the top of the stack.

○ Example: Inserting an operand into an expression stack.

stack[++top] = value;

2.
3. Pop: Removes the top element from the stack.

○ Example: Evaluating a postfix expression.

value = stack[top--];

4.
5. Peek/Top: Retrieves the top element without removing it.

6. IsEmpty: Checks if the stack is empty.

7. IsFull: Checks if the stack is full (array implementation).

Applications:

● Parenthesis matching in expressions.

● Backtracking (e.g., solving a maze).
● Converting infix to postfix expressions.

22. Tree Traversal Techniques

Tree traversal refers to visiting all the nodes of a tree in a specific order.

Types:

1. Inorder Traversal (Left → Root → Right):

○First visits the left subtree, then the root, followed by the right subtree.
○Example: Binary Search Trees (BSTs) produce sorted order.
○Steps:
1. Traverse the left subtree.
2. Visit the root node.
3. Traverse the right subtree.
2. Preorder Traversal (Root → Left → Right):

○Visits the root first, followed by left and right subtrees.

○Example: Used in expression trees to represent prefix notation.
○Steps:
1. Visit the root node.
2. Traverse the left subtree.
3. Traverse the right subtree.
3. Postorder Traversal (Left → Right → Root):

○Visits the left and right subtrees before the root.

○Example: Used in expression trees for postfix notation.
○Steps:
1. Traverse the left subtree.
2. Traverse the right subtree.
3. Visit the root node.
4. Level-Order Traversal:

○ Visits nodes level by level from top to bottom.

○ Example: BFS algorithm for trees.

Applications:

● Inorder: Sorting.
● Preorder: Generating trees.
● Postorder: Deleting trees.
23. AVL Tree

An AVL Tree is a self-balancing binary search tree where the difference in height between
the left and right subtrees (balance factor) is at most 1 for all nodes.

Characteristics:

1. Balance Factor: Difference between heights of left and right subtrees.

Balance Factor=Height(left)−Height(right)\text{Balance Factor} = \text{Height(left)} -
\text{Height(right)}
2. Rotations are used to maintain balance:
○ Single Rotations: Left-Left (LL), Right-Right (RR).
○ Double Rotations: Left-Right (LR), Right-Left (RL).

Operations:

1. Insertion:

○ Insert the node as in a normal BST.

○ Recalculate balance factors and perform necessary rotations to maintain
balance.
2. Deletion:

○ Delete the node as in a BST.

○ Recalculate balance factors and rotate if required.

Applications:

● Databases for quick lookups.

● Memory indexing in operating systems.

24. Dijkstra's Algorithm

Dijkstra's Algorithm is used to find the shortest path from a source node to all other nodes
in a weighted graph.
Steps:

1. Initialize:

○ Set the distance to the source node as 0 and all other nodes to infinity.
○ Mark all nodes as unvisited.
2. Select Node:

○ Choose the unvisited node with the smallest distance.

3. Update Neighbors:

○
For each neighbor of the current node, calculate the tentative distance:
Tentative Distance=Current Distance+Edge Weight\text{Tentative Distance} =
\text{Current Distance} + \text{Edge Weight}
○ If the tentative distance is smaller, update it.
4. Mark as Visited:

○ Once all neighbors are processed, mark the current node as visited.
5. Repeat:

○ Continue until all nodes are visited or the shortest paths are found.

Example:

For a graph:
A→B(1),B→C(2),A→C(4)A → B (1), B → C (2), A → C (4)

● From A, the shortest path to C is A → B → C.

Applications:

● Routing algorithms in networks.

● GPS navigation systems.
● Shortest path problems in AI.