Exam (elaborations)
COS2611 Exam pack 2024(Programming: Data Structures)
- Course
- Institution
COS2611 Exam pack 2024(Programming: Data Structures) With accurate answers and assurance that they are in the exam
[Show more]
Seller
Follow
gabrielmusyoka940
Reviews received
Content preview
COS2611 EXAMPACK 2024
QUESTIONS AND
ANSWERS
FOR ASSISTANCE CONTACT
EMAIL:gabrielmusyoka940@gmail.com
, 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 (gabrielmusyoka940@gmail.com)
, 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 (gabrielmusyoka940@gmail.com)
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller gabrielmusyoka940. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $2.50. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
83637 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now