## Year 2010

0

**ISC 2010**

**COMPUTER SCIENCE PAPER 1**

**THEORY**

**Question 1.**

a) If X=A’BC + AB’C + ABC + A’BC’ then find the value of X when A=1; B=0; C=1

b) Verify if, P.(~P+Q’)=(P→Q) using truth table.

c) Draw the logic circuit of NOR using NAND gate only.

d) Convert the following function into its Canonical Sum-Of_products form:

F(X,Y,Z)= Σ(0,1,5,7)

e) Show that the dual of P’QR’ + PQ’R + P’Q’R is equal to the complement of PQ’R + Q(P’R’ + PR’)

[ 2 x 5 = 10 ]

**Question 2.**

a) State the difference between an interface and a class.

b) Convert the following infix notation to postfix notation.

( A+B) / C * (D +E)

c) A character array B[7][6] has a base address 1046 at 0,0. Calculate the address at B[2][3] if the

array is stored Column Major wise. Each character requires 2 bytes of storage.

d) State the use of exception handling. Name the two types of exceptions.

e) i) What is the worst-case complexity of the following code segment :

for(int i=0;i<N;i++)

{

Sequence of statements

}

for(int j=0;j<M;j++)

{

Sequence of statements

}

ii) How would the complexity change if the second loop went to N instead of M?

[ 2 x 5 = 10 ]

**Question 3.**

a) The following function numbers(int) and numbers1(int) are a part of some class. Answer the

questions given below showing the dry run/working:

public void numbers(int n)

{

if(n>0)

{

System.out.print(n+” “);

numbers(n-2);

System.out.print(n+” “);

}

}

public String numbers1(int n)

{

if(n<=0)

return “”;

return(numbers(n-1)+n+” “;

}

i) What will be the output of the function numbers(int n) when n=5? [ 2 ]

ii) What will the function numbers1(int n) return when n=6? [ 2 ]

iii) State in one line what is the function numbers1(int) doing apart from recursion? [ 1 ]

b) The following function is a part of some class. It sorts the array a[] in ascending order using

insertion sort technique. There are some places in the code marked by ?1?, ?2?, ?3?, ?4?, ?5?

which must be replaced by expression/ statement so that the function works correctly.

void insertsort(int a[])

{

int m= ?1?;

int b,I,t;

for(i=?2?;i<m;i++)

{

t=a[i];

b=i-1;

while(?3?>=0 && t<a[b])

{

a[b+1]= a[b];

?4?;

}

?5?=t;

}

}

i) What is the expression or statement at ?1? [ 1 ]

ii) What is the expression or statement at ?2? [ 1 ]

iii) What is the expression or statement at ?3? [ 1 ]

iv) What is the expression or statement at ?4? [ 1 ]

v) What is the expression or statement at ?5? [ 1 ]

**Part II**

**Section A**

**Answer any three questions**

**Question 4.**

a) Given F(P,Q,R,S)= Σ(0,2,5,7,8,10,11,13,14,15)

i) Reduce the above expression by using 4- variable K-Map, showing the various groups (

i.e. octals, quads and pairs).

ii) Draw the logic gate diagram of the reduced expression using NAND gate only.

b) Given F(A,B,C,D)=

(A+B+C+D).(A+B+C+D’).(A+B+C’+D’).(A+B+C’+D).(A+B’+C+D’).(A+B’+C’+D’).(A’+B+C+D).(A’+B+C’+

D)

i) Reduce the above expression by using 4- variable K-Map, showing the various groups (

i.e. octals, quads and pairs).

ii) Draw the logic gate diagram of the reduced expression using NOR gate only.

[ 5 x 2 =10 ]

**Question 5.**

A government institution intends to award a medal to a person who qualifies any one of the following

criteria:

The person should have been an Indian citizen and had lost his/her life in a war but has not completed

25 years of service.

OR

The person must be an Indian citizen and has served the nation for a continuous period of 25 years or

more but has not lost his/her life in a war.

OR

The person is not an Indian citizen but has taken active part in activities for the upliftment of the nation.

The inputs are:

INPUTS

A The person is/was an Indian citizen

B Has a continuous service of more than 25 years

C Lost his/her life in a war

D Taken part in activities for upliftment of the nation

Output

X Denotes eligible for medal [ 1 indicates YES ad 0 indicates NO in all cases]

a) Draw the truth table for the inputs and outputs given above and write the POS expression for

X(A,B,C,D)..

b) Reduce X(A,B,C,D) using Karnaugh’s map.

Draw the logic gate diagram for the reduced POS expression for X(A,B,C,D) 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 x 2 = 10]

**Question 6.**

a) What are Maxterms? Convert the following function as a Product of Maxterms:

F(P,Q,R)= (P+Q).(P’+R’)

b) State whether the following expression is a Tautology or Contradiction with the help of a truth

table:

(X↔Z). [(X→Y).(Y→Z)]

c) What is a Multiplexer? Draw the truth table and logic diagram of a 8:1 multiplexer.

[ 2+3+5=10]

Question 7.

a) Draw the circuit diagram for a 3 to 8 decoder.

b) Draw the truth table for a half adder. Also derive a POS expression for the half adder and draw

its logic circuit.

c) Simplify the following expression and also draw the circuit for the reduced expression. [ Show

the step wise working along with the laws used.]

F= X. (Y+Z.(X.Y +X.Z)’)

[3+3+4=10]

**Section B**

**Answer any 2 questions.**

**Each program should be written in such a way that it clearly depicts the logic of the problem. This can be**

**achieved by using mnemonic names and comments in the program.**

**Question 8.**

The co-ordinates of a point P on a two-dimensional plane can be represented by P(x,y) with x as the x

co-ordinate and y as the y co-ordinate. The co-ordinates of midpoint of two points P1(x1,y1) and

P2(x2,y2) can be calculated as P(x,y) where:

x=x1+x2/2, y=y1+y2/2

Design a class Point with the following details:

Class name : Point

Data members

x : stores the x co-ordinate

y : stores the y co-ordinate

Member functions:

Point() : constructor to initialize x=0 and y=0

void readPoint() : accepts the co-ordinates x and y of a point

Point midpoint(Point A, Point B): calculates and returns the midpoint of the two points A and B.

void displaypoint() : displays the co-ordinates of a point

Specify the class Point giving details of the constructor( ), member functions void readPoint(), Point

midpoint(Point, Point) and void displaypoint() along with the main function to create an object and call

the functions accordingly to calculate the midpoint between any two given points.

[ 10 ]

**Question 9.**

Input a word in uppercase and check for the position of the first occurring vowel and perform the

following operation.

i) Words that begin with a vowel are concatenated with “Y” . For example, EUROPE becomes

EUROPEY.

ii) Words that contain a vowel in between should have the first part from the position of the

vowel till end, followed by the part of the string from beginning till position of the vowel and

is concatenated by “C”. For example PROJECT becomes OJECTPRC.

iii) Words which do not contain a vowel are concatenated with “N”. For example, SKY becomes

SKYN.

Design a class Rearrange using the description of the data members and member functions given below:

Class name : Rearrange

Data members

Txt : to store a word

Cxt : to store the rearranged word

len : to store the length of the word

Member functions

Rearrange() : constructor to initialize the instance variables

void readword() : to accept the word input in UPPERCASE

void convert() : converts the word into its changed form and stores it in

string Txt

void display() : displays the original and the changed word

Specify the class Rearrange giving the details of the constructor(), void readword(), void convert() and

void display(). Define a main function to create an object and call the function accordingly to enable the

task. [ 10 ]

**Question 10.**

Design a class Change to perform string related operations. The details of the class are given below:

Class name : Change

Data members

str : stores the word

newstr : stores the changed word

len : stores the length of the word

Member functions

Change() : default constructor

void inputword() : to accept a word

char caseconvert(char ch) : converts the case of the character and returns it

void recchange(int) : extracts characters using recursive technique and

changes its case using caseconvert() and forms a new

word

void display() : displays both the words

a) Specify the class Change, giving details of the constructor(), member functions void inputword(),

char caseconvert(char ch), void recchange(int) and void display(). Define the main function to

create an object and call the functions accordingly to enable the above change in the given

word. [ 8 ]

b) Differentiate between finite and infinite recursion. [ 2 ]

**Section C**

**Answer any 2 questions.**

**Each program/algorithm should be written in such a way that it clearly depicts the logic of the problem**

**step wise. This can also be achieved by using pseudo codes.**

**(Flowcharts are not required)**

**The programs must be written in Java.**

**The algorithm must be written in general standard form wherever required.**

**Question 11.**

A super class Worker has been defined to store the details of a worker. Define a sub class Wages to

compute the monthly wages for the worker. The details of both the classes are given below:

Class name : Worker

Data members :

Name : to store the name of the worker

Basic : to store the basic pay in decimal

Member functions

Worker(….) : parameterized constructor to assign values to

the instance variables

void display() : display worker details

class name : Wages

Data members

hrs : stores the hours worked

rate : stores rate per hour

wage : stores the overall wage of the worker

Member functions

Wages(….) : parameterized constructor to assign values to

the instance variables of both classes

double overtime( ) : calculates and returns the overtime amount as

(hours * rate )

void display() : calculates the wage using the formula

wage=overtime amount +basic pay and displays

it along with other details

Specify the class Worker giving details of the constructor() and void display(). Using the concept of

inheritance, specify the class Wages giving details of the constructor(), double overtime() and void

display(). The main function need not be written.

[ 10 ]

**Question 12.**

Define a class Repeat which allows the user to add elements from one end (rear) and remove elements

from one end (rear) and remove elements from the other end (front) only.

The following details of the class Repeat are given below:

Class name : Repeat

Data members

st[] : an array to hold a maximum of 100 integer

elements

cap : stores the capacity of the array

f : to point to the index of the front

r : to point to the index of the rear

Member functions

Repeat(int m) : constructor to initialize the data members

cap=m, f=0, r=0 and to create the integer array

void pushvalue(int v) : to add integers from the rear index if possible

else display the message “overflow”

int popvalue() : to remove and return element from the front, if

array is empty then return -9999

void disp() : displays the elements present in the list

a) Specify the class Repeat giving details of the constructor(int), member function void

pushvalue(int), int popvalue() and void disp(). The main function need not be written. [ 8 ]

b) What is the common name of the entity described above? [ 1 ]

c) On what principle does this entity work? [ 1 ]

**Question 13.**

a) A linked list is formed from the objects of the class,

class ListNodes

{

int item;

ListNodes next;

}

Write a method OR an algorithm to compute and return the sum of all integers items stored in

the linked list. The method declaration is specified below:

int listsum(ListNodes start);

b) What is Big ‘O’ notation? State its significance.

c) Answer the following from the diagram of a Binary tree given below:

8

i) Name the parent node of E. [ 1 ]

ii) Write the postorder tree traversal. [ 1 ]

iii) Write the internal nodes of the tree. [ 1 ]

iv) State the level of the root of the tree. [ 1 ]

**************