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

Course No: CSCDSC-151T | Full Marks: 70 | Time: 3 Hours

Subject: Computer Science

Paper Code: CSCDSC-151T

Semester: 2nd Semester (FYUG)

Exam Name: Even Semester Exam, 2024

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

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

A multidimensional array is an array with more than one dimension, often visualized as a grid (2D) or a collection of grids (3D). In memory, which is linear, they are represented using either Row-Major Order (elements stored row by row) or Column-Major Order (elements stored column by column).

2. Write down the limitations of array.

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?

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.
0123456789
-81726324923627101-

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