Formatting page ...
MADHUSTHALI VIDYAPEETH F.M 70 Time 3h Date : PRE-BOARD EXAMINATION: 2020-2021 SUBJECT: COMPUTER SCIENCE CLASS- XII (Candidates are allowed additional 15 minutes for only reading the paper. They must NOT start writing during this time.) Answer all questions in Part I (compulsory) and six questions from Part II, choosing two questions from Section A, two from Section B and two from Section C. All working, including rough work, should be done on the same sheet as the rest of the answer. The intended marks fir questions or parts of questions are given in brackets [ ]. PART I (20 Marks) Answer all questions. While answering questions in this part, indicate briefly your working and reasoning, wherever required. Question 1 (a) State the properties of zero in Boolean algebra. (b) Find the complement of the following Boolean expression using De Morgan s law: F(P, Q, R) = P + (Q . R) (c) Find the dual of: (A + 0) . (B + 1) = A (d) State whether the following proposition is a tautology, contradiction or a contingency: F = (P Q) (Q ~P) (e) Study the diagram given below and answer the questions that follow: (i) Name the basic gate which is represented by the diagram. (ii) What will be the value of X when A = 1 and B = 0? Question 2 (a) State the difference between a Binary Tree structure and a Stack. (b) A matrix B[10][20] is stored in the memory with each element requiring 2 bytes of storage. If the base address at B[2][1] is 2140, find the address of B[5][4] when the matrix is stored in Column Major Wise. (c) Convert the following infix notation to prefix form: (X + Y) / (Z * W / V) (d) State the best case and the worst case complexity for bubble sort algorithm. (e) What is the significance of the keyword new in Java? Mention the areas where it is used. Question 3 The following function check() is a part of some class. What will the function check() return when the value of (i) n = 25 and (ii) n = 10. Show the dry run/working. int check(int n){ if(n <= 1) return 1; if(n % 2 == 0) return 1 + check(n / 2); else return 1 + check(n / 2 + 1); } 1 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. SECTION A Answer any two questions. Question 4 (a) Given the Boolean function: F(A, B, C, D) = (0, 1, 2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 14). (i) Reduce the above expression by using 4-variable Karnaugh map, showing the various groups (i.e. octal, quads and pairs). (ii) Draw the logic gate diagram for the reduced expression. Assume that the variables and their are available as inputs. (b) Given the Boolean function: F(A, B, C, D) = (3, 4, 6, 9, 11, 12, 13, 14, 15). complements (i) Reduce the above expression by using 4-variable Karnaugh map, showing the various groups (i.e. octal, quads and pairs). (ii) Draw the logic circuit diagram for the reduced expression. Assume that the variables and their complements are available as inputs. Question 5 (a) Draw the logic circuit diagram for an octal to binary encoder and explain its working when a particular digit is pressed. Also, state the difference between encoders and decoders. (b) Draw the circuit of a two input XOR gate with the help of NOR gates. (c) Convert the following expression to its cardinal SOP form: F(P, Q, R) = P Q R + P QR + PQ R + PQR Question 6 (a) A company intends to develop a device to show the high status power load for a household inverter depending on the criteria given below: If Air Conditioner and Geyser are on OR If Air Conditioner is off, but Geyser and Refrigerator are on OR If Geyser is off, but Air Conditioner and Water Purifier are on OR When all are on The inputs are: (In all the above cases 1 indicates yes and 0 indicates no.) Draw the truth table for the inputs and outputs given above and write the SOP expression for X (A, G, R, W). (b) Draw the truth table and derive an SOP expression for sum and carry for a full adder. Also, draw the logic circuit for the carry of a full adder. (c) Simplify the following expression using Boolean laws: F = [(X + Y) . (Y + Z)] + (X + Z) 2 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. (Flowcharts and Algorithms are not required.) The program must be written in Java. Question 7 Design a class Convert to find date and month from a given day number for a particular year. Example: If day number is 64 and the year is 2020, then the corresponding date would be: March 4, 2020 i.e. (31 + 29 + 4 = 64). Some of the members of the class are given below: Class name: Convert Data members/instance variables: n: integer to store the day number. d: integer to store the day of the month (date). m: integer to store the month. y: integer to store the year. Methods/Member functions: Convert(): constructor to initialize the data members with legal initial values. void accept(): to accept the day number and the year. void dayToDate(): converts the day number to its corresponding date for a particular year and stores the date in d and the month in m . void display(): displays the month name, date and year. Specify the class Convert giving details of the constructor, void accept(), void dayToDate() and void display(). Define a main() function to create an object and call the functions accordingly to enable the task. Question 8 Design a class BinSearch to search for a particular value in an array. Some of the members of the class are given below: Class name: BinSearch Data members/instance variables: arr[]: to store integer elements. n: integer to store the size of the array. Member functions/methods: BinSearch(int num): parameterized constructor to initialize n = num. void fillArray(): to enter elements in the array. void sort(): sorts the array elements in ascending order using any standard sorting technique. int binSearch(int l, int u, int v): searches for the value v using binary search and recursive technique and returns its location if found otherwise returns -1. Define the class BinSearch giving details of the constructor, void fillArray(), void sort() and int binSearch(int, int, int). Define the main() function to create an object and call the functions accordingly to enable the task. Question 9 A class Mix has been defined to mix two words, character by character, in the following manner: The first character of the first word is followed by the first character of the second word and so on. If the words are of different length, the remaining characters of the longer word are put at the end. Example: If the first word is JUMP and the second word is STROLL , then the required word will be JSUTMRPOLL . 3 Some of the members of the class are given below: Class name: Mix Data members/instance variables: wrd: to store a word. len: to store the length of the word. Member functions/methods: Mix(): default constructor to initialize the data members with legal initial values. void feedWord(): to accept the word in uppercase. void mixWord(Mix p, Mix q): mixes the words of objects p and q as stated above and stores the resultant word in the current object. void display(): displays the word. Specify the class Mix giving details of the constructor, void feedWord(), void mixWord(Mix, Mix) and void display(). Define the main() function to create objects and call the functions accordingly to enable the task. SECTION C Answer any two questions. Each program should be written in such a way that it clearly depicts the logic of the problem step-wise. This can be achieved by using comments in the program and mnemonic names or pseudo codes for algorithms. The programs must be written in Java and the algorithms must be written in general/standard form, wherever required/specified. (Flowcharts are not required.) Question 10 A Circular Queue is a linear data structure which works on the principle of FIFO, enables the user to enter data from the rear end and remove data from the front end with the rear end connected to the front end to form a circular pattern. Define a class CirQueue with the following details: Class name: CirQueue Data members/instance variables: cq[]: array to store integers. cap: stores the maximum capacity of the array. front: to point the index of the front end. rear: to point the index of the rear end. Member functions: CirQueue(int max): constructor to initialize the data member cap = max, front = 0 and rear = 0. void push(int n): to add integer in the queue from the rear end if possible, otherwise display the message QUEUE IS FULL . int pop(): removes and returns the integer from the front end of the queue if any, else returns -9999. void show(): displays the queue elements. (a) Specify the class CirQueue giving details of the functions void push(int) and int pop(). Assume that the other functions have been defined. The main function and algorithm need not be written. (b) How is a linear queue structure different from a circular queue structure? Question 11 An interface Data is defined with a data member and a method volume() which returns the volume of the implementing shape. A super class Base has been defined to contain the radius of a geometrical shape. Define a 4 sub-class CalVol which uses the properties of the interface Data and the class Base and calculates the volume of a cylinder. The details of the members of the interface and both the classes are given below: Interface name: Data Data member: double pi: initialize pi = 3.142. Member function/method: double volume() Class name: Base Data member/instance variable: rad: to store the radius in decimal. Member functions/methods: Base( ): parameterized constructor to initialize the data members. void show(): displays the radius with an appropriate message. Class name: CalVol Data member/instance variable: ht: to store the height in decimal. Member functions/methods: CalVol( ): parameterized constructor to initialize the data members of both the classes. double volume(): calculates the volume of a sphere by using the formula (pi radius2 height) void show(): displays the data members of both the classes and the volume of the sphere with appropriate message. Assume that the interface Data and the super class Base has been defined. Using the concept of inheritance, specify the class CalVol giving details of the constructor, double volume() and void show(). The interface, super class, main() function and algorithm need not be written. Question 12 (a) Explain any two standard ways of traversing a binary tree. (b) Answer the following questions from the diagram of a Binary Tree given below: (i) Write the post-order traversal of the left sub-tree of the above structure. (ii) State the degree of the Nodes E and H. (iii) Mention the external nodes of the right sub-tree. 5
|
