Data Structures — Complete Solutions
Step-by-Step Explanations for All Questions
Q1 b) Linear Arrays
(i) Number of Elements in Each Array
For a Linear Array declared as ARRAY(lower : upper), the formula for number of elements is:
Number of Elements = upper − lower + 1
XXX(−10 : 10)
Number of elements = 10 − (−10) + 1 = 10 + 10 + 1 = 21
YYY(1935 : 1985)
Number of elements = 1985 − 1935 + 1 = 51
ZZZ(35) — single element
ZZZ(35) means only one element at index 35. Number of elements = 1
(ii) Address Calculation for YYY
Given: Base(YYY) = 400, w = 3 words per cell, Lower Bound = 1935
Address formula: LOC(YYY[K]) = Base(YYY) + w × (K − LB)
YYY[1942]
LOC = 400 + 3 × (1942 − 1935) = 400 + 3 × 7 = 400 + 21 = 421
YYY[1977]
LOC = 400 + 3 × (1977 − 1935) = 400 + 3 × 42 = 400 + 126 = 526
YYY[1988]
LOC = 400 + 3 × (1988 − 1935) = 400 + 3 × 53 = 400 + 159 = 559
Q2 a) Bubble Sort on PEOPLE
We sort the 6-letter sequence P, E, O, P, L, E alphabetically using Bubble Sort and count comparisons (C)
and interchanges (D).
Bubble Sort — Pass by Pass
In each pass, adjacent elements are compared. If they are out of order, they are swapped.
Pass Array State Comparisons Swaps
Initial PEOPLE — —
Pass 1 EOPLEP 5 4
Pass 2 EOLEPP 4 2
Pass 3 ELEOPP 3 2
Pass 4 EELOPP 2 1
Pass 5 EELOPP 1 0
TOTAL 15 9
C (Comparisons) = 15, D (Interchanges) = 9
Worst Case Proof: For n elements, max comparisons = n(n−1)/2 = 6×5/2 = 15. This equals our count, confirming
Bubble Sort runs in O(n²) time at worst case.
Q2 b) Linked List — Hospital Patients
(i) Alphabetical Listing — NLINK (NSTART)
Arrange names alphabetically: Adams(3), Brown(1), Burns(5), Jones(4), Smith(2). NSTART = 3 (Adams is
first alphabetically).
# NAME ROOM NLINK
1 Brown 650 5
2 Smith 422 0
3 Adams 704 1
4 Jones 462 2
5 Burns 632 4
NSTART = 3. Chain: 3→Adams→1→Brown→5→Burns→4→Jones→2→Smith→0(end)
(ii) Room Number Order — RLINK (RSTART)
Sort by room number: Smith(422), Jones(462), Brown(650), Burns(632), Adams(704). Ascending order:
422→462→632→650→704. RSTART = 2 (Smith, room 422).
# NAME ROOM RLINK
1 Brown 650 3
2 Smith 422 4
3 Adams 704 0
4 Jones 462 5
5 Burns 632 1
RSTART = 2. Chain: 2(422)→4(462)→5(632)→1(650)→3(704)→0(end)
Q3 a) Stack — Definition and Delete Procedure
Definition:
A Stack is a linear data structure that follows the LIFO (Last In, First Out) principle. Elements are added
(PUSH) and removed (POP) only from the TOP of the stack. It is analogous to a pile of plates.
Procedure to Delete (POP) from a Stack:
Procedure POP(STACK, TOP, ITEM): Step 1: If TOP = 0 then Print "UNDERFLOW — Stack is
Empty" Return Step 2: Set ITEM := STACK[TOP] [Assign top element to ITEM] Step 3: Set
TOP := TOP − 1 [Decrease TOP by 1] Step 4: Return
Explanation: First we check for underflow (empty stack). Then we save the top element, decrement the TOP
pointer, and return the saved element.
Q3 b) Infix to Reverse Polish (Postfix) Notation
Convert: A*(B+D)/E − F*(G+H/K) to Postfix using a Stack.
Step-by-Step Conversion:
Step Symbol Stack Postfix Output Action
1 A A Operand → output
2 * * A Push *
3 ( *( A Push (
4 B *( A B Operand → output
5 + *(+ A B Push +
6 D *(+ A B D Operand → output
7 ) * A B D + Pop till (, output +
8 / / A B D +* Pop *, push /
9 E / A B D +* E Operand → output
10 − − A B D +* E / Pop /, push −
11 F − A B D +* E / F Operand → output
12 * −* A B D +* E / F Push *
13 ( −*( A B D +* E / F Push (
14 G −*( A B D +* E / F G Operand → output
15 + −*(+ A B D +* E / F G Push +
16 H −*(+ A B D +* E / F G H Operand → output
17 / −*(+/ A B D +* E / F G H Push /
18 K −*(+/ A B D +* E / F G H K Operand → output
19 ) −* A B D +* E / F G H K/ + Pop till (, output /, +
20 END A B D +* E / F G H K/ + * − Pop all: *, −
Final Postfix Expression: A B D + * E / F G H K / + * −
Q4 a) Binary Search for ITEM = 13
Array DATA (13 elements): 13, 20, 23, 27, 33, 45, 47, 53, 65, 70, 75, 80, 88
Binary Search Algorithm Steps:
Binary search works on a sorted array by repeatedly halving the search interval. Set BEG=1, END=13
initially.
Iteration BEG END MID = (BEG+END)//2 DATA[MID] Action
1 1 13 (1+13)//2 = 7 47 47 > 13 → END = MID−1 = 6
2 1 6 (1+6)//2 = 3 23 23 > 13 → END = MID−1 = 2
3 1 2 (1+2)//2 = 1 13 13 = 13 → FOUND at index 1 ✓
Result: ITEM = 13 found at position 1 after 3 comparisons.
Q4 b) Binary Search Tree — Insertion of F, A, B, Z, G, X
Rules: If value < current node → go LEFT. If value > current node → go RIGHT.
Stage 1: Insert F
F becomes root.
F
Stage 2: Insert A
A < F → goes LEFT of F.
F
/
A
Stage 3: Insert B
B < F → go left. B > A → goes RIGHT of A.
F
/
A
\
B
Stage 4: Insert Z
Z > F → goes RIGHT of F.
F
/ \
A Z
\
B
Stage 5: Insert G
G > F → go right. G < Z → goes LEFT of Z.
F
/ \
A Z
\ /
B G
Stage 6: Insert X
X > F → right. X < Z → left. X > G → RIGHT of G.
F
/ \
A Z
\ /
B G
\
X
Q5 a) What is a Binary Tree?
A Binary Tree is a tree data structure where each node has at most two children, called the Left Child
and the Right Child. The topmost node is called the Root. A node with no children is called a Leaf node.
Key Terms:
• Root: The topmost node (F in the given tree)
• Left Subtree: The subtree rooted at the left child
• Right Subtree: The subtree rooted at the right child
• Leaf Node: A node with no children (A, C, E, H, I in the tree)
• Height: Number of edges on longest root-to-leaf path
Q5 b) Binary Tree T — Sequential & Linked Representation
The tree T has nodes: F(root), B(left), G(right), A, D(children of B), I(child of G), C, E(children of D), H(child
of I). Numbering by level:
(i) Sequential (Array) Representation:
Use array positions where for node at index i: Left child = 2i, Right child = 2i+1.
Index 1 2 3 4 5 6 7 8 9 10
Node F B G A D − I − − C
Index 11 12 13 14 15
Node E − − H −
'−' means NULL (no node at that position).
(ii) Linked Representation:
Each node stores: [LEFT_CHILD | DATA | RIGHT_CHILD]. NULL pointers shown as 0.
Node LEFT (pointer) DATA RIGHT (pointer)
Root →B F →G
B →A B →D
G NULL G →I
A NULL A NULL
D →C D →E
I →H I NULL
C NULL C NULL
E NULL E NULL
H NULL H NULL
ROOT pointer → F. NULL pointers indicate no child exists.
Q6 a) Definition of a Linked List
A Linked List is a linear data structure where elements (called nodes) are stored in non-contiguous
memory locations. Each node contains two parts: (1) DATA field — stores the actual value, and (2)
LINK/NEXT field — stores the address (pointer) of the next node. The last node points to NULL. Access is
sequential via a START/HEAD pointer.
Q6 b) Procedures for Linked List Operations
(i) Count occurrences of ITEM in LIST
Procedure COUNT_ITEM(LIST, ITEM, NUM): Step 1: Set NUM := 0 Step 2: Set PTR := START
[Start from first node] Step 3: Repeat while PTR ≠ NULL: If LIST[PTR].DATA = ITEM then
Set NUM := NUM + 1 [Increment count] Set PTR := LIST[PTR].NEXT [Move to next] [End
Loop] Step 4: Print "ITEM appears", NUM, "times" Step 5: Return
Explanation: We traverse the entire list from START to NULL. Each time DATA equals ITEM, we increment NUM.
At the end, NUM holds the total count.
(ii) Count Non-Zero Elements in LIST
Procedure COUNT_NONZERO(LIST, NUM): Step 1: Set NUM := 0 Step 2: Set PTR := START Step
3: Repeat while PTR ≠ NULL: If LIST[PTR].DATA ≠ 0 then Set NUM := NUM + 1 Set PTR :=
LIST[PTR].NEXT [End Loop] Step 4: Print "Non-zero elements:", NUM Step 5: Return
Explanation: Similar traversal, but we count nodes whose DATA is NOT zero.
(iii) Add a given value VAL to each element in LIST
Procedure ADD_VALUE(LIST, VAL): Step 1: Set PTR := START Step 2: Repeat while PTR ≠
NULL: Set LIST[PTR].DATA := LIST[PTR].DATA + VAL Set PTR := LIST[PTR].NEXT [End Loop]
Step 3: Print "Value", VAL, "added to all elements" Step 4: Return
Explanation: We traverse the entire list and modify each node's DATA field by adding VAL to it. This is an in-place
update.
— End of Solutions —