Computer Science
Paper 1 (Theory)
Part I
While working
questions in this part, indicate briefly your working and reasoning wherever
required.
Question 1.
a)
Using truth table, verify the following expression: X + ( Y + Z ) = (
X + Y ) + Z
Also state the law.
b)
Given, F(X, Y, Z)= (X’+ Y’). (Y + Z’)
write the function in canonical product of sum
form.
c)
Draw the truth table and logic circuit for a 2 – input XNOR gate.
d)
Find the complement of the following expression:
X’ + XY’
e)
If (X → Y) then write its:
i) Converse
ii) Contra positive
[ 2 x 5 = 10]
Question 2.
a) Differentiate between the keyword extends
and implements.
Ans: extends keyword is used to inheritance, a sub class inherits the super class using the extends keyword. implements keyword is used by a class to implement interfaces.
b)
State
how a binary tree is a recursive data structure.
Ans: Binary tree is
known as a recursive data structure as the structure is not linear and to add,
delete or search any node in the structure needs recursive function.
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
B[7][3] is 1060, determine the value x where the matrix is stored in column
major wise.
Ans: Address calculating formula of a matrix when the matrix is stored in column major order is : Base Address + w*(E2*L1+E1) where E1 is the effective index of 1st dimension, E2 is the effective index of 2nd dimension, L1 is the length of 1st dimension and L2 is the length of 2nd dimension.
Ans: Address calculating formula of a matrix when the matrix is stored in column major order is : Base Address + w*(E2*L1+E1) where E1 is the effective index of 1st dimension, E2 is the effective index of 2nd dimension, L1 is the length of 1st dimension and L2 is the length of 2nd dimension.
For 2nd case
E1=7
E2=3
1012 + 2 * ((3-1) * 10 + (7-x))=1060
1012 + 40 + 14 – 2x = 1060
2x=6
X=3
d) Convert the following infix notation into
its postfix form:
A + (( B+ C) + ( D + E) * F ) / G
Ans: A BC+DE+F*G/+
Ans: A BC+DE+F*G/+
e)
What is a constructor? State one difference between a constructor and
any other member function of a class.
Ans: Constructor is a special function which must be executed to create an object.
Ans: Constructor is a special function which must be executed to create an object.
One difference
between constructor and other member method is that constructor name should be
same as the class name where other method should have a different name.
[ 2 x 5 = 10]
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:
Download eBook on BlueJ
class Trial
{
void
bubblesort(intarr[])
{
inti,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?
ii)
What is the
expression or statement at ?2?
iii)
What is the
expression or statement at ?3?
iv)
What is the
expression or statement at ?4?
v)
What is the
expression or statement at ?5?
Ans:
Ans:
i) arr.length-1
ii)
arr.length-i-1
iii)
arr[j+1]
iv)
arr[j]
v)
temp
[ 1 x 5 = 5 ]
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:
class Trial1
{
public void witty(String n, int p)
{
if(p<0 span="">
System.out.println("");
else
{
System.out.println(n.charAt(p)+".");
witty(n,p-1); System.out.print(n.charAt(p));
}
}
}
[ 5 ]
Ans:
C. Stack of pending statements
N. S
E. C
I.
I
C. E
S. N
C
So
the output:
C.
N.
E.
I.
C.
S.
SCIENC
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)= ∑(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.
octals, quads and pairs).
ii) Draw the logic gate
diagram of the reduced expression. Assume that the variables and their
complements are available as inputs.
[ 4 + 1 = 5 ]
b)
Given the Boolean function F(P,Q,R,S)= π(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.
octals, quads and pairs).
ii) Draw the logic gate
diagram of the reduced expression. Assume that the variables and their
complements are available as inputs.
[ 4 + 1 = 5 ]
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 :
INPUTS
S Student is of the same school
P Has passed the Class X Board Examination
with more than 60% marks.
C Has taken active
part in co-curricular activities.
T Has participated in
sports at the National Level.
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.
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 x 2 = 10]
Question 6.
a) Verify
algebraically if,
X’Y’Z’ + X’Y’Z + X’YZ + X’YZ’ + XY’Z’ + XY’Z = X’
+ Y’
[ 2 ]
b)
Represent the Boolean expression X + YZ’ with the help of NOR gates
only.
[ 2 ]
c) Define
the terms contingency, contradiction and tautology.
[ 3 ]
d)
Consider the following truth table where A and B are two inputs and X is
the output:
A
|
B
|
X
|
|||||
0
|
0
|
0
|
|||||
0
|
1
|
1
|
|||||
1
|
0
|
1
|
|||||
1
|
1
|
0
|
|||||
[ 2 ]
|
|||||||
i)
|
Name and draw the logic gate for the given
truth table.
|
||||||
ii)
|
Write the POS of X(A,B)
|
[ 1 ]
|
|||||
Question 7.
a) Define multiplexer and state
one of its uses. Draw the logic gate diagram for 4:1Multiplexer.
[ 4 ]
b) State how a half adder is
different from a full adder. Also give their respective uses.
[ 3 ]
c) Minimize the following
expression using Boolean laws:
Q(Q’+P).R.(Q+R) [ 3 ] Also draw the logic
gate for the reduced Boolean expression.
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.
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:
Class
Name
|
:
|
Combine
|
Data
members
|
||
com[ ]
|
:
|
integer array
|
size
|
:
|
size of the array
|
Member
functions/methods
|
||
Combine(intnn)
|
:
|
parameterized constructor to assign
size = nn
|
voidinputarray( )
|
:
|
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 the
|
||
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.
Ans:
Ans:
[ 10 ]
import java.io.*;
class Combine
{
int com[], size;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
Combine(int nn)
{
size=nn;
com=new int[size];
}
void inputarray( ) throws Exception
{
int i;
for(i=0;i< size;i++)
{
System.out.print("\nEnter Value:");
com[i]=Integer.parseInt(br.readLine());
}
}
void sort()
{
int i,j,t;
for(i=0;i< size-1;i++)
{
for(j=i+1;j< size;j++)
{
if(com[i] >com[j])
{
t=com[i];
com[i]=com[j];
com[j]=t;
}
}
}
}
void mix(Combine A, Combine B)
{
int i,x=0;
for(i=0;i< A.size;i++)
com[x++]=A.com[i];
for(i=0;i< B.size;i++)
com[x++]=B.com[i];
}
void display( )
{
for(int i=0;i< size;i++)
System.out.print(" "+com[i]);
}
public static void main(String args[]) throws Exception
{
Combine A,B,C;
int s;
A=new Combine(5);
B=new Combine(6);
C=new Combine(11);
System.out.print("\nValues for 1st array:");
A.inputarray();
System.out.print("\nValues for 2nd array:");
B.inputarray();
A.sort();
B.sort();
C.mix(A,B);
C.sort();
System.out.print("\nValues of 1st array:");
A.display();
System.out.print("Values of 2nd array:");
B.display();
System.out.print("Values of 3rd array:");
C.display();
}
}
class Combine
{
int com[], size;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
Combine(int nn)
{
size=nn;
com=new int[size];
}
void inputarray( ) throws Exception
{
int i;
for(i=0;i< size;i++)
{
System.out.print("\nEnter Value:");
com[i]=Integer.parseInt(br.readLine());
}
}
void sort()
{
int i,j,t;
for(i=0;i< size-1;i++)
{
for(j=i+1;j< size;j++)
{
if(com[i] >com[j])
{
t=com[i];
com[i]=com[j];
com[j]=t;
}
}
}
}
void mix(Combine A, Combine B)
{
int i,x=0;
for(i=0;i< A.size;i++)
com[x++]=A.com[i];
for(i=0;i< B.size;i++)
com[x++]=B.com[i];
}
void display( )
{
for(int i=0;i< size;i++)
System.out.print(" "+com[i]);
}
public static void main(String args[]) throws Exception
{
Combine A,B,C;
int s;
A=new Combine(5);
B=new Combine(6);
C=new Combine(11);
System.out.print("\nValues for 1st array:");
A.inputarray();
System.out.print("\nValues for 2nd array:");
B.inputarray();
A.sort();
B.sort();
C.mix(A,B);
C.sort();
System.out.print("\nValues of 1st array:");
A.display();
System.out.print("Values of 2nd array:");
B.display();
System.out.print("Values of 3rd array:");
C.display();
}
}
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:
Class Name
|
:
|
VowelWord
|
Data
members
|
||
str
|
:
|
to store a sentence
|
freq
|
:
|
to store the frequency of words
beginning with a
|
vowel.
|
||
Member
functions
|
||
VowelWord()
|
:
|
constructor to initialize data members
to legal initial
|
values.
|
||
voidreadstr()
|
:
|
to accept a sentence.
|
voidfreq_vowel(
)
|
:
|
counts the frequency of the words
beginning 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 defing the main function to create an
object and call the methods accordingly to enable the task.
[ 10 ]
Ans:
class VowelWord
{
int freq;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String str;
VowelWord()
{
freq=0;
str="";
}
void readstr( ) throws Exception
{
System.out.print("\nEnter the sentence:");
str=br.readLine();
}
void freq_vowel()
{
String s,s1;
int i;
freq=0;
s=str.toUpperCase();
while(true)
{
i=s.indexOf(" ");
if(i<0 font="">
break;
s1=s.substring(0,i);
s=s.substring(i+1);
switch(s1.charAt(0))
{
case 'A':
case 'E':
case 'I':
case 'O':
case 'U':
freq++;
}
}
switch(s.charAt(0))
{
case 'A':
case 'E':
case 'I':
case 'O':
case 'U':
freq++;
}
}
void display( )
{
System.out.print("\nEntered sentence:"+str + " and frequency of words started with vowel="+freq);
}
public static void main(String args[]) throws Exception
{
VowelWord ob=new VowelWord();
ob.readstr();
ob.freq_vowel();
ob.display();
}
}
Question 10.
A happy number is a
number in which the eventual sum of the square of the digits of the number is
equal to 1.
Example :
28 = (2)2 + ( 8 )2 = 4 + 64 = 68
68 = (6)2 + ( 8)2 = 36 + 64 = 100
100 = ( 1 )2 + ( 0 )2 + ( 0 )2 = 1 + 0 + 0 = 1
Hence 28 is a happy
number.
Example :
12 = (1)2 + (2)2 = 1 + 4 = 5 Hence
12 is not a happy number.
Design a
class Happy to check if a given number is a happy number. Some of the members
of the class are given below:
Class Name
|
:
|
Happy
|
Data Members
|
||
n
|
:
|
stores the number
|
Member functions:
|
Happy( )
voidgetnum(intnn) intsum_sq_digits(int x)
voidishappy()
:
constructor
to assign 0 to n
:
to assign
the parameter value to the number n = nn
:
returns the sum of the square of the digits of the number x, using the
recursive technique.
:
checks if the given number is a happy by calling the
functionsum_sq_digits(int) and displays an appropriate message.
Specify the class
Happy giving details of the constructor( ), void getnum( int),
intsum_sq_digits(int) and void ishappy(). Also define a main function to create
an object and call the methods to check for a happy number.
Ans:
import java.io.*;
class Happy
{
int n,j;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
Happy( )
{
n=0;
}
void getnum(int nn)
{
n=nn;
}
int sum_sq_digits(int x)
{
if(x/10==0)
return x*x;
else
return (int)Math.pow(x%10,2)+ sum_sq_digits(x/10);
}
void ishappy()
{
while((j=sum_sq_digits(n))/10!=0)
{
n=j;
}
if ( j==1)
System.out.println("It is a happy number ");
else
System.out.println("Not a happy number");
}
public static void main(String args[]) throws Exception
{
Happy ob = new Happy();
int x;
System.out.println("Enter the number:");
x=Integer.parseInt(ob.br.readLine());
ob.getnum(x);
ob.ishappy();
}
}
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 suing 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.
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
|
||
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.
|
voidaddlink(int v)
|
:
|
to add an element from the rear index if
possible
|
otherwise display the message “ OUT OF SIZE “.
|
||
intdellink()
|
:
|
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 ), intdellink() and void display().
THE MAIN FUNCTION AND ALGORITHM NEED NOT
BE WRITTEN.
Ans:
import java.io.*;
class Link
{
int lnk[], max, begin,end;
Link( int mm)
{
max=mm-1;
lnk=new int[mm];
begin=0;
end=0;
}
void addlink(int v)
{
if(end<=max)
lnk[end++]=v;
else
System.out.println("OUT OF SIZE ");
}
int dellink()
{
if(begin==max)
{
System.out.println("EMPTY..");
return -99;
}
else
return lnk[begin++];
}
void display()
{
for(int i=begin;i<=end;i++)
System.out.print(" "+lnk[i]);
}
public static void main(String args[]) throws Exception
{
Link ob;
int x;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int ch;
System.out.print("\nSize of the link:");
x=Integer.parseInt(br.readLine());
ob=new Link(x);
while(true)
{
System.out.print("\n1 for add, 2 for deletion and 3 for quit:");
ch=Integer.parseInt(br.readLine());
if(ch==1)
{
System.out.print("\nValue:");
x=Integer.parseInt(br.readLine());
ob.addlink(x);
System.out.print("\nNow the list:");
ob.display();
}
else if(ch==2)
{
x=ob.dellink();
System.out.print("\nDeleted element:"+x);
System.out.print("\nNow the list:");
ob.display();
}
else if(ch==3)
break;
}
}
}
Ans:
import java.io.*;
class Link
{
int lnk[], max, begin,end;
Link( int mm)
{
max=mm-1;
lnk=new int[mm];
begin=0;
end=0;
}
void addlink(int v)
{
if(end<=max)
lnk[end++]=v;
else
System.out.println("OUT OF SIZE ");
}
int dellink()
{
if(begin==max)
{
System.out.println("EMPTY..");
return -99;
}
else
return lnk[begin++];
}
void display()
{
for(int i=begin;i<=end;i++)
System.out.print(" "+lnk[i]);
}
public static void main(String args[]) throws Exception
{
Link ob;
int x;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int ch;
System.out.print("\nSize of the link:");
x=Integer.parseInt(br.readLine());
ob=new Link(x);
while(true)
{
System.out.print("\n1 for add, 2 for deletion and 3 for quit:");
ch=Integer.parseInt(br.readLine());
if(ch==1)
{
System.out.print("\nValue:");
x=Integer.parseInt(br.readLine());
ob.addlink(x);
System.out.print("\nNow the list:");
ob.display();
}
else if(ch==2)
{
x=ob.dellink();
System.out.print("\nDeleted element:"+x);
System.out.print("\nNow the list:");
ob.display();
}
else if(ch==3)
break;
}
}
}
b)
What type of data structure is the above entity? [ 1 ]
Ans:
Queue
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:
NUMBER OF CALLS
|
RATE
|
1-
100
|
Only rental charge
|
101-200
|
60 paisa per call + rental charge
|
201-300
|
80 paisa per call + rental charge
|
Above 300
|
1 rupee per call + rental charge
|
The
details of both the classes are given below:
|
||
Class Name
|
:
|
Detail
|
Data members
|
||
name
|
:
|
to store the name of the customer.
|
address
|
:
|
to store the address of the customer.
|
telno
|
:
|
to store the phone number of the customer.
|
rent
|
:
|
to store the monthly rental charge
|
Member functions:
|
||
Detail(..)
|
:
|
parameterized constructor to assign values to
data
|
members.
|
||
void show()
|
:
|
to display the detail of the customer.
|
Class Name
|
:
|
Bill
|
Data members
|
||
n
|
:
|
to store the number of calls.
|
amt
|
:
|
to store the amount to be paid by the customer.
|
Member functions:
|
||
Bill(..)
|
:
|
parameterized constructor to assign values to
data
|
Members of both classes and to initialize amt =
0.0.
|
||
voidcal()
|
:
|
calculates the monthly telephone charge
as per the
|
charge given above.
|
||
void
show()
|
:
|
to display the detail of the customer
and amount to be
|
paid.
|
||
Specify the
class Detail giving details of the constructor( ) and void show(). Uisng 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.
[ 10 ]
Ans:
class Detail
{
String name;
String address;
String telno;
double rent;
Detail(String n, String a, String t, double d)
{
name=n;
address=a;
telno=t;
rent=d;
}
void show()
{
System.out.println("\nName="+name);
System.out.println("\nAddress="+address);
System.out.println("\nTelephone Number="+telno);
System.out.println("\nRent="+rent);
}
}
class Bill extends Detail
{
int n;
double amt;
Bill(String n1, String a, String t, double d, int c)
{
super(n1,a,t,d);
n=c;
amt=0;
}
void call()
{
int n1;
amt=rent;
n1=n;
n1=n1-100;
if(n1>0 && n1<=100)
{
amt=amt+n1*.6;
n1=0;
}
else
{
amt=amt+100*.6;
n1=n1-100;
}
if(n1>0 && n1<=100)
{
amt=amt+n1*.8;
n1=0;
}
else
{
amt=amt+100*.8;
n1=n1-100;
}
if(n1>0)
{
amt=amt+n1*.1;
}
}
void show()
{
super.show();
System.out.println("\nTotal Calls="+n);
System.out.println("\nTotal amount to pay="+amt);
}
public static void main(String args[]) throws Exception
{
Bill ob;
String n,a,t;
double rent;
int call;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.print("\nEnter Customer Name:");
n=br.readLine();
System.out.print("\nEnter Address:");
a=br.readLine();
System.out.print("\nEnter Telephone Number:");
t=br.readLine();
System.out.print("\nEnter Rent:");
rent=Double.parseDouble(br.readLine());
System.out.print("\nEnter Total Calls:");
call=Integer.parseInt(br.readLine());
ob=new Bill(n,a,t,rent,call);
ob.call();
ob.show();
}
}
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 the
node. The method declaration is given below:
void search(node
start, String b)
Ans:
Program
Ans:
Program
void search(node
start, String b)
{
While(start!=null)
{
If(start.n.equalsIgnoreCase(b))
{
System.out.println(“\nName=”+start.n);
System.out.println(start.p);
Break;
}
Start=start.next;
}
If(start==null)
System.out.println(“\nRecord
not found);
}
Algorithm
Step 1: Repeat the
following steps 1 and 2 until start reaches null
Step 2: Compare the
entered name with string part value of the node, if match found display all
values and go out of step 3
Step 3: Move start
to the next node
[ 4 ]
b) Answer
the following from the diagram of the binary tree given below:
i)
|
External nodes of the tree.
|
[ 1 ]
|
ii)
|
Parent node of D. Ans: C
|
[ 1 ]
|
iii)
|
Inorder traversal of the tree. Ans: D C E B A F G
|
[ 1 ]
|
iv)
|
Right subtree of node B.
|
[ 1 ]
|
No comments:
Post a Comment