Little homework help from Ch 17 of Programming and Problem Solving With C++ 5. a
ID: 3538372 • Letter: L
Question
Little homework help from Ch 17 of Programming and Problem Solving With C++
5.
a. Write an algorithm to perform in-order traversal of a binary tree.
b. Write an algorithm to perform pre-order traversal of a binary tree.
c. Write an algorithm to perform post-order traversal of a binary tree.
6.
a. What is the relationship of the values in the parent node and its two children in a binary search tree?
b. If a binary search tree contains 63 nodes, what is the maximum time required to search for a matching value among its nodes?
c. How many leaves are there in a binary search tree with 7 nodes?
7.
a. What problem can result from resolving a collision in a hash table by incrementing the index and using the next location in the table?
b. What do we mean by the "chain" in a chained hash table?
8.
a. Is an iterator the same as a pointer? Explain.
b. What happens to an iterator after a deletion from a container?
c. Which operator do you use to advance an iterator?
d. which operator causes an iterator to move backward?
e. In which direction does a reverse_iterator move when it is incremented?
9.
a. which aspect of vector does deque implement?
b. which apsect of list does deque implement?
c. What happens to a deque when the clear operation is called?
d. What happens to a deque when the erase operation is called?
10.
a. What are the five operations provided by stack?
b. What are the six operations provided be queue?
11.
a. What is the difference between the size and capacity of a vector?
b. How does the vector at operator differ from the [ ] operator?
c. When would you use the reserve operation with a vector?
12.
a. For map and set, what is returned by the upper_bound operation?
b. Which primary capability does a map add to those of the set?
c. Name three set-theoretic operations from the STL algorithms library.
d. You want a data structure that keeps track of whether shareholders are present at a corporate meeting. Would you choose a map or a set? explain.
Explanation / Answer
9.
a
a. vector and deque offer nearly identical interfaces and are generally interchangeable. deque also offers push_front() and pop_front(), which vector does not. (True, vector offers capacity() and reserve(), which deque does not, but that's no loss -- those functions are actually a weakness of vector, as I'll demonstrate in a moment.)
The main structural difference between vector and deque lies in the way the two containers organize their internal storage: Under the covers, a deque allocates its storage in pages, or "chunks," with a fixed number of contained elements in each page; this why a deque is often compared to (and pronounced as) a "deck" of cards, although its name originally came from "double-ended queue" because of is ability to insert elements efficiently at either end of the sequence. On the other hand, a vector allocates a contiguous block of memory, and can only insert elements efficiently at the end of the sequence.
b.
A deque is very much like a vector: like vector, it is a sequence that supports random access to elements, constant time insertion and removal of elements at the end of the sequence, and linear time insertion and removal of elements in the middle.
The main way in which deque differs from vector is that deque also supports constant time insertion and removal of elements at the beginning of the sequence. Additionally, deque does not have any member functions analogous to vector's capacity() and reserve(), and does not provide any of the guarantees on iterator validity that are associated with those member functions.
A list is a doubly linked list. That is, it is a Sequence that supports both forward and backward traversal, and (amortized) constant time insertion and removal of elements at the beginning or the end, or in the middle. Lists have the important property that insertion and splicing do not invalidate iterators to list elements, and that even removal invalidates only the iterators that point to the elements that are removed. The ordering of iterators may be changed (that is, list::iterator might have a different predecessor or successor after a list operation than it did before), but the iterators themselves will not be invalidated or made to point to different elements unless that invalidation or mutation is explicit.
c.clear() removes all of the elements from the deque, erasing the data and freeing memory
Removes from the deque container either a single element (position) or a range of elements ([first,last)).
This effectively reduces the container size by the number of elements removed, which are destroyed.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.