Chapter 15 Linked Data Structures – absolute java test bank

Download  file with the answers

Chapter 15 Linked Data Structures - absolute java test bank

1 file(s)   55.44 KB

Not a member!
Create a FREE account here to get access and download this file with answers

Chapter 15
Linked Data Structures
 Multiple Choice
1) The first node in a linked list is commonly referred to as the ________ node.
(a) head
(b) tail
(c) predecessor
(d) successor

2) In Java, a node is a/an:
(a) String
(b) Integer
(c) Object
(d) Exception

3) A node contains:
(a) data item(s)
(b) reference(s) to another node
(c) both A and B
(d) none of the above

4) In Java, you indicate the end of a linked list be setting the link instance variable of the last node in the linked list to __________.
(a) 0
(b) -1
(c) 1
(d) null

5) If the head instance variable of a linked list contains a reference to null, this means the list is:
(a) full
(b) empty
(c) lost
(d) none of the above

6) Making the Node class a private inner class of a linked data structure is an example of:
(a) polymorphism
(b) encapsulation
(c) inheritance
(d) all of the above

7) A common exception that occurs when using linked lists is the:
(a) NodeOutOfBoundsException
(b) NodeEmptyException
(c) NullPointerException
(d) NullNodeOccurredException

8) A ____________ copy of an object is a copy that has no references in common with the original object.
(a) bit copy
(b) deep copy
(c) shallow copy
(d) none of the above

9) A _____________ copy of an object is a copy that has references in common with the original object.
(a) bit copy
(b) deep copy
(c) shallow copy
(d) none of the above

10) To use the Java Iterator Interface you must import the ____________ package.
(a) java.tools
(b) java.linkedlist
(c) java.iterator
(d) java.util

11) Java contains a mechanism that automatically reclaims memory. This mechanism is called:
(a) Garbage elimination
(b) Garbage collection
(c) Taking out the trash
(d) None of the above

12) A ____________ linked list has nodes that contain two references to Nodes.
(a) circular
(b) sequential
(c) doubly
(d) one-way

13) The _________ node is the first node in the tree data structure.
(a) leaf
(b) root
(c) sibling
(d) branch

14) A binary tree has exactly _________ link instance variables.
(a) zero
(b) one
(c) two
(d) three

15) Recursively visiting the root node, left subtree and then the right subtree describes:
(a) preorder processing
(b) inorder processing
(c) postorder processing
(d) none of the above

16) Recursively visiting the left subtree, right subtree and then the root describes:
(a) preordering processing
(b) inorder processing
(c) postorder processing
(d) none of the above

17) A _________________ maps a data value such as a String into a number:
(a) recursive function
(b) key function
(c) hash function
(d) none of the above

 True/False
1) A linked data structure contains nodes and links.

2) Java does not come with a LinkedList library class.

3) When using a linked list, you do not need to know when the end of the list has been reached.

4) Forgetting to set the reference instance variable of the last node in a linked list to null will cause a logic error.

5) Linked lists introduce the possibility of a privacy leak occurring.

6) A deep copy of an object is a copy that has references in common with the original object.

7) A copy constructor and a clone method should normally make a deep copy whenever possible.

8) If you define a clone method, the class should implement the Cloneable interface.

9) An iterator is any object that allows you to step through the list one item at a time.

10) A stack cannot be represented as a linked list.

11) A queue is a last-in/first-out structure.

 Short Answer/Essay
1) What is the function of the variable head when used with a linked list? What is the data type of the head variable?
Answer: The head variable references the first node in a linked list. Without this reference variable, the beginning of the list is lost. The data type of the head variable is of the Node type.
2) Draw a diagram of a linked list that contains nodes with data items of type String that contains the name of a city and type double that contains a pollution index. Include an instance variable named head to indicate the beginning of the list. Insert the following nodes: Franklin, 15.7, Chicago, 23.2, Denver, 7.2.
Answer:

3) Redraw the diagram created in number 2 above after inserting a node containing Chattanooga, 27.6.
Answer:

4) Redraw the diagram created in number 3 above, after deleting the node containing Chicago.
Answer:

5) Redraw the diagram created in number 4 above after deleting the head node.
Answer:

6) Create a generic Node class to represent the linked list depicted in your diagrams above.
Answer:
public class Node
{
private String cityName;
private double pollutionCount;
private Node link;

public Node()
{
link = null;
cityName = null;
pollutionCount = 0.0;
}
public Node(String cName, double pCount, Node linkValue)
{
setData(cName, pCount);
link = linkValue;
}
public void setData(String cName, double pCount)
{
cityName = cName;
pollutionCount = pCount;
}
public void setLink(Node newLink)
{
link = newLink;
}
public String getCityName()
{
return cityName;
}
public double getPollutionCount()
{
return pollutionCount;
}
public Node getLink()
{
return link;
}
}
7) Given the Node class created in number 6 above, write Java statements to insert a new node containing (Chattanooga, 23.7) into an empty list.
Answer:
Node head=null;
Node current=null;
//Create a new node and insert it into an empty list.
current = new Node(“Chattanooga”, 23.7, null);
head = current;
8) Given the Node class created in number 6 above, write Java statements to delete a node from the beginning of the list.
Answer:
current = head;
//Check for one element list
if(current.getLink() == null)
head = null;
else
{
current = current.getLink();
head = current;
current = null;
}
9) Write a method called displayList that displays the data items in the Node class created in number 6 above.
Answer:
public static void DisplayList(Node h)
{
Node current = h;
while(current != null)
{
System.out.println(“The node contains ” + current.getCityName() + ” with
a pollution index of ” + current.getPollutionCount());
current = current.getLink();
}
}
10) What is the binary search tree storage rule?
Answer:
1. All the values in the left subtree are less than the value in the root node.
2. All the values in the right subtree are greater than or equal to the value in the root node.
3. This rule applies recursively to each of the two subtrees.
(The base case for the recursion is an empty tree, which is always considered to satisfy the rule.)
11) Draw the resulting binary search tree inserting the following values in the given order: 7, 10, 5, 12, 1, 3, 9.
Answer:

12) What is the result of a preorder traversal of the binary search tree created in question 12 above?
Answer: 7, 5, 1, 3, 10, 9, 12
13) What is the result of an inorder traversal of the binary search tree created in question 12 above?
Answer: 1, 3, 5, 7, 9, 10, 12
14) What is the result of a postorder traversal of the binary search tree created in question 12 above?
Answer: 1, 3, 5, 9, 12, 10, 7
15) Discuss the differences between a queue and a stack.
Answer: A stack is a last-in/first-out (LIFO) data structure. Items are removed in the reverse order in which they were inserted. A queue is a first-in/first-out (FIFO) data structure. It mimics a line. Items are inserted at the end of the structure and are removed from the front of the structure.