Final Exam Flashcards
#include
using namespace std;
template
type Max(type Var1, type Var2)
{
if (Var1 > Var2)
return Var1;
else
return Var2;
}
int main()
{
int p;
p = Max(100, 200);
cout << p << endl;
return 0;
}200
Which of the following correctly indicates templates?
template
#include
using namespace std;
template
void loopIt(T x)
{
int count = 3;
T val[count];
for (int ii=0; ii < count; ii++)
{
val[ii] = x++;
cout << val[ii] << endl;
}
};
int main()
{
float xx = 2.1;
loopIt(xx);
}- 1
- 1
- 1
Which is true about template functions: One will work with many different types Duplicate code is increased Takes longer to execute None
One will work with many different types.
#include
using namespace std;
template
class Test
{
public:
Test()
{
};
~Test()
{
};
type Funct1(type Var1)
{
return Var1;
}
type Funct2(type Var2)
{
return Var2;
}
};
int main()
{
Test Var1;
Test Var2;
cout << Var1.Funct1(200) << endl;
cout << Var2.Funct2(3.123) << endl;
return 0;
}
200
3.123
A generic data type is one in which the types of the items being manipulated are defined, but the operations are not. (T or F)
False
Assume that there is a BinaryTreeNode class and we are prototyping the insertion operator in the in the header file for the BinaryTreeNode.
The following prototype compiles without warning or error assuming that the method is appropriately implemented elsewhere.
friend ostream& operator
False
What is the output of this program?
#include
using namespace std;
template
class TestVirt
{
public:
virtual type TestFunct(type Var1)
{
return Var1 * 2;
}
};
int main()
{
TestVirt Var1;
cout << Var1.TestFunct(100) << endl;
return 0;
}
200
void fun2(int n)
{
if(n == 0)
return;
fun2(n / 2);
cout «_space;n % 2;
}
Assume we call it as follows:
fun2(4);
100
When crafting a recursive method, which of the following is NOT required?
- Recursive call
- Parameter to recursive call that heads toward base case
- Multiple base cases (e.g for 0 and 1)
- Single base case
Multiple base cases
Assume we have the following function defined:
#define LIMIT 20
void fun2(int n)
{
if (n <= 0)
return;
if (n > LIMIT)
return;
cout << n << " ";
fun2(2 * n);
cout << n << " ";
}
Assume we call it in the following way:
fun2(2);
What is displayed?
2 4 8 16 16 8 4 2
Assume we have the following function defined:
int fun1(int x, int y)
{
if(x == 0)
return y;
else
return fun1(x - 1, x + y);
}
Assume that we call it as follows:
cout «_space;fun1(3, 2);
8
Assume that we are implementing a traditional Binary Search Tree without balancing. What is the worst-case efficiency for the insert method?
O(N)
A/n ___________________ is a sequence of edges from one node in a binary tree to one of its descendants.
path
Assume the following values have been inserted into a binary search tree in the following order:
15 7 9 21 44 30 33 29 10 1 17
What is the height of the tree?
4
Assume the following items are inserted into a binary search tree in the order shown.
15 7 9 21 44 30 33 29 10 1 17
Which value is the inorder successor of 15?
17
Assume the following values have been inserted into a binary search tree in the order shown.
15 7 9 21 44 30 33 29 10 1 17
Assume that the value 3 is then inserted, which node is the parent of 3?
1
The algorithmic complexity of the search method for binary search tree is
O(logN)
When using the AVL strategy to balance a binary tree, what property of the node’s children is used to determine whether the node is considered balanced?
height
Assume the following values are inserted into an AVL tree in this order.
15 7 9 21 44 30 33 29 10 1 17
After which value’s insertion will the tree be rebalanced for the first time?
9
What is the efficiency of an AVL tree’s search function?
O(LogN)
Assume the following values are inserted into an AVL tree in this order.
15 7 9 21 44 30 33 29 10 1 17
After which value’s insertion will the tree be rebalanced for the second time?
44
Heaps are often used to represent what other data structure because of their efficiency?
Priority Queue
Heaps are “totally ordered” datasets like binary trees (T or F)
false
Assume the following values are inserted into a heap such that the “lowest” value has the “highest” priority.
15 7 9 21 44 30 33 29 10 1 17
Which value is the right child of 9?
33
In a Binary Heap represented by an array indexed starting at 1 (i.e. the first item in the heap is at location 1). For the item in location 15, what is the location of its parent?
7
In a Binary Heap represented by an array indexed starting at 1 (i.e. the first item in the heap is at location 1). For the item in location 15, what is the location of its left child?
30
A/n ____________________ connected graph is a directed graph where the underlying undirected graph is connected but the directed graph is not.
weakly
When using an adjacency matrix to represent the edges in a directed graph, the edges are mirrored across the “axis of symmetry” (diagonal). (T or F)
False
In a graph, a simple path may contain duplicate vertices (nodes) but not duplicate edges.
false
In a graph, the length of a path is defined by the number of vertices (nodes) in the path. (T or F)
False
Adjacency matrices can be used to represent weighted graphs but cannot be multiplied to determine path lengths. (T or F)
True
In a complete graph, there exists a path from every vertex (or node) to every other vertex
True
When using an adjacency matrix to represent the edges in a undirected graph, the edges are mirrored across the “axis of symmetry” (diagonal).
True
In Djikstra’s algorithm, a/n ______________ must be used to store the collection of nodes that are yet to be expanded (usually called “to visit”).
Priority Queue
Assume that we have a set of integers called myset. We want to display all the items in the set using an iterator, which of the following correctly creates an iterator into mySet and initializes it to the first item in the set?
set::iterator it = myset.begin();
Sets are usually stored using which of the following data structures?
Binary Search Tree
Sets represent a sorted collection of unique items.
True
Insert and search operations for a Hash Table are both O(1). (T or F)
True
When designing a hash function for a HashTable, what is the most important characteristic?
Collisions rarely occur until it is at least 1/2 full
When a Hash Table is full, you should increase its size by 5 items at a time so that the amount of memory used is still O(N). (T or F)
False
Which of the following statements correctly declares a map that uses a student’s identification number (like those used at UCCS) to look up their name?
map students;
