COMPSCI 1103/1203 Algorithm Design and Data Structures Semester 1, 2012
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Primary Examination, Semester 1, 2012
Algorithm Design and Data Structures
COMPSCI 1103/1203
Fundamental Programming
Question 1
(a) Consider each of the following questions carefully. You are required to give the answer true or false and justify your answer. If it is true, explain why it is true.
i. Structs are the same as classes, except that their access control is, by default, private. [2 marks]
ii. You should use delete [] to return the space allocated to any object to the freestore.[2 marks]
iii. You cannot make an reference to unallocated memory when using a vector.[2 marks]
iv. The virtual keyword must be used for all inherited functions.[2 marks]
v. Every class you define must contain a main function.[2 marks]
(b) Write a loop that will search an array of int values, myArray, to determine if it contains the integer value stored in a variable myInt and display the message
“Found” if it finds it.
Clearly comment your code. You may assume the myArray and myInt are both declared and initialised.
[6 marks]
[Total for Question 1: 16 marks]
Recursion
Question 2
(a) What is recursion?
(b) What are the three requirements for successful recursion in C++?
(c) The fibonacci function is defined mathematically as:
[2 marks]
[3 marks]
Fib(n) = Fib(n · 1) + Fib(n · 2), Fib(1) = Fib(0) = 1, n >= 2.
Write a C++ function to implement this with the signature int fibonacci(int n). [5 marks]
(d) We often refer to recursion being less efficient than an iterative solution. Why is the recursive Fibonacci less efficient than its iterative counterpart? Provide a diagram to support your discussion.
[4 marks]
[Total for Question 2: 14 marks]
Ethics and Professional Practice
Question 3
(a) What is the basic idea behind Utilitarianism? [2 marks]
(b) Your employer asks you to install some pirated software that you need to com-
plete a project that you’re doing, for free, for a Children’s Charity.
i. Provide two reasons that would support this action, from an ethical perspec- tive. [4 marks]
ii. Provide two reasons that would oppose this action, from an ethical perspec- tive.
[4 marks]
[Total for Question 3: 10 marks]
Algorithmic Strategies
Question 4
(a) When are you justified in using an O(n2 ) algorithm? [2 marks]
(b) Exhaustive search is an example of which type of strategy? Give an example where
you might use it. [4 marks]
(c) What is a Divide-and-Conquer strategy? Give an example. [4 marks]
(d) What is a Greedy algorithm? Briefly explain how it works and give an example. [5 marks]
(e) A Decrease-by-One strategy is one where the size of the problem to be solved is
steadily decreased by one element on each iteration.
“Insertion sort is a Decrease-by-One algorithm” .
Given the definition and your knowledge of insertion sort, is this statement true? Explain your answer and clearly identify the features of insertion sort that are supporting your argument.
[4 marks]
[Total for Question 4: 19 marks]
Object Oriented Programming
Question 5
(a) What access modifier should be used to make a base class’ variables accessible by any of its derived classes? [2 marks]
(b) Define encapsulation. [3 marks]
(c) Give definitions for overloading and overriding. [4 marks]
(d) Given the following classes of animal:
Snake, Parrot, Lizard, Emu, Penguin, Bird, Cow
draw a diagram that illustrates the inheritance hierarchy of the animals. You may include extra classes. [3 marks]
(e) The class Shape contains private variables for its x and y coordinates, a con- structor that takes in the coordinates, and a function void printDetails() that outputs the coordinates.
i. Define Shape and implement printDetails. [4 marks]
ii. If derived classes of Shape had their own implementation of void printDetails(), how could you ensure that the correct printDetails would be used? [2 marks]
[Total for Question 5: 18 marks]
Software Engineering
Question 6
(a) Consider a software company that produces specialised software for schools. Al- though each school has similar requirements, the software company creates a completely new software project for each school.
i. Using the software company scenario as an example, provide three phases of the software lifecycle model that can benefit from reuse. Explain your choices. [3 marks]
ii. Describe two possible benefits of reuse. [4 marks]
(b) The following question involves testing the construction of the SimplifiedATM class.
class SimplifiedATM{
private:
int numTwentyNotes;
int numFiftyNotes;
public:
SimplifiedATM(int numTwentyNotes, int numFiftyNotes);
int dispenseMoney (int amount);
int getNumTwentyNotes();
int getNumFiftyNotes();
};
i. Assume that you are given the full implementation of dispenseMoney. De- scribe white-box testing, and explain how it will help to determine if the function is correct. [2 marks]
ii. Provide an example of how automated testing may occur on this project. [2 marks]
iii. Name three benefits of automated testing over manual testing. [3 marks] (c) Explain why maintenance is a necessary step in the lifecycle of a piece of software. [2 marks]
[Total for Question 6: 16 marks]
Abstract Data Types
Question 7
(a) Give a definition for Abstract Data Types. [3 marks]
(b) Explain the difference between a stack and a queue. [2 marks]
(c) The following question involves the class QueueInterface which contains all the functions required for a queue. QueueInterface contains elements of type int.
i. Write the definition for QueueInterface. [3 marks]
ii. Define a class called VectorQueue which inherits from QueueInterface. VectorQueue uses a vector for its queue. [3 marks]
iii. Implement a new function of VectorQueue that returns an element of the queue without removing it from the queue. You will need to decide which element to return. Explain your choice of element. [4 marks]
[Total for Question 7: 15 marks]
Question 8
(a) Explain the terms best case and worst case in terms of an algorithm. [2 marks]
(b) The following question investigates searching and sorting performance on un- sorted arrays.
i. In general, sorting an array takes longer than searching for an element in an unsorted array. If this is the case, explain why we would sort an array. [2 marks]
ii. What is the complexity of a search on an unsorted array? What is this type of search called? [2 marks]
iii. Give the best case and worst case performance of BubbleSort on an unsorted array. Explain the best case performance. [3 marks]
(c) What is the complexity of the following function, triplicate? Explain your answer.
struct Node{
Node* next;
int value;
}
void triplicate (Node* list){
if (list == NULL) return;
for (int i = 0; i < 3; i++){
Node* ptr = list;
while (ptr != NULL){
cout << ptr->value << "\n";
ptr = ptr->next;
}
}
}
[3 marks]
[Total for Question 8: 12 marks]
2022-10-11