COMP104-17B程序辅导、讲解c++编程、c++程序语言调试
解析Java程序|辅导Web开发
Paper Code: COMP104-17B (HAM)
TURN OVER
2017 B SEMESTER EXAMINATIONS
DEPARTMENT Computer Science
PAPER TITLE Introduction to Computer Science 2
TIME ALLOWED Three Hours
NUMBER OF QUESTIONS Ten
IN PAPER
NUMBER OF QUESTIONS Ten
TO BE ANSWERED
VALUE OF EACH QUESTION The value of each question is ten marks.
GENERAL INSTRUCTIONS Answer questions in the Answer Booklet provided.
SPECIAL INSTRUCTIONS Nil
CALCULATORS PERMITTED No
THIS EXAMININATION PAPER MUST BE HANDED IN TIED TO
YOUR ANSWER BOOKLET
-2- Paper Code: COMP104-17B (HAM)
CONTINUED
1. Explain the difference between the following pairs of C# object-oriented terminology:
(a) object and class
(b) abstract method and virtual method
(c) call by reference and call by value
(d) local variable and private class variable
(e) List<> and ArrayList
(f) iteration and recursion
(g) inheriting from an interface and inheriting from a class
(h) private methods and protected methods
(i) composition and inheritance
(j) Requires and Ensures in Code Contracts
(10 marks, 1 for each part)
2. (a) Add the following 8-bit binary numbers: 00111010 and 01011101.
(2 marks)
(b) How many ways are there of representing the value 0 in 2s complement form?
(2 marks)
(c) Write down the negative number –113 in 8-bit 2s complement form.
(2 marks)
(d) Write binary 01011101 in hexadecimal.
(2 marks)
(e) What is the highest positive value that can be represented in 8-bit 2s complement form?
(2 marks)
-3- Paper Code: COMP104-17B (HAM)
TURN OVER
3. Indicate for each of the following statements whether it is true or false:
(a) a pre-condition for a method is expressed using a Contract.Requires statement
(b) when an arithmetic calculation exceeds the maximum or minimum value that can be
represented, the C# program always throws an exception
(c) an interface cannot be instantiated to give an object
(d) to be called a iterative solution the code in question must use a method that calls itself
from within its own body
(e) a protected method is only accessible from within that class or one of its subclasses
(f) an argument in a method passed as a ref parameter must be unassigned before the
method is called
(g) a virtual method can be overridden in a subclass
(h) all items stored in an ArrayList must be of the same class
(i) Finite State Machines can solve a larger set of problems than Turing Machines
(j) If the input is large enough, an algorithm of complexity O(n!) will outperform (i.e.,
solve a problem more quickly than) an algorithm of complexity O(n log n).
(10 marks, 1 for each part)
4. (a) Write out the Boolean expression for the following circuit:
(3 marks)
(b) Apply De Morgan’s law to eliminate the OR operation(s) for your expression in (a)
(2 marks)
(c) Write out the Truth Table for the circuit given in (a)
(3 marks)
(d) From inspecting the Truth Table in (c), draw a simpler equivalent circuit, using AND,
OR and NOT gates, to that given in (a).
(2 marks)
-6- Paper Code: COMP104-17B (HAM)
CONTINUED
5. Problem Description: The Department of Internal Affairs keeps track of births, deaths and
marriages in New Zealand. Every record has a registration number, a date, and a place it
was registered. For births, the records keep track of the baby's name and parents' names. A
death record stores the name of the deceased and the cause of death, along with the doctor,
coroner or medical examiner who diagnosed it. A marriage record stores the names of the
bride and groom (both prior to marriage and their married names), and their parents' names.
They also want to bring adoption and name changes into the same system.
The Department is looking at launching a website that makes these records available to
registered genealogists and interested members of the public. To do this they want to start
identifying different records that are about the same person, for example, their birth record
and their death record. Further records associated with that person will allow a user to build
a family tree, which can be saved if they are a registered genealogist.
(a) Identify 6 nouns in the description above that would make suitable candidates for
representation as objects in the design of a program that supports the required
functionality.
(2 marks)
(b) Identify three nouns in the above description that would benefit from sharing the same
base-class through inheritance. Detail any separation of fields between the base-class
and its three subclasses. Note: the nouns chosen need not be restricted to those given
in your answer to (a).
(2 marks)
(c) Write a suitable enumerated type for the categories of people who can diagnose cause
of death, i.e. doctor, coroner and medical examiner.
(2 marks)
(d) Identify two classes that are in a ‘has a’ relationship in the above description. Show
how these two classes would be related using a UML diagram.
(2 marks)
(e) Assume class Genealogist : User {}
(i) Which of the following will cause a run time error?
1. User u = new User ();
Genealogist g = (Genealogist) u;
2. Genealogist g = new Genealogist ();
User u = (User) g;
(ii) Which of the following will cause a compile time error?
1. User u = new User ();
Genealogist g = u;
2. Genealogist g = new Genealogist ();
User u = g;
(2 marks)
-5- Paper Code: COMP104-17B (HAM)
TURN OVER
6. This question relates to WRAMP instructions and programs.
(a) For each of the three specifications below write one WRAMP instruction that satisfies
the specification:
(i) Set the value in register $1 to the decimal value of 10.
(ii) Add the value in $4 to the value in $3 and store the result in $3.
(iii) Load the value currently pointed to by the stack point $sp into $8.
(3 marks, 1 for each part)
(b) Prior to the WRAMP code below being executed, the registers $1, $2, $3, and $4 have
all been set to the hexadecimal value 0xE0. What are their values, again expressed in
hexadecimal, after the code has been executed?
subui $1, $1, 1
slli $2, $2, 4
andi $3, $3, 0xF0
seq $4, $4, $0
(4 marks)
(c) The excerpt of WRAMP assembly code below encodes the same logic as a high-level
language if-statement with an else clause (e.g., in C#). Assuming, in the high-level
language, that the variables: m is mapped to $2, x to $3 and y to $4, write out an ifstatement
that is equivalent to the WRAMP code.
Note: although the assembly code also uses $13, you do not need to declare any
additional high-level language variables to those already mentioned to answer the
question.
slt $13, $3, $4
beqz $13, label
add $2, $0, $3
j label2
label:
add $2, $0, $4
label2:
# …
(3 marks)
-6- Paper Code: COMP104-17B (HAM)
CONTINUED
7. (a) What would be the output of the following program?
static bool mystery(string s)
{
if (s.Length < 2){
return true;
}
else {
string inner_s = s.Substring(1, s.Length - 2);
return (s[0] == s[s.Length-1]) && mystery(inner_s);
}
}
static void Main(string[] args)
{
string test1 = "abccba";
Console.WriteLine(test1 + " = " + mystery(test1).ToString());
string test2 = "abcdcba";
Console.WriteLine(test2 + " = " + mystery(test2).ToString());
string test3 = "abcabc";
Console.WriteLine(test3 + " = " + mystery(test3).ToString());
string test4 = "abcdcbb";
Console.WriteLine(test4 + " = " + mystery(test4).ToString());
}
Recall that “string string.Substring(int startIndex, int
length) retrieves a substring from this instance. The substring starts at a specified
character position and has a specified length.” Character positions are numbered
starting at zero. For example, s.Substring(0,1) retrieves the first character
from string ‘s’.
(4 marks)
(b) What would be a more appropriate name for the mystery method?
(1 marks)
(c) You have to write a method sumN that calculates the total sum of the first N integers
(N>=1) starting at 1. For example, sumN(5) is 15. Here is a recursive definition:
“The sum of the first N integers when N is 1, is 1. The sum of the first N integers
when N is greater than 1 is N PLUS the sum of the first N–1 integers.”
Turn this recursive definition into a C# recursive function.
(5 marks)
-9- Paper Code: COMP104-17B (HAM)
TURN OVER
8. The following is a syntactic description of a Turing Machine:
; State 1
S1 x x r S1
S1 @ @ r S2
S1 _ _ * halt-reject
S1 . . * halt-reject
; State 2
S2 x x r S2
S2 . . r S2
S2 _ _ * halt-accept
Where the start state is S1 and the input tape consists of x, @, . and the blank symbols.
The syntax used in the description above is the same as the on-line Turing Machine website
studied in lectures, where:
• Each line contains one tuple of the form '
'.
• You can use any number or word for and , e.g., 10,
a, state1. State labels are case-sensitive.
• You can use any character for and , or '_' to
represent blank (space). Symbols are case-sensitive.
• should be 'l', 'r' or '*', denoting 'move left', 'move right' or 'do not
move', respectively.
• Anything after a ';' is a comment and is ignored.
• The machine halts when it reaches any state starting with 'halt', e.g., halt-reject,
halt-accept.
(a) Draw the Turing Machine Diagram of the above machine description:
(2 marks)
(b) What are the halt states for the following inputs:
x.xx@xx.xxx
xxx@xxxxxxx.xxx
xxxxx@xx..xxx
x@xxxxx.xxx.
(4 marks)
(c) Using a simplified input alphabet of ‘x’, ‘@’ and ‘.’ the intention of the Turing
Machine is to determine if an input string is a valid email address. There are, however,
some deficiencies as currently implemented. In summary, valid email addresses:
• Can include multiple dots on either side (left part or right part) of the ‘@’ symbol.
• The dots, however, cannot appear consecutively.
• The final character in either the left or right part cannot be a dot.
• The part to the left of the ‘@’ symbol may have no dots at all.
• The part to the right must include at least one.
• The ‘@’ symbol itself can only appear once.
Draw an improved Turing Machine that correctly handles all the cases itemize above.
You do not need to write the full Turing Machine tuple description.
(4 marks)
-10- Paper Code: COMP104-17B (HAM)
Question 9 – continued on next page
9. Here are the Ball and Paddle classes from an in-development Break-Out program (see
next page for a snapshot of the original game by Atari).
public class Ball {
private int x;
private int y;
private Brush green_brush;
private const int RADIUS = 20;
public Ball(int x, int y) {
this.x = x;
this.y = y;
green_brush = new SolidBrush(Color.Green);
}
public int X { get { return x; } }
public int Y { get { return y; } }
public void Move(int delta_x, int delta_y) {
x += delta_x;
y += delta_y;
}
public void Draw(Graphics paper) {
Rectangle rect
= new Rectangle(x - RADIUS, y - RADIUS, 2 * RADIUS, 2 * RADIUS);
paper.FillEllipse(green_brush, rect);
}
}
public class Paddle {
private int x;
private int y;
private Brush blue_brush;
private const int WIDTH = 10;
private const int HEIGHT = 30;
public Paddle(int x, int y) {
this.x = x;
this.y = y;
blue_brush = new SolidBrush(Color.Blue);
}
public int X { get { return x; } }
public int Y { get { return y; } }
public void Move(int delta_x, int delta_y) {
x += delta_x;
y += delta_y;
}
public void MoveRight(int v) { Move(v,0); }
public void MoveLeft(int v) { Move(-v,0); }
public void Draw(Graphics paper) {
Rectangle rect
= new Rectangle(x - WIDTH / 2, y - HEIGHT / 2, WIDTH, HEIGHT);
paper.FillRectangle(blue_brush, rect);
}
}
Paper Code: COMP104-17B (HAM)
TURN OVER
-9-
The following snapshot is taken from the original Atari Break Out game, and is used as
inspiration for the in-development C# program. In the C# program, the ball has be
“upgraded” to be round!
(a) Write an abstract class called Sprite that contains all code elements common to both
Ball and Paddle, so that they can both inherit from it.
(5 marks)
(b) Rewrite both Ball and Paddle to be subclasses of your new Sprite class.
(5 marks)
-10- Paper Code: COMP104-17B (HAM)
10. Recall the sorting algorithms (given in pseudo code):
Bubble Sort:
for i := 1:n,
swapped := false
for j := n:i+1,
if a[j] < a[j-1],
swap a[j],a[j-1]
swapped := true
// invariant: a[1..i] in final position
break if not swapped
end
Selection Sort:
for i := 1:n,
k := i
for j := i+1:n, if a[j] < a[k], k := j
// invariant: a[k] smallest of a[i..n]
swap a[i],a[k]
// invariant: a[1..i] in final position
end
For the following array of eight integers:
4 1 2 5 6 9 8 8
Answer the following questions:
(a) When using BubbleSort, how many number comparison operations and swap
operations are performed? (Note: the number of comparisons and swaps need not be
the same.)
(3 marks)
(b) When using SelectionSort, how many number comparison operations and swap
operations are performed? (Note: the number of comparisons and swaps need not be
the same.)
(2 marks)
(c) Write out the Big O notation for the following runtime complexities:
T(f(A)) = 2n3 + 5n2 + 9n
T(f(A)) = 5n3 + 2n4 + 10n + 110,
T(f(A)) = 3n + 4n2
T(f(A)) = 2n + 2n2 + 2n!
(4 marks)
(d) In terms of the Big O notations given in (c), which one has (or ones share) the biggest
growth rate?
(1 mark)