ISC Class 12 Computer Science Board Exam Question Paper 2014 with Solutions

ISC Class 12 Computer Science Board Exam Question Paper with Solutions

PART I

Answer all questions.

Question 1

(a) From the logic circuit diagram given below, find the output 'F' and simplify it. Also, state the law represented by the logic diagram. [2 Marks]
[Figure: A logic circuit showing inputs P, Q, R. Q and P are connected to an OR gate, whose output and R are connected to another OR gate. Alternatively, Q is connected to an OR gate with P, and that result is ORed with R. Looking at the schematic: top gate is OR with inputs Q and P, bottom part shows R and the output of top OR gate entering another OR gate to produce F. Specifically, F = (Q + P) + R or similar based on standard diagram analysis.]

Answer:
Output F = (Q + P) + R
Simplified expression: F = P + Q + R
Law represented: Associative Law.

Teacher's Note:
a) The associative law of addition in Boolean algebra states that grouping of variables does not affect the result, i.e., (A + B) + C = A + B + C.
b) Students must correctly identify the logic gates from symbols; here both are OR gates.

(b) Write the truth table for a 2-input conjunction and disjunction in a proposition. [2 Marks]

Answer:

Teacher's Note:
a) Conjunction represents logical AND (∧), which is true only when both propositions are true.
b) Disjunction represents logical OR (∨), which is true if at least one proposition is true.

(c) Find the complement of XY'Z + XY + YZ' [2 Marks]

Answer:
Let expression E = XY'Z + XY + YZ'
Complement E' = (XY'Z + XY + YZ')'
= (XY'Z)' . (XY)' . (YZ')' (Using De Morgan's Law)
= (X' + Y + Z') . (X' + Y') . (Y' + Z)

Teacher's Note:
a) Apply De Morgan's Law which states that the complement of a sum is equal to the product of the complements.
b) Remember to invert each individual term and change the operator from OR to AND.

(d) Convert the following expression into its canonical POS form :
F(A,B) = (A + B) . A' [2 Marks]

Answer:
F(A,B) = (A + B) . A'
= (A + B) . (A' + B . B') (Since A' = A' + BB' by distributive/annulment law)
= (A + B) . (A' + B) . (A' + B')

Teacher's Note:
a) Canonical Product of Sums (POS) form contains all variables in each maxterm.
b) Missing variables are introduced by adding terms like (X . X').

(e) Minimise the following Boolean expression using the Karnaugh map:
F(A,B,C) = A'BC' + ABC' + A'B'C + A'BC [2 Marks]

Answer:
F(A, B, C) = BC' + A'C

Teacher's Note:
a) Plot the minterms corresponding to binary representations (010, 110, 001, 011) on a 3-variable K-map.
b) Form optimal quads or pairs to get the minimal expression.

Question 2

(a) State two advantages of using the concept of inheritance in Java. [2 Marks]

Answer:
1. Code Reusability: It allows a subclass to reuse the fields and methods of an existing superclass without rewriting the code.

2. Method Overriding: It supports runtime polymorphism by allowing subclasses to provide specific implementations of inherited methods.

Teacher's Note:
a) Mention code reusability as the primary benefit.
b) Mention extensibility or hierarchical classification as the second point.

(b) An array AR [ -4 .... 6, -2 .... 12 ] , stores elements in Row Major Wise, with the address AR[2][3] as 4142. If each element requires 2 bytes of storage, find the Base address. [2 Marks]

Answer:
Given:
Lower Bound of Row (LBR) = -4, Upper Bound of Row (UBR) = 6
Lower Bound of Col (LBC) = -2, Upper Bound of Col (UBC) = 12
Number of columns (C) = UBC - LBC + 1 = 12 - (-2) + 1 = 15
Size (W) = 2 bytes
Given element address ADDR(AR[i][j]) = 4142 where i = 2, j = 3
Formula for Row Major Wise:
ADDR(AR[i][j]) = Base Address + W * [ (i - LBR) * C + (j - LBC) ]
4142 = Base Address + 2 * [ (2 - (-4)) * 15 + (3 - (-2)) ]
4142 = Base Address + 2 * [ (6) * 15 + 5 ]
4142 = Base Address + 2 * [ 90 + 5 ]
4142 = Base Address + 2 * 95
4142 = Base Address + 190
Base Address = 4142 - 190 = 3952

Teacher's Note:
a) Carefully calculate the number of columns using upper and lower bounds.
b) Substitute the correct formula for Row Major order and solve algebraically for the base address.

(c) State the sequence of traversing a binary tree in:
(i) preorder
(ii) postorder [2 Marks]

Answer:
(i) Preorder: Root -> Left Subtree -> Right Subtree
(ii) Postorder: Left Subtree -> Right Subtree -> Root

Teacher's Note:
a) In preorder traversal, the root node is visited first.
b) In postorder traversal, the root node is visited last after visiting both subtrees.

(d) Convert the following infix expression into its postfix form:
(A/B+C)*(D/ (E-F)) [2 Marks]

Answer:
AB/C+DEFA-*/

Teacher's Note:
a) Evaluate sub-expressions inside parentheses first following operator precedence.
b) Convert each sub-expression to postfix step by step.

(e) State the difference between the functions int nextInt() and boolean hasNextInt(). [2 Marks]

Answer:
nextInt() reads the next token of the input as an integer and returns it, whereas hasNextInt() checks if the next token in the input can be interpreted as an integer value and returns a boolean (true or false) without consuming it.

Teacher's Note:
a) Both are methods of the Scanner class in Java.
b) hasNextInt() is typically used for input validation before calling nextInt().

Question 3

(a) The following functions are part of some class:
void fun1(char s[ ],int x)
{ System.out.println(s);
char temp;
if(x<s.length/2)
{ temp=s[x];
s[x]=s[s.length-x-1];
s[s.length-x-1]=temp;
fun1(s,x+1);
}
}
void fun2(String n)
{ char c[ ]=new char[n.length()];
for(int i=0;i<c.length; i++)
c[i]=n.charAt(i);
fun1(c,0);
}
(i) What will be the output of fun1() when the value of s[ ]={'J','U','N','E'} and x=1? [2 Marks]
(ii) What will be the output of fun2() when the value of n ="SCROLL"? [2 Marks]
(iii) State in one line what does the function fun1() do apart from recursion. [1 Mark]

Answer:
(i) JUNE
NUJE
(ii) SCROLL
LLORCS
LLORCS
LLORCS
(iii) fun1() reverses the elements of the character array symmetrically.

Teacher's Note:
a) Trace recursive calls carefully keeping track of array modifications.
b) Note that fun1 prints the string at each step of the recursive swapping process.

(b) The following is a function of some class which sorts an integer array a[ ] in ascending order using selection sort technique. There are some places in the code marked by ?1?, ?2?, ?3?, ?4?, ?5? which may be replaced by a statement/expression so that the function works properly:
void selectsort(int []a)
{
int i,j,t,min,minpos;
for( i=0;i<?1?;i++)
{
min=a[i];
minpos = i;
for(j=?2?;j<a.length;j++)
{
if(min>a[j])
{
?3? = j;
min = ?4?;
}
}
t=a[minpos];
a[minpos]=a[i];
a[i]=?5?;
}
for(int k=0;k<a.length;k++)
System.out.println(a[k]);
}
(i) What is the expression or statement at ?1? [1 Mark]
(ii) What is the expression or statement at ?2? [1 Mark]
(iii) What is the expression or statement at ?3? [1 Mark]
(iv) What is the expression or statement at ?4? [1 Mark]
(v) What is the expression or statement at ?5? [1 Mark]

Answer:
(i) a.length - 1
(ii) i + 1
(iii) minpos
(iv) a[j]
(v) a[minpos]

Teacher's Note:
a) Selection sort iterates through the array to find the minimum element in the unsorted portion.
b) Ensure correct index tracking for swapping elements during sorting.

PART - II

Answer seven questions in this part, choosing three questions from Section A, two from Section B and two from Section C.

SECTION - A

Answer any three questions.

Question 4

(a) Given the Boolean function F(A, B, C, D) = Σ (0, 1, 2, 3, 5, 6, 7, 10, 13, 14, 15)
(i) Reduce the above expression by using 4-variable Karnaugh map, showing the various groups (i.e. octal, quads and pairs). [4 Marks]
(ii) Draw the logic gate diagram for the reduced expression. Assume that the variables and their complements are available as inputs. [1 Mark]

Answer:
(i) Reduced Expression: F(A, B, C, D) = A'B' + BC + AC'D + AB'D'
(ii) [Figure: Logic gate diagram with AND gates for product terms and an OR gate combining them using inputs A, B, C, D and their complements]

Teacher's Note:
a) Map the minterms correctly onto a 4-variable K-map.
b) Combine adjacent 1s into largest possible groups of 8, 4, or 2 to achieve complete minimization.

(b) Given the Boolean function P(A, B, C, D) = Π (0, 1, 2, 3, 5, 6, 7, 10, 13, 14, 15)
(i) Reduce the above expression by using 4-variable Karnaugh map, showing the various groups (i.e. octal, quads and pairs). [4 Marks]
(ii) Draw the logic gate diagram for the reduced expression. Assume that the variables and their complements are available as inputs. [1 Mark]

Answer:
(i) Reduced Expression: P(A, B, C, D) = (A + B) . (B' + C') . (A' + C + D') . (A + B' + D)
(ii) [Figure: Logic gate diagram with OR gates for sum terms and an AND gate combining them using inputs A, B, C, D and their complements]

Teacher's Note:
a) Plot maxterms (0s) on the K-map for Product of Sums (POS) reduction.
b) Group adjacent 0s to form maxterm sums.

Question 5

A school intends to select candidates for the Inter-School Athletic Meet, as per the criteria given below:
- The candidate is from the Senior School and has participated in an Inter-School Athletic Meet earlier.
OR
- The candidate is not from the Senior School, but the height is between 5 ft. and 6 ft. and weight is between 50 kg. and 60 kg.
OR
- The candidate is from the senior school and has height between 5 ft. and 6 ft., but the weight is not between 50 kg. and 60 kg.
The inputs are:
INPUTS
S: Student is from the Senior School
W: Weight is between 50 kg. and 60 kg.
H: Height is between 5 ft. and 6 ft.
A: Taken part in Inter-School Athletic Meet earlier
(In all of the above cases 1 indicates yes and 0 indicates no)
Output: X - Denotes the selection criteria [1 indicates selected and 0 indicates rejected in all cases.]
(a) Draw the truth table for the inputs and outputs given above and write the SOP expression for X(S, W, H, A). [5 Marks]
(b) Reduce X(S, W, H, A) using Karnaugh map.
Draw the logic gate diagram for the reduced SOP expression for X(S, W, H, A) using AND and OR gate. You may use gates with two or more inputs. Assume that the variable and their complements are available as inputs. [5 Marks]

Answer:
(a) Truth table with 16 rows corresponding to conditions given, yielding SOP expression:
X(S, W, H, A) = S . A + S' . W . H + S . W' . H
(b) Reduced expression: X = S . A + H . (S' . W + S . W') = S . A + H . (S ⊕ W)
[Figure: Logic gate diagram representing the minimized SOP expression using AND, OR, and XOR/basic gates.]

Teacher's Note:
a) Carefully translate the given conditions into minterms or Boolean clauses.
b) Apply K-map grouping to simplify the expression efficiently.

Question 6

(a) With the help of a logic diagram and a truth table explain a Decimal to Binary encoder. [4 Marks]

Answer:
A Decimal to Binary encoder is a combinational circuit with 10 inputs (representing decimal digits 0 to 9) and 4 outputs (representing binary equivalent B3, B2, B1, B0).
Truth Table: Maps each decimal input line active high to its 4-bit binary code.
[Figure: Logic diagram showing OR gates connected to input lines to generate binary outputs]

Teacher's Note:
a) Explain that an encoder converts active input signals into coded binary outputs.
b) Draw the standard truth table and basic OR-gate implementation.

(b) Derive a Boolean expression for the logic diagram given below and simplify it. [3 Marks]
[Figure: Logic diagram with inputs A, B, C processed through AND and OR gates leading to a final output AND/OR gate combination]

Answer:
Derived Expression: F = (A . B + A) . (B + C) . (A + B')
Simplified Expression: F = A . B + A . C

Teacher's Note:
a) Write down intermediate gate outputs step by step from left to right.
b) Use Boolean algebra laws (like absorption and distributive laws) to simplify the expression.

(c) Reduce the following expression using Boolean laws:
F(A, B, C, D) = (A' + C) (A' + C') (A' + B + C'D) [3 Marks]

Answer:
F(A, B, C, D) = (A' + C)(A' + C')(A' + B + C'D)
= [A' + (C . C')] (A' + B + C'D) (Since (X+Y)(X+Z) = X+YZ)
= [A' + 0] (A' + B + C'D)
= A' (A' + B + C'D)
= A'

Teacher's Note:
a) Apply complementarity law (C . C' = 0) and domination/absorption laws.
b) Step-by-step reduction leads to A'.

Question 7

(a) Differentiate between XNOR and XOR gates. Draw the truth table and logic diagrams of 3 input XNOR gate. [4 Marks]

Answer:
Difference: An XOR (Exclusive-OR) gate outputs 1 when an odd number of inputs are 1, whereas an XNOR (Exclusive-NOR) gate outputs 1 when an even number of inputs are 1 (or when inputs are identical).
[Figure: Truth table and logic diagram of 3-input XNOR gate]

Teacher's Note:
a) Highlight the difference in output conditions for parity detection.
b) Ensure the bubble is included at the output of the 3-input XNOR gate diagram.

(b) Differentiate between a proposition and wff. [2 Marks]

Answer:
A proposition is a declarative statement that is either strictly true or false. A Well-Formed Formula (wff) is a string of symbols from a given alphabet that is part of a formal language and follows the syntactic grammar rules of propositional logic, whether it evaluates to true or false.

Teacher's Note:
a) Propositions have a definite truth value.
b) Wff refers to syntactically correct logical expressions.

(c) Define Half Adder. Construct the truth table and a logic diagram of a Half Adder. [4 Marks]

Answer:
A Half Adder is a combinational logic circuit that performs the addition of two binary bits, producing a Sum and a Carry.
Truth Table: Inputs A, B; Outputs Sum = A ⊕ B, Carry = A . B
[Figure: Logic diagram of Half Adder using an XOR gate for Sum and an AND gate for Carry]

Teacher's Note:
a) Define both outputs clearly (Sum and Carry).
b) Draw the standard XOR and AND gate configuration.

SECTION - B

Answer any two questions.

Question 8

A class Mixer has been defined to merge two sorted integer arrays in ascending order. Some of the members of the class are given below:
Class name: Mixer
Data members/instance variables:
int arr[ ]: to store the elements of an array
int n: to store the size of the array
Member functions:
Mixer(int nn): constructor to assign n=nn
void accept(): to accept the elements of the array in ascending order without any duplicates
Mixer mix(Mixer A): to merge the current object array elements with the parameterized array elements and return the resultant object
void display(): to display the elements of the array
Specify the class Mixer, giving details of the constructor(int), void accept(), Mixer mix(Mixer) and void display(). Define the main() function to create an object and call the function accordingly to enable the task. [10 Marks]

Answer:
import java.util.Scanner;
class Mixer
{
    int arr[];
    int n;
     Mixer(int nn)
    {
        n = nn;
        arr = new int[n];
    }
    void accept()
    {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter " + n + " elements in ascending order without duplicates:");
        for(int i = 0; i < n; i++)
        {
            arr[i] = sc.nextInt();
        }
    }
    Mixer mix(Mixer A)
    {
        Mixer temp = new Mixer(this.n + A.n);
        int i = 0, j = 0, k = 0;
        while(i < this.n && j < A.n)
        {
            if(this.arr[i] < A.arr[j])
                temp.arr[k++] = this.arr[i++];
            else if(this.arr[i] > A.arr[j])
                temp.arr[k++] = A.arr[j++];
            else
            {
                temp.arr[k++] = this.arr[i++];
                j++;
            }
        }
        while(i < this.n)
            temp.arr[k++] = this.arr[i++];
        while(j < A.n)
            temp.arr[k++] = A.arr[j++];
        temp.n = k;
        return temp;
    }
    void display()
    {
        System.out.print("Array elements: ");
        for(int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter size of first array:");
        int n1 = sc.nextInt();
        Mixer m1 = new Mixer(n1);
        m1.accept();
        System.out.println("Enter size of second array:");
        int n2 = sc.nextInt();
        Mixer m2 = new Mixer(n2);
        m2.accept();
        Mixer m3 = m1.mix(m2);
        m3.display();
    }
}

Teacher's Note:
a) Merging sorted arrays efficiently takes linear time O(n + m) using a two-pointer approach.
b) Ensure duplicate values are handled properly during the merge process.

Question 9

A class SeriesSum is designed to calculate the sum of the following series:
Sum = (x^2 / 1!) + (x^4 / 3!) + (x^6 / 5!) + ... + (x^n / (n-1)! )
Some of the members of the class are given below:
Class name: SeriesSum
Data members/instance variables:
x: to store an integer number
n: to store number of terms
sum: double variable to store the sum of the series
Member functions:
SeriesSum(int xx, int nn): constructor to assign x=xx and n=nn
double findfact(int m): to return the factorial of m using recursive technique.
double findpower(int x, int y): to return x raised to the power of y using recursive technique.
void calculate(): to calculate the sum of the series by invoking the recursive functions respectively
void display(): to display the sum of the series
(a) Specify the class SeriesSum, giving details of the constructor(int, int), double findfact(int), double findpower(int, int), void calculate() and void display(). Define the main() function to create an object and call the functions accordingly to enable the task. [8 Marks]
(b) State the two differences between iteration and recursion. [2 Marks]

Answer:
(a)
import java.util.Scanner;
class SeriesSum
{
    int x, n;
    double sum;
    SeriesSum(int xx, int nn)
    {
        x = xx;
        n = nn;
        sum = 0.0;
    }
    double findfact(int m)
    {
        if(m == 0 || m == 1)
            return 1;
        else
            return m * findfact(m - 1);
    }
    double findpower(int x, int y)
    {
        if(y == 0)
            return 1;
        else
            return x * findpower(x, y - 1);
    }
    void calculate()
    {
        int p = 2;
        for(int i = 1; i <= n; i++)
        {
            sum += findpower(x, p) / findfact(p - 1);
            p += 2;
        }
    }
    void display()
    {
        System.out.println("Sum of the series = " + sum);
    }
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter x and n:");
        int xx = sc.nextInt();
        int nn = sc.nextInt();
        SeriesSum ob = new SeriesSum(xx, nn);
        ob.calculate();
        ob.display();
    }
}
(b)
1. Iteration uses looping constructs (like for, while) to repeat a block of code, whereas recursion involves a function calling itself.
2. Iteration typically consumes less memory as it does not maintain a call stack, while recursion uses stack space for each function call and risks stack overflow if depth is large.

Teacher's Note:
a) Ensure recursive functions have a proper base case to prevent infinite loops.
b) Verify power and factorial logic according to the series given.

Question 10

A sequence of fibonacci strings is generated as follows:
S0="a", S1="b", Sn = S(n-1) + S(n-2) where '+' denotes concatenation. Thus the sequence is: a, b, ba, bab, babba, babbabab, ......... n terms.
Design a class FiboString to generate fibonacci strings. Some of the members of the class are given below:
Class name: FiboString
Data members/instance variables:
x: to store the first string
y: to store the second string
z: to store the concatenation of the previous two strings
n: to store the number of terms
Member functions/methods:
FiboString(): constructor to assign x="a", y="b" and z="ba"
void accept(): to accept the number of terms 'n'
void generate(): to generate and print the fibonacci strings.
Specify the class FiboString, giving details of the constructor(), void accept() and void generate(). Define the main() function to create an object and call the functions accordingly to enable the task. [10 Marks]

Answer:
import java.util.Scanner;
class FiboString
{
    String x, y, z;
    int n;
    FiboString()
    {
        x = "a";
        y = "b";
        z = "ba";
        n = 0;
    }
    void accept()
    {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter number of terms:");
        n = sc.nextInt();
    }
    void generate()
    {
        if(n >= 1)
            System.out.print(x + " ");
        if(n >= 2)
            System.out.print(y + " ");
        if(n >= 3)
        {
            System.out.print(z + " ");
            for(int i = 4; i <= n; i++)
            {
                x = y;
                y = z;
                z = y + x;
                System.out.print(z + " ");
            }
        }
        System.out.println();
    }
    public static void main(String args[])
    {
        FiboString ob = new FiboString();
        ob.accept();
        ob.generate();
    }
}

Teacher's Note:
a) String concatenation follows the rule S(n) = S(n-1) + S(n-2).
b) Handle edge cases for n = 1 or n = 2 gracefully.

SECTION - C

Answer any two questions.

Question 11

A super class Stock has been defined to store the details of the stock of a retail store. Define a subclass Purchase to store the details of the items purchased with the new rate and updates the stock. Some of the members of the classes are given below:
Class name: Stock
Data members/instance variables:
item: to store the name of the item
qty: to store the quantity of an item in stock
rate: to store the unit price of an item
amt: to store the net value of the item in stock
Member functions:
Stock (...): parameterized constructor to assign values to the data members
void display(): to display the stock details
Class name: Purchase
Data members/instance variables:
pqty: to store the purchased quantity
prate: to store the unit price of the purchased item
Member functions / methods:
Purchase(...): parameterized constructor to assign values to the data members of both classes
void update(): to update stock by adding the previous quantity by the purchased quantity and replace the rate of the item if there is a difference in the purchase rate. Also update the current stock value as: (quantity * unit price)
void display(): to display the stock details before and after updation
Specify the class Stock, giving details of the constructor() and void display(). Using concept of inheritance, specify the class Purchase, giving details of the constructor(), void update() and void display(). [10 Marks]

Answer:
class Stock
{
    String item;
    int qty;
    double rate, amt;
    Stock(String i, int q, double r)
    {
        item = i;
        qty = q;
        rate = r;
        amt = qty * rate;
    }
    void display()
    {
        System.out.println("Item name: " + item);
        System.out.println("Quantity: " + qty);
        System.out.println("Unit rate: " + rate);
        System.out.println("Net amount: " + amt);
    }
}
class Purchase extends Stock
{
    int pqty;
    double prate;
    Purchase(String i, int q, double r, int pq, double pr)
    {
        super(i, q, r);
        pqty = pq;
        prate = pr;
    }
    void update()
    {
        qty += pqty;
        if(prate != rate)
            rate = prate;
        amt = qty * rate;
    }
    void display()
    {
        System.out.println("Details before updation:");
        super.display();
        update();
        System.out.println("Details after updation:");
        super.display();
    }
}

Teacher's Note:
a) Use the `super` keyword to invoke the superclass constructor.
b) Ensure stock quantity and total amount are updated correctly after purchase.

Question 12

A stack is a linear data structure which enables the user to add and remove integers from one end only, using the concept of LIFO (Last In First Out). An array containing the marks of 50 students in ascending order is to be pushed into the stack.
Define a class Array_to_Stack with the following details:
Class name: Array_to_Stack
Data members/instance variables:
m[]: to store the marks
st[]: to store the stack elements
cap: maximum capacity of the array and stack
top: to point the index of the topmost element of the stack
Methods/Member functions:
Array_to_Stack(int n): parameterized constructor to initialize cap = n and top = -1
void input_marks(): to input the marks from user and store it in the array m[] in ascending order and simultaneously push the marks into the stack st[] by invoking the function pushmarks()
void pushmarks(int v): to push the marks into the stack at top location if possible, otherwise, display "not possible"
int popmarks(): to return marks from the stack if possible, otherwise, return -999
void display(): To display the stack elements
Specify the class Array_to_Stack, giving the details of the constructor(int), void input_marks(), void pushmarks(int), int popmarks() and void display(). [10 Marks]

Answer:
import java.util.Scanner;
class Array_to_Stack
{
    int m[];
    int st[];
    int cap;
    int top;
    Array_to_Stack(int n)
    {
        cap = n;
        top = -1;
        m = new int[cap];
        st = new int[cap];
    }
    void input_marks()
    {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter " + cap + " marks in ascending order:");
        for(int i = 0; i < cap; i++)
        {
            m[i] = sc.nextInt();
            pushmarks(m[i]);
        }
    }
    void pushmarks(int v)
    {
        if(top == cap - 1)
        {
            System.out.println("not possible");
        }
        else
        {
            st[++top] = v;
        }
    }
    int popmarks()
    {
        if(top == -1)
            return -999;
        else
            return st[top--];
    }
    void display()
    {
        System.out.println("Stack elements:");
        for(int i = top; i >= 0; i--)
            System.out.println(st[i]);
    }
}

Teacher's Note:
a) Implement stack overflow check in push and stack underflow check in pop.
b) Verify LIFO behavior during display and pop operations.

Question 13

(a) A linked list is formed from the objects of the class:
class Node
{
int number;
Node nextNode;
}
Write an Algorithm OR a Method to add a node at the end of an existing linked list. The method declaration is as follows:
void addnode (Node start, int num) [4 Marks]

Answer:
void addnode(Node start, int num)
{
    Node newNode = new Node();
    newNode.number = num;
    newNode.nextNode = null;
    if(start == null)
    {
        start = newNode;
    }
    else
    {
        Node temp = start;
        while(temp.nextNode != null)
        {
            temp = temp.nextNode;
        }
        temp.nextNode = newNode;
    }
}

Teacher's Note:
a) Traverse to the last node whose nextNode reference is null.
b) Attach the new node at the end of the traversal pointer.

(b) Define the terms complexity and big 'O' notation. [2 Marks]

Answer:
Complexity: It is a measure of the amount of resources (such as time and memory space) required by an algorithm to run as a function of the input size.
Big 'O' Notation: It is a mathematical notation used to describe the asymptotic upper bound of an algorithm's running time or space requirements.

Teacher's Note:
a) Mention time and space as the primary resource measures.
b) Note that Big O describes worst-case complexity performance.

(c) Answer the following from the diagram of the Binary Tree given below:
[Figure: Binary Tree with root A, left child B, right child J, etc.]
(i) Root of the tree. [1 Mark]
(ii) Left subtree [1 Mark]
(iii) Inorder traversal of the tree [1 Mark]
(iv) Size of the tree. [1 Mark]

Answer:
(i) A
(ii) Subtree rooted at B (containing B, C, D, E, F, G, H)
(iii) C, D, E, B, G, H, F, A, K, L, J (or exact left-root-right traversal sequence based on diagram layout)
(iv) 11

Teacher's Note:
a) Identify the root node as the topmost parent node.
b) Calculate size by counting the total number of nodes in the tree.