COS2611 EXAM
PACK 2024
QUESTIONS AND
ANSWERS
FOR ASSISTANCE CONTACT
EMAIL:
, lOMoARcPSD|31863004
UNIVERSITY EXAMINATIONS
May/June 2020
COS2611
Programming: Data Structures
70 Marks
3 Hours
This paper consists of 10 pages including Appendix A, B and C (pp 9-10).
Instructions:
1. Answer all questions.
2. The total marks for this examination is 70 marks.
3. The mark for each question is indicated in brackets next to the question.
4. If you do not submit your work on or before the indicated time, for whatever reason,
you will be marked as absent. In that case, you will be automatically deferred to the
October/November 2020 examination.
5. The code in this exam paper can also be downloaded from myUnisa additional
resource in Exam code folder.
PLAGIARISM is the presentation by a student of an assignment or piece of work which has in fact
been copied in whole or in part from another student’s work, or from any other source, without due
acknowledgement in the text. Dishonest practices may also amount to criminal offences, such as
fraud, theft and criminal copyright liability. Such dishonest practices include the following: copying
information from another person (e.g. another student’s assignment or portfolio) and submitting
identical work where such work is not the result of teamwork and indicated as such by all participants,
asking someone else to do the work on one’s behalf.
Having another person do the work on your behalf will result in disciplinary action, and
potential suspension or expulsion from the university.
First Examiner: Mr T Masombuka
Second Examiner: Mr L Aron
GOOD LUCK
[Turn Over]
, lOMoARcPSD|31863004
2 COS2611
May/June 2020
Question 1 Program Analysis [10]
For each of the following questions choose the correct alternative.
Questions 1.1, 1.2 and 1.3 refer to the following code fragment.
1 for(int j = 10; j <= n; j++ )
2 for(int k = 1; k <= n; k*=2 )
3 sum++;
4 for(int p = n; p > 1; p/=2 )
5 for(int q = 0; q < 500; q+=4 )
6 sum--;
1.1. How many times is statement 3 executed?
A. O(N)
B. O(N2)
C. O(N3)
D. O(N log N)
E. O(log N)
1.2. How many times is statement 6 executed?
A. O(N)
B. O(N2)
C. O(N3)
D. O(log N)
E. O(N log N)
1.3. What is the running time of the entire code fragment?
A. O(N)
B. O(N2)
C. O(N3)
D. O(log N)
E. O(N log N)
1.4. An algorithm takes 90 seconds for an input size of 100. How long will it take for an input
size of 10 000 if the running time is O(log n)?
A. 100s
B. 108s
C. 180s
D. 360s
E. 900s
[Turn Over]
Downloaded by Gabriel Musyoka ()
, lOMoARcPSD|31863004
3 COS2611
May/June 2020
1.5. An algorithm takes 4 seconds for an input size of 8. How large a problem can be solved
in 64 seconds if the running time is quadratic O(n 2)?
A. 8
B. 16
C. 32
D. 68
E. 132
Question 2 Linked List [8]
Implement the operation shareList, which is part of class unorderedLinkedList (See
appendix A). This operation copies the elements ofOrig list into listA and listB. All
elements in the even position (elements in position: 0, 2, 4, etc) are copied to listA and the
one’s in an odd position (elements in position: 1, 3, 5, etc) are copied to listB.
Use the following header:
template <class Type>
void shareList(const unorderedLinkedList<Type> & Orig,
unorderedLinkedList<Type> & listA, unorderedLinkedList<Type> &
listB);
Question 3 Searching [6]
Consider the sorted array myList of integers below.
2 5 21 25 35 40 45 48 70 75 89 99
The Binary Search algorithm uses two index variables first and last to determine the position
(stored in another index variable mid) to search for an element. Using Binary Search to search
for the element 75 in myList, give the values of myList[first], myList[mid] and
myList[last] (in the form of a table) every time a new value is calculated for mid.
[Turn Over]
Downloaded by Gabriel Musyoka ()
PACK 2024
QUESTIONS AND
ANSWERS
FOR ASSISTANCE CONTACT
EMAIL:
, lOMoARcPSD|31863004
UNIVERSITY EXAMINATIONS
May/June 2020
COS2611
Programming: Data Structures
70 Marks
3 Hours
This paper consists of 10 pages including Appendix A, B and C (pp 9-10).
Instructions:
1. Answer all questions.
2. The total marks for this examination is 70 marks.
3. The mark for each question is indicated in brackets next to the question.
4. If you do not submit your work on or before the indicated time, for whatever reason,
you will be marked as absent. In that case, you will be automatically deferred to the
October/November 2020 examination.
5. The code in this exam paper can also be downloaded from myUnisa additional
resource in Exam code folder.
PLAGIARISM is the presentation by a student of an assignment or piece of work which has in fact
been copied in whole or in part from another student’s work, or from any other source, without due
acknowledgement in the text. Dishonest practices may also amount to criminal offences, such as
fraud, theft and criminal copyright liability. Such dishonest practices include the following: copying
information from another person (e.g. another student’s assignment or portfolio) and submitting
identical work where such work is not the result of teamwork and indicated as such by all participants,
asking someone else to do the work on one’s behalf.
Having another person do the work on your behalf will result in disciplinary action, and
potential suspension or expulsion from the university.
First Examiner: Mr T Masombuka
Second Examiner: Mr L Aron
GOOD LUCK
[Turn Over]
, lOMoARcPSD|31863004
2 COS2611
May/June 2020
Question 1 Program Analysis [10]
For each of the following questions choose the correct alternative.
Questions 1.1, 1.2 and 1.3 refer to the following code fragment.
1 for(int j = 10; j <= n; j++ )
2 for(int k = 1; k <= n; k*=2 )
3 sum++;
4 for(int p = n; p > 1; p/=2 )
5 for(int q = 0; q < 500; q+=4 )
6 sum--;
1.1. How many times is statement 3 executed?
A. O(N)
B. O(N2)
C. O(N3)
D. O(N log N)
E. O(log N)
1.2. How many times is statement 6 executed?
A. O(N)
B. O(N2)
C. O(N3)
D. O(log N)
E. O(N log N)
1.3. What is the running time of the entire code fragment?
A. O(N)
B. O(N2)
C. O(N3)
D. O(log N)
E. O(N log N)
1.4. An algorithm takes 90 seconds for an input size of 100. How long will it take for an input
size of 10 000 if the running time is O(log n)?
A. 100s
B. 108s
C. 180s
D. 360s
E. 900s
[Turn Over]
Downloaded by Gabriel Musyoka ()
, lOMoARcPSD|31863004
3 COS2611
May/June 2020
1.5. An algorithm takes 4 seconds for an input size of 8. How large a problem can be solved
in 64 seconds if the running time is quadratic O(n 2)?
A. 8
B. 16
C. 32
D. 68
E. 132
Question 2 Linked List [8]
Implement the operation shareList, which is part of class unorderedLinkedList (See
appendix A). This operation copies the elements ofOrig list into listA and listB. All
elements in the even position (elements in position: 0, 2, 4, etc) are copied to listA and the
one’s in an odd position (elements in position: 1, 3, 5, etc) are copied to listB.
Use the following header:
template <class Type>
void shareList(const unorderedLinkedList<Type> & Orig,
unorderedLinkedList<Type> & listA, unorderedLinkedList<Type> &
listB);
Question 3 Searching [6]
Consider the sorted array myList of integers below.
2 5 21 25 35 40 45 48 70 75 89 99
The Binary Search algorithm uses two index variables first and last to determine the position
(stored in another index variable mid) to search for an element. Using Binary Search to search
for the element 75 in myList, give the values of myList[first], myList[mid] and
myList[last] (in the form of a table) every time a new value is calculated for mid.
[Turn Over]
Downloaded by Gabriel Musyoka ()
