Midterm 1 - Specific Topics

Question 1

what are some collections we have learned?

Answer 1

• stacks
• sets
• vectors (stanford)
• arrays
• string (collection fo chars
• maps, sets
• queues

Question 2

what is a string a collection of?

Answer 2

chars

Question 3

how do you declare a string?

Answer 3

std::string msg = “hello”;

Question 4

what is casting?

Answer 4

allows you to forcibly convert from one type to another

Question 5

casting example

Answer 5

std::string name = std::string(“Nate”) + “Dog”;

Question 6

what are some member objects of a string?

Answer 6

.clear()
.empty()
.front()
.back()
.find()
.substr()

Question 7

what is .substr()

Answer 7

takes 2 parameters
-index to start at
-number of char to include
returns new string that contains requested range char

Question 8

substr example

Answer 8

std::string title = “A Tale of Two Cities”;

//yields "of Two"
std::string ofTwo = title.substr(7,6);

//yields "Two Cities"
std::string twoCities = title.substr(10)

Question 9

how do you check to see if an item is in a string?

Answer 9

.find()

Question 10

what is .find()

Answer 10

takes two parameters

• the string you are searching for
• index you want to start search at
• returns index of first appearance of the requested string

Question 11

example of .find()

Answer 11

std::string title = “A Tale of Two Cities”;

// search for first instance of "of"
// starting at index 0
int index = title.find("of", 0);
std::cout << index << std::endl;

// search for first instance of "hello"
// will return value of npos because "hello" is not found
std::cout << title.find("hello") << std::endl

Question 12

what is passing by reference?

Answer 12

change will persist

Question 13

what is passing by value?

Answer 13

make a copy

Question 14

what do we pass by value?

Answer 14

basic types (int, double, float, char)

Question 15

what do we pass by reference?

Answer 15

non-basic types (std::string, std::ifstream, std::ofstream etc.)

Question 16

how do you declare a stanford vector?

Answer 16

Vector myVector;

Question 17

how do you declare a stanford vector?

Answer 17

include “vector.h”

Vector myVector;

Question 18

vector example: declare a vector of strings

Answer 18

Vector> names;

Question 19

what are some member functions of vectors?

Answer 19

.size()
.add()
.remove(index)
.isEmpty() (returns true if empty)
.clear()

Question 20

what is myVector.insert(index, element)

Answer 20

-inserts element before the specified index

Question 21

what is std::getline

Answer 21

allows you to get an entire line of input (so it doesn’t stop until an enter)

Question 22

how does std::getline work?

Answer 22

takes two parameters

• input stream you want to grab line from
• string that you want to store the line in (passed by reference)

Question 23

std::getline example with cities

Answer 23

std: :cout &laquo_space;“Enter a city: “;
std: :string city;
std: :getline(std::cin, city)
std: :cout &laquo_space;“You entered “

Question 24

how do you fix cin and getline problem?

Answer 24

std::cin.ignore();

before getline

Question 25

what type of behavior do queues have?

Answer 25

FIFO

LILO

Question 26

where can you add/remove elements from a queue?

Answer 26

add elements to end

remove elements form front

Question 27

how do you declare a stanford queue?

Answer 27

include “queue.h”

Queue myQueue;

Question 28

what are some basic queue member functions?

Answer 28

.isEmpty()
.clear()
.size()
.peek()

Question 29

how do you add/remove from a queue?

Answer 29

.enqueue()

.dequeue()

Question 30

what type of behavior do stacks have?

Answer 30

LIFO

Question 31

where do you add/remove from a stack?

Answer 31

add to top of stack

remove from top of stack

Question 32

how do you delcare a stack?

Answer 32

include “stack.h”

Stack myStack;

Question 33

what does myStack.push(element) do?

Answer 33

pushes an element to the top of the stack

Question 34

what does myStack.pop() do?

Answer 34

removes element from top of the stack and returns it

Question 35

infix vs. postfix notation

Answer 35

infix - binary operators appear between the operands

postfix - binary operators appear after operands

Question 36

what is a map?

Answer 36

-container that has two types (key and a value)

Question 37

how do you declare a map?

Answer 37

include “map.h”

Map myMap;

Question 38

what does myMap.put() do?

Answer 38

-associates specified key with a value

myMap.put(key, value)

Question 39

what does myMap.containsKey.() do?

Answer 39

-returns true if the key is associated with a value in the map

Question 40

how do you use .containsKey()?

Answer 40

if (myMap.containsKey(key)) { // key is associated with something }

Question 41

what does myMap.get() do?

Answer 41

returns value associated with the key, provided that key is in the map
(can also use [ ] operator)

Question 42

which containers support [ ] operator?

Answer 42

-maps
-vectors
-arrays
-

Question 43

do friend functions belong to the class?

Answer 43

no

Question 44

when is a function recursive?

Answer 44

when it calls itself

Question 45

what is the base case?

Answer 45

-what prevents the recursion function from going on forever

Question 46

what is a stack overflow?

Answer 46

-too many functions active at once

Question 47

when does stack overflow often occur?

Answer 47

when your base case is wrong

Question 48

write a binary search function

Answer 48

int binarySearch (Vector& vec, std::string&, value) {
return binarySearchPart(vec, value, 0, vec.size()-1); 
}

Question 49

what is Big O notation?

Answer 49

describe worst-case performance of a particular algorithm

Question 50

what is linear search in big O notation?

Answer 50

O(n)

Question 51

what is binary search in big O notation?

Answer 51

O(log n)

Question 52

what is selection sort in big O notation?

Answer 52

O(n^2)

Question 53

what are 2 other O(n^2) sorts?

Answer 53

insertion sort (stable)
bubble sort (stable)

Question 54

what are 2 other O(n log n) sorts?

Answer 54

merge sort (not stable)
quicksort (stable)