Solved 2024: COMPUTER SCIENCE: Data Structure (CSCDSC-151T)<br>FYUG Even Semester Exam, 2024

SECTION-A (Answer any ten) 2 × 10 = 20 Marks

1. What is multidimensional array? How is it represented in memory?

2. Write down the limitations of array.

• Static size: The size must be known at compile-time and cannot be changed during execution.
• Homogeneous elements: Only elements of the same data type can be stored.
• Costly Insertions/Deletions: Moving elements to maintain order is time-consuming.

3. Write the postfix notation of (A-B)+C.

Expression: (A-B)+C

1. Solve brackets: (A-B) → AB-
2. Final expression: AB-+C → AB-C+

4. What do you mean by input-restricted and output-restricted dequeue?

• Input-restricted Dequeue: Insertion is allowed only at one end, while deletion is allowed at both ends.
• Output-restricted Dequeue: Deletion is allowed only at one end, while insertion is allowed at both ends.

5. Define doubly linked list with example.

A doubly linked list is a complex type of linked list in which each node contains a pointer to the next node as well as a pointer to the previous node

.

Example: Node(Prev, Data, Next). If we have nodes A, B, and C, B's 'prev' points to A and its 'next' points to C.

6. State the differences between array and linked list.

Feature Array Linked List Size Fixed/Static Dynamic Memory Allocation Compile time Run time Access Random access (Fast) Sequential access (Slow)

7. Define height-balanced tree.

A height-balanced tree (such as an AVL tree) is a binary tree in which the height of the left and right subtrees of every node differs by no more than one

.

8. Write down the properties of binary search tree (BST).

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• The left and right subtrees must also be binary search trees.

9. Write the advantages and disadvantages of threaded binary tree.

Advantages: Efficient traversal (no stack/recursion needed) and better utilization of null links

.
Disadvantages: More complex insertion/deletion and extra memory required for threads (flags).

10. Differences between linear search and binary search.

Linear Search: Works on both sorted and unsorted lists; time complexity is O(n)

.
Binary Search: Works only on sorted lists; time complexity is O(log n).

11. Best case and worst case time complexities.

Best Case: Minimum time required by an algorithm for a given input size (optimal scenario)

.
Worst Case: Maximum time required by an algorithm for any input of size n (guaranteed upper bound).

13. Define hashing.

Hashing is a technique used to uniquely identify a specific object from a group of similar objects using a mathematical formula called a hash function, which maps data of arbitrary size to a fixed-size table

.

---

SECTION-B (Answer any five) 10 × 5 = 50 Marks

16. (a) What is stack? Algorithms for stack operations. (b) Recursion and its advantages. [6+4=10]

Stack: A linear data structure that follows the LIFO (Last In First Out) principle

.

Algorithms:

PUSH(item): If TOP == MAX-1, Overflow; else { TOP = TOP + 1; STACK[TOP] = item; }
• POP(): If TOP == -1, Underflow; else { item = STACK[TOP]; TOP = TOP - 1; return item; }

Recursion: A process in which a function calls itself directly or indirectly

.
Advantages: Reduces code length, easier to solve problems like Tree traversals and Towers of Hanoi.

18. What is circular linked list? Algorithm to insert and delete. [2+4+4=10]

Circular Linked List: A linked list where all nodes are connected to form a circle; there is no NULL at the end

.

Insertion (at end): Create new node. Set new_node->next = head. Traverse to last node and set last_node->next = new_node.
Deletion (at end): Traverse to second last node. Set second_last->next = head. Delete the last node.

20. (a) Algebraic Expression E to Binary Tree and Traversals. (b) BST Construction. [5+5=10]

Expression E: [a+(b-c)] * [(d-e)/(f+g-h)]

Traversals:
Pre-order: * + a - b c / - d e - + f g h
Post-order: a b c - + d e - f g + h - / *

(b) BST Construction: 30, 60, 50, 35, 15, 25

22. Algorithm for Binary Search and search steps for 45. [5+5=10]

Binary_Search(A, n, item):
    Set beg = 0, end = n-1
    While beg <= end:
        mid = (beg + end) / 2
        If A[mid] == item: return mid
        Else If item < A[mid]: end = mid - 1
        Else: beg = mid + 1
    Return -1
    

Steps for 45 in [15, 21, 26, 30, 35, 45, 50, 55]:

1. Iteration 1: beg=0, end=7, mid=3. A[3]=30 < 45. beg=4.
2. Iteration 2: beg=4, end=7, mid=5. A[5]=45 == 45. Found at index 5.

24. (a) Hash functions. (b) Open vs Closed Addressing. [7+3=10]

Hash Functions: Division method ($h(k) = k \mod m$), Mid-square method, Folding method

.

Differences:
Open Addressing: All elements are stored in the hash table itself (Linear Probing, Quadratic Probing).
Closed Addressing (Chaining): Each slot of the hash table contains a link to a list of elements that hash to the same slot.

25. (a) Collision Resolution. (b) Linear Probing insertion. [5+5=10]

Strategies: Chaining, Linear Probing, Quadratic Probing, Double Hashing

.

Insertion (Size 10) for [72, 27, 36, 24, 63, 81, 92, 101]:

72 → 2, 27 → 7, 36 → 6, 24 → 4, 63 → 3, 81 → 1
• 92 → 2 (Collision) → Next free is 5. 101 → 1 (Collision) → Next free is 8.

0	1	2	3	4	5	6	7	8	9
-	81	72	63	24	92	36	27	101	-

Exam Focus Enhancements

• Exam Tips: For Tree questions, always draw the tree clearly. For complexity, use Big-O notation.
• Common Mistakes: Don't forget that array indices usually start from 0. In circular linked lists, ensure the last node points back to the head.
• Important Formulas: Address in 2D array (Row Major): $Loc(A[i][j]) = Base + W[n(i-L1) + (j-L2)]$.
• Strategy: Attempt numerical questions (Postfix evaluation, BST construction) first as they are scoring and take less time.

© 2026 Knowlet | Computer Science Series