Deck 15: Linked Data Structures

Question 1

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

Answer 1

C

Question 2

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

Answer 2

B

Question 3

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

Answer 3

A

Question 4

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 5

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

Question 6

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

Question 7

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

Question 8

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 9

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

Question 10

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 11

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

Question 12

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

Question 13

Java does not come with a LinkedList library class.

Question 14

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 15

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

Question 16

The first node in a linked list is commonly referred to as the ________ node.
(a)head
(b)tail
(c)predecessor
(d)successor

Question 17

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

Question 18

A linked data structure contains nodes and links.

Question 19

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 20

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

Question 21

Linked lists introduce the possibility of a privacy leak occurring.

Question 22

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

Question 23

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

Question 24

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

Question 25

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 26

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

Question 27

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

Question 28

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

Question 29

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

Question 30

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

Question 31

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

Question 32

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

Question 33

A stack cannot be represented as a linked list.

Question 34

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

Question 35

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

Question 36

What is the binary search tree storage rule?

Question 37

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

Question 38

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

Question 39

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 40

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

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?