COS2611
EXAM PACK
,UNIVERSITY EXAMINATIONS
October/November 2020
COS2611
Programming: Data Structures
70 Marks
3 Hours
This paper consists of 11 pages including Appendix A, B and C (pp 10-11).
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.
5. The code in this exam paper can also be downloaded from myUnisa additional
resource in the 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]
, 2 COS2611
October/November 2020
Question 1 Program Analysis [12]
For each of the following questions choose the correct alternative.
1.1. What is the running time of the entire code fragment?
for(int i = 1; i < n; i = i*2)
sum++;
A. O(N)
B. O(N2)
C. O(log N)
D. O(N log N)
E. O(1)
Questions 1.2, 1.3 and 1.4 refer to the following code fragment.
1 for(int j = 10; j <= n; j++ )
2 for(int k = 1; k <= n; k++ )
3 sum++;
4 for(int p = n; p > 1; p/=2 )
5 for(int q = n; q >=0; q-- )
6 sum--;
1.2. 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.3. 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)
[Turn Over]
, 3 COS2611
October/November 2020
1.4. 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.5. An algorithm takes 10 seconds for an input size of 1000. How long will it take for an input
size of 2 000 if the running time is O(N2)?
A. 10s
B. 20s
C. 30s
D. 40s
E. 60s
1.6. An algorithm takes 10 seconds for an input size of 1000. How large a problem can be
solved in 80 seconds if the running time is cubic O(N3)?
A. 800
B. 1250
C. 2000
D. 2500
E. 3000
Question 2 Linked List [8]
The insert function of the class orderedLinkedList does not check if the item to be
inserted is already in the list; that is, it does not check for duplicates. Rewrite the definition of
the insert function so that before inserting the item it checks whether the item to be inserted
is already in the list. If the item to be inserted is already in the list, the function outputs an
appropriate error message.
Use the following header:
template <class Type>
void insert(const Type& newItem)
See Appendix A for orderedLinkedList class
[Turn Over]
EXAM PACK
,UNIVERSITY EXAMINATIONS
October/November 2020
COS2611
Programming: Data Structures
70 Marks
3 Hours
This paper consists of 11 pages including Appendix A, B and C (pp 10-11).
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.
5. The code in this exam paper can also be downloaded from myUnisa additional
resource in the 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]
, 2 COS2611
October/November 2020
Question 1 Program Analysis [12]
For each of the following questions choose the correct alternative.
1.1. What is the running time of the entire code fragment?
for(int i = 1; i < n; i = i*2)
sum++;
A. O(N)
B. O(N2)
C. O(log N)
D. O(N log N)
E. O(1)
Questions 1.2, 1.3 and 1.4 refer to the following code fragment.
1 for(int j = 10; j <= n; j++ )
2 for(int k = 1; k <= n; k++ )
3 sum++;
4 for(int p = n; p > 1; p/=2 )
5 for(int q = n; q >=0; q-- )
6 sum--;
1.2. 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.3. 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)
[Turn Over]
, 3 COS2611
October/November 2020
1.4. 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.5. An algorithm takes 10 seconds for an input size of 1000. How long will it take for an input
size of 2 000 if the running time is O(N2)?
A. 10s
B. 20s
C. 30s
D. 40s
E. 60s
1.6. An algorithm takes 10 seconds for an input size of 1000. How large a problem can be
solved in 80 seconds if the running time is cubic O(N3)?
A. 800
B. 1250
C. 2000
D. 2500
E. 3000
Question 2 Linked List [8]
The insert function of the class orderedLinkedList does not check if the item to be
inserted is already in the list; that is, it does not check for duplicates. Rewrite the definition of
the insert function so that before inserting the item it checks whether the item to be inserted
is already in the list. If the item to be inserted is already in the list, the function outputs an
appropriate error message.
Use the following header:
template <class Type>
void insert(const Type& newItem)
See Appendix A for orderedLinkedList class
[Turn Over]
