The questions below are from a "data structures and algorithms in c++"

The mathematical description for the moves used in the Towers of Hanoi puzzle is described as follows: T(n) = T(n 1) + 1 + T(n 1), for all n > 1 What is the best test for the ground (or anchor) case when this function is implemented using recursion?

Return from the function if n > 1

Return from the function if n = 2

Return from the function if n = 1

Return from the function if n < 2

A recursive function is always much easier to understand then an iterative function that performs the same task.

True

False

Which of the following is true about recursion? (Select all that apply)

It requires advanced mathematics

It can be used with two or more functions

It can often be hard to debug

It should only be used with mathematical functions

Which of the following can be implemented using recursion? (Select all that apply)

The tower of Hanoi

The game Sudoku

A program that uses loops

Printing items in a linked list

What is its big-O for the following function?

For (int j=1; j < 100; j++)

{

cout << j= << j << endl;

for (int k=1; k < 100; k++)

{

cout << j= << j << endl;

cout << j * k << j * k << endl;

}

}

O(n³)

O(n²)

O(n)

O(1)

In big-O notation both n₀ and N mean the same thing.

True

False

Which technique is typically used to solve an NP-complete problem?

Brute force calculation until the solution is found

Estimation, approximation, or even an initial guess at the solution

Big-O complexity analysis

You cannot find solutions NP-complete problems

Which of the following a true about big-O? (Select all that apply)

It measures the lower bound of an algorithm

It measures the run-time of an algorithm

It measures the upper bound of an algorithm

It estimates an algorithms complexity

In a program that implements a linked list, the memory for each of the nodes will be allocated in a sequential manner.

True

False

A linked list is an example of (Select all that apply):

A linear data structure

An algorithm

A dynamic data structure

An NP-complete problem

Which of the following are good applications of a linked list (Select all that apply):

A Web browsers back button

An program that manages an e-mail address book

A program that manages print jobs

An program that manages product inventory

What is the big-O for a function that copies all of the items in a give list to another list?

O(1)

O(n)

O(n²)

Cannot be determined

Which of the following primitives would be required in both a queue and a stack data structure? (Select all that apply)

Pop()

isEmpty()

getFirstElement()

initialize()

Which items would still be in the stack after executing the following operations? (Select all that apply)

push(5), push(10), push(11), pop(), push(17), push(12), push(13), pop(), push(10), pop(), pop(), push(5), pop(), pop(), push(7).

5

10

12

17

An element within the middle of the queue can be accessed directly if necessary.

True

False

Which software implementation would provide a good application for using a stack? (Select all that apply)

A program that implements a prefix calculator algorithm

A program that implements a compiler

A program that implements an algorithm designed to add large numbers

A program that implements an algorithm to send first come/first serve reports to a printer

What is the big-O of the pop() operation in a stack data structure?

O(1)

O(n)

O(n²)

Cannot be determined