Final

Question 1

The classes that implement the _______ interface are all indexed collections

Answer 1

List

Question 2

Set objects:

Answer 2

are not indexed do not reveal the order of insertion of items

Denable efficient search and retrieval of information

allow removal of elements without moving other elements around

Question 3

Relative to a Set, Map objects provide efficient _____ and ______ of entries that contain pairs of objects (a unique key and the information)

Answer 3

search

retrieval

Question 4

Hash tables (used to implement a Map or Set ) store objects at arbitrary locations and offer an average constant time for ______,_______,_______.

Answer 4

insertion, removal, and searching

Question 5

is a collection that contains no duplicate elements and at most one null element

Answer 5

A set

Question 6

Required methods for set interface and methods:

Answer 6

testing set ,
testing for an empty set,
determining set size,
creating an iterator over the set

Question 7

Additional methods for adding an element and removing an element (the add method does not allow _________________ ).

Answer 7

duplicate items to be inserted

Question 8

Constructors that enforce the “________________” rule

Answer 8

no duplicate members

Question 9

Required method: __________ tests the subset relationship

Answer 9

containsAll

Question 10

Union:
Intersection:
Difference:

Answer 10

addAll
retainAll
removeAll

Question 11

Unlike the List.add method, the Set.add method returns false if you attempt to:

Answer 11

insert a duplicate item

Question 12

Unlike a List, a Set does not have a ____ method elements cannot be accessed by index

Answer 12

get

Question 13

You can iterate through all elements in a Set using an __________ object, but the elements will be accessed in arbitrary order

Answer 13

Iterator

Question 14

Returns an iterator over the elements in this set.

Answer 14

iterator()

Question 15

Collections implementing the ____ interface must contain unique elements

Answer 15

Set

Question 16

Unlike the ______ method, the _____ method returns _____ if you attempt to insert a duplicate item

Answer 16

List.add. Set.add. false

Question 17

Unlike a _____, a_____ does not have a ____ method-elements cannot be accessed by index

Answer 17

List. Set. get

Question 18

You can iterate through all elements in a _____ using an ________ object , but the elements will be accessed in arbitrary order

Answer 18

Set. Iterator

Question 19

The Map is related to the

Answer 19

Set

Question 20

Mathematically , a _____ is a set of ordered pairs whose elements are known as the key and the value

Answer 20

Map

Question 21

The collection of all keys is known as the

Answer 21

keySet

Question 22

The collection of all values is known as the

Answer 22

valueSet

Question 23

All the elements of ________ have a corresponding member in key Set

Answer 23

valueSet

Question 24

The goal of hash table is to

Answer 24

be able to access an entry based on its key value, not its location

Question 25

Using a hash table enables us to find elements

Answer 25

as quickly as possible

Question 26

The basis of hashing is to transform the item’s key value into an _________________ which is then transformed into a table index

Answer 26

integer value (its hash code)

Question 27

The hash function calculation is simply:

Answer 27

int index = asciiChar;

Question 28

If you assume that on average 100 characters were used, you could use a table of 200 characters and compute the index by :

Answer 28

int index = uniChar % 200

Question 29

If two hashcodes are the same indices this is called

Answer 29

A collision

Question 30

To resolve collisions, ___________ can be used to store or access an item in a hash table

Answer 30

linear probing

Question 31

another way of solving collisions:

Answer 31

Chaining

Question 32

What is the calculations for load factor?

Answer 32

Load factor = number of filled cells / table size

Question 33

What does load factor percentage tell us?

Answer 33

Performance

Question 34

With load factor the lower it is the

Answer 34

better there performance as there is a smaller chance of collision

Question 35

In hash tables, If there are no collisions, items can

Answer 35

be added or retrieved without searching, regardless of table size

Question 36

With a hash table you cannot

Answer 36

traverse a hash table in a meaningful way since the sequence of stored values is arbitrary

Question 37

Unlike lists, trees are ________ and

___________

Answer 37

nonlinear

hierarchical

Question 38

Trees can represent hierarchical organizations of information:

Answer 38

class hierarchy disk directory and subdirectories

Question 39

Trees can be defined and processed ___________

Answer 39

recursively

Question 40

A binary tree consists of a collection of elements or nodes , with each node linked to _____________ successors

Answer 40

at most two

Question 41

What is the root of a tree hierarchy?

Answer 41

The node at the top of the tree

Question 42

The successors of a tree node called it’s

Answer 42

children

Question 43

Each node in a tree has exactly _____ parent except for the root node which has no parent

Answer 43

one

Question 44

node that has no children is called a

Answer 44

Leaf node

Question 45

In recursive fashion, the child of a node is considered the root of a ________ of that node

Answer 45

subtree

Question 46

Three common kinds of tree traversal

Answer 46

Inorder
Preorder
Postorder

Question 47

In a preorder traversal the first node we visit is always

Answer 47

The root

Question 48

In a postorder traversal the last node we visit is always

Answer 48

The root

Question 49

In a binary search tree, all elements in the left subtree _________ those in the right subtree

Answer 49

Precede

Question 50

A binary search tree is an “________” tree, which never has to be sorted because its elements always satisfy the “________” requirement

Answer 50

ordered

Question 51

When new elements are inserted (or removed) properly, the binary search tree _________ its property

Answer 51

maintains

Question 52

The TreeSet class implements the Set interface by storing elements in a

Answer 52

balanced Binary Search Tree

Question 53

As elements are added to / removed from the TreeSet, the class may __________ nodes so that the tree remains balanced

Answer 53

rearrange

Question 54

A class of objects added to a ________ must provide a way to “compare” objects

Answer 54

TreeSet

Question 55

Given an object to be added to a TreeSet or TreeMap , we must be able to determine if the new object is

Answer 55

• Equal to the object at the root
• Less than the object at the root
• Greater than the object at the root

Therefore, the objects must be comparable

Question 56

Classes (such as String) that implement the Comparable interface must define a ___________ method

Answer 56

compareTo

Question 57

Method obji.compareTo (obj2) returns an integer with the following values

Answer 57

Negative if obj1 < obj2
Zero obj1=obj2
Positive if obj1>obj2

Question 58

Implementing the __________ interface provides a way to compare objects during a search

Answer 58

Comparable