Questions Chapter 2

Question 1

Inserting an item into an unordered array:

a. takes time proportional to the size of the array.
b. requires multiple comparisons
c. requires shifting other items to make room
d. takes the same time no matter how many items there are

Answer 1

takes the same time no matter how many items are there

Question 2

True or False: When you delete an item from an unordered array, in most cases you shift other items to fill in the gap.

Answer 2

True

Question 3

In an unordered array, allowing duplicates:

a. increases times for all operations
b. increases search times in some situations
c. always increases insertion times
d. sometimes decreases insertion times

Answer 3

increases search times in some situations

Question 4

True or False: In an unordered array, it’s generally faster to find out an item is not in the array than to find out it is.

Answer 4

False

Question 5

Creating an array in Java requires using the keyword _______.

Answer 5

new

Question 6

If class A is going to use class B for something, then:

a. class A’s methods should be easy to understand
b. it’s preferable if class B communicates with the program’s user
c. the more complex operations should be placed in class A
d. the more work that class B can do, the better.

Answer 6

d. the more work that class B can do, the better.

Question 7

When class A is using class B for something, the methods and fields class A can access in class B are called class B’s ____________.

Answer 7

interface.

Question 8

Ordered arrays, compared with unordered arrays, are:

a. much quicker at deletion
b. quicker at insertion
c. quicker to create
d. quicker at searching

Answer 8

d. quicker at searching

Question 9

A logarithm is the inverse of ________ _______ _________.

Answer 9

raising to a power.

Question 10

The base 10 logarithm of 1,000 is _________.

Answer 10

3

Question 11

The maximum number of elements that must be examined to complete a binary search in an array of 200 elements is:

a. 200
b. 8
c. 1
d. 13

Answer 11

8

Question 12

The base 2 logarithm of 64 is ____.

Answer 12

6

Question 13

True or False: The base 2 logarithm of 100 is 2.

Answer 13

False

Question 14

Big O notation tells:

a. how the speed of an algorithm relates to the number of items
b. the running time of an algorithm for a given size data structure
c. the running time of an algorithm for a given number of items
d. how the size of a data structure relates to the number of items

Answer 14

a how the speed of an algorithm relates to the number of items

Question 15

O(1) means a process operates in _________ time.

Answer 15

constant

Question 16

Either variables of primitive types or ________ can be placed in an array.

Answer 16

objects

Question 17

__________ arrays offer fast insertion, but slow searching and deletion.

Answer 17

Unordered

Question 18

A _______ ________ is composed of the methods (and occasionally fields that the class user can access.

Answer 18

class interface

Question 19

A binary search can be applied to an ________ array.

Answer 19

ordered

Question 20

The logarithm to the base B of a number A is (roughly) the number of times you can divide A by B before the result is less than ______.

Answer 20

1

Question 21

Binary searches require time proportional to the logarithm of the number of _______.

Answer 21

items

Question 22

An algorithm that runs in _____ time is best, _____ time is good, _____ time is fair, and ______ is pretty bad.

Answer 22

O(1) is best, O(log N) is good, O(N) is fair, and O(N^2) is pretty bad.