辅导案例-A27228
A27228 No calculator allowed in this examination School of Computer Science Fourth Year Undergraduate/Postgraduate 21933 Fundamentals: Introduction to Computer Science Main Summer Examinations 2019 Time allowed: 1:30 [Answer all questions] – 1 – Turn Over No calculator Note This paper consists of THREE questions. Answer ALL questions. Each question will be marked out of 20. The paper will be marked out of 60, which will be rescaled to a mark out of 100. Useful information You might find the following information useful in answering some of the questions. iJVM instruction set Mnemonic Operands Description BIPUSH constant Push constant onto stack GOTO label name or line number Unconditional jump HALT N/A Halt the simulator IADD N/A Pop two words from stack; push their sum IFEQ label name or line number Pop elem from stack and branch if it is zero IFLT label name or line number Pop elem from stack and branch if it is less than zero IFGT label name or line number Pop elem from stack and branch if it is greater than zero IF ICMPEQ label name or line number Pop two elements from stack and branch if they are equal IINC variable name, byte Add a constant value to a local variable ILOAD variable name Push local variable onto stack ISTORE variable name Pop word from stack and store in local variable ISUB N/A Pop two words from stack; subtract the top word from the second to top word, push the answer; – 2 – Turn OverA27228 No calculator LMC instruction set NOTE: The operand ‘xx’ below can be either a variable or a label. Mnemonic Operands Description ADD xx Add the value stored at xx to whatever value is currently on the accumulator. SUB xx Subtract the value stored at xx from whatever value is currently on the accumulator. STA xx Store the contents of the accumulator to xx. LDA xx Load the value from xx and enter it in the accumulator. BRA xx Set the program counter to the given address (value xx). That is, value xx will be the next instruction executed. BRZ xx If the accumulator contains the value 000, set the program counter to the value xx. Otherwise, do nothing. BRP xx If the accumulator is 0 or positive, set the program counter to the value xx. Otherwise, do nothing. INP N/A fetch the value from the user, and put it in the accumulator OUT N/A Output the value of the accumulator HLT N/A Halt DAT DATA This is an assembler instruction which loads the value into the next available memory location. DAT can also be used in conjunction with labels to declare variables. – 3 – Turn OverA27228 No calculator Question 1 (a) Convert the following decimal numbers to binary and hexadecimal. Clearly show all working. (i) 73 (ii) 32 [4 marks] (b) This question requires you to use the answer from each sub-part in the next part. (i) Represent the following numbers using a binary system wherein numbers are represented in 6-bits. The first bit is used as the sign bit and negative numbers are represented using 2’s complement. i. -12 ii. + 8 [2 marks] (ii) Add the two numbers from the previous section in binary. Clearly show all working. [3 marks] (iii) Show that the result obtained in the previous section is indeed correct by per- forming the same operation in decimal and showing that the result is the same as in binary. [3 marks] [8 marks] (c) Write an assembly language program for the toy LCM assembler that takes three numbers (a, b, c) as input and prints the sum of the last two numbers (b+c) if the first (a) is greater than 10 or prints the difference between the last two numbers (b-c) if the first (a) is less than or equal to 10. [8 marks] – 4 – Turn OverA27228 No calculator Question 2 (a) Briefly describe the purpose of the Java Virtual Machine with specific emphasis on the need for such a system and the problems it solves. [4 marks] (b) The Java Virtual Machine makes use of a stack to track its internal operations. This stack is called the “Operand Stack” and is why the JVM is called a Stack Machine. Describe the use of this stack with a relevant (but short) example. [8 marks] (c) This question relates to the Reverse Polish Notation and consists of two parts: (i) Convert the following infix expression to the Reverse Polish Notation. Clearly show the contents of any data structures (i.e. Stack, Queue, . . . ) that you make use of: 5 + 3 ∗ 6 ∗ (8 ∗ 2 + 1) [5 marks] (ii) Now evaluate the value of the postfix expression you generated in the previous section and confirm that this value is the same as when the infix expression (provided in the previous section) is evaluated. You do not have to illustrate the contents of the stack after every step - just when an operation is performed. [3 marks] [8 marks] – 5 – Turn OverA27228 No calculator Question 3 (a) Describe any TWO kinds of errors that could occur in programs with a brief example of each. [4 marks] (b) The following table provides you with a list of functions and their corresponding complexity when they are provided with an input array of length n: Function Name Complexity f1 O(n) f2 O(n2) f3 O(log(n)) f4 O(1) What is the complexity of the following function f5 when the length of the array “inArray” is n? Justify your answer. public static void f5( int [] inArray ) – f1( inArray ); f2( inArray ); for( int i = 0; i ¡ inArray.length; i++ ) – f3( inArray ); ˝ f4( inArray ); ˝ [4 marks] (c) Write an iJVM code snippet that performs the same operations as the following Java code snippet. Include comments to show which Java statement is being executed by which sections of your iJVM code. Continued Overleaf – 6 – Turn OverA27228 Question 3 continued No calculator NOTES: • In addition to writing the program, ensure that you provide adequate comments to describe the working of your program. • You might find the iJVM statements listed at the start of this exam paper useful for this task. • Assume that you also have access to a single iJVM statement “PRT” that will pop and print the top value on the iJVM stack int current˙number = 1 ; int end = 10 ; int sum = 0 ; while( current˙number ¡= end ) – sum += current˙number ; current˙number += 1 ; ˝ System.out.println( sum ); [12 marks] – 7 – Turn OverA27228 Do not complete the attendance slip, fill in the front of the answer book or turn over the question paper until you are told to do so Important Reminders • Coats/outwear should be placed in the designated area. • Unauthorised materials (e.g. notes or Tippex) must be placed in the designated area. • Check that you do not have any unauthorised materials with you (e.g. in your pockets, pencil case). • Mobile phones and smart watches must be switched off and placed in the designated area or under your desk. They must not be left on your person or in your pockets. • You are not permitted to use a mobile phone as a clock. If you have difficulty seeing a clock, please alert an Invigilator. • You are not permitted to have writing on your hand, arm or other body part. • Check that you do not have writing on your hand, arm or other body part – if you do, you must inform an Invigilator immediately • Alert an Invigilator immediately if you find any unauthorised item upon you during the examination. Any students found with non-permitted items upon their person during the examination, or who fail to comply with Examination rules may be subject to Student Conduct procedures. A27228 Fundamentals: Introduction to Computer Science