Sem-data-structure-with-python-mcan-201-2023 (1).

pdf
Group-A (Very Short Answer Type Question)

1. Answer any ten of the following : 1×10=101×10=10

i) Question: What is the average time complexity of bubble sort?

Answer: O(n²)

ii) Question: What is direct addressing?

Answer: A technique where each key directly maps to a unique array index, allowing O(1) access
time. Requires keys to be unique and within a bounded range.

iii) Question: What is the best case time complexity of binary search?
Answer: O(1) (occurs when the target element is found at the middle position in the first
comparison)

iv) Question: Write the postfix form of the expression: (A + B) * (C - D)

Answer: AB+CD-*

v) Question: In the worst case, what is the number of comparisons needed to search a singly
linked list of length n for a given element?
Answer: n comparisons (must check every element in the worst case)

vi) Question: If binary trees are represented in arrays, what formula can be used to locate a left
child, if the node has an index i?
Answer: 2i + 1 (for 0-based indexing)

vii) Question: What is the difference between Stack and Queue?

Answer: Stack follows LIFO (Last-In-First-Out) while Queue follows FIFO (First-In-First-Out)
principle

viii) Question: What is the time complexity to insert an element to the front of a LinkedList
(head pointer given)?
Answer: O(1) (constant time for insertion at head)

ix) Question: What is the average case time complexity to delete an element from a binary
search tree?
Answer: O(log n) (for balanced BST)

x) Question: What is the number of edges present in a complete graph having n vertices?
Answer: n(n-1)/2 edges (every vertex connects to all others)

xi) Question: What is priority queue?

Answer: A queue where elements are removed based on priority rather than insertion order
xii) Question: Let P be a singly linked list, Let Q be the pointer to an intermediate node x in the
list. What is the worst-case time complexity of the best known algorithm to delete the node x
from the list?
Answer: O(1) (given pointer to node x, can delete by copying next node's data and bypassing it)

Group-B (Short Answer Type Question)

Answer any three of the following : 5×3=155×3=15

2. What do you mean by the time complexity of an algorithm? [5]

Time complexity is a computational concept used to describe the amount of time an algorithm
takes to complete as a function of the input size (n). It helps in analyzing the efficiency of an
algorithm and compares it with others.

It is generally expressed using asymptotic notations:

 Big-O (O): Worst-case scenario.

 Omega (Ω): Best-case scenario.

 Theta (Θ): Average-case scenario.

Example:

If an algorithm has a time complexity of O(n^2), the time it takes to run increases quadratically
as the input size increases.

3. Write the algorithm for the evaluation of Postfix Expression using Stack. [5]

Algorithm: Postfix Evaluation

1. Create an empty stack.

2. Scan the postfix expression from left to right.

3. For each token in the expression:

a. If the token is an operand, push it onto the stack.
b. If the token is an operator:

o Pop two operands from the stack.

o Apply the operator.

o Push the result back onto the stack.

4. After the expression is fully processed, the top of the stack will contain the final result.
Example:

Postfix: 5 3 + 8 *
Steps:

 Push 5

 Push 3

 + → Pop 3, 5 → (5+3=8) → Push 8

 Push 8

 * → Pop 8, 8 → (8*8=64) → Push 64

Result: 64

(A + B) * C - (D - E) * (F + G ^ H) [5]
4. Convert the following Infix Expression to Postfix using stack:

Step-by-step using stack:

1. Infix: (A + B) * C - (D - E) * (F + G ^ H)

2. Postfix:

 AB+C*DE-FGH^+*-

✅ Postfix Expression: AB+C*DE-FGH^+*-

5. Write a Python program to implement the "Insert at End" and "Delete from End" operation of
a singly Linked List using Class "Node". [5]
5. Discuss Prim's MST algorithm with an example. [5]
 Prim’s Algorithm:

Prim’s Algorithm is a greedy algorithm that finds the Minimum Spanning Tree (MST) of a
weighted, connected graph.

Steps:

1. Start with any vertex.

2. Select the edge with the minimum weight that connects a vertex in the MST to a vertex
outside.

3. Add the selected edge and vertex to the MST.

4. Repeat until all vertices are included.

Example:

Edges with weights:

 A-B = 1

 A-C = 3

 B-C = 2

Prim's MST Steps:

1. Start with A → Include edge A-B (weight = 1)

2. Now in MST: A, B

3. Next minimum edge: B-C (weight = 2)

4. MST Edges: A-B, B-C

Total weight = 1 + 2 = 3

✅ MST = {A-B, B-C}

Group-C (Long Answer Type Question)

Answer any three of the following : 15×3=4515×3=45
7. (a) Write a Python program to implement stack. [8]

(b) Write a Python program to implement queue. [7]

8. (a) What is the difference between linear and non-linear data structure? [5]

Feature Linear Data Structure Non-Linear Data Structure

Structure Arranged sequentially Hierarchical or graph-like

Examples Array, Stack, Queue Tree, Graph

Traversal One level at a time Multiple paths possible

Memory Usage Easy to manage Complex memory requirements

Implementation Simple Complex

(b) Calculate the average time complexity of binary search algorithm. [6]
  Binary Search Time Complexities:

o Best Case: O(1) → Element found at middle.

o Worst Case: O(log n)

o Average Case: O(log n)

✅ Answer: The average time complexity of Binary Search is O(log n), since with each
comparison, the search space is halved.

(c) Write a Python program to implement linear search. [4]

9. (a) What do you mean by data structure? [4]

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

(b) Write a Python program to insert an item in a sorted list in the appropriate position. [5]
(c) Write a Python program to implement binary search for a given list of elements which are
sorted in descending order. [6]

10. (a) Write the algorithm to convert infix to postfix expression with a suitable example. [8]
Algorithm:

1. Initialize an empty stack and postfix list.

2. Scan the infix expression from left to right.

3. If operand → Add to postfix.

4. If ( → Push to stack.

5. If ) → Pop until (.

6. If operator → Pop from stack while it has higher precedence and push the current
operator.

Example:

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

(b) Why and when should we use Stack or Queue data structures instead of Arrays/Lists? [7]

Criteria Stack / Queue Array / List

Usage LIFO/FIFO operations Random access and iteration

Flexibility Better for recursion, parsing, etc. Better for indexed data

Performance Efficient in Less efficient for these

push/pop/enqueue/dequeue

✅ Use Stack for recursion, undo operations, expression evaluation.

✅ Use Queue for scheduling, order management, streaming data.

11. (a) Write a Python program to implement a circular queue. [10]

(b) Explain why Stack is a recursive data structure. [5]

A Stack is called a recursive data structure because function calls in recursion are managed by
a call stack in memory. Each recursive call pushes the current state onto the stack and pops it
upon return. The LIFO nature of stacks makes them ideal for recursive operations like tree
traversals, backtracking, etc.

[Link]
Group-A (Very Short Answer Type Question)

1. Answer any ten of the following : 1×10=101×10=10

(i) What is Hash function?
A hash function is a function that takes an input (or 'key') and returns a fixed-size numerical
value (hash value) used for efficient data retrieval in hash tables. It maps data of arbitrary size to
fixed-size values.

(ii) Define ADT (Abstract Data Type).

An Abstract Data Type (ADT) is a mathematical model for data types that defines a set of
operations on the data and their behavior without specifying implementation details. Examples
include Stack, Queue, and List.

(iii) FRONT = REAR + 1 is the Overflow condition of ______ queue.

Circular queue.

(iv) What is Node?

A node is a fundamental unit in data structures (e.g., linked lists, trees) that contains data and a
reference (or pointer) to the next node or other related nodes.

(v) What is a sibling node?

In a tree data structure, sibling nodes are nodes that share the same parent node.

(vi) What is directed graph?

A directed graph (digraph) is a graph where edges have a direction, meaning they go from one
vertex to another and are not bidirectional unless specified.

(vii) What is the worst-case time complexity of quick sort?

O(n²), when the pivot selection leads to highly unbalanced partitions.

(viii) If several elements are competing for the same bucket in the hash table, it is called
______.
Collision.

(ix) What is the time complexity of an algorithm?

Time complexity measures the amount of time an algorithm takes to run as a function of the
input size, expressed using asymptotic notations like O, Ω, or Θ.

(x) The initial configuration of a queue is a, b, c, d (‘a’ is in the front end). To get the
configuration d, c, b, a, how many deletions and additions required?
  Deletions: 4 (remove all elements: a, b, c, d).

 Additions: 4 (reinsert in reverse order: d, c, b, a).

Total operations: 8 (4 deletions + 4 additions).

(xi) Write the information stored in a doubly-linked list’s nodes.

Each node in a doubly-linked list stores:

1. Data (value).

2. Pointer to the next node (next).

3. Pointer to the previous node (prev).

(xii) What is skewed binary search tree?

A skewed binary search tree is an unbalanced BST where all nodes are either entirely left-
skewed (every node has only a left child) or right-skewed (every node has only a right child),
degrading performance to O(n).

Group-B (Short Answer Type Question)

Answer any three of the following : 5×3=155×3=15

2. Write an algorithm of bubble sort. [5]

Bubble Sort Algorithm

Bubble Sort is a simple comparison-based sorting algorithm that repeatedly steps through the
list, compares adjacent elements, and swaps them if they are in the wrong order. The process is
repeated until the list is sorted.

Algorithm Steps:

1. Start with an unsorted list of n elements.

2. Compare each pair of adjacent elements from the start of the list.

3. If the elements are in the wrong order (e.g., ascending order for a min-heap), swap
them.

4. Repeat the process for each element until the end of the list.

5. After each pass, the largest unsorted element "bubbles up" to its correct position at the
end of the list.

6. Reduce the range of the list by one (since the last element is now sorted) and repeat the
process until no more swaps are needed.
Python Implementation:

Time Complexity:

 Worst/Average Case: O(n²) (quadratic time).

 Best Case: O(n) (when the list is already sorted).

3. Define a min_priority queue. Define its two functions: insert and decrease_key. [5]

Min-Priority Queue
A min-priority queue is an abstract data type (ADT) that stores elements with associated
priorities and allows retrieval of the element with the minimum priority first. It is commonly
implemented using a min-heap.

Key Functions:

1. Insert(key, value):

o Adds a new element to the priority queue while maintaining the min-heap
property.

o Steps:

1. Append the new element to the end of the heap.

2. "Bubble up" the element to its correct position by comparing it with its
parent and swapping if necessary.

Python Implementation:
 2. Decrease_key(index, new_key):

o Decreases the priority of an element at index to new_key and restores the min-
heap property.

o Steps:

1. Update the element's priority to the new (smaller) value.

2. "Bubble up" the element to its correct position if its new priority is
smaller than its parent's.

Python Implementation:

4. Explain Stack as an ADT. [5]

Stack (Abstract Data Type)

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

Core Operations:

1. push(x): Inserts element x at the top of the stack.

2. pop(): Removes and returns the top element of the stack.

3. peek(): Returns the top element without removing it.

4. isEmpty(): Checks if the stack is empty.

5. size(): Returns the number of elements in the stack.

Example (Python List Implementation):

Applications:

 Function call management (call stack).

 Undo mechanisms in text editors.

 Expression evaluation (e.g., postfix notation).

5. Write the Depth First Search algorithm for a given graph G(V, E). [5]

Depth First Search (DFS) Algorithm

DFS is a graph traversal algorithm that explores as far as possible along each branch before
backtracking. It uses a stack (implicitly via recursion) to keep track of vertices.

Algorithm Steps:

1. Start at a source vertex s.

2. Mark s as visited.

3. For each unvisited neighbor v of s:

o Recursively apply DFS to v.

Python Implementation:

Example Usage:
Time Complexity: O(V + E) for adjacency list representation.

6. Write a function to insert a node at the beginning of an existing double linked list. [5]

Doubly Linked List Insertion at Beginning

A doubly linked list node contains:

 data: The value stored.

 prev: Pointer to the previous node.

 next: Pointer to the next node.

Function Steps:

1. Create a new node with the given data.

2. If the list is empty (head is None), return the new node as the head.

3. Otherwise:

o Set the new node’s next to the current head.

o Set the current head’s prev to the new node.

o Update head to point to the new node.

Python Implementation:
Example Usage:

Group-C (Long Answer Type Question)

Answer any three of the following : 15×3=4515×3=45

7. (a) Write the algorithm of binary search. [6]

Answer:

Binary Search Algorithm Binary Search is used to search an element in a sorted array.

7. (b) Explain asymptotic notations O (Big Oh), Ω (Big Omega), and Θ (Big Theta) with graph.
[9]

Answer:

1. Big O Notation (O):

 Describes the upper bound of time complexity.

 It tells us the worst-case time an algorithm will take.

 Example: If T(n) = 3n² + 2n + 1, then T(n) = O(n²)

2. Big Omega Notation (Ω):

 Describes the lower bound of time complexity.

 It represents the best-case performance.

 Example: If T(n) ≥ cn for large n, then T(n) = Ω(n)

3. Big Theta Notation (Θ):

 Describes the tight bound – both upper and lower.

 It represents the average-case or exact growth.

  Example: T(n) = Θ(n²) means it grows exactly like n²

Graphical Representation:

8. (a) Write the steps to change the infix expression (7 + 3) * 5 to postfix notation using stack.
Also evaluate the postfix expression using stack. [6 + 4]

Answer:

Steps to Convert (7 + 3) * 5 to Postfix:

1. Read '(' → push to stack

2. Read '7' → output

3. Read '+' → push

4. Read '3' → output

5. Read ')'→ pop and output till '(' → output '+'

6. Read '*' → push

7. Read '5' → output

8. End of expression → pop remaining operators

**Postfix expression: **``

**Evaluate Postfix (7 3 + 5 *):

1. Stack: push 7

2. Stack: push 3
 3. Pop 3 and 7 → 7 + 3 = 10 → push 10

4. Push 5

5. Pop 5 and 10 → 10 * 5 = 50 → push 50

Final Result = 50

8. (b) Write the algorithm to insert an element at the end of a circular queue. [3] Also write an
algorithm to delete an element from the beginning of a circular queue. [2]

Answer:

Insertion in Circular Queue:

Deletion in Circular Queue:

9. Write a program to insert a node at any position of an existing double linked list. Your
function should run correctly when you are inserting at the first and the last position of the
list and when you are inserting an element when the list is empty. [2 + 4]

Answer (Python-like Pseudocode):

10. (a) Define a Max Heap. Write an algorithm to build a Max Heap. [9]

Answer:

Max Heap: A binary tree where:

1. It is complete (every level is filled left to right).

2. Every parent node is greater than or equal to its child nodes.

Build Max Heap Algorithm:

10. (b) Create a Max Heap from the following sequence of nodes:
80, 20, 90, 40, 100, 60, 120, 60, 50, 70 [3]

Answer:

Start inserting elements one by one and maintain the Max Heap property (each parent must be
≥ its children):

Initial Insertion Sequence:

[80, 20, 90, 40, 100, 60, 120, 60, 50, 70]

Use bottom-up heapify (starting from the last non-leaf node up to the root).

Final Max Heap (Level Order):

[120, 100, 90, 60, 70, 60, 80, 20, 50, 40]

Tree Representation of the Max Heap:

  Complete Binary Tree ✅

 Parent ≥ Children ✅

This is the correct Max Heap created from the given sequence.

11. (a) What is reverse polish notation? [12]

Answer:

Reverse Polish Notation (RPN):

 A way to write arithmetic expressions without parentheses.

 Also called postfix notation.

 Operators come after their operands.

 Example: Infix (A + B) * C → Postfix A B + C *

Advantages:

 No need for operator precedence or brackets.

 Easier and faster for computers to evaluate using stack.

11. (b) Suppose you need to match the opening and closing brackets of a given expression.
Write a program using stack data structure.
Answer (Python):