Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Data Structures > Exam 2 > Flashcards

Exam 2 Flashcards

1
Q

An array is an indexed structure:

A

elements may be accessed in any order using subscript

elements can be accessed in sequence using a loop that increments the subscript

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

With Java arrays object , you cannot

A

increase or decrease its length (length is fixed )

insert an element at a specified position

remove an element at a specified position

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

A _____ is a collection of elements, each with a position

A

list

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

In Java, the methods to be implemented by lists are defined in the ____ interface

A

List

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Classes that implement the List interface provide the functionality of an array and offer several operations :

A

Obtain an element at a specified position

Replace an element at a specified position

Find a specified target value

Add an element at either end a

Remove an element from either end

Insert or remove an element at any position

Traverse the list

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

The simplest class that implements the List interface

A

ArrayList class

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Use an ArrayList class when:

A

you will be adding new elements to the end of a list

you need to access elements quickly in arbitrary order

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

How do you declare a List “object” whose elements will reference String objects :

A

List myList = new ArrayList();

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

ArrayList is empty and has a default capacity of:

A

10 elements

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

In an ArrayList, you cannot access an element using a bracket index as you can with arrays (array[1]).

Instead use _____ method.

A

get()

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

How to search an ArrayList to get location

A

.indexOf()

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

List myList new ArrayList <>() ; language feature called:

A

generics

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

The statement creates a List of Strings; only references of type String can be stored in the list

A

Generic collections

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

In generic collection, String in this statement is called a:

A

type parameter

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

The _______________ sets the data type of all objects stored in a collection

A

type parameter

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

The general declaration for generic collection is:

A

CollectionClass ab1e= new 1ass<>() ;

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

In a generic collection The indicates a:

A

type parameter

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Adding a noncompatible type to a generic collection will generate an error during:

A

compile time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

The elements of a list can be of any type, including your own classes :

A

List inventory new ArrayList (); = new ArrayList();

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

In order to use _______ with a List of user-defined objects, there must be a way to determine when two objects are equal

A

indexof

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

indexOf is done by overriding the ______ method inherited from ______

A

equals

object

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

The equals method has a parameter of type:

A

Object

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

How to use Object.equals

A

public boolean equals (Object other)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What does Object.equals do?

A

Compares two references to determine if they refer to the same object:

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

An Object.equals method class must _____________ for the comparison to be meaningful

A

Override equals

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

How do you override an equals() in computer class?

A 
@Override 
public boolean equals (Object obj) 
{
    if (obj instanceof Computer)  
    {         
       Computer other = (Computer) obj: 
       return computePower() == other.computePower
    }
   (); return false ;
}
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

Internally, the elements of an ArrayList are stored in an array. Three variables are needed:

A

theData : An array to hold the elements capacity : Physical size of array
size : Number of data items in the list

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

We have two add methods:

A

One will append at the end of the list

The other will insert an item at a specified position

29
Q

Implementing add (String anEntry), If size is less than capacity, then to append a new item:

A

insert the new item at the position indicated by the value of size

increment the value of size

return true to indicate successful insertion

30
Q

To insert into the middle of the array, the values at the insertion point are shifted over to make room, beginning at the end of the array and proceeding in the indicated order

A

Implementing add (int index, String anEntry)

31
Q

When an item is removed , the items that follow it must be moved
________ to close the gap

A

forward

32
Q

Creates a new array that is twice the size of the current array and then copy the contents of the new array

A

reallocate Method

33
Q

Single-linked ArrayList is limited because

A

It’s add and remove method require a loop to shift elements

34
Q

_________ is useful for inserting and removing at arbitrary locations without shifting elements, regardless of the size of the list

A

linked list

35
Q

In a linked list, instead of using an array , each element is stored in a ______ and linked to the ______ element

A

node

next

36
Q

A LinkedList object can be used anywhere an ArrayList is used :

A

List < String > myList = new Linkedlist<>();

37
Q

List < String > myList = new Linkedlist<>();

The initial list is empty. How do we add strings?

A

myList.add(“Tom”);

38
Q

A list node contains :

A

a data item

one (or more) link(s) (references to other node(s))

39
Q

A Linkedlist object has a data field _____, which references the first list node.

A

head

40
Q

Limitations of a singly-linked list include:

A

Insertion at the front is quickinsertion at other positions may require a list traversal to find insertion place

Insertion is convenient only after a referenced node

Removing a node requires a reference to the previous node

We can traverse the list only in the forward direction

41
Q

Limitations such as:

Insertion at the front is quickinsertion at other positions may require a list traversal to find insertion place

Insertion is convenient only after a referenced node

Removing a node requires a reference to the previous node

We can traverse the list only in the forward direction

We can overcome these limitations by:

A

Adding a reference in each node to the previous node, creating a double-linked list

42
Q

can be viewed as a moving place marker that keeps track of the current position in a particular linked list

A

An iterator

43
Q

An Iterator object for a list starts at the:

A

List head

44
Q

The programmer can move the Iterator by calling its _____ method.

A

next

45
Q

The ________ stays on its current list item until it is needed

A

Iterator

46
Q

By using an Iterator to traverse a linked list, the code segment can be:

A

rewritten so as to require n operations

47
Q

Where is the iterative interface defined?

A

In java.util

48
Q

The _____ interface declares the method ________ which returns an ________ object that iterates over the elements of that list

A

List

iterator

Iterator

49
Q

An Iterator is:

it does not refer to a particular object at any given time

A

conceptually between elements

50
Q

How do we process all List through Iterator?

A

Iterator iter = aList.iterator();

while(iter.hasNext()) {
item = iter.next();

}

51
Q

You can use the ____________ method to remove items from a list as you access them.

A

Iterator remove()

52
Q

deletes the most recent element returned in an Iterator

A

remove()

53
Q

You must call next() before each remove(); otherwise , an _________ will be thrown

A

IllegalStateException

54
Q

What’s the different LinkedList.remove(i) vs Iterator.remove

A

LinkedList.remove(i): must walk down the list each time , then remove

Iterator.remove removes items without starting over at the beginning

55
Q

How do you remove all elements from a list of type Integer that are divisible by a particular value:

A

public static void remove DivisibleBy (LinkedList alist, int div)

Iterator iter = aList.iterator());

while ( iter.hasNext() ) {

int nextInt = iter.next (); 
if ( nextInt % div == 0) {
     iter.remove();
}
}
}
56
Q

Iterator limitations:

How do we overcome these limitations?

A

Traverses List only in the forward direction

Provides a remove method, but no add method

You must advance the Iterator using your own loop if you do not start from the beginning of the list

ListIterator extends Iterator, overcoming these limitations

57
Q

ListIterator positions are assigned an index from ____ to ____

A

0

Size

58
Q

ListIterator has a method which is able to receive the proceeding and future index of items.

A

nextIndex();

previousIndex();

59
Q

ListIterator is a subinterface of:

A

Iterator

60
Q

Classes that implement ListIterator must provide the features of:

A

Both ListIterator and Iterator

61
Q

Requires fewer methods

Can iterate over more general data structures

used by enhanced for loop

A

Iterator

62
Q

Iterator is required by the ________ interface

A

Collection

63
Q

ListIterator is required only by the _______ interface

A

List

64
Q

The collection interface specifically excludes:

But including:

A

add (int , E)
get ( int)
remove ( int)
set (int, E )

add (E)
remove (Object)
the iterator method

65
Q

In a general Collection the order of elements is:

A

not specified

66
Q

For collections implementing the List interface, the order of the elements is determined by the:

A

index

67
Q

In a general Collection, the position where an ______ is inserted is not specified

A

object

68
Q

In ArrayList and LinkedList, add (E) always inserts at the ____ and always returns:

A

end

true

Data Structures (4 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions