Exam (elaborations)
COS2611 EXAM PACK 2022
- Course
- Institution
Latest exam pack questions and answers and summarized notes for exam preparation. for assistance. All the best on your exams!!
[Show more]
Seller
Follow
iStudy
Reviews received
Content preview
COS2611EXAM 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]
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 iStudy. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $2.94. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
82191 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now