CMPT 225, Spring 2018, Practice final
Instructions: There are 7 questions worth 15 points each. Good luck!
1. Given two doubly linked lists, L
0 and L
00, give the pseudocode for a procedure for
merging them into a single doubly linked list L that has all the nodes of L
0
followed
by all th...
practice final instructions there are 7 questions worth 15 points each good luck 1 given two doubly linked lists
Written for
CMPT 225
All documents for this subject (9)
Seller
Follow
beckyfawcet
Reviews received
Content preview
CMPT225, Spring 2021
Final Exam
Name_________________________
SFU ID: |__|__|__|__|__|__|__|__|__|
Problem 1
Problem 2
Problem 3
Problem 4
TOTAL
Instructions:
1. You should write your solutions directly in this word file,
and submit it to Coursys. Submitting a pdf is also ok.
2. Submit your solutions to Coursys before April 20, 23:59.
No late submissions, no exceptions
3. Write your name and SFU ID on the top of this page.
4. This is an open book exam.
You may use textbooks, calculators, wiki, stack overflow, geeksforgeeks, etc.
If you do, specify the references in your solutions.
5. Discussions with other students are not allowed.
Posting questions online asking for solutions is not allowed.
6. The exam consists of four (4) problems. Each problem is worth 25 points.
7. Write your answers in the provided space.
8. You may use all classes in standard Java, and everything we have learned.
9. Explain all your answers.
10. Really, explain all your answers.
Good luck!
Problem 1 [25 points]
This study source was downloaded by 100000850872992 from CourseHero.com on 04-09-2023 03:16:50 GMT -05:00
, A. (15 points) In this question you need to design a data structure that supports
PriorityQueue with deletions. Specifically, you need to write the class
PriorityQueueWithDeletions. As a motivation you may think of a priority queue for a
printer that allows adding a document, removing a document in some order (e.g.
shorter documents are printed first), or a user can cancel the job. Specifically the class
needs to support the following operations:
The running time of each operation must be O(log(size of the queue)).
public class PriorityQueueWithDeletions<T extends Comparable<T>> {
public PriorityQueueWithDeletions() - creates an empty priority
queue
public Ticket add(T item) - adds a new element to the queue.
Returns a ticket that can be used to remove your item from the
queue.
public T removeHighestPriority() - removes the element with the
highest priority from the queue and
returns it.
public removeByTicket(Ticket t) - removes an element by ticket,
and returns the removed
element.
public int size() - returns the number of elements in the queue
public boolean isEmpty() - checks if the queue is empty
}
The running time of each operation must be O(log(n)), where n is the size of the
priority queue.
Explain your answer in detail. Define the class Ticket and explain how you use it.
Make sure Ticket does not allow the user to modify the queue adversarially.
This study source was downloaded by 100000850872992 from CourseHero.com on 04-09-2023 03:16:50 GMT -05:00
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 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 beckyfawcet. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for £5.30. You're not tied to anything after your purchase.
