lOMoARcPSD|2720983
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]
Downloaded by Marco Peramaul ()
, lOMoARcPSD|2720983
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 Marco Peramaul ()
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]
Downloaded by Marco Peramaul ()
, lOMoARcPSD|2720983
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 Marco Peramaul ()
