程序代写代做代考 graph algorithm King’s College London

King’s College London
This paper is part of an examination of the College counting toward the award of a degree. Examinations are governed by the College Regulations under the authority of the Academic Board.
Degree Programmes
Module Code Module Title Examination Period
MSc, MSci
7CCSMASE
Advanced Software Engineering January 2016 (Period 1)
Time Allowed 2 hours
Rubric ANSWER ALL QUESTIONS.
Books, notes or other written material may not be brought into this examination.
ANSWER EACH QUESTION IN A SEPARATE ANSWER BOOK AND WRITE ITS NUMBER ON THE COVER
Calculators Calculators may be used. The following models are permitted: Casio fx83 / Casio fx85
PLEASE DO NOT REMOVE THIS PAPER FROM THE EXAMINATION ROOM
King’s College London © 2016

7CCSMASE Advanced Software Engineering
Question 1
(a) Define the notions of white box testing and black box testing and
explain the difference between them. (5 marks) (b) Define the notions of test cases, test suite, and adequacy criteria.
(5 marks)
(c) Explain why it is often impossible to construct a test suite that satisfies the adequacy criteria. Give one example (a small program, a criterion, and why it is impossible to satisfy it).
(5 marks) (d) Give two reasons why we need coverage metrics. (5 marks)
(e) Define the notion of random testing. Give one reason in favour of using it and one reason against using it. (5 marks)
(f) Explain the difference between reliability and correctness.
(5 marks)
[30 marks]
2
SEE NEXT PAGE

7CCSMASE Advanced Software Engineering
Question 2
For the following program computing the greatest common divisor:
public int gcd(int x, int y){ int tmp;
while(y != 0) { tmp = x%y;
x=y;
y=tmp; }
return x; }
(a) Draw the control graph of the program.
(b) Annotate the nodes to indicate the definitions/uses of variables
(6 marks) tmp, x and y. (6 marks)
(c) Apply the Reach algorithm to determine the sets of definitions reaching each statement of this program. Show each step of the algorithm. (6 marks)
(d) Define one structural coverage metric suitable for this program.
(5 marks)
(e) Build a minimal test suite having 100% coverage according to the criterion defined in (d). (6 marks)
(f) Give two sets of inputs, which would lead to different paths
through the program.
(6 marks)
[35 marks]
3
SEE NEXT PAGE

7CCSMASE Advanced Software Engineering
Question 3
Natural language requirements for a vending machine for a single type of a chocolate bar are as follows:

Release item after receiving 15 cents
o Single coin slot for dimes (10 cents) and nickels (5 cents) –
assuming sensor specifies coin type o Machine does not give change
(a) Draw a Finite State Machine (FSM) that is a reference model for the vending machine by considering the below input sequences:
1) 3 nickels
2) 2 nickels, 1 dime 3) 1 nickel, 1 dime 4) 1 dime, 1 nickel 5) 2 dimes
*Inputs: N (nickel), D (dime), R (reset) *Output: Open
(6 marks) (b) Show the paths through the FSM on the sequences of inputs 1), 2),
3), 4), 5) from the sub-question (a). (6 marks)
(c) What would change if the machine had the option to dispense two types of chocolate bars: type A and type B? Both bars cost the same (15 cents), but there are two additional buttons: one for bar A and one for bar B. Assume that the machine still does not give change.
(6 marks) (d) Give the definition of branch coverage for FSM. (5 marks)
(e) Build a minimal test suite with 100% branch coverage for the FSM in sub-question (a). (6 marks)
(f) Give the definition of path coverage for FSM. Can we get 100% path coverage? If yes, give a test suite with 100% path coverage. If no, explain why it is impossible to get 100% path coverage, and what
paths we can and cannot cover.
(6 marks)
[35 marks]
4
S E E N EFXI NT APLA GP AE G E