DS 2 Marks

2Marks

1. Define Recursion.

Recursion is a process in which a function calls itself directly or indirectly to solve a smaller version of the same problem until it reaches a base case. It is commonly used for tasks like calculating factorials or Fibonacci sequences.

2. List advantages of using linked lists over arrays.

• Dynamic Size: Linked lists can grow or shrink in size during execution, unlike fixed-size arrays.
• Efficient Insertion/Deletion: Adding or removing elements does not require shifting all subsequent elements.
• No Memory Wastage: Memory is allocated only when a new node is added.

3. Write a note on Polish notation.

Polish notation, also known as Prefix notation, is a way of writing mathematical expressions where operators precede their operands (e.g., +AB instead of A+B). It eliminates the need for parentheses and operator precedence rules during evaluation using a stack.

4. Illustrate the representation of a queue using an array.

A queue is represented using a linear array with two pointers: Front (for deletion) and Rear (for insertion).

• Initial state: Front = -1, Rear = -1.
• Insertion: Rear increments as elements are added.
• Deletion: Front increments as elements are removed.

5. Define a binary tree.

A binary tree is a non-linear data structure where each node can have at most two children, referred to as the left child and the right child. The top-most node is called the root.

6. List the different types of tree traversals.

The three main types of tree traversals are:

• Inorder: Left child → Root → Right child.
• Preorder: Root → Left child → Right child.
• Postorder: Left child → Right child → Root.

7. State the time complexity of quick sort.

Quick sort typically uses a divide-and-conquer approach:

• Best/Average Case: O(n \log n).
• Worst Case: O(n^2) (occurs when the pivot is the smallest or largest element).

8. Differentiate between BFS and DFS.

• BFS (Breadth First Search): Explores neighbor nodes first using a Queue data structure.
• DFS (Depth First Search): Explores as far as possible along each branch before backtracking using a Stack.

9. Define a graph and mention its types.

A graph is a non-linear data structure consisting of a finite set of vertices (nodes) and edges that connect them.

• Types: Directed Graphs (edges have direction) and Undirected Graphs (edges have no direction).

10. Give the adjacency matrix representation of a graph.

An adjacency matrix is a 2D array of size V \times V (where V is the number of vertices) where a cell adj[i][j] contains 1 if there is an edge between vertex i and j, and 0 otherwise.

11. Define Abstract Data Type (ADT) with example.

An ADT is a mathematical model for a certain class of data structures that defines the data and operations without specifying the implementation details.

• Example: A Stack is an ADT with operations like push() and pop().

12. Differentiate linear and non-linear data structures.

• Linear: Elements are arranged in a sequential order (e.g., Arrays, Stacks, Queues, Linked Lists).
• Non-Linear: Elements are arranged in a hierarchical or interconnected way (e.g., Trees, Graphs).

13. Define stack. Write any two stack operations.

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

• Operations: push() (adds an element to the top) and pop() (removes the top element).

14. Convert the infix expression A+B*C into postfix.

Following operator precedence (multiplication before addition):

• Postfix: ABC*+

15. Define Binary Search Tree (BST).

A BST is a binary tree where the left subtree contains only nodes with values less than the parent, and the right subtree contains only nodes with values greater than the parent.

16. Write the inorder traversal of a BST.

Inorder traversal of a Binary Search Tree always yields the nodes in ascending (sorted) order.

• Pattern: Visit Left Subtree → Visit Root → Visit Right Subtree.

17. Differentiate Hashing and Collision.

• Hashing: The process of mapping a large range of data into a smaller range of indices in a hash table using a hash function.
• Collision: Occurs when two different keys produce the same hash value (index).

18. State the time complexity of Merge sort.

Merge sort is a stable, divide-and-conquer algorithm with a consistent time complexity:

• All cases (Best, Average, Worst): O(n \log n).

19. Define graph and degree of a vertex.

• Graph: A collection of nodes (vertices) and lines (edges) connecting them.
• Degree of a vertex: The total number of edges connected to that specific vertex in a graph.

20. Define Dijkstra’s algorithm.

Dijkstra’s algorithm is a greedy algorithm used to find the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights.