Object-Oriented Software Design Chapter 13 Replace The Systemoutprintln Statements Denoted Comments And With The Statement Qenqueueqdequeue Would

29) If we replace the System.out.println statements (denoted in comments as d1, d2 and d3) with

the statement q.enqueue(q.dequeue( )); q would contain which order of int values after all

instructions have executed?

A) 3, 5, 9, 2, 4, 1, 8

B) 3, 5, 9, 1, 8, 2, 4

C) 5, 9, 2, 4, 1, 8, 3

D) 3, 2, 4, 5, 9, 1, 8

E) 2, 4, 1, 8, 3, 5, 9

30) After the instructions execute, x has the value

A) 16

B) 12

C) 19

D) 0

E) none of the above, the instruction int x = s.pop( ) results in an Exception being thrown

31) After the instructions execute, z has the value

A) 4

B) 9

C) 5

D) 12

E) 16

32) A dynamic data structure

A) almost always is implemented using lists of one sort or another

B) is just a collection

C) almost always is implemented using references (pointers) to objects

D) can have a fixed size

E) none of the above

33) In a linked list in Java

A) the link is an object

B) the link is a node

C) the link is a reference

D) the link is an int

E) the link is a class

34) A linear data structure

A) always has more than one link per node

B) is sometimes represented as a tree or a graph

C) can have but a single link per node

D) almost always is kept in sorted order either ascending or descending

E) none of the above

35) A simple linear list

A) is an example of a degenerate tree

B) is an example of a degenerate graph

C) is an example of a degenerate digraph

D) cannot be represented as a degenerate tree, graph or digraph

E) none of the above

13.2 True/False Questions

1) An Abstract Data Type is a data structure, that is, it is the listing of the instance data and the

visibility modifiers for those instance data.

2) The push and enqueue operations are essentially the same operations, push is used for Stacks

and enqueue is used for Queues.

3) The Abstract Data Type (ADT) is thought of as abstract because the operations that are to be

implemented are separated from the actual implementation, that is, an ADT can be implemented

in more than one way and that implementation is separate from how we might use the ADT.

4) An array is a List Abstract Data Type.

5) A linked list that contains 6 Nodes will have 6 reference pointers.

6) The linked list is superior to the array in all ways when it comes to implementing a list.

7) Queues and Stacks can be implemented using either arrays or linked lists.

8) In order to input a list of values and output them in order, you could use a Queue. In order to

input a list of values and output them in opposite order, you could use a Stack.

9) All classes are considered Abstract Data Types.

10) All Abstract Data Types are defined as classes in Java.

11) It is possible to restrict the type of object which is stored within a Java collection by using a

generic type when the collection is declared.

12) Trees and graphs, because they are dynamic in nature, cannot be implemented using Java

arrays.

13) A bi-directional list is an example of a non-linear data structure.

14) The only difference between a stack and a queue is that stacks operate using FIFO and

queues operate using LIFO.

15) Generics provide a mechanism for ensuring that collections are heterogeneous rather than

homogeneous.

19

13.3 Free-Form Questions

For the next questions, use the following class definition of a linked list Node:

class Node

{

int info;

Node next;

}

1) Show the instructions required to create a linked list that is referenced by head and stores in

order, the int values 3, 6 and 2. Assume that Node’s constructor receives no parameters.

2) Assume that head references a linked list that stores the values 3, 6 and 2 in that order. Show

the instructions needed to move the value 2 in front of the value 6 (so that the list is now 3, 2, 6).

3) Assume that head references a linked list that stores the values 3, 6 and 2. Show the

instructions needed to delete the Node with 3 from the list so that head would reference the list of

6 and 2.

4) Assume that head references a linked list although we don’t know what is currently stored in

that list. Write a block of code using a try-catch block that will work through the entire linked

list printing each element out, stopping only when we have reached the end of the list because a

NullPointerException is thrown. Once the Exception is thrown, output the number of elements

found in the list.

5) Rather than defining BookNode inside of BookList, another option is to define BookNode as a

separate class and import it into BookList. Why might we do this rather than define BookNode

inside of BookList?

6) What changes would have to be made to the BookNode class in order to define it as its own

class outside of BookList?

7) What changes would have to be made to the BookList class in order to properly use the

separate BookNode class?

8) Draw this structure.

9) Assume that DoubleNode temp references the node with the value 3. Provide code to delete

this DoubleNode without disconnecting the rest of the list.

10) A Queue q stores int values. Show what q will look like after each of the following

instructions is executed.

q.enqueue(6);

q.enqueue(12);

q.enqueue(13);

q.dequeue( );

q.enqueue(19);

q.enqueue(21);

q.enqueue(22);

q.dequeue( );

q.enqueue(20);

11) A Stack s stores int values. Show what s will look like after each of the following

instructions is executed.

12) One use of a Stack is to reverse the order of input. Write a method that reads a series of

Strings from the keyboard (assume the Scanner class has been imported) and outputs the Strings

in reverse order of how they were entered. The input will end with the String “end” but do not

output the String “end”. Assume that SStack is a Stack that can store Strings. Remember to

declare and instantiate your SStack in your method.

}

13) An abstract data type not covered in detail in the chapter is the Set ADT. A Set is like a set

as covered in your Mathematics courses. For instance, a set of even numbers might be {2, 4, 8,

12, 18, 32}. List 6 operations that you might implement for a Set ADT.

14) Two abstract data types are the ordered list and the unordered list. Explain how these two

ADTs are similar and how they will differ. To answer this question, assume that you do not

know how they are implemented (that is, whether they are implemented using an array or a

linked list).

15) What common Exception(s) might arise when using an array? What common Exception(s)

might arise when using a linked list?

16) (Challenger Problem) In implementing a Queue using an array, a problem might arise if the

Queue is implemented in such a way that items in the Queue are inserted at the next available

location and removed from the next leading position, but such that, once deleted, the emptied

space is unused. The problem that arises is one where there is free space still in the array, but it

is not usable because it is not at the end. Demonstrate this problem with a Queue that is stored in

an array of size 5 for the following instructions. Next, explain how you might resolve this

problem.

Queue q = new Queue(5); // assume the Queue constructor takes 5 as the size of the array

q.enqueue(3);

q.enqueue(4);

q.enqueue(1);

q.dequeue( );

q.enqueue(6);

q.enqueue(5);

q.dequeue( ); // at this point, there are only 2 item2 in the queue

q.enqueue(7); // this enqueue can not occur, why??

17) What is an ADT (an Abstract Data Type) and why are they considered to be “abstract?”

18) A double-ended queue, called a dequeue, is a queue that instead of having single links, in one

direction, has a pair of links, one pointed in each direction. Dequeues allows one to “push” and

“pop” information at either end. Is this ADT the same or different from a doubly linked list, as

described in the textbook?