midterm2

Question 1

The most efficient technique for finding nth Fibonacci number is recursion.

Answer 1

false

Question 2

We generally use best case running time to measure time complexity T.

Answer 2

false

Question 3

STL algorithms operate only on vectors.

Answer 3

true

Question 4

If T(n) = 2n + 100n10 + 1000n5 + 10000, then T(n) is O(n10).

Answer 4

false

Question 5

f T(n) = n3 + 1000n2log2n + 10000, then T(n) is O(n3)

Answer 5

true

Question 6

double f(unsigned n)
{
if(n == 1)
return 1.0;
else
return n + f(n/2);
}

Given the recursive function above, what is the value of f(8)?

Answer 6

15

Question 7

The time complexity of binary search is O(log(n))

Answer 7

true

Question 8

unsigned f(unsigned n)
{
if(n == 0)
return 0;
else
return f(n / 10) + n % 10;
}

Given the recursive function above, what is the value of f(312)?

Answer 8

6

Question 9

Recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem

Answer 9

true

Question 10

If you have a vector of integers v, accumulate(v.begin(),v.end(),0) returns the sum of the elements in the vector.

Answer 10

true

Question 11

Which of the following data structure is not suitable for binary search?

Answer 11

Linked List

Question 12

Each node must have exactly two children in a binary tree

Answer 12

false

Question 13

In the array representation of a binary tree, which nodes store the children of node stored at index 6?

Answer 13

(13,14)

Question 14

In a binary search tree (BST), left child of a node cannot be greater than its right child.

Answer 14

True

Question 15

The node in a tree without an incoming arc is called the leaf.

Answer 15

False

Question 16

The worst case computing time of linear search is O(log2n)

Answer 16

False

Question 17

Stacks must be implemented using an array.

Answer 17

False

Question 18

There is no need to specify the capacity of a linked queue in its declaration

Answer 18

True

Question 19

Two variables are needed in a queue to represent the front and the back of the queue

Answer 19

true

Question 20

For an array-based queue “myBack == -1” returns true when the queue is empty.

Answer 20

False

Question 21

A queue is a first-in-first-out (FIFO) data structure

Answer 21

true

Question 22

The array element at index 0 should always be the top of the stack for efficiency.

Answer 22

false

Question 23

In a queue, the value of myFront is always less than myBack

Answer 23

false

Question 24

A stack is a last-in-first-out (LIFO) data structure.

Answer 24

true

Question 25

Stack is a suitable data structure for a base conversion program, which converts a decimal number to a binary number

Answer 25

true

Question 26

For an array-based stack “myTop == -1” returns true when the stack is empty.

Answer 26

true