Test 3

Question 1

is one of the most commonly used data structures in computer science

Answer 1

A stack

Question 2

The stack’s storage policy is

Answer 2

Last-In, First Out , or LIFO

Question 3

What methods can Stacks use?

Answer 3

boolean empty()
E peek()
E pop()
E push( E obj )

Question 4

a string that reads identically in either direction, letter by letter (ignoring case)

Answer 4

Palindrome

Question 5

When analyzing arithmetic expressions, it is important to determine whether an expression is balanced with respect to parentheses.

The problem is further complicated if braces or brackets are used in conjunction with parentheses

The solution is to use:

Answer 5

stacks!

Question 6

PITFALL of stacks: attempting to pop an empty stack will:

Answer 6

throw an Emptystackexception . You can guard against this by either testing for an empty stack or catching the exception

Question 7

Stacks are so common in computing , that Java included. A Stack class in its early versions:

Answer 7

import java.util.Stack; 
Stack myStack = new Stack();

Question 8

A queue differs from a stack in one important way:

Answer 8

a queue a is FIFO list - First-In, First-Out

Question 9

Operating systems use queues to:

Answer 9

keep track of tasks waiting for a scarce resource

ensure that the tasks are carried out in FIFO order

Question 10

Queue uses methods:

Answer 10

boolean offer(E item) 
E remove() 
E peek()
E element()

Question 11

The __________ class provides methods for inserting and removing elements at either end of a linked list, which means all _______ methods can be implemented easily

Answer 11

Linkedlist

Queue

Question 12

can be used to generate simple solutions to problems that are difficult to solve by other means

Answer 12

Recursion

Question 13

reduces a problem into one or more simpler versions of itself

Answer 13

Recursion

Question 14

I’m recursive strategy there must be _______________ (the _________), for a small value of n, that can be solved directly

Answer 14

at least one case

base case

Question 15

In recursive strategy a problem of a given size n can be reduced to smaller versions of the same problem (____________)

Answer 15

recursive case(s)

Question 16

The process of returning from recursive calls and computing the partial results is called

Answer 16

unwinding the recursion

Question 17

Java maintains a ___________ on which it saves new information in the form of an _____________

Answer 17

run-time stack

activation frame

Question 18

The activation frame contains storage for:

Answer 18

method arguments

local variables ( if any)

the return address of the instruction that called the method

Question 19

Whenever a new method is called ( recursive not ), a new activation frame is:

Answer 19

pushed onto the run-time stack

Question 20

Mathematicians often use recursive definitions of formulas that lead naturally to recursive algorithms

Examples include :

Answer 20

factorials
powers
greatest common divisors (gcd)

Question 21

Known as infinite recursion: the program will eventually throw:

Answer 21

Stack OverflowError exception

Question 22

In the factorial method, you could throw an ________________ if n is negative

Answer 22

IllegalArgumentException

Question 23

In iteration, a loop condition determines:

Answer 23

whether to repeat the loop body or exit the loop

Question 24

A recursive algorithm may be simpler than an iterative algorithm and thus:

Answer 24

easier to write, code, debug, and read

Question 25

Recursive methods often have __________________ relative to their iterative counterparts

Answer 25

slower execution times

Question 26

The overhead for loop repetition is _______ than the overhead for a method call and return

Answer 26

smaller

Question 27

If it is easier to design a solution using recursion , then:

Answer 27

you should code it as a recursive method

Question 28

The reduction in efficiency does not outweigh:

Answer 28

the advantage of readable code