Brainscape's Knowledge GenomeTM

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


See full index

CIS 211 > Exam 1 > Flashcards

Exam 1 Flashcards

Ch. 11-14

1
Q

The efficiency of an algorithm is usually expressed in terms of its use of __________ ____.

A

processing time

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

The _______ __ ___________ involves categorizing an algorithm in terms of efficiency.

A

analysis of algorithms

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

For every algorithm we want to analyze, we need to define the ____ of the problem

A

size

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

For a searching algorithm, the size of the problem is the size of the _________ ____

A

searching pool

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

For a sorting algorithm, the size of the problem is the ______ __ ________ to be sorted

A

number of elements

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

CPU processing time

A

time complexity

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

memory space

A

space complexity

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

A ______ ________ shows the relationship between the size of the problem (n) and the value optimized (time).

A

growth function

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

__________ __________ is based on the dominant term of the growth function - the term that increases most quickly as n increases

A

Asymptotic complexity

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

Asymptotic complexity is called the _____ of the algorithm

A

order

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

We say that an algorithm is order n^2 which is written ____

A

O(n^2)

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

Processor speed and memory ______ make up for the differences in efficiency of algorithms.

A

cannot

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

As n increases, the various growth functions diverge ____________

A

dramatically

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

nested loops: multiply the complexity of the _____ ____ by the complexity of the _____ ____

A

outer loop; inner loop

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

to analyze loop execution: first determine the order of the ____ of the loop, then multiply that by the _____ __ _____ the loop will execute

A

body; number of times

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

We can use _________________ to measure elapsed execution time in Java

A

System.nanoTime()

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

A __________ is an object that holds and organizes another object. It provides operations for accessing and managing its elements

A

collection

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

Some collections are ______ in nature, others are _________

A

linear; non-linear

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

A linear collection is one in which the elements of the collection are organized in a ________ ____

A

straight line

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

A nonlinear collection is one in which the elements are organized in something other than a straight line such as _________ or a network

A

hierarchy

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

An ___________ hides details to make a concept easier to manage

A

abstraction

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

A collection is an abstraction that defines the
_____________ operations through which the
user can manage the objects in the collection.

A

interface

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

The interface hides (_______________) the object’s data and the implementation of the
operations.

A

encapsulates

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

A
_________________ is a group of values and the operations defined on those values.

A

data type

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

A
__________________________ is the set of programming constructs and techniques
used to implement a collection.

A

data structure

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

An
_______________________________ (ADT) is a data type that is not pre-defined in the
programming language.

A

abstract data type

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

A class that uses a collection interacts with it through a particular _______________

A

interface

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

The various classes provided with Java are referred to as the _____________ (Application
Programming Interface). The subset of those classes that support collections is called the
______________________
.

A

Java API; Java Collections API

28
Q

A
_________
is a linear collection whose elements are added in a
________________ (LIFO

A

stack; last in, first out

29
Q

One of the principal uses of a stack in computing is to ___________ the order of something.

A

reverse

30
Q

These are the classic stack operations: _______, _______, _______, __________, _______

A

push, pop, peek, isEmpty, size

31
Q

_____________________ indicates whether a particular assignment of an object to a
reference is lega

A

type compatability

32
Q

Java provides compile-time
__________________ that will flag any invalid assignment.

A

type checking

33
Q

_________________ can be used to create a class hierarchy where a reference variable can
be used to point to any object related to it by ________ relationship.

A

Inheritance; is-a

34
Q

A
__________________________
is a reference variable that can refer to
_____________
types of objects at different points in time.

A

polymorphic reference; different

35
Q

Java enables us to define a class based on a
_________ type, that is, we can define a class so
that it stores, operates on, and manages objects whose type is _____ specified until the
class is
_________________
.

A

generic type; not; instantiated

36
Q

Suppose we define a stack that holds Object references, which would allow it to hold any
object, we can define that class to store a
__________________
.

A

generic type T

37
Q

The type is referred to ________________ in the class, and the specific type is specified
only when an object of that class is created.

A

generically

38
Q

The generic type placeholder is specified in ___________________ in the class header:

A

angle brackets

39
Q

For our conversion, we’ll use an algorithm called _______________________
that uses a
__________ to keep track of the binary digits.

A

“divide by 2”; stack

40
Q

A ________________________ is written with the operator ___________ the two operands
instead of between them.

A

postfix expression; following

41
Q

Postfix expressions eliminate the need for ____________ to specify the order of operations.

A

parenthesis

42
Q

Both examples use the
______________________ class, which has been part of the Java
collections API.

A

java.util.Stack

43
Q

Javadoc comments begin with ______
and end with ______

A

/** */

44
Q

Specific Javadoc tags, which begin with _____, are used to identify particular information.

A

@

45
Q

A Java
____________ provides a formal mechanism for defining the set of operations for
any collection.

A

interface

46
Q

A Java interface defines a set of
__________ methods, specifying each method’s _________
but not its body.

A

abstract; signature

47
Q

A
________ that implements an interface provides _____________
for the methods defined
in the interface.

A

class; definitions

48
Q

The number of cells in an array is called its ____________
.

A

capacity

49
Q

To
_____________ the capacity of the stack, we’ll create a new (larger) array and copy over
the elements.

A

expand

50
Q

An integer called _______ will indicate where the top of the stack is, as well as how many
elements are in the stack currently.

A

top

51
Q

You cannot instantiate an array of a generic type directly. Instead, create an array of
___________ references and cast them to the generic type.

A

objects

52
Q

An
_____________ is an object that defines an unusual or erroneous situation.

A

exception

53
Q

An exception is ___________ by a program, and it can be caught and handled appropriately.

A

thrown

54
Q

An
________________________________
is thrown when pop or peek is attempted, and
the stack is empty.

A

EmptyCollectionException

55
Q

It is defined to extend _________________

A

RuntimeException

56
Q

An
________________ to array-based implementations are linked structures.

A

alternative

57
Q

A
___________________ uses object references to create ________ between objects.

A

linked structure; links

58
Q

There are
____________
values built into linked lists.

A

no index

59
Q

To access each node in the list, you must __________
the references from one node to the
next.

A

follow

60
Q

Care must be taken to maintain the
___________
of the links.

A

integrity

61
Q

To
_________
a node at the
________ of the list, first point the new node to the front node,
then reassign the front reference.

A

insert; front

62
Q

To
_________ the first node, reassign the front reference accordingly.

A

delete

63
Q

If the deleted node is needed elsewhere, a reference to it must be established ______
reassigning the front pointer.

A

before

64
Q

There are many _____________ on the basic linked list concept.

A

variations

65
Q

For example, we could create a doubly-linked list with
_______
and
___________
references in each node and a separate pointer to the rear of the list.

A

next; previous

66
Q

A separate ______________
class forms the list and holds a reference to the element
stored.

A

LinearNode<T></T>

67
Q

Our
_____________ class stores a generic type T and implements the same _____________
interface used previously.

A

LinkedStack<T>; StackADT<T></T></T>

68
Q

An integer ________ will store how many elements are currently in the stack.

A

count

CIS 211 (1 decks)

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