Formatting page ...
JOHNSON GRAMMAR SCHOOL, ISC PRE-BOARD-2- EXAMINATION COMPUTER SCIENCE Paper 1 Theory (Candidates are allowed additional 15 minutes for only reading the paper. They must NOT start writing during this time) Class: XII Date: Marks: 70 Time: 3Hrs Answer all questions in part I (compulsory) and six Questions from Part II, choosing two questions from Section A, two questions from Section B and two questions from Section C The intended marks for questions are given in brackets { } Part I Answer all questions. While answering questions to this part, indicate briefly your working and reasoning, wherever required. Question-1 a. Convert A.B+B.C to its canonical SOP form using Boolean Algebra? b. State the dual of the following expression xy .(xy z+x+x z )and reduce after obtaining dual, using Boolean laws c. State the law represented by the following expression A+AB=A and prove it with the help of A truth table d. Verify if the following proposition is valid (a b) (a c)= a (b c) e. Convert (x +y+z ).(x+y +z)(x+y+z ).(x+y+z) into SOP form [1] [1] [1] Question 2 a) Define Computational complexity. Calculate the worst case complexity using Big O [2] notation for the following code segment for(int x=1;x<=a;x++) { Statements---} for(int y=1;y<=b;y++) { for(int z=1;z<=c;z++) { Statements--} } How would the complexity change if all the three loops went to N instead of a,b and c. b) Convert the following infix expression to its postfix form:A+(B-C*(D/E)*F) [2] c) Each element of an array X[-15 10,15 40] requires one byte of storage. If the array is [2] stored in column major order with the beginning location 1500, determine the location of X[5,20]. d) Differentiate between throw and throws keyword? [2] e) Differentiate between extends and implements keyword [2] Question-3 Following is a small Java code to print the first 15 numbers of the Pell series. In mathematics, the Pell numbers are an infinite sequence of integers. The sequence of Pell numbers starts with 1, and then each Pell number is the sum of twice the previous Pell number and the Pell number before that.: thus, 70 is the companion to 29, and 70 = 2 29 + 12 = 58 + 12. The first few terms of the sequence are : 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, 5741, 13860, import java.util.Scanner; public class Pell { public static void main() { int n,a=?1?,b=0,c; System.out.println("First 15 Pell numbers: "); for(n=1; n<=?2?; n++) { c= a + ?3?; System.out.print(c+" "); a = ?4?; b = ?5?; } } } i) What is the ii) What is the iii) What is the iv) What is the v) What is the expression / value expression / value expression / value expression / value expression / value at at at at at ?1? ?2? ?3? ?4? ?5? PART II (50 Marks) Answer six questions in this part, choosing two questions from Section-A , two from Section-B and two from Section-C ECTION-A Answer any two questions Question-4 (a) Given the Boolean function F(A,B,C,D)= (1,2,3,4,5,6,7,10,11,12,13,14,15) Use Karnaugh s map to reduce the given function F using the SOP form. Draw a logic gate diagram for the reduced SOP form. You may use gates with more than two inputs. Assume that the variables and their complements are available as inputs. [10] b) Given the Boolean function F(A,B,C,D)= ( 1,3,4,5,6,7,8,9,10,11,13,15) Use Karnaugh s map to reduce the given function F using the POS form. Draw a logic gate diagram for - the reduced POS form. You may use gates with more than two inputs. Assume that the variables and their complements are available as inputs. Question-5 (a) What is a multiplexer?State an application of a multiplexer.Draw the truth table and logic diagram [5] a 8X1 multiplexer (b) A combinational circuit with 3 inputs A,B,C detects an error during transmission of code and gives the output D as 1 if any two of the inputs are low(0). i) Write the truth table with Inputs A,B,C and Outputs D. [ 1] ii) Write the SOP expression for D(A,B,C) using minterms. Implement D using NAND gates only. [2] iii) Write the POS expression for D(A,B,C) using maxterms. Implement D using NOR gates only. [2] Question-6 [5] (a) An airlines company had certain reservations on allotting window seat in long journey.A window seat was allotted to a passenger if The passenger s age is between 3 to 7 years and the passenger is accompanied by an adult (OR) The passenger is a lady and is not accompanied by an adult (OR) The passenger s age is not between 3 to 7 years and the passenger is travelling for the first time (OR) The passenger is a lady and is travelling for the first time Inputs: G A L F - The Passenger s age is between 3 to 7 years The passenger is accompanied by an adult The Passenger is a lady The passenger is travelling for the first time Output : W The passenger gets a window seat[I indicates yes, o indicates no] (i) Draw the truth table for the inputs and the outputs given above (ii) Write the Sum of product expression for W(G,A,L,F) (b) Using Universal NOR gates, draw the elementary gates (c) Convert the following SOP expression F(u,v,w)=u v w +u v w+u vw+uv w into its corresponding POS form SECTION-B Answer any two 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. (Flow charts and algorithms are not required) [3] [2] The programs must be written in Java. -----------------------------------------------------------------------------------------------------------------------------------Question-7 [10] A class Series is defined to find the sum of the following series: S=1+x2/3! x3/4! + x4/5!- - x5/6!+ .xn/(n+1)! Some of the members of the class Series are as follows Class Name : Series Data members/instance variables : x n sum : : : integer to store a number integer to store the limit of the series double variable to store sum of the series Member functions/methods : Series() Series(int nx,int nn) int fact(int d) : : : int power(int a,int b) : void sumSeries() : Default Constructor Parameterized constructor to assign x=nx and n to nn To return factorial of d using recursive technique. The factorial of a number is calculated as d!=d*(d-1)*(d-2)*-------*1 To return a raised to the power b using recursive technique. Do not use Math.pow() function Find and print sum of the above series by calling fact and power method. Specify the class Series giving details of the two constructors and functions int fact(int),int power(int,int) and void sumSeries(). Define the main function to create an object and call the methods accordingly to enable the task. Question-8 [10] A class Trans has been designed to transfer the digits of a number to an array.some of the members of the class are given below. Class Name : Trans Data members/instance variables DN SD DNA[] : : : Integer Integer to store the number of digits in DN Integer Array of length SD Member functions Trans() int countDigits(int N) void fnBegin\() Trans fnBig(Trans t1,Trans 2): : Constructor to initialize DN and SD to zero : To calculate and return the number of digits present in N : To input DN, fill SD, and DNA Accordingly\ To store the members of the object with the larger DN in the current object members and return accordingly Specify the class Trans giving the details of the above member data and methods along with the main() method. Question-9 [10] Design a class Piece that accepts a string sentence and creates a new string by replacing uppercase alphabet by its equivalent ASCII value . each lowercase alphabet by a hash symbol(#) and each non alphabet by a underscore(_) symbol For example: Input Output : : ABC abc D? 656667_###_68_ Some of the members of the class Piece are given below. Class Name : Piece Data members/instance variables pal : The String Member functions Piece() void fnInput() void fnShow() : : : String fnConvert() int fnCountCap() : : constructor to initialize member data to null To input the member String To print the member string and the converted string and the number of uppercase alphabets To create and return the modified String To count and return the number of upper case alphabets specify the class Piece, giving the details of the above member data and methods only. SECTION-C Answer any two questions Each program should be written in such a way that it clearly depicts the logic of the problem stepwise This can be achieved by using mnemonic names and comments in the program. The programs must be written in JAVA and the algorithms must be written in general /standard form wherever required. (Flow charts are not required) Question-10 [5] A super class called Prime checks if a number is prime number or not and a sub class Emirp checks if a number is Emirp number or not(an emirp number is a number which is prime both backwards and forwards example 13 and its reverse 31 are both primes. The details of the members of both the classes are given below Class Name : Prime Data member/instance variable n : To store an integer Member functions/methods Prime(int nn) : Parameterized constructor to initialize the data member n=nn int check(int x) : Returns 1 if x is a prime else returns 0 if x is not a prime void display() : Displays the data member n Class Name : Emirp Data members/instance variables rev : integer to store the reverse of number n from subclass Member functions/methods Emirp( ) : Paramaterised constructor ,to initialize the data members of both the classes int check(int x) : To check if x is emirp number and return 1, else return 0; void display() : Displays the original data member , reversed number and also display if it s a emirp number Assume that the super class Prime has been defined. Using the concept of inheritance, Specify the class Emirp giving the details of the constructor( ),int check(int x) and void display(). Note: The super class,main function and algorithm need not be written. Question-11 A doubly queue is a linear data structure which enables the user to add and remove integers from either ends, i.e. from front or rear. Define a class Dequeue with the following details: [5] Class name : Dequeue Data members arr[] lim front rear : : : : array to hold upto 100 integer elements stores the limit of the dequeue to point to the index of front end to point to the index of rear end Member functions Dequeue(int l) void addfront(int val) : : void addrear(int val) : int popfront() int poprear() : : constructor to initialise the data members lim=l; front=rear=0 to add integer from the front if possible else display the message ( Overflow from front ) to add integer from the rear if possible else display the message ( Overflow from rear ) returns element from front, if possible otherwise returns -9999. returns element from rear, if possible otherwise returns -9999 Specify class Dequeue giving details of the constructor(), void addfront(int), void addrear(int), int popfront(), The main function and algorithm need not be written. Question-12 a) A linked list is formed from the objects of a class Node. The class structure of Node is given below: [2] Class Node { int at; Node next; } Write an algorithm or code to find the smallest node in the singly linked list of N nodes the method declaration is given below int findSmall(Node start) b) Answer the following question based on the given binary tree. [3] B C R N F M H E P i) ii) iii) Write the post-order traversal of the left sub tree of node B, including itself State the level number of nodes R and M when the root is at level 0 Name the internal nodes of the tree
|
