midterm2 Flashcards
The most efficient technique for finding nth Fibonacci number is recursion.
false
We generally use best case running time to measure time complexity T.
false
STL algorithms operate only on vectors.
true
If T(n) = 2n + 100n10 + 1000n5 + 10000, then T(n) is O(n10).
false
f T(n) = n3 + 1000n2log2n + 10000, then T(n) is O(n3)
true
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)?
15
The time complexity of binary search is O(log(n))
true
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)?
6
Recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem
true
If you have a vector of integers v, accumulate(v.begin(),v.end(),0) returns the sum of the elements in the vector.
true
Which of the following data structure is not suitable for binary search?
Linked List
Each node must have exactly two children in a binary tree
false
In the array representation of a binary tree, which nodes store the children of node stored at index 6?
(13,14)
In a binary search tree (BST), left child of a node cannot be greater than its right child.
True
The node in a tree without an incoming arc is called the leaf.
False
The worst case computing time of linear search is O(log2n)
False
Stacks must be implemented using an array.
False
There is no need to specify the capacity of a linked queue in its declaration
True
Two variables are needed in a queue to represent the front and the back of the queue
true
For an array-based queue “myBack == -1” returns true when the queue is empty.
False
A queue is a first-in-first-out (FIFO) data structure
true
The array element at index 0 should always be the top of the stack for efficiency.
false
In a queue, the value of myFront is always less than myBack
false
A stack is a last-in-first-out (LIFO) data structure.
true
Stack is a suitable data structure for a base conversion program, which converts a decimal number to a binary number
true
For an array-based stack “myTop == -1” returns true when the stack is empty.
true
