Question 1

Two abstract data types are the ordered list and the unordered list. Explain how these two ADTs are similar and how they 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).

Accepted Answer

The answer of Two abstract data types are the ordered...

Question 2

Example Code Ch 13-5
Consider the following operations on a queue data structure that stores int values:
Queue q = new Queue();
q.enqueue(3);
q.enqueue(5);
q.enqueue(9);
System.out.println(q.dequeue()); // d1
q.enqueue(2);
q.enqueue(4);
System.out.println(q.dequeue()); // d2
System.out.println(q.dequeue()); // d3
q.enqueue(1);
q.enqueue(8);
-Refer to Example Code Ch 13-5: What value is returned by the last dequeue operation, denoted with a d3 as a comment.

Accepted Answer

Based on the operations performed, the queue currently stores the values 2, 4, 1, and 8. The next value to be dequeued is the first item that was added to the queue, which was 9. Therefore, the last dequeue operation will return the value 9.

Question 3

Example Code Ch 13-1
The following is a class definition of a linked list Node:
class Node
{
int info;
Node next;
}
-Refer to Example Code Ch 13-1: Assume that head references a linked list and stores in order, the int values 3, 6 and 2. Show the instructions needed to delete the Node with 3 so that head would reference the list 6 and 2.

Accepted Answer

The answer of Example Code Ch 13-1
The following is a...

Question 4

Example Code Ch 13-5
Consider the following operations on a queue data structure that stores int values:
Queue q = new Queue();
q.enqueue(3);
q.enqueue(5);
q.enqueue(9);
System.out.println(q.dequeue()); // d1
q.enqueue(2);
q.enqueue(4);
System.out.println(q.dequeue()); // d2
System.out.println(q.dequeue()); // d3
q.enqueue(1);
q.enqueue(8);
-Refer to Example Code Ch 13-5: After this code executes, how many elements would remain in q?

Accepted Answer

After the first three enqueues, the queue contains [3,5,9]. 
dequeue() removes and returns the first element of the queue, so d1 is equal to 3 and the queue now contains [5,9]. 
The next two enqueues add to the end of the queue, resulting in [5,9,2,4]. 
dequeue() is called again, removing and returning 5 which makes the queue [9,2,4]. 
dequeue() is called again, removing and returning 9 which makes the queue [2,4]. 
The next two enqueues add to the end of the queue, resulting in [2,4,1,8]. 
So there are 4 elements remaining in the queue.

Question 5

What is an ADT (Abstract Data Type) and why are ADTs considered to be abstract?

Accepted Answer

The answer of What is an ADT (Abstract Data Type)...

Question 6

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 allow 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?

Accepted Answer

The answer of A double-ended queue, called a dequeue, is...

Question 7

Example Code Ch 13-1
The following is a class definition of a linked list Node:
class Node
{
int info;
Node next;
}
-Refer to Example Code Ch 13-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.

Accepted Answer

The answer of Example Code Ch 13-1
The following is a...

Question 8

Example Code Ch 13-1
The following is a class definition of a linked list Node:
class Node
{
int info;
Node next;
}
-Refer to Example Code Ch 13-1: Assume that head references a linked list and stores in order, the int values 3, 2 and 6. Show the instructions needed to move the value 2 in front of the value 6 so that the list is now 3, 2 and 6.

Accepted Answer

The answer of Example Code Ch 13-1
The following is a...

Question 9

A simple linear list

Accepted Answer

A linear list can be represented as a degenerate tree where every node has either 0 or 1 child.

Question 10

Example Code Ch 13-1
The following is a class definition of a linked list Node:
class Node
{
int info;
Node next;
}
-Refer to Example Code Ch 13-1: 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.

Accepted Answer

The answer of Example Code Ch 13-1
The following is a...

Question 11

Example Code Ch 13-5
Consider the following operations on a queue data structure that stores int values:
Queue q = new Queue();
q.enqueue(3);
q.enqueue(5);
q.enqueue(9);
System.out.println(q.dequeue()); // d1
q.enqueue(2);
q.enqueue(4);
System.out.println(q.dequeue()); // d2
System.out.println(q.dequeue()); // d3
q.enqueue(1);
q.enqueue(8);
-Refer to Example Code Ch 13-5: 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?

Accepted Answer

The answer of Example Code Ch 13-5
Consider the following operations...

Question 12

Example Code Ch 13-6
Assume a stack class stores int values. Consider the following sequence of instructions.
Stack s = new Stack();
s.push(16);
s.push(12);
s.push(19);
int x = s.pop();
s.push(5);
s.push(9);
s.push(4);
int y = s.pop();
int z = s.pop();
-Refer to Example Code Ch 13-6: After the instructions execute, x has the value

Accepted Answer

The first three push operations add the values 16, 12, and 19 to the stack. The first pop operation removes the top value (19) and assigns it to x. The next three push operations add the values 5, 9, and 4 to the stack. The second pop operation removes the top value (4) and assigns it to y. The third pop operation removes the top value (9) and assigns it to z. Therefore, at the end of the instructions, x has the value of 19, y has the value of 4, and z has the value of 9.

Question 13

Challenge: Assume a function g(x) is defined as follows where x is an int parameter:
g(x) = g(x - 1) * g (x - 3) if x is even and x > 3
= g(x - 2) if x is odd and x > 3
= x otherwise
Write a recursive method to compute
g. 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.dequeue();
q.enqueue(6);
q.enqueue(5);
q.dequeue(); // at this point, there are only 2 items
in the queue
q.enqueue(7); // this enqueue can not occur, why??

Accepted Answer

The answer of Challenge: Assume a function g(x) is defined...

Question 14

What common exception(s) might arise when using an array? What common exception(s) might arise when using a linked list?

Accepted Answer

The answer of What common exception(s) might arise when using...

Question 15

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.dequeue();
q.enqueue(19);
q.enqueue(21);
q.enqueue(22);
q.dequeue();
q.enqueue(20);

Accepted Answer

The answer of A queue q stores int values. Show...

Question 16

An abstract data type not covered in detail in the chapter is the Set ADT. A Set is like a set as covered in 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.

Accepted Answer

The answer of An abstract data type not covered in...

Question 17

A dynamic data structure

Accepted Answer

Dynamic data structures require the ability to allocate and deallocate memory during program execution, which is typically achieved through the use of references or pointers to objects. Lists and collections are examples of dynamic data structures, but they are not requirements. The dynamic aspect of the structure refers to its ability to change size as needed, so a fixed size would not be possible.

Question 18

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.

Accepted Answer

The answer of One use of a stack is to...

Question 19

A stack s stores int values. Show what s will look like after each of the following instructions is executed.
s.push(5);
s.push(1);
s.push(4);
s.push(3);
s.pop();
s.push(2);
s.pop();
s.pop();
s.push(8);
s.push(7);
s.pop();
s.push(3);

Accepted Answer

The answer of A stack s stores int values. Show...

Question 20

Example Code Ch 13-6
Assume a stack class stores int values. Consider the following sequence of instructions.
Stack s = new Stack();
s.push(16);
s.push(12);
s.push(19);
int x = s.pop();
s.push(5);
s.push(9);
s.push(4);
int y = s.pop();
int z = s.pop();
-Refer to Example Code Ch 13-6: After the instructions execute, z has the value

Accepted Answer

The sequence of instructions creates a new stack object, adds the values 16, 12, and 19 to the stack, and then removes the top value (19) and assigns it to the variable x. The next three values added to the stack are 5, 9, and 4 (in that order). The next two values removed from the stack are y (which will be the top value, 4) and z (which will be the second value in the stack, 9). Therefore, z has a value of 9.

Quiz 13: Collections

Two abstract data types are the ordered list and the unordered list. Explain how these two ADTs are similar and how they 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).

What is an ADT (Abstract Data Type) and why are ADTs considered to be abstract?

A simple linear list

What common exception(s) might arise when using an array? What common exception(s) might arise when using a linked list?

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.dequeue(); q.enqueue(19); q.enqueue(21); q.enqueue(22); q.dequeue(); q.enqueue(20);

An abstract data type not covered in detail in the chapter is the Set ADT. A Set is like a set as covered in 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.

A dynamic data structure

A stack s stores int values. Show what s will look like after each of the following instructions is executed. s.push(5); s.push(1); s.push(4); s.push(3); s.pop(); s.push(2); s.pop(); s.pop(); s.push(8); s.push(7); s.pop(); s.push(3);