FYUG Even Semester Exam, 2025
Computer Science: Data Structure
UNIT-I
1. (a) Why is sparse matrix used? [2 Marks]
A Sparse Matrix is a matrix in which most of the elements are zero. It is used primarily for two reasons:
- Storage Efficiency: Instead of storing all elements (including zeros), we only store non-zero elements along with their row and column indices. This saves a significant amount of memory.
- Computational Efficiency: Processing only non-zero elements reduces the time complexity of matrix operations like addition and multiplication.
1. (b) What are overflow and underflow? [2 Marks]
Overflow: Occurs when an attempt is made to insert an element into a data structure (like a Stack or Queue) that is already full.
Underflow: Occurs when an attempt is made to delete or access an element from a data structure that is currently empty.
1. (c) What are the advantages of recursion? [2 Marks]
- Code Conciseness: Recursion reduces the length of the code and makes it easier to read and maintain for problems that have a naturally recursive structure (e.g., Tree traversals).
- Problem Solving: It simplifies the implementation of complex algorithms like Tower of Hanoi, Quick Sort, and Merge Sort.
2. (a) (i) Write an algorithm to delete an element from an array. [4 Marks]
Algorithm: Delete_Element(A, N, POS)
Here, A is the linear array, N is the number of elements, and POS is the position of the element to be deleted.
- Start.
- Set ITEM = A[POS].
- Repeat for I = POS to N - 1:
- Set N = N - 1 (Decrement the size).
- End.
2. (a) (ii) How do you declare a single-dimensional array? [2 Marks]
In C/C++, a single-dimensional array is declared by specifying the data type, the name of the array, and the size in square brackets.
Syntax: data_type array_name[size];
Example: int marks[50]; (This declares an integer array named 'marks' that can hold 50 elements).
2. (b) Convert the infix expression into postfix: 8+(((7-5)*9(9-4)+6)/4) [10 Marks]
Note: Assuming the expression is 8+(((7-5)*9/(9-4)+6)/4) as the '9(9-4)' syntax likely implies multiplication or division in standard CS problems.
| Token |
Stack |
Postfix Expression |
| 8 | (empty) | 8 |
| + | + | 8 |
| ( | +( | 8 |
| ( | +(( | 8 |
| ( | +((( | 8 |
| 7 | +((( | 8 7 |
| - | +(((- | 8 7 |
| 5 | +(((- | 8 7 5 |
| ) | +(( | 8 7 5 - |
| * | +((* | 8 7 5 - |
| 9 | +((* | 8 7 5 - 9 |
| / | +((/ | 8 7 5 - 9 * |
| ( | +((/( | 8 7 5 - 9 * |
| 9 | +((/( | 8 7 5 - 9 * 9 |
| - | +((/(- | 8 7 5 - 9 * 9 |
| 4 | +((/(- | 8 7 5 - 9 * 9 4 |
| ) | +((/ | 8 7 5 - 9 * 9 4 - |
| + | +((+ | 8 7 5 - 9 * 9 4 - / |
| 6 | +((+ | 8 7 5 - 9 * 9 4 - / 6 |
| ) | +( | 8 7 5 - 9 * 9 4 - / 6 + |
| / | +(/ | 8 7 5 - 9 * 9 4 - / 6 + |
| 4 | +(/ | 8 7 5 - 9 * 9 4 - / 6 + 4 |
| ) | + | 8 7 5 - 9 * 9 4 - / 6 + 4 / |
| (end) | (empty) | 8 7 5 - 9 * 9 4 - / 6 + 4 / + |
Final Postfix: 8 7 5 - 9 * 9 4 - / 6 + 4 / +
UNIT-II
3. (a) Differentiate between singly linked list and doubly linked list. [2 Marks]
| Feature |
Singly Linked List |
Doubly Linked List |
| Pointers |
Each node has one pointer (Next). |
Each node has two pointers (Next and Previous). |
| Traversal |
Forward direction only. |
Both forward and backward directions. |
3. (b) What is deque? Mention its types. [2 Marks]
A Deque (Double-Ended Queue) is a linear data structure where insertion and deletion can be performed from both ends (Front and Rear).
Types:
- Input Restricted Deque: Insertion at one end, deletion at both ends.
- Output Restricted Deque: Insertion at both ends, deletion at one end.
3. (c) What is skip list? [2 Marks]
A Skip List is a probabilistic data structure that allows fast search within an ordered sequence of elements. It consists of multiple layers of linked lists, where the bottom layer is a normal sorted list and higher layers act as "express lanes" to skip elements.
4. (a) Write an algorithm to insert and delete an element in a singly linked list. [10 Marks]
Algorithm: Insert_At_Beginning(START, ITEM)
- Allocate memory for NewNode.
- Set NewNode -> Data = ITEM.
- Set NewNode -> Next = START.
- Set START = NewNode.
Algorithm: Delete_From_Beginning(START)
- If START is NULL, print "Underflow" and exit.
- Set TEMP = START.
- Set START = START -> Next.
- Free TEMP memory.
UNIT-III
5. (a) Write down the properties of a tree. [2 Marks]
- A tree has one designated node called the Root.
- There is exactly one path between any two nodes in a tree.
- A tree with N nodes always has exactly N-1 edges.
5. (b) Define AVL tree. [2 Marks]
An AVL Tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees (Balance Factor) for any node cannot be more than 1 (i.e., -1, 0, or 1).
6. (a) (i) Show the tree after inserting: 18, 6, 20, 25, 32, 8, 12, 16 into a BST. [6 Marks]
Steps for BST Construction:
- 18 (Root)
- 6 < 18 (Left of 18)
- 20 > 18 (Right of 18)
- 25 > 20 (Right of 20)
- 32 > 25 (Right of 25)
- 8 > 6 (Right of 6)
- 12 > 8 (Right of 8)
- 16 > 12 (Right of 12)
After Deleting Root (18): The root is replaced by its in-order successor (20).
UNIT-IV
8. (a) Write an algorithm for linear search. [3 Marks]
Algorithm: Linear_Search(A, N, ITEM)
- Set I = 0.
- Repeat while I < N:
- If A[I] == ITEM, Return I (Found).
- Set I = I + 1.
- Return -1 (Not Found).
UNIT-V
9. (a) Define hash table. [2 Marks]
A Hash Table is a data structure that maps keys to values using a special function called a hash function. It provides very fast data retrieval, ideally in O(1) time.
10. (b) (i) Hash Table (Size 10) using Linear Probing for: 72, 27, 36, 24, 63, 81, 92, 101. [6 Marks]
Using Hash Function h(k) = k mod 10:
- 72 mod 10 = 2 (Index 2)
- 27 mod 10 = 7 (Index 7)
- 36 mod 10 = 6 (Index 6)
- 24 mod 10 = 4 (Index 4)
- 63 mod 10 = 3 (Index 3)
- 81 mod 10 = 1 (Index 1)
- 92 mod 10 = 2 (Collision! Index 2 full, move to 3 (full), move to Index 5)
- 101 mod 10 = 1 (Collision! Index 1 full, move to 2, 3, 4, 5 (all full), move to Index 8)
| Index | Key |
|---|
| 0 | - |
| 1 | 81 |
| 2 | 72 |
| 3 | 63 |
| 4 | 24 |
| 5 | 92 |
| 6 | 36 |
| 7 | 27 |
| 8 | 101 |
| 9 | - |
Exam Focus & Tips
Important Formulas List
- Binary Tree Height (N nodes): h = log2(N + 1) - 1
- Hash Function (Division): h(k) = k mod m
- Linear Probing: h(k, i) = (h'(k) + i) mod m
Common Mistakes
- Forgetting the "Underflow" check in deletion algorithms.
- Incorrect stack positions during infix-to-postfix conversion.
- Mixing up "Selection Sort" and "Bubble Sort" logic.
Answer Presentation Strategy
Always start long answers with a formal definition. Use diagrams for Linked Lists and Trees to secure full marks. When writing algorithms, ensure step numbering is logical and includes a start/end step.