Exam (elaborations)
DSA Quiz 11 Questions and Answers
- Course
- Institution
Exam of 2 pages for the course DSA at DSA (DSA Quiz 11)
[Show more]
Content preview
DSA Quiz 11What is the overall structure of a heap? - answer Elements are stored first on the left,
and leaves are only on the last and second to last layer. For min heaps, children's
values are >= their parent's values. For max heaps, children's values are <= their
parent's values
In a list, what is the index of the root? - answer list[0]
In a list, what is the index of a node's left child? - answer2 * current index
In a list, what is the index of a node's right child? - answer (2 * current index) + 1
In a list, what is the index of a node's parent? – answer Math. Floor(current index / 2)
Why is it preferred to use an array for a binary heap? - answer Saves space (No need
to store pointers, arrays are more compact in memory), Saves time (*2 /2 operations are
faster than dereferences), Parent is easy to locate (free parent "pointer")
What does the push(T data) method do in binary heaps? - answer Adds data to the
heap
What does the poll() method do in binary heaps? - answer Remove next priority item in
the heap
What does the peek() method do in binary heaps? - answerReturn the value of the root
What is the time complexity of push? - answerworst: O(log n) average: O(1)
What is the pseudocode of push? - answer-Add element to the bottom level of the heap
while maintaining the shape property,
-Compare value of element with parent value, if it's in correct order, stop.
- If not in correct order, swap with parent and keep comparing until in correct place (This
is known as percolateUp)
How many of the elements are leaves? - answerHalf
What is the average number of checks for per insert for push? - answer2
What is the pseudocode of poll in a heap? - answer-Remove the root
- Make the last element in the 1D array the new root
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 Dreamer252. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $11.99. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
84866 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now