Deck 15: Linked Data Structures

Question 1

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

Answer 1

C

Question 2

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

Answer 2

C

Question 3

To use the Java Iterator Interface you must import the ____________ package.

A)java.tools
B)java.linkedlist
C)java.iterator
D)java.util

Answer 3

D

Question 4

A linked data structure contains nodes and links.

Question 5

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

Question 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

Question 7

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

Question 8

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

Question 9

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

Question 10

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

Question 11

The _________ node is the first node in the tree data structure.

A)leaf
B)root
C)sibling
D)branch

Question 12

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

Question 13

Java does not come with a LinkedList library class.

Question 14

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

Question 15

A binary tree has exactly _________ link instance variables.

A)zero
B)one
C)two
D)three

Question 16

A node contains:

A)data items)
B)references)to another node
C)both A and B
D)none of the above

Question 17

A ____________ linked list has nodes that contain two references to Nodes.

A)circular
B)sequential
C)doubly
D)one-way

Question 18

The first node in a linked list is commonly referred to as the ________ node.

A)head
B)tail
C)predecessor
D)successor

Question 19

In Java,a node is a/an:

A)String
B)Integer
C)Object
D)Exception

Question 20

A common exception that occurs when using linked lists is the:

A)NodeOutOfBoundsException
B)NodeEmptyException
C)NullPointerException
D)NullNodeOccurredException

Question 21

What is the result of a preorder traversal of the binary search tree created in question 12 above?

Question 22

Redraw the diagram created in number 4 above after deleting the head node.

Question 23

Redraw the diagram created in number 3 above,after deleting the node containing Chicago.

Question 24

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.

Question 25

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

Question 26

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

Question 27

Create a generic Node class to represent the linked list depicted in your diagrams above.

Question 28

A stack cannot be represented as a linked list.

Question 29

Linked lists introduce the possibility of a privacy leak occurring.

Question 30

Write a method called displayList that displays the data items in the Node class created in number 6 above.

Question 31

What is the binary search tree storage rule?

Question 32

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.

Question 33

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

Question 34

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

Question 35

What is the function of the variable head when used with a linked list? What is the data type of the head variable?

Question 36

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

Question 37

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

Question 38

Draw the resulting binary search tree inserting the following values in the given order: 7,10,5,12,1,3,9.

Question 39

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

Question 40

Given the Node class created in number 6 above,write Java statements to delete a node from the beginning of the list.

Question 41

What is the result of an inorder traversal of the binary search tree created in question 12 above?

Question 42

Discuss the differences between a queue and a stack.

Question 43

What is the result of a postorder traversal of the binary search tree created in question 12 above?