Chapter 19

[Skip Breadcrumb Navigation]

Home

Student Resources

Quizzes

Chapter 19

Standard Template Library

This activity contains 10 questions.

Which of the following programs will correctly define an iterator and print the contents of the vector?

#include <iostream>
#include <vector>
using namespace std;

void main()
{
	vector<int> myData;
	iterator p;

	myData.push_back(3);
	myData.push_back(4);
	myData.push_back(5);

	for (p = myData.begin(); p!= myData.end(); p++) {
		cout << *p << endl;
	}
}

#include <iostream>
#include <vector>
using namespace std;

void main()
{
	vector<int> myData;
	vector<int>::iterator p;

	myData.push_back(3);
	myData.push_back(4);
	myData.push_back(5);

	for (p = myData.begin(); p!= myData.end(); p++) {
		cout << *p << endl;
	}
}

#include <iostream>
#include <vector>
using namespace std;

void main()
{
	vector<int> myData;
	iterator p;

	myData.push_back(3);
	myData.push_back(4);
	myData.push_back(5);

	for (p = 0;  p< myData.size(); p++) {
		cout << myData[p] << endl;
	}
}

#include <iostream>
using namespace std;

void main()
{
	vector<int> myData;
	iterator p;

	myData.push_back(3);
	myData.push_back(4);
	myData.push_back(5);

	for (p = myData.begin(); p!= myData.end(); p++) {
		cout << *p << endl;
	}
}

The following code creates a vector of integers. Which snippet does not correctly output the data in the vector?


#include <iostream>
#include <vector>
using namespace std;

// Main
void main()
{
	vector<int> myData;
	vector<int>::iterator p;

	myData.push_back(3);
	myData.push_back(4);
	myData.push_back(5);

	// CODE TO OUTPUT DATA HERE
}

for (p = myData.begin(); p!= myData.end(); p++) {
	cout << *p << endl;
}

for (p = myData.begin(); p!= myData.end(); p++) {
	cout << p[0] << endl;
}

for (int i=0; i< myData.size(); i++) {
	cout << myData[i] << endl;
}

p = myData.begin();
for (int i=0; i< myData.size(); i++, p++) {
	cout << p[i] << endl;
}

What will the following program output when run?


void main()
{
	vector<int> myData;
	vector<int>::iterator p;

	myData.push_back(2);
	myData.push_back(4);
	myData.push_back(6);

	p = myData.begin();
	cout << *(p+2) << endl;
	myData[2] = 5;
	cout << *(p+2) << endl;
}

6
66
54
44
5

What will the following program output when run?


void main()
{
	vector<int> myData;
	vector<int>::iterator p;

	myData.push_back(2);
	myData.push_back(4);
	myData.push_back(6);

	p = myData.end();
	while (p!=myData.begin()) {
		cout << *p << endl;
		p--;
	}
}

This program will not compile because it is illegal to access the iterator for a vector in reverse order unless we explicitly declare the iterator to be reverse_iterator.(unknown value)
6
46
4
22
4
6

What will the following program output when run?


void main()
{
	vector<int> myData;
	vector<int>::reverse_iterator p;

	myData.push_back(2);
	myData.push_back(4);
	myData.push_back(6);

	p = myData.rend()-1;
	while (p!=myData.rbegin())
	{
		cout << *p << endl;
		p--;
	}
	cout << *p << endl;
}

6
4
22
4
66
4
2
22
4
6
6

What is the output of the following program when run?


#include <iostream>
#include <map>
#include <string>
using namespace std;

void main()
{
	map<string,string> idMap;
	map<string,string>::iterator iter;

	idMap["501-10-3011"] = "DeBanque, Robin";
	idMap["301-10-3012"] = "Wright, Eaton";
	idMap["201-10-3010"] = "Oki, Cary";

	for (iter = idMap.begin(); iter != idMap.end(); iter++)
	{
		cout << iter->first << " " << iter->second << endl;
	}
}

Oki, Cary 201-10-3010
Wright, Eaton 301-10-3012
DeBanque, Robin 501-10-3011
0 Oki, Cary
1 Wright, Eaton
2 DeBanque, Robin
201-10-3010 Oki, Cary
301-10-3012 Wright, Eaton
501-10-3011 DeBanque, Robin
This program will not compile. It is not valid to use strings inside the square brackets, e.g. idMap["201-10-3010"].

Which function will correctly find the name in the map that matches the target? The output of the program should be:


Wright, Eaton
Name not found

#include <iostream>
#include <map>
#include <string>
using namespace std;

// Main
void main()
{
	map<string,string> idMap;

	idMap["501-10-3011"] = "DeBanque, Robin";
	idMap["301-10-3012"] = "Wright, Eaton";
	idMap["201-10-3010"] = "Oki, Cary";

	cout << GetName(idMap,"301-10-3012") << endl;
	cout << GetName(idMap,"999-99-9999") << endl;
}

string GetName(map<string,string> idMap, string targetKey)
{
	map<string,string>::iterator iter;

	iter = idMap.find(targetKey);
	if (iter == idMap.end()) {
		return("Name not found");
	}
	else {
		return (iter->second);
	}
}

string GetName(map<string,string> idMap, string targetKey)
{
	if (!idMap.find(targetKey))
		return("Name not found");
	}
	else {
		return (idMap[targetKey]);
	}
}

string GetName(map<string,string> idMap, string targetKey)
{
	map<string,string>::iterator iter;

	iter = idMap.find(targetKey);
	if (iter == false) {
		return("Name not found");
	}
	else {
		return (iter->second);
	}
}

string GetName(map<string,string> idMap, string targetKey)
{
	map<string,string>::iterator iter;

	iter = idMap.find(targetKey);
	if (iter == NULL) {
		return("Name not found");
	}
	else {
		return (iter->second);
	}
}

Rank the following runtime estimates in terms of their Big-O notation. Give the smallest asymptotically growing function first, the largest last.


2^ (log n)
2000(n^2) + log n
2^n
(log n)^2

 (log n)^2
2^(log n)
2^n
2000(n^2) + log n

2^(log n)
(log n)^2
2^n
2000(n^2) + log n

2000(n^2) + log n
(log n)^2
2^(log n)
2^n

 (log n)^2
2^(log n)
2000(n^2) + log n
2^n

The following two functions will both work correctly to retrieve a name from a STL map. What is the Big-O runtime of each?


string GetName1(map<string,string> idMap, string targetKey)
{
	map<string,string>::iterator iter;

	iter = idMap.find(targetKey);
	if (iter == idMap.end()) {
		return("Name not found.");
	}
	else {
		return (iter->second);
	}
}

string GetName2(map<string,string> idMap, string targetKey)
{
	map<string,string>::iterator iter;
	for (iter = idMap.begin(); iter != idMap.end(); iter++) {
		if (iter->first == targetKey) return iter->second;
	}
	return("Name not found");
}

GetName1 runs in time O(N).
GetName2 runs in time O(log N).GetName1 runs in time O(N).
GetName2 runs in time O(N).GetName1 runs in time O(1).
GetName2 runs in time O(N).GetName1 runs in time O(log N).
GetName2 runs in time O(N).

Why might a O(N) algorithm be preferred to a O(log N) algorithm?

Since the Big-O notation ignores constant factors, the O(N) algorithm may be faster for small values of N.A O(N) algorithm will always be simpler to implement than a O(log N) algorithm.The O(N) algorithm will run faster.A O(N) algorithm will require less storage space than a O(log N) algorithm.

The Submit Answers for Grading feature requires scripting to function. Your browser either does not support scripting or you have turned scripting off.

So, the Submit Answers for Grading button below will not work.

The following Submit Answers for Grading button is provided in its place and will clear your answers:
The Clear Answers and Start Over feature requires scripting to function. Your browser either does not support scripting or you have turned scripting off.

So, the Clear Answers and Start Over button below will not work.

The following Clear Answers button is provided in its place and will clear your answers:

Your browser either does not support scripting or you have turned scripting off. Because of this, the answer choices will NOT appear in a different order each time the page is loaded, though that is mentioned below. Note that you do not need this feature to use this site.

Answer choices in this exercise appear in a different order each time the page is loaded.

Chapter 19

Which of the following programs will correctly define an iterator and print the contents of the vector?

What will the following program output when run?
void main() { vector<int> myData; vector<int>::iterator p; myData.push_back(2); myData.push_back(4); myData.push_back(6); p = myData.end(); while (p!=myData.begin()) { cout << *p << endl; p--; } }

Rank the following runtime estimates in terms of their Big-O notation. Give the smallest asymptotically growing function first, the largest last.
2^ (log n) 2000(n^2) + log n 2^n (log n)^2

Why might a O(N) algorithm be preferred to a O(log N) algorithm?

Chapter 19

Which of the following programs will correctly define an iterator and print the contents of the vector?

What will the following program output when run? void main() { vector<int> myData; vector<int>::iterator p; myData.push_back(2); myData.push_back(4); myData.push_back(6); p = myData.end(); while (p!=myData.begin()) { cout << *p << endl; p--; } }

Rank the following runtime estimates in terms of their Big-O notation. Give the smallest asymptotically growing function first, the largest last. 2^ (log n) 2000(n^2) + log n 2^n (log n)^2

Why might a O(N) algorithm be preferred to a O(log N) algorithm?

What will the following program output when run?
void main() { vector<int> myData; vector<int>::iterator p; myData.push_back(2); myData.push_back(4); myData.push_back(6); p = myData.end(); while (p!=myData.begin()) { cout << *p << endl; p--; } }

Rank the following runtime estimates in terms of their Big-O notation. Give the smallest asymptotically growing function first, the largest last.
2^ (log n) 2000(n^2) + log n 2^n (log n)^2