23. Algorithm Efficiency and Sorting

[Page 690]

Review Questions

Sections 20.1 “20.2

20.1	What is a data structure? What is an object-oriented data structure?
20.2	What are the limitations of the array data type?
20.3	MyArrayList is implemented using an array, and an array is a fixed- size data structure. Why is MyArrayList considered a dynamic data structure?
20.4	What are the benefits of defining both the MyList interface and the MyAbstractList class? What is a convenience class?
20.5	What is wrong in the following code? MyArrayList list = new MyArrayList(); list.add( 100 );
20.6	What is wrong if lines 11 “12 in Listing 20.3, MyArrayList.java data = objects; size = objects.length; are replaced by super (objects);
20.7	If the number of elements in the program is fixed, what data structure should you use? If the number of elements in the program changes, what data structure should you use?
20.8	If you have to add or delete the elements anywhere in a list, should you use ArrayList or LinkedList ?

Section 20.3 Stacks and Queues

20.9	You can use inheritance or composition to design the data structures for stacks and queues. Discuss the pros and cons of these two approaches.
20.10	Which lines of the following code are wrong? MyList list = new MyArrayList(); list.add( "Tom" ); list = new MyLinkedList(); list.add( "Tom" ); list = new MyStack(); list.add( "Tom" );

Section 20.4 Binary Trees

20.11

If a set of the same elements is inserted into a binary tree in two different orders, will the two corresponding binary trees look the same? Will the inorder traversal be the same? Will the postorder traversal be the same? Will the preorder traversal be the same?

Section 20.5 Heaps

20.12	What is a complete binary tree? What is a heap? Describe how to remove the root from a heap and how to add a new object to a heap.
20.13	What is the return value from invoking the remove method if the heap is empty?

---

[Page 691]

Section 20.6 Priority Queues

20.14

What is a priority queue?