Exam 1

Question 1

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

Answer 1

processing time

Question 2

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

Answer 2

analysis of algorithms

Question 3

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

Answer 3

size

Question 4

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

Answer 4

searching pool

Question 5

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

Answer 5

number of elements

Question 6

CPU processing time

Answer 6

time complexity

Question 7

memory space

Answer 7

space complexity

Question 8

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

Answer 8

growth function

Question 9

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

Answer 9

Asymptotic complexity

Question 10

Asymptotic complexity is called the _____ of the algorithm

Answer 10

order

Question 11

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

Answer 11

O(n^2)

Question 12

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

Answer 12

cannot

Question 13

As n increases, the various growth functions diverge ____________

Answer 13

dramatically

Question 14

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

Answer 14

outer loop; inner loop

Question 15

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

Answer 15

body; number of times

Question 16

We can use _________________ to measure elapsed execution time in Java

Answer 16

System.nanoTime()

Question 17

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

Answer 17

collection

Question 18

Some collections are ______ in nature, others are _________

Answer 18

linear; non-linear

Question 19

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

Answer 19

straight line

Question 20

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

Answer 20

hierarchy

Question 21

An ___________ hides details to make a concept easier to manage

Answer 21

abstraction

Question 22

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

Answer 22

interface

Question 23

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

Answer 23

encapsulates

Question 24

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

Answer 24

data type

Question 25

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

Answer 25

data structure

Question 25

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

Answer 25

abstract data type

Question 26

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

Answer 26

interface

Question 27

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 ______________________ .

Answer 27

Java API; Java Collections API

Question 28

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

Answer 28

stack; last in, first out

Question 29

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

Answer 29

reverse

Question 30

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

Answer 30

push, pop, peek, isEmpty, size

Question 31

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

Answer 31

type compatability

Question 32

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

Answer 32

type checking

Question 33

_________________ 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.

Answer 33

Inheritance; is-a

Question 34

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

Answer 34

polymorphic reference; different

Question 35

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 _________________ .

Answer 35

generic type; not; instantiated

Question 36

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 __________________ .

Answer 36

generic type T

Question 37

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

Answer 37

generically

Question 38

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

Answer 38

angle brackets

Question 39

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

Answer 39

"divide by 2"; stack

Question 40

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

Answer 40

postfix expression; following

Question 41

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

Answer 41

parenthesis

Question 42

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

Answer 42

java.util.Stack

Question 43

Javadoc comments begin with ______ and end with ______

Answer 43

/** */

Question 44

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

Answer 44

@

Question 45

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

Answer 45

interface

Question 46

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

Answer 46

abstract; signature

Question 47

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

Answer 47

class; definitions

Question 48

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

Answer 48

capacity

Question 49

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

Answer 49

expand

Question 50

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

Answer 50

top

Question 51

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

Answer 51

objects

Question 52

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

Answer 52

exception

Question 53

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

Answer 53

thrown

Question 54

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

Answer 54

EmptyCollectionException

Question 55

It is defined to extend _________________

Answer 55

RuntimeException

Question 56

An ________________ to array-based implementations are linked structures.

Answer 56

alternative

Question 57

A ___________________ uses object references to create ________ between objects.

Answer 57

linked structure; links

Question 58

There are ____________ values built into linked lists.

Answer 58

no index

Question 59

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

Answer 59

follow

Question 60

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

Answer 60

integrity

Question 61

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

Answer 61

insert; front

Question 62

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

Answer 62

delete

Question 63

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

Answer 63

before

Question 64

There are many _____________ on the basic linked list concept.

Answer 64

variations

Question 65

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.

Answer 65

next; previous

Question 66

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

Answer 66

LinearNode

Question 67

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

Answer 67

LinkedStack; StackADT

Question 68

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

Answer 68

count