Home

Student Resources

Chapter Quizzes

Chapter 15

Chapter 15

Linked Data Structures

This activity contains 15 questions.

	Is it true that LinkedList2 is a "better" implementation of a simple linked list than LinkedList1?   Yes, because the privacy issues have been solved No, because it's a more complex declaration due to the use of inner classes Yes, but only if the inner class is declared to be public - not private No, because the number of classes has increased

	Privacy leaks may occur any time a method returns a reference. Does the Node1 getLink method have this problem?   Yes, Node1's getLink does pose a privacy leak - both pieces of private data become accessible No, it's not a problem because Node1's instance data is private No, it's not a problem because Node1's String data is immutable No, it's not a problem because you can guarantee that Node1 will be placed in a package

	The links in a tree node should be declared to be   private to prevent privacy leaks protected so that inheritance works properly using "package" access, so that all methods within the package have easy access to nodes within the tree public so that external methods can access nodes farther down the tree

	The root in a tree has the property that:   Every leaf is accessible from the root by following a sequence of links You can (fully) traverse a tree by starting at any node other than the root The root cannot be a leaf You can reach the root from any leaf by following a sequence of links

	What are the advantages of the Iterator pattern?   They all will have ways to start, stop, restart, and move to the next iteration in a relatively uniform fashion They all will have ways to start, stop, and move to the next iteration in a relatively uniform fashion They all will have ways to start, top, move to the next iteration, tell how many iterations may occur in a relatively uniform fashion They all will have ways to start, stop, move forward, and move backward in a relatively uniform fashion

	What are the differences between a deep copy and a shallow copy? A deep copy contains no references in common with the original data structure A shallow copy contains no references in common with the original data structure A deep copy usually is more expensive (in time) and more complicated to implement than a shallow copy A deep copy usually will execute more slowly than a shallow copy   True statements: (b), (c), (d) True statements: only (a) and (c) True statements: (a), (c), (d) True statements: only (b) and (d)

	What is an immutable iterator?   It returns a clone of the data object rather than a reference to the data object It returns a data object containing only non-reference information It returns a (shallow) copy of the data object rather than a reference to the data object It returns a static copy of the data object rather than a reference to the data object

	What is the advantage of maintaining a doubly linked list?   You can delete nodes in the middle of the list far more easily You can remove nodes more easily at each end of the list There's no particular advantage - such lists are just more complicated to maintain You can traverse the list easily in both "forward" and "backward" directions

	What is the advantage of maintaining references to both the head and tail (first and last nodes) in a list structure?   It makes adding to the head of the list far easier and more efficient It makes extending the list far easier and more efficient There is no particular advantage It makes deleting the first node far easier and more efficient

	What must be done in the Java code that deletes a node from a linked data structure?   All values of instance data should be reset to zero before the node is deleted The node should be added to an "available storage list" before being deleted Nothing special needs to be done since Java uses automatic garbage collection The references in the deleted node should be set to null before being deleted

	What statement(s) is (are) true? A balanced tree has about the same number of nodes in its left subtree as in its right subtree, and this is true at all nodes in the tree A balanced tree has about the same number of leaf nodes in its left subtree as in its right subtree A balanced tree has about O(log n) worst case running time Searching a balanced tree is about as efficient as searching a sorted array   All statements are true Only statement (b) is false Only statement (c) is false Only statement (d) is false

	Which statement(s) are true? A stack: Exhibits "last in, first out" behavior Exhibits "first in, first out" behavior Can be implemented as a simple list Can be implemented as an array   True: (a), (c), (d) True: only (a) and (c) True: (b), (c), (d) True: only (b) and (c)

	Which statements are true about linked data structures (LDT) ? An LDT consists of a collection of nodes A node in an LDT usually contains at least one link A node in an LDT can contain any kind of data LDTs (nodes) usually are realized as instances of a class called Node   True: all the statements True: (a), (c), (d) True: only (a) and (d) True: all the statements, except (c)

	Which statements are true? The three tree traversal variants, preorder, inorder, and postorder... only apply to sorted binary trees apply to all binary trees only apply to trees that are implemented as list structures apply to all trees, independent of implementation method   True: only (b) True: (b) and (d) True: (a) and (d) True: (b) and (c)

	Would it be a good idea to use a reference back to the head of a list instead of null to indicate the end of a list?   No, because null always is easy to test for - while testing for the head node makes it difficult to create general-purpose code Yes, because that way you can terminate each list with a special reference No, because there's no good way to get an reference to the head Yes, it would be just as good as using null

Copyright © 1995 - 2010 Pearson Education . All rights reserved. Pearson Addison Wesley is an imprint of Pearson . Legal Notice | Privacy Policy | Permissions