Answers to Selected Exercises Chapter 1
Download 0.49 Mb.
|
- Navigate this page:
- INT_MAX
Chapter 92. The relational operator <= should be replaced with >=. 5. (a) The member functions would not change, but the private data members would change. The only data member would be a pointer to a linked lists. (b) The code for SortedType::InsertItem (linked implementation) can be used directly with the relational operator reversed. (c) The code is identical to StackType::Pop. (d) Dequeue for a priority queue implemented as a linked list (ordered from highest to lowest priority) is very simple and efficient; we have direct access to the largest element. There is less work involved in fixing the structure after the largest element is removed, because the next-largest element immediately follows it. Thus the operation is 0(1). In the heap implementation we have immediate access to the largest element, but we have to perform a reheap operation to fix the structure, resulting in an O(log2N) operation. The linked list implementation is more efficient, in terms of Big O. When the priority queue is implemented as a linked list, the efficiency of Enqueue varies according to the position that the new element occupies in the list. If the new element belongs in the last position, the whole list is searched before the insert place is found. Thus the operation is O(N). Using heaps, the insertion operation is O(log2N). The linked list implementation might be better if the elements were inserted in largely sorted order from smallest to largest value. 8. (a) The highest-priority element is the one with the largest time stamp. (This assumes that the time stamp never reaches INT_MAX. (b)
Push Assign the next largest time stamp to the new element Put new element in the stack (position is unimportant)
Find the element with the largest time stamp Assign this element to item (to be returned) Remove the element (c) The Push operation has O(1) because it doesn't matter where the item is stored in the structure. The Pop operation has O(N), because the item with the largest time stamp must be searched for. Therefore, Push is the same in both implementations, but Pop is not. If the priority queue is implemented using a heap with largest value the highest priority, Pop and Push have O(log2N). 12. EmployeeGraph
.Edges
14. "works with" is the best description of the relationship represented by the edges between vertices in EmployeeGraph, because it is an undirected graph. The other relationships listed have an order implicit in them. 17. The correct answer is (b). For example, a dalmatian is an example of a dog. 20. (a) StateGraph
.Edges
(b)
23. Deleting a vertex is more complicated than deleting an edge for two reasons. First, in addition to removing the vertex from the set of vertices, we must also remove the edges to all its adjacent vertices in the set of edges. Second, we must dedecide what to do about the now unused vertex number. The best solution is to keep a list of returned vertex numbers and assign new numbers from there first. 25. Implicit set representations represent those items that are present in an instance of a set explicitly; those items that are not represented are not in the set. Explicit set representations associate a place (bit or Boolean flag) for each item in the base type in the instance of each set . The place for an item is true if the item is in the set and false if the item is not in the set.
Directory: samples samples -> Running head: capstone project samples -> Memorandum of understanding long beach city college- long beach unified school district samples -> Cell Phone Antennas: a look at the history and design of vhf antennas samples -> Affinity program guidelines samples -> Chapter 2: Setting Up Your Android Development Environment Multiple Choice Questions samples -> High School Musical samples -> Finance crisis Introduction samples -> Android Application Development: Working with the Emulator samples -> - Download 0.49 Mb. Share with your friends:
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||