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

ISC Class 12 Computer Science Board Exam Question Paper with Solutions

PART I

Question 1

(a) Using a truth table, verify the following expression:
X + (Y + Z) = (X + Y) + Z
Also state the law. [2 Marks]

Answer:

Since the columns for X + (Y + Z) and (X + Y) + Z are identical, the expression is verified.
Law: Associative Law.

Teacher's Note:
a) To verify an identity using a truth table, construct columns for each sub-expression and check if the output columns are identical for all combinations.
b) Students often forget to explicitly state the name of the Boolean law when asked in the question, losing marks.

(b) Given, F(X, Y, Z) = (X' + Y') . (Y + Z')
write the function in canonical product-of-sum form. [2 Marks]

Answer:
Given expression: F(X, Y, Z) = (X' + Y') . (Y + Z')
Term 1: (X' + Y') is missing variable Z. Writing it as (X' + Y' + (Z . Z')) = (X' + Y' + Z) . (X' + Y' + Z')
Term 2: (Y + Z') is missing variable X. Writing it as (Y + Z' + (X . X')) = (X + Y + Z') . (X' + Y + Z')
Combining all unique maxterms: F(X, Y, Z) = M₁ . M₃ . M₄ . M₆ = \Pi(1, 3, 4, 6).

Teacher's Note:
a) In Product-of-Sum (POS) form, missing variables are introduced by adding terms using the distributive law in the form of (variable + variable').
b) Ensure that maxterm indices are correctly assigned where 0 represents the uncomplemented variable and 1 represents the complemented variable.

(c) Draw the truth table and logic circuit for a 2-input XNOR gate. [2 Marks]

Answer:

[Figure: Logic circuit diagram of a 2-input XNOR gate showing inputs A and B entering an exclusive-NOR shaped gate with an output equal to AB + A'B'.]

Teacher's Note:
a) An XNOR gate outputs 1 when both inputs are identical (either both 0 or both 1).
b) Remember that the XNOR symbol is an XOR gate symbol preceded by a small bubble indicating inversion.

(d) Find the complement of the following expression:
X' + XY' [2 Marks]

Answer:
Complement of expression = (X' + XY')'
= (X')' . (XY')'      (Using De Morgan's Law)
= X . (X' + (Y')')      (Using De Morgan's Law again)
= X . (X' + Y)
= (X . X') + (X . Y)
= 0 + (X . Y)
= XY.

Teacher's Note:
a) Apply De Morgan's Law by breaking the outer complement bar and changing the operator between terms from OR to AND.
b) Further simplify the resulting expression using standard Boolean algebra rules like absorption or distributive laws.

(e) If (X → Y) then write its:
(i) Converse
(ii) Contra positive [2 Marks]

Answer:
(i) Converse: (Y → X)
(ii) Contra positive: (Y' → X')

Teacher's Note:
a) The converse of an implication swaps the hypothesis and the conclusion.
b) The contrapositive swaps the hypothesis and conclusion and negates both.

Question 2

(a) Differentiate between the keywords extends and implements. [2 Marks]

Answer:

Teacher's Note:
a) Focus on the inheritance relationship type, such as class-to-class versus class-to-interface.
b) Mention the multiple inheritance capability as the key differentiating feature.

(b) State how a binary tree is a recursive data structure. [2 Marks]

Answer:
A binary tree is defined recursively because every node in a binary tree points to zero, one, or two subtrees (left subtree and right subtree), each of which is itself a binary tree. Thus, the structure is defined in terms of smaller instances of the same structure.

Teacher's Note:
a) Highlight that a sub-node and its children form another valid binary tree.
b) Mention the base case being a null node or a leaf node with no children.

(c) A matrix B[10][7] is stored in the memory with each element requiring 2 bytes of storage. If the base address at B[x][1] is 1012 and the address at B[7][3] is 1060, determine the value 'x' where the matrix is stored in Column Major wise. [2 Marks]

Answer:
Given: Rows = 10, Columns = 7, W = 2 bytes.
Column major address formula:
Address(B[i][j]) = Base(B) + W * [ M * (j - lower_j) + (i - lower_i) ]
Assuming 0-based indexing (lower_i = 0, lower_j = 0, M = 10):
Address(B[7][3]) = Base(B) + 2 * [ 10 * (3 - 0) + (7 - 0) ]
1060 = Base(B) + 2 * [ 30 + 7 ]
1060 = Base(B) + 2 * 37
1060 = Base(B) + 74
Base(B) = 1060 - 74 = 986.
Now, given Address(B[x][1]) = 1012:
1012 = 986 + 2 * [ 10 * (1 - 0) + (x - 0) ]
1012 - 986 = 2 * [ 10 + x ]
26 = 2 * (10 + x)
13 = 10 + x
x = 3.

Teacher's Note:
a) First find the unknown base address using the given address of B[7][3].
b) Substitute the base address into the formula for B[x][1] to solve for x.

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

Answer:
Given expression: A + ((B + C) + (D + E) * F) / G
Step 1: Parenthesize operations according to precedence:
A + (((B + C) + ((D + E) * F)) / G)
Step 2: Convert innermost parentheses:
(B + C) becomes BC+
(D + E) becomes DE+
Step 3: Convert multiplication:
((D + E) * F) becomes DE+F*
Step 4: Convert inner addition:
((B + C) + (DE+F*)) becomes BC+DE+F*+
Step 5: Convert division by G:
(BC+DE+F*+ / G) becomes BC+DE+F*+G/
Step 6: Convert final addition with A:
A + (BC+DE+F*+G/) becomes ABC+DE+F*+G/+

Teacher's Note:
a) Convert sub-expressions inside parentheses first before moving outwards.
b) Double-check operator precedence where multiplication and division take precedence over addition.

(e) What is a constructor? State one difference between a constructor and any other member function of a class. [2 Marks]

Answer:
A constructor is a special member function of a class that has the same name as the class and is used to initialize the data members of an object when it is created.
Difference: A constructor does not have any return type (not even void), whereas any other ordinary member function must specify a return type.

Teacher's Note:
a) Highlight that constructors are invoked automatically upon object instantiation.
b) Emphasize the absence of a return type as the primary syntactic difference.

Question 3

(a) The following function is a part of some class which computes and sorts an array arr[ ] in ascending order using the bubble sort technique. There are some places in the code marked by ?1?, ?2?, ?3?, ?4?, ?5? which must be replaced by a statement / expression so that the function works properly:
void bubblesort(int arr[ ])
{
    int i, j, k, tmp;
    for(i = 0; ?1?; i++)
    {
        for(j = 0; ?2?; j++)
        {
            if(arr[j] > ?3?)
            {
                tmp = arr[j];
                ?4? = arr[j+1];
                arr[j+1] = ?5?;
            }
        }
    }
}
(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) arr.length - 1
(ii) arr.length - 1 - i
(iii) arr[j + 1]
(iv) arr[j]
(v) tmp

Teacher's Note:
a) Bubble sort requires nested loops where the inner loop shrinks with each pass (arr.length - 1 - i).
b) Swapping requires a temporary variable where arr[j] is assigned to arr[j+1] using tmp.

(b) The following function witty( ) is a part of some class. What will be the output of the function witty( ) when the value of n is "SCIENCE" and the value of p is 5. Show the dry run / working:
void witty(String n, int p)
{
    if (p < 0)
        System.out.println("");
    else
    {
        System.out.println(n.charAt(p) + " ");
        witty(n, p-1);
        System.out.print(n.charAt(p));
    }
    }
[5 Marks]

Answer:
Dry Run:
witty("SCIENCE", 5): prints C, calls witty("SCIENCE", 4)
witty("SCIENCE", 4): prints N, calls witty("SCIENCE", 3)
witty("SCIENCE", 3): prints E, calls witty("SCIENCE", 2)
witty("SCIENCE", 2): prints IC, calls witty("SCIENCE", 1)
witty("SCIENCE", 1): prints C, calls witty("SCIENCE", 0)
witty("SCIENCE", 0): prints S, calls witty("SCIENCE", -1)
witty("SCIENCE", -1): prints empty line.
Unwinding recursion prints trailing characters in reverse order of calls.
Output:
C
N
E
I
C
S
SCENIC

Teacher's Note:
a) Note that charAt(5) is 'C' (indices: S=0, C=1, I=2, E=3, N=4, C=5, E=6).
b) The method uses tail and head recursion printing characters before and after recursive calls.

PART - II

SECTION - A

Question 4

(a) Given the Boolean function: F(A, B, C, D) = \Sigma (4, 6, 7, 10, 11, 12, 14, 15)
(i) Reduce the above expression by using 4 - variable K-Map, showing the various groups (i.e. octal, quads and pairs). [4 Marks]
(ii) Draw the logic gate diagram of the reduced expression. Assume that the variables and their complements are available as inputs. [1 Mark]

Answer:
(i) K-Map grouping for minterms 4, 6, 7, 10, 11, 12, 14, 15:
- Quad 1 (m₄, m₆, m₁₂, m₁₄): BC'
- Quad 2 (m₆, m₇, m₁₄, m₁₅): AB
- Quad 3 (m₁₀, m₁₁, m₁₄, m₁₅): AC
Reduced Expression: F(A, B, C, D) = BC' + AB + AC
(ii) [Figure: Logic gate diagram featuring inputs A, B, C, D and their complements, three 2-input AND gates for products BC', AB, and AC, and one 3-input OR gate producing output F.]

Teacher's Note:
a) Form overlapping quads to achieve the minimal SOP expression.
b) Verify that all specified minterms are covered by at least one group.

(b) Given the Boolean function: F(P, Q, R, S) = \Pi (0, 5, 7, 8, 10, 12, 13, 14, 15)
(i) Reduce the above expression by using 4 - variable K-Map, showing the various groups (i.e. octal, quads and pairs). [4 Marks]
(ii) Draw the logic gate diagram of the reduced expression. Assume that the variables and their complements are available as inputs. [1 Mark]

Answer:
(i) K-Map grouping for maxterms 0, 5, 7, 8, 10, 12, 13, 14, 15:
- Quad 1 (M₈, M₁₀, M₁₂, M₁₄): P' + S'
- Quad 2 (M₅, M₇, M₁₃, M₁₅): Q' + S
- Pair / Quad combinations yield: F(P, Q, R, S) = (P + Q') . (Q + S') . ...
(ii) [Figure: Logic gate diagram with OR gates for sum terms connected to a final AND gate for the POS expression.]

Teacher's Note:
a) For Product-of-Sums, group 0s in the K-map.
b) Ensure correct conversion of groups into maxterms.

Question 5

The Principal of a school intends to select students for admission to class XI on the following criteria:
- Student is of the same school and has passed the class X Board Examination with more than 60% marks.
OR
- Student is of the same school, has passed the class X Board Examination with less than 60% marks but has taken active part in co-curricular activities.
OR
- Student is not from the same school but has either passed the class X Board Examination with more than 60% marks or has participated in sports at the National level.
The inputs are:

Output: X - Denotes admission status [1 indicates granted and 0 indicates refused in all the cases.]
(a) Draw the truth table for the inputs and outputs given above and write the SOP expression. [5 Marks]
(b) Reduce X (S, P, C, T) using Karnaugh's Map.
Draw the logic gate diagram for the reduced SOP expression for X (S, P, C, T) 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:
S=0, P=0, C=0, T=0 -> X=0
S=0, P=0, C=0, T=1 -> X=1 (Not same school, National sports)
S=0, P=0, C=1, T=0 -> X=0
S=0, P=0, C=1, T=1 -> X=1
S=0, P=1, C=0, T=0 -> X=1 (Not same school, >60% marks)
S=0, P=1, C=0, T=1 -> X=1
S=0, P=1, C=1, T=0 -> X=1
S=0, P=1, C=1, T=1 -> X=1
S=1, P=0, C=0, T=0 -> X=0
S=1, P=0, C=0, T=1 -> X=0
S=1, P=0, C=1, T=0 -> X=1 (Same school, <60%, co-curricular)
S=1, P=0, C=1, T=1 -> X=1
S=1, P=1, C=0, T=0 -> X=1 (Same school, >60%)
S=1, P=1, C=0, T=1 -> X=1
S=1, P=1, C=1, T=0 -> X=1
S=1, P=1, C=1, T=1 -> X=1
SOP Expression: X = \Sigma (1, 3, 4, 5, 6, 7, 10, 11, 12, 13, 14, 15)
(b) Reduced using K-Map: X = P + S'T + SC
[Figure: Logic gate diagram showing inputs S, P, C, T with AND gates for S'T and SC, combined with P using an OR gate.]

Teacher's Note:
a) Carefully translate each statement in the problem description into minterms.
b) Group adjacent 1s in the K-map to achieve maximum simplification.

Question 6

(a) Verify algebraically if,
X'Y'Z' + X'Y'Z + X'YZ + X'YZ' + XY'Z' + XY'Z = X' + Y' [2 Marks]

Answer:
LHS = X'Y'(Z' + Z) + X'Y(Z + Z') + XY'(Z' + Z)
= X'Y'(1) + X'Y(1) + XY'(1)
= X'Y' + X'Y + XY'
= X'(Y' + Y) + XY'
= X'(1) + XY'
= X' + XY'
= (X' + X) . (X' + Y')
= 1 . (X' + Y')
= X' + Y' = RHS.

Teacher's Note:
a) Use distributive and complementarity laws (Z + Z' = 1) to eliminate variables.
b) Apply absorption or distributive law in the final steps to arrive at the target expression.

(b) Represent the Boolean expression X + YZ' with the help of NOR gates only. [2 Marks]

Answer:
Given expression: X + YZ'
Using double negation: ((X + YZ')')'
Applying De Morgan's Law: ((X)' . (YZ')')'
Representing using NOR gates: X NOR (Y NOR Z').

Teacher's Note:
a) A universal gate like NOR can implement any Boolean function through double complementation.
b) Ensure all AND and OR operations are converted to equivalent NOR forms.

(c) Define the terms Contingency, Contradiction and Tautology. [3 Marks]

Answer:
- Contingency: A Boolean expression whose truth table results in a combination of both 1s and 0s.
- Contradiction: A Boolean expression whose truth table results in all 0s (False) for all input combinations.
- Tautology: A Boolean expression whose truth table results in all 1s (True) for all input combinations.

Teacher's Note:
a) Clearly distinguish based on the final column of the truth table.
b) Give brief definitions or examples for clarity.

(d) Consider the following truth table where A and B are two inputs and X is the output:

(i) Name and draw the logic gate for the given truth table. [2 Marks]
(ii) Write the POS of X(A,B). [1 Mark]

Answer:
(i) Name: XOR Gate.
[Figure: Logic gate diagram of a 2-input XOR gate with inputs A, B and output X.]
(ii) POS of X(A,B) = \Pi (0, 3) = (A + B) . (A' + B')

Teacher's Note:
a) Identify the truth table as representing the Exclusive-OR (XOR) operation.
b) POS is formed by taking maxterms where the output is 0.

Question 7

(a) Define Multiplexer and state one of its uses. Draw the logic diagram for a 4:1 Multiplexer. [4 Marks]

Answer:
Definition: A multiplexer is a combinational circuit that selects binary information from one of many input lines and directs it to a single output line based on select lines.
Use: Used in data routing, communication systems, and digital-to-analog converters.
[Figure: Logic diagram of a 4:1 Multiplexer showing 4 data inputs (D0-D3), 2 select lines (S0, S1), and a single output Y.]

Teacher's Note:
a) Multiplexers are often referred to as 'data selectors'.
b) The number of select lines is calculated as log₂(n) where n is the number of inputs.

(b) State how a Half Adder is different from a Full Adder. Also give their respective uses. [3 Marks]

Answer:
Difference: A Half Adder adds two binary bits and produces Sum and Carry outputs, whereas a Full Adder adds three binary bits (two significant bits and a previous carry) producing Sum and Carry outputs.
Uses: Half Adders are used for basic binary addition of two single-bit numbers; Full Adders are cascaded to add multi-bit binary numbers.

Teacher's Note:
a) Highlight the number of inputs handled by each adder.
b) Mention the cascading capability of full adders for large binary numbers.

(c) Minimize the following expression using Boolean laws:
Q . (Q' + P) . R . (Q + R)
Also draw the logic gate for the reduced expression. [3 Marks]

Answer:
Given expression: Q . (Q' + P) . R . (Q + R)
= (QQ' + QP) . R . (Q + R)     (Distributive law)
= (0 + QP) . R . (Q + R)     (Complementarity)
= QPR . (Q + R)
= (QP . R . Q) + (QP . R . R)     (Distributive law)
= (QQ . P . R) + (Q . P . RR)
= (Q . P . R) + (Q . P . R)     (Idempotent law)
= QPR.
[Figure: Logic gate diagram showing a 3-input AND gate with inputs Q, P, and R producing output QPR.]

Teacher's Note:
a) Expand terms systematically using distributive and absorption laws.
b) Apply idempotent laws (X . X = X) to simplify duplicate terms.

SECTION - B

Question 8

A class Combine contains an array of integers which combines two arrays into a single array including the duplicate elements, if any, and sorts the combined array. Some of the members of the class are given below: [10 Marks]
Class name: Combine
Data members / instance variables:
com[ ] - integer array
size - size of the array
Member functions/methods:
Combine (int nn) - parameterized constructor to assign size = nn
void inputarray( ) - to accept the array elements
void sort( ) - sorts the elements of combined array in ascending order using the selection sort technique
void mix(Combine A, Combine B) - combines the parameterized object arrays and stores the result in the current object array along with duplicate elements, if any
void display( ) - displays the array elements
Specify the class Combine giving details of the constructor(int), void inputarray( ), void sort( ), void mix(Combine, Combine) and void display( ). Also define the main( ) function to create an object and call the methods accordingly to enable the task.

Answer:

import java.util.Scanner;
public class Combine
{
    int com[];
    int size;

    public Combine(int nn)
    {
        size = nn;
        com = new int[size];
    }

    public void inputarray()
    {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter " + size + " elements:");
        for(int i = 0; i < size; i++)
        {
            com[i] = sc.nextInt();
        }
    }

    public void sort()
    {
        for(int i = 0; i < size - 1; i++)
        {
            int min = i;
            for(int j = i + 1; j < size; j++)
            {
                if(com[j] < com[min])
                {
                    min = j;
                }
            }
            int temp = com[min];
            com[min] = com[i];
            com[i] = temp;
        }
    }

    public void mix(Combine A, Combine B)
    {
        int k = 0;
        for(int i = 0; i < A.size; i++)
        {
            com[k++] = A.com[i];
        }
        for(int i = 0; i < B.size; i++)
        {
            com[k++] = B.com[i];
        }
    }

    public void display()
    {
        for(int i = 0; i < size; i++)
        {
            System.out.print(com[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();
        System.out.println("Enter size of second array:");
        int n2 = sc.nextInt();
        Combine obj1 = new Combine(n1);
        Combine obj2 = new Combine(n2);
        obj1.inputarray();
        obj2.inputarray();
        Combine obj3 = new Combine(n1 + n2);
        obj3.mix(obj1, obj2);
        obj3.sort();
        obj3.display();
    }
}

Teacher's Note:
a) Ensure the current object's array size is allocated correctly in mix().
b) Selection sort must correctly compare and swap elements.

Question 9

Design a class VowelWord to accept a sentence and calculate the frequency of words that begin with a vowel. The words in the input string are separated by a single blank space and terminated by a full stop. The description of the class is given below: [10 Marks]
Class name: VowelWord
Data members / instance variables:
str - to store a sentence
freq - store the frequency of the words beginning with a vowel
Member functions:
VowelWord( ) - constructor to initialize data members to legal initial value
void readstr( ) - to accept a sentence
void freq_vowel( ) - counts the frequency of the words that begin with a vowel
void display( ) - to display the original string and the frequency of the words that begin with a vowel
Specify the class VowelWord giving details of the constructor( ), void readstr( ), void freq_vowel( ) and void display( ). Also define the main( ) function to create an object and call the methods accordingly to enable the task.

Answer:

import java.util.Scanner;
public class VowelWord
{
    String str;
    int freq;

    public VowelWord()
    {
        str = "";
        freq = 0;
    }

    public void readstr()
    {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter a sentence ending with a full stop:");
        str = sc.nextLine();
    }

    public void freq_vowel()
    {
        freq = 0;
        String s = str.trim();
        String w = "";
        for(int i = 0; i < s.length(); i++)
        {
            char ch = s.charAt(i);
            if(ch == ' ' || ch == '.')
            {
                if(w.length() > 0)
                {
                    char f = Character.toUpperCase(w.charAt(0));
                    if(f == 'A' || f == 'E' || f == 'I' || f == 'O' || f == 'U')
                    {
                        freq++;
                    }
                }
                w = "";
            }
            else
            {
                w = w + ch;
            }
        }
    }

    public void display()
    {
        System.out.println("Sentence: " + str);
        System.out.println("Frequency of words beginning with vowel: " + freq);
    }

    public static void main(String args[])
    {
        VowelWord obj = new VowelWord();
        obj.readstr();
        obj.freq_vowel();
        obj.display();
    }
}

Teacher's Note:
a) Ensure words are extracted correctly by checking for space and full stop characters.
b) Check both uppercase and lowercase vowels for accuracy.

Question 10

Design a class Happy to check if a given number is a happy number. Some of the members of the class are given below: [10 Marks]
Class name: Happy
Data members/instance variables: n - stores the number
Member functions:
Happy( ) - constructor to assign 0 to n
void getnum(int nn) - to assign the parameter value to the number n = nn
int sum_sq_digits(int x) - returns the sum of the square of the digits of the number x, using the recursive technique
void ishappy( ) - checks if the given number is a happy number by calling the function sum_sq_digits(int) and displays an appropriate message
Specify the class Happy giving details of the constructor( ), void getnum(int), int sum_sq_digits(int) and void ishappy( ). Also define a main( ) function to create an object and call the methods to check for happy number.

Answer:

import java.util.Scanner;
public class Happy
{
    int n;

    public Happy()
    {
        n = 0;
    }

    public void getnum(int nn)
    {
        n = nn;
    }

    public int sum_sq_digits(int x)
    {
        if(x == 0)
            return 0;
        int d = x % 10;
        return (d * d) + sum_sq_digits(x / 10);
    }

    public void ishappy()
    {
        int temp = n;
        while(temp > 9)
        {
            temp = sum_sq_digits(temp);
        }
        if(temp == 1 || temp == 7)
        {
            System.out.println(n + " is a happy number.");
        }
        else
        {
            System.out.println(n + " is not a happy number.");
        }
    }

    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter a number:");
        int num = sc.nextInt();
        Happy obj = new Happy();
        obj.getnum(num);
        obj.ishappy();
    }
}

Teacher's Note:
a) The recursive method sum_sq_digits must extract digits using modulus and division operators.
b) A happy number eventually reduces to 1 (or 7 for single digit checks).

SECTION - C

Question 11

Link is an entity which can hold a maximum of 100 integers. Link enables the user to add elements from the rear end and remove integers from the front end of the entity. Define a class Link with the following details:
Class name: Link
Data members/instant variables:
lnk[ ] - entity to hold the integer elements
max - stores the maximum capacity of the entity
begin - to point to the index of the front end
end - to point to the index of the rear end
Member functions:
Link(int mm) - constructor to initialize max = mm, begin = 0, end = 0
void addlink(int v) - to add an element from the rear index if possible otherwise display the message "OUT OF SIZE..."
int dellink( ) - to remove and return an element from the front index, if possible otherwise display the message "EMPTY..." and return -99
void display( ) - displays the elements of the entity
(a) Specify the class Link giving details of the constructor(int), void addlink(int), int dellink( ) and void display( ). [9 Marks]
THE MAIN FUNCTION AND ALGORITHM NEED NOT BE WRITTEN.
(b) What type of data structure is the above entity? [1 Mark]

Answer:

public class Link
{
    int lnk[];
    int max;
    int begin;
    int end;

    public Link(int mm)
    {
        max = mm;
        lnk = new int[max];
        begin = 0;
        end = 0;
    }

    public void addlink(int v)
    {
        if(end == max)
        {
            System.out.println("OUT OF SIZE...");
        }
        else
        {
            lnk[end++] = v;
        }
    }

    public int dellink()
    {
        if(begin == end)
        {
            System.out.println("EMPTY...");
            return -99;
        }
        else
        {
            return lnk[begin++];
        }
    }

    public void display()
    {
        if(begin == end)
        {
            System.out.println("Queue is empty.");
        }
        else
        {
            for(int i = begin; i < end; i++)
            {
                System.out.print(lnk[i] + " ");
            }
            System.out.println();
        }
    }
}

(b) Queue (Linear Queue)

Teacher's Note:
a) This data structure operates on FIFO (First In, First Out) principles, identifying it as a Queue.
b) Check overflow and underflow conditions appropriately using begin and end pointers.

Question 12

A super class Detail has been defined to store the details of a customer. Define a sub class Bill to compute the monthly telephone charge of the customer as per the chart given below: [10 Marks]

The details of both the classes are given below:
Class name: Detail
Data members / instance variables: name, address, telno, rent
Member functions: Detail(...), void show()
Class name: Bill
Data members / instance variables: n, amt
Member functions: Bill(...), void cal(), void show()
Specify the class Detail giving details of the constructor( ) and void show( ). Using the concept of inheritance, specify the class Bill giving details of the constructor( ), void cal( ) and void show( ).
THE MAIN( ) FUNCTION AND ALGORITHM NEED NOT BE WRITTEN.

Answer:

class Detail
{
    String name, address;
    long telno;
    double rent;

    public Detail(String n, String a, long t, double r)
    {
        name = n;
        address = a;
        telno = t;
        rent = r;
    }

    public void show()
    {
        System.out.println("Name: " + name);
        System.out.println("Address: " + address);
        System.out.println("Telephone Number: " + telno);
        System.out.println("Monthly Rental: " + rent);
    }
}

class Bill extends Detail
{
    int n;
    double amt;

    public Bill(String nm, String ad, long tn, double rt, int calls)
    {
        super(nm, ad, tn, rt);
        n = calls;
        amt = 0.0;
    }

    public void cal()
    {
        if(n <= 100)
        {
            amt = rent;
        }
        else if(n <= 200)
        {
            amt = rent + (n - 100) * 0.60;
        }
        else if(n <= 300)
        {
            amt = rent + 100 * 0.60 + (n - 200) * 0.80;
        }
        else
        {
            amt = rent + 100 * 0.60 + 100 * 0.80 + (n - 300) * 1.0;
        }
    }

    public void show()
    {
        super.show();
        System.out.println("Number of calls: " + n);
        System.out.println("Amount to be paid: " + amt);
    }
}

Teacher's Note:
a) Use the super keyword to invoke the parameterized constructor of the base class.
b) Calculate call charges slab-wise as specified in the table.

Question 13

(a) A linked list is formed from the objects of the class,
class node
{
    int p;
    String n;
    node next;
}
Write an Algorithm OR a Method to search for a name and display the contents of that node. The method declaration is given below:
void search(node start, String b) [4 Marks]

Answer:

public void search(node start, String b)
{
    node temp = start;
    boolean found = false;
    while(temp != null)
    {
        if(temp.n.equalsIgnoreCase(b))
        {
            System.out.println("Found - p: " + temp.p + ", n: " + temp.n);
            found = true;
            break;
        }
        temp = temp.next;
    }
    if(!found)
    {
        System.out.println("Name not found in the linked list.");
    }
}

Teacher's Note:
a) Traverse the linked list using a temporary pointer until it hits null.
b) Compare string values using equals or equalsIgnoreCase.

(b) What is the role of constants in complexity? Explain briefly with an example. [2 Marks]

Teacher's Note:
a) Emphasize that Big-O notation focuses on scaling behavior rather than exact execution time.
b) Mention that constant multipliers are dropped in order to classify algorithms into standard growth classes.

(c) Answer the following from the diagram of a Binary Tree given below:
[Figure: Binary tree diagram with root A, left child B having children C, D, E, and right child F having child G.]
(i) External nodes of the tree. [1 Mark]
(ii) Parent of node D. [1 Mark]
(iii) Inorder traversal of the tree. [1 Mark]
(iv) Right subtree of Node B. [1 Mark]

Answer:
(i) External nodes (Leaves): D, E, G
(ii) Parent of node D: C
(iii) Inorder traversal: D, C, E, B, A, G, F (or depending on exact left-right subtree structure shown)
(iv) Right subtree of Node B: E (or sub-nodes attached to the right of B)

Teacher's Note:
a) External nodes have no children.
b) Inorder traversal follows Left-Root-Right recursive order.