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

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

Part - I (20 Marks)

Question 1.

(a) Name and draw the logic gate represented by the following truth table, where A and B are inputs and X is the output. [1]

Answer:
XOR gate
[Figure: XOR gate symbol with inputs A and B entering an exclusive OR gate shape, producing output X]

Teacher's Note:
a) An XOR (Exclusive-OR) gate outputs 1 only when an odd number of inputs are 1.
b) Students must memorize truth tables for basic gates (AND, OR, NOT, NAND, NOR, XOR, XNOR).

(b) Write the canonical POS expression of: F(P, Q) = Π(0, 2) [1]

Answer:
(A + B).(A' + B)

Teacher's Note:
a) Pi (Π) denotes Product of Sums (POS), where maxterms corresponding to the given indices are multiplied.
b) For POS, a bit 0 represents the uncomplemented variable and 1 represents the complemented variable.

(c) Find the dual of: X.Y + X.Y' = X + 0 [1]

Answer:
(X + Y).(X + Y') = X.1

Teacher's Note:
a) To find the dual of a Boolean expression, replace AND (.) with OR (+), OR (+) with AND (.), 0 with 1, and 1 with 0.
b) Variables themselves remain unchanged when finding the dual.

(d) If F(A, B, C) = A'.B'.C' + A'.B.C' then find F' using De Morgan's Law. [1]

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

Teacher's Note:
a) De Morgan's first law states that the complement of a sum is equal to the product of the complements: (X + Y)' = X'.Y'.
b) Apply complement to the whole expression and break the terms using De Morgan's laws step by step.

(e) If A = "It is cloudy" and B = "It is raining", then write the proposition for [1]
(i) Contrapositive
(ii) Converse

Answer:
(i) If it is not raining then it is not cloudy.
(ii) If it is raining then it is cloudy.

Teacher's Note:
a) The contrapositive of implication P => Q is ~Q => ~P.
b) The converse of implication P => Q is Q => P.

Question 2.

(a) What is an Interface? How is it different from a class? [2]

Answer:
An interface is a reference type in Java that is similar to a class, but it contains only static constants and abstract methods. It is used to achieve multiple inheritance in Java.
Difference: A class can be instantiated and can contain instance variables and method bodies, whereas an interface cannot be instantiated and contains only abstract methods and public static final variables.

Teacher's Note:
a) Interfaces provide a fully abstract structure that implementing classes must override.
b) Mentioning multiple inheritance support is crucial for full marks.

(b) A matrix ARR[-4 ..... 6, 3 ....... 8] is stored in the memory with each element requiring 4 bytes of storage. If the base address is 1430, find the address of ARR[3][6] when the matrix is stored in Row Major Wise. [2]

Answer:
Given, L1 = -4, U1 = 6, L2 = 3, U2 = 8, w = 4, Base (B) = 1430.
Number of columns (n) = U2 - L2 + 1 = 8 - 3 + 1 = 6.
Row-major formula: Address = B + w * (n * (p - L1) + (q - L2))
Address = 1430 + 4 * (6 * (3 - (-4)) + (6 - 3))
= 1430 + 4 * (6 * 7 + 3)
= 1430 + 4 * (42 + 3)
= 1430 + 4 * 45
= 1430 + 180 = 1610.

Teacher's Note:
a) Always calculate the number of columns correctly using U - L + 1.
b) Pay close attention to negative lower bounds when calculating (p - L1).

(c) Convert the following infix notation to postfix form: [2]
(A + B * C) - (E * F / H) + J

Answer:
ABC*+EF*H/-J*
Step-by-step conversion:
1. (A + BC*) - (EF* / H) + J
2. (ABC*+) - (EF*H/) + J
3. ABC*+ EF*H/- + J
4. ABC*+ EF*H/-J*

Teacher's Note:
a) Operator precedence and associativity must be strictly followed during conversion.
b) Use stack-based dry run or parenthesization method to avoid errors.

(d) Compare the two complexities O(n²) and O(2ⁿ) and state which is better and why. [2]

Answer:
O(n²) is better than O(2ⁿ).
Reason: O(n²) represents polynomial time complexity, whereas O(2ⁿ) represents exponential time complexity. As the input size n grows, an exponential function grows at a much faster rate than a polynomial function, taking significantly more execution time and resources.

Teacher's Note:
a) Polynomial complexities scale much better than exponential complexities.
b) Providing a simple numerical comparison (e.g., for n = 8) secures full credit.

(e) State the difference between internal nodes and external nodes of a binary tree structure. [2]

Answer:
Internal nodes are nodes in a binary tree that have at least one child (i.e., non-leaf nodes), whereas external nodes (also known as leaf nodes) are nodes that do not have any children (i.e., both left and right pointers are null).

Teacher's Note:
a) External nodes form the fringe or bottom level of the tree hierarchy.
b) Internal nodes include the root node as long as it is not the only node in the tree.

Question 3.

The following function Mystery() is a part of some class. What will the function Mystery() return when the value of num=43629, x=3 and y=4 respectively? Show the dry run/working. [5]

int Mystery (int num, int x, int y)
{
if(num<10)
return num;
else
{
int z = num % 10;
if(z%2 == 0)
return z*x + Mystery (num/10, x, y);
else
return z*y + Mystery(num/10, x, y);
}
}

Answer:
The function returns 76.
Dry Run / Working:
- Mystery(43629, 3, 4): z = 9 (odd) -> returns 9*4 + Mystery(4362, 3, 4) = 36 + 40 = 76
- Mystery(4362, 3, 4): z = 2 (even) -> returns 2*3 + Mystery(436, 3, 4) = 6 + 34 = 40
- Mystery(436, 3, 4): z = 6 (even) -> returns 6*3 + Mystery(43, 3, 4) = 18 + 16 = 34
- Mystery(43, 3, 4): z = 3 (odd) -> returns 3*4 + Mystery(4, 3, 4) = 12 + 4 = 16
- Mystery(4, 3, 4): num < 10 -> returns 4.

Teacher's Note:
a) Trace recursive calls from bottom to top or top to bottom clearly showing each step.
b) Check whether the extracted digit is even or odd to apply correct multiplication factors (x or y).

Part - II (50 Marks)

SECTION - A

Answer any two questions.

Question 4.

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

Answer:
(i) F(A, B, C, D) = B'D' + BC' + B'C
[Figure: 4-variable K-map for minterms 0, 2, 3, 4, 5, 8, 10, 11, 12, 13 with Quad 1 covering m0, m2, m8, m10 (B'D'), Quad 2 covering m0, m4, m12, m8 (C'D'), and Quad 3 covering m3, m2, m11, m10 (B'C). Resulting simplified expression: B'D' + BC' + B'C]
(ii) [Figure: Logic gate diagram using only NAND gates for B'D' + BC' + B'C, taking inputs B, B', C, C', D, D']

Teacher's Note:
a) Group adjacent 1s in powers of 2 (octets, quads, pairs) to achieve maximum reduction.
b) Use double inversion and De Morgan's law to convert an AND-OR expression into an all-NAND implementation.

(b) Given the Boolean function : F(P, Q, R, S) = Π(0, 1, 2, 8, 9, 11, 13, 15).
(i) Reduce the above expression by using a 4-variable Karnaugh map, showing the various groups (i.e, octal, quads and pairs). [4]
(ii) Draw the logic gate diagram for the reduced expression using only NOR gates. Assume that the variables and their complements are available as inputs. [1]

Answer:
(i) F(P, Q, R, S) = (Q + R).(P' + S').(P + Q + S)
[Figure: 4-variable K-map for maxterms 0, 1, 2, 8, 9, 11, 13, 15 with Quad 1 covering m0, m1, m8, m9 (Q + R), Quad 2 covering m13, m15, m9, m11 (P' + S'), and Pair covering m0, m2 (P + Q + S)]
(ii) [Figure: Logic gate diagram using only NOR gates for (Q + R).(P' + S').(P + Q + S)]

Teacher's Note:
a) For Product of Sums (POS), group 0s in the K-map.
b) Ensure all maxterms are covered with minimum number of groups.

Question 5.

(a) How is a decoder different from a multiplexer? Write the truth table and draw the logic circuit diagram for a 3 to 8 decoder and explain its working. [5]

Answer:
Difference: A multiplexer selects one of many input lines and forwards it to a single output line, whereas a decoder converts n binary input lines to up to 2ⁿ unique output lines.
[Figure: Truth table for 3-to-8 decoder mapping 3 inputs (X, Y, Z) to 8 outputs (D0 to D7)]
[Figure: Logic circuit diagram of a 3-to-8 decoder using AND/NAND gates and NOT gates for inputs X, Y, Z]
Working: A 3-to-8 decoder takes 3 binary inputs and activates exactly one of the 8 output lines corresponding to the binary value of the inputs.

Teacher's Note:
a) Clearly state the input-output relationship for multiplexers and decoders.
b) Ensure the truth table lists all 8 combinations from 000 to 111.

(b) From the logic circuit diagram given below, derive the Boolean expression and simplify it to show that it represents a logic gate. Name and draw the logic gate. [3]

[Figure: Logic circuit with inputs X, Y, Z where X and Y go into an OR gate (X + Y), Z goes into a NOT gate or directly, and output F = (X + Y).XZ]

Answer:
Derived Expression: F = (X + Y) . XZ
= (X.X.Z) + (X.Y.Z)
= X.Z + X.Y.Z (since X.X = X)
= X.Z (1 + Y)
= X.Z (since 1 + Y = 1)
This represents an AND gate with inputs X and Z.
[Figure: Standard AND gate symbol with inputs X and Z and output X.Z]

Teacher's Note:
a) Apply Boolean laws step by step to simplify complex expressions.
b) Recognize standard algebraic simplifications like absorption and distributive laws.

(c) Using a truth table, state whether the following proposition is a Tautology, Contradiction or Contingency: [2]
~(P => Q) <=> (~P ∨ Q)

Answer:
Truth Table:
P | Q | P => Q | ~(P => Q) | ~P | ~P ∨ Q | ~(P => Q) <=> (~P ∨ Q)
0 | 0 | 1 | 0 | 1 | 1 | 0
0 | 1 | 1 | 0 | 1 | 1 | 0
1 | 0 | 0 | 1 | 0 | 0 | 0
1 | 1 | 1 | 0 | 0 | 1 | 0
Since the final column contains only False (0) values, the proposition is a Contradiction (Fallacy).

Teacher's Note:
a) A Tautology contains all True values, a Contradiction contains all False values, and a Contingency contains a mix of both.
b) Construct intermediate columns carefully for conditional, biconditional, and negation operations.

Question 6.

(a) The owner of a company pays the bonus to his salesmen as per the criteria are given below: [5]
If the salesman works overtime for more than 4 hours but does not work on off days/holidays.
OR
If the salesman works when festival sales are on and updates showroom arrangements.
OR
If the salesman works on an off day/holiday when the festival sales are on.
The inputs are: O (Overtime > 4 hrs), F (Festival sales on), H (Working on off day/holiday), U (Updates showroom arrangements).
Draw the truth table for the inputs and outputs given above and write the POS expression for X(O, F, H, U).

Answer:
[Figure: Truth table with 16 rows for inputs O, F, H, U and output X based on the given conditions]
POS Expression: X(O, F, H, U) = Π(0, 4, 6, 8, 9, 12, 14, 15)

Teacher's Note:
a) Translate each condition into logical terms before constructing the truth table.
b) Ensure all 16 rows of 4-variable inputs are correctly evaluated for output X.

(b) What is a half adder? Write the truth table and derive an SOP expression for sum and carry for a half adder. [3]

Answer:
A half adder is a digital combinational circuit that performs addition of two single-bit binary numbers and produces two outputs: Sum and Carry.
Truth Table:
x | y | C | S
0 | 0 | 0 | 0
0 | 1 | 0 | 1
1 | 0 | 0 | 1
1 | 1 | 1 | 0
SOP Expressions:
Sum (S) = x'y + xy'
Carry (C) = xy

Teacher's Note:
a) Half adder cannot take a carry-in from a previous addition.
b) Sum is equivalent to XOR operation and Carry is equivalent to AND operation.

(c) Simplify the following expression, using Boolean laws: [2]
(X + Z).(X.Y + Y.Z') + X.Z + Y

Answer:
= (X + Z).(Y.Z') + X.Z + Y
= X.Y.Z' + Z.Z' + X.Z + Y
= X.Y.Z' + 0 + X.Z + Y
= Y

Teacher's Note:
a) Apply distributive and complementarity laws carefully at each step.
b) Recognize absorption and identity laws to reduce complex expressions to a single variable.

SECTION - B

Answer any two questions.

Question 7.

Design a class ArmNum to check if a given number is an Armstrong number or not. [10]

Answer:
import java.io.*;
import java.util.*;
class ArmNum
{
    private int n;
    private int l;
    public ArmNum(int nn)
    {
        n = nn;
        l = 0;
        for(int i = n; i != 0; i /= 10)
            l++;
    }
    public int sumPow(int i)
    {
        if(i < 10)
            return (int)Math.pow(i, l);
        return (int)Math.pow(i % 10, l) + sumPow(i / 10);
    }
    public void isArmstrong()
    {
        if(n == sumPow(n))
            System.out.println(n + " is an Armstrong number.");
        else
            System.out.println(n + " is not an Armstrong number.");
    }
    public static void main(String args[]) throws IOException
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("N = ");
        int num = sc.nextInt();
        ArmNum obj = new ArmNum(num);
        obj.isArmstrong();
    }
}

Teacher's Note:
a) Recursive calculation of sum of digits raised to the power of length must have a proper base case.
b) Ensure data members and methods match the specifications given in the question.

Question 8.

Design a class MatRev to reverse each element of a matrix. [10]

Answer:
import java.io.*;
import java.util.*;
class MatRev
{
    private int arr[][];
    private int m;
    private int n;
    public MatRev(int mm, int nn)
    {
        m = mm;
        n = nn;
        arr = new int[m][n];
    }
    public void fillArray() throws IOException
    {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter matrix elements:");
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                arr[i][j] = sc.nextInt();
            }
        }
    }
    public int reverse(int x)
    {
        int rev = 0;
        for(int i = x; i != 0; i /= 10)
            rev = rev * 10 + i % 10;
        return rev;
    }
    public void revMat(MatRev p)
    {
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                this.arr[i][j] = reverse(p.arr[i][j]);
            }
        }
    }
    public void show()
    {
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                System.out.print(arr[i][j] + "\t");
            }
            System.out.println();
        }
    }
    public static void main(String args[]) throws IOException
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter number of rows: ");
        int x = sc.nextInt();
        System.out.print("Enter number of columns: ");
        int y = sc.nextInt();
        MatRev obj1 = new MatRev(x, y);
        MatRev obj2 = new MatRev(x, y);
        obj1.fillArray();
        obj2.revMat(obj1);
        System.out.println("Original Matrix is:");
        obj1.show();
        System.out.println("Matrix with reversed elements:");
        obj2.show();
    }
}

Teacher's Note:
a) Object-oriented matrix operations require passing object references (MatRev p) to access data from another object.
b) Double loops are necessary for traversing 2D arrays.

Question 9.

A class Rearrange has been defined to modify a word by bringing all the vowels in the word at the beginning followed by the consonants. [10]

Answer:
import java.io.*;
import java.util.*;
class Rearrange
{
    private String wrd;
    private String newwrd;
    public Rearrange()
    {
        wrd = new String();
        newwrd = new String();
    }
    public void readword() throws IOException
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter the word: ");
        wrd = sc.next();
    }
    public void freq_vow_con()
    {
        wrd = wrd.toUpperCase();
        int v = 0, c = 0;
        for(int i = 0; i < wrd.length(); i++)
        {
            char ch = wrd.charAt(i);
            if(Character.isLetter(ch))
            {
                switch(ch)
                {
                    case 'A':
                    case 'E':
                    case 'I':
                    case 'O':
                    case 'U':
                        v++;
                        break;
                    default:
                        c++;
                }
            }
        }
        System.out.println("Frequency of vowels: " + v);
        System.out.println("Frequency of consonants: " + c);
    }
    public void arrange()
    {
        String v = "";
        String c = "";
        wrd = wrd.toUpperCase();
        for(int i = 0; i < wrd.length(); i++)
        {
            char ch = wrd.charAt(i);
            if(Character.isLetter(ch))
            {
                switch(ch)
                {
                    case 'A':
                    case 'E':
                    case 'I':
                    case 'O':
                    case 'U':
                        v += ch;
                        break;
                    default:
                        c += ch;
                }
            }
        }
        newwrd = v + c;
    }
    public void display()
    {
        System.out.println("Original word: " + wrd);
        System.out.println("Rearranged word: " + newwrd);
    }
    public static void main(String args[]) throws IOException
    {
        Rearrange obj = new Rearrange();
        obj.readword();
        obj.freq_vow_con();
        obj.arrange();
        obj.display();
    }
}

Teacher's Note:
a) String manipulation methods like charAt() and concatenation should be handled carefully.
b) Ensure all vowels (A, E, I, O, U) are explicitly accounted for in switch-case statements.

SECTION - C

Answer any two questions.

Question 10.

A superclass Record contains names and marks of the students in two different single dimensional arrays. Define a subclass Highest to display the names of the students obtaining the highest mark [5]

Answer:
class Highest extends Record
{
    private int ind;
    public Highest(int cap)
    {
        super(cap);
    }
    public void find()
    {
        ind = 0;
        for(int i = 0; i < size; i++)
        {
            if(m[i] > m[ind])
            {
                ind = i;
            }
        }
    }
    public void display()
    {
        super.display();
        System.out.println("Highest marks are: " + m[ind]);
        System.out.println("Students who score the highest marks are:");
        for(int i = 0; i < size; i++)
        {
            if(m[i] == m[ind])
            {
                System.out.println(n[i]);
            }
        }
    }
}

Teacher's Note:
a) Use super() to invoke the parameterized constructor of the base class.
b) Handle cases where multiple students might share the highest mark by iterating and checking equality with the highest score.

Question 11.

A linear data structure enables the user to add an address from rear end and remove address from front. Define a class Diary with the following details :
Class name: Diary
Data members: Q[] (array to store addresses), size, start, end.
(a) Specify the class Diary giving details of the functions void pushadd(String) and String popadd(). Assume that the other functions have been defined. [4]
(b) Name the entity used in the above data structure arrangement. [1]

Answer:
(a)
class Diary
{
    public void pushadd(String n)
    {
        if(end == size - 1)
        {
            System.out.println("NO SPACE");
        }
        else
        {
            if(start == -1)
                start = 0;
            Q[++end] = n;
        }
    }
    public String popadd()
    {
        if(start == -1 || start > end)
        {
            return "?????";
        }
        else
        {
            String val = Q[start++];
            return val;
        }
    }
}
(b) Queue

Teacher's Note:
a) A queue follows FIFO (First In, First Out) principle where insertion happens at the rear and deletion happens at the front.
b) Boundary conditions like overflow ("NO SPACE") and underflow ("?????") must be checked.

Question 12.

(a) A linked list is formed from the objects of the class Node. The class structure of the Node is given below: [2]
class Node { int num; Node next; }
Write an Algorithm OR a Method to find and display the sum of even integers from an existing linked list.
The method declaration is as follows: void SumEvenNode(Node str)
(b) Answer the following questions from the diagram of a Binary Tree given below:
(i) Write the pre-order traversal of the above tree structure. [1]
(ii) State the size of the tree. [1]
(iii) Name the siblings of the nodes E and G [1]

Answer:
(a)
void SumEvenNode(Node str)
{
    int sum = 0;
    Node temp = str;
    while(temp != null)
    {
        if(temp.num % 2 == 0)
        {
            sum += temp.num;
        }
        temp = temp.next;
    }
    System.out.println("Sum of even integers: " + sum);
}
(b)
(i) A -> E -> G -> I -> C -> H -> B -> D -> F
(ii) The size of the tree is 9 (total number of nodes).
(iii) Sibling of E is B. Sibling of G is C.

Teacher's Note:
a) Linked list traversal requires checking for null pointer termination.
b) Pre-order traversal visits nodes in Root -> Left -> Right order.