CMPT 135 Concept Review

Suppose a and b are both valid non-null pointers of type double*.

i) If a == b, then it must be the case that *a == *b ii) If a != b, then it must be the case that *a != *b

Consider this code fragment:

int arr[5] = {8, 2, 6, 4, 15}; cout << ???; Select all the following statements that, when put in place of ??? in the code fragment, will print the third element of arr.

Suppose n is a variable of type int, and consider this program:

#include

int main() { int n = 5; std::cout << &n; } If you run this program multiple times on the same computer, it will always output the same thing.

It's never safe to de-reference the null pointer.

In the context of garbage collection, garbage is free store memory that has:

Consider these statements:

i) Every C++ if-else-if structure can be re-written as a logically equivalent switch statement. ii) Every C++ switch statement can be re-written as a logically equivalent if-else-if structure.

Consider these statements:

i) In this course, when we use a makefile it is to compile a C++ program. ii) In this course, when we use a makefile it is to run a C++ program.

Consider these two statements:

i) Blackbox testing is a kind of whitebox testing. ii) Whitebox testing is a kind of blackbox testing.

Which one of these statements is most accurate?

Consider these two statements:

i) new int(5) returns a value of type int* ii) new int[5] returns a value of type int*

Which one of these statements is most accurate?

Where does C++ store global variables?

Suppose p is a pointer to a value that was allocated on the free store using new.

What kind of error results if p is de-allocated before the value it points to is de-allocated?

If p is a pointer of type char* and p == nullptr, then evaluating &p is always an error.

Consider these statements:

i) The maximum amount of free store memory used by a program can always be determined at compile-time. ii) The maximum amount of call stack memory used by a program can always be determined at compile-time.

Consider these statements:

i) A pointer variable in free store memory can point to a value in stack memory. ii) A pointer variable in stack memory can point to a value in free store memory.

What is a class in C++?

Which of the following follows the Last In, First Out (LIFO) principle?

What happens when a local variable goes out of scope?

What is a dangling pointer?

What is the best way to prevent memory leaks?

What is the difference between referencing and de-referencing?

Where is free store memory located?

What is the correct syntax for defining a constructor in C++?

Which keyword is used to deallocate memory from the free store in C++?

What is the purpose of the private keyword in a class?

Local variables are allocated in the heap.

A destructor has the same name as the class but starts with a tilde (~)

Stack memory is managed manually, while free store memory is managed automatically.

Pointers can be used to store the memory addresses of variables.

The switch statement can only evaluate integer and character values.

Pointer arithmetic allows arithmetic operations such as addition and subtraction on memory addresses.

If a class has no constructor, C++ automatically provides a default constructor.

The delete keyword should only be used for objects allocated with new.

Public members of a class can be accessed from outside the class.

An array in C++ can dynamically change its size at runtime.

A std::vector automatically manages memory allocation and deallocation.

Accessing an array out of its bounds in C++ results in a compile-time error.

Vectors use contiguous memory allocation, just like arrays.

The push_back() function in a vector increases the vector’s capacity every time it is called.

The only difference between a struct and a class in C++ is that members of a struct are public by default, while members of a class are private by default.

A struct can have member functions just like a class.

Structs are more commonly used for data structures, while classes are used for object-oriented programming.

A class can inherit from a struct, but a struct cannot inherit from a class.

Local variables are stored in stack memory.

Global variables are stored in the free store (heap).

Dynamic memory allocated using new is stored in free store (heap).

Static memory allocation is done at runtime.

The delete keyword deallocates memory from the stack.

A dangling pointer occurs when a pointer still points to a memory location that has been freed.

Using a dangling pointer can lead to undefined behavior.

A memory leak occurs when allocated memory is not properly freed.

Setting a pointer to nullptr after deleting it helps prevent dangling pointers.

What is the difference between an array and a vector in C++?

How do you declare a static array of size 10 in C++?

How do you add an element to a vector named vec?

What is the time complexity of accessing an element in an array or vector using an index?

When would you use a struct instead of a class in C++?

What is one advantage of using classes over structs in object-oriented programming?

What is the difference between stack and heap memory?

Where is the static variable stored in memory?

What happens if you forget to delete dynamically allocated memory?

How do you prevent a dangling pointer?

What is the difference between a dangling pointer and a memory leak?

How do you allocate memory dynamically for an array of 5 integers?

How do you correctly free the memory allocated in an array?

Which of these functions has a memory leak?

int f(int a) { double* p = new double(2.11); p = new double(-6.38); delete p; return 3 * a; }

int g(int a) { double* p = new double(2.11); delete p; return 3 * a; }

Consider these two statements:

i) If a program has a memory leak, then it must also have a dangling pointer problem. ii) If a program has a dangling pointer problem, then it must also have a memory leak.

Consider this code fragment:

double* p = new double(1.35); double** x = &p;

Which statement correctly de-allocates the double that p points to?

Consider this function:

double* f(double x) { int result = x+3; return &return; }

Consider these two statements:

i) Calling f results in a memory leak. ii) Calling f results in a dangling pointer.

Which one of these statements is most accurate?

Consider these two statements:

i) A mutating method in a class is a const method. ii) A const method in a class is mutating.

Which one of these statements is most accurate?

What is the difference between a struct and a class?

What is the return type of a constructor?

Consider these two statements:

i) new and delete can be used to allocate and de-allocate free store memory. ii) new and delete can be used to allocate and de-allocate stack memory.

Consider this function:

int f(int a) { int a = 5; int * p = &a; return a + 1; }

Consider these two statements:

i) Calling f results in a memory leak. ii) Calling f results in a dangling pointer.

Which one of these statements is most accurate?

Consider this code:

char f(char a) { char* c = new char('t'); char* d = c; return a + *c + *d; }

Consider these two statements:

i) Calling f results in a memory leak. ii) Calling f results in a dangling pointer.

What is a constructor initializer list?

A class must have exactly one constructor

What does b point to after this code fragment runs?

int* a = new int(5); int* b = a; a = nullptr;

Consider these two statements:

i) new and delete can be used to allocate and de-allocate free store memory ii) new and delete can be used to allocate and de-allocate stack memory

What is most accurate?

Consider these two statements:

i) Getters are usually const. ii) Setters are usually const.

Which one of these statements is most accurate?

A const method in a class can modify the public variables of the class, but not its private variables.

How many inputs does an ordinary copy constructor take?

The following single-line code fragment calls the default constructor for the programmer-defined class Folder:

Folder root;

What is the name for a destructor for a class called Page?

In a C++ class, a common use of destructors is to de-allocate resources allocated by constructors.

Getters are usually non-mutating methods.

Consider these two statements:

i) Setters are usually declared const. ii) Getters are usually declared const.

Which one of these statements is most accurate?

In C++, all constructors must have an initializer list.

Private variables defined in a class cannot be modified.

Consider these two statements: i) A { corresponds to a “push” onto the call stack ii) A } corresponds to a “pop” on the call stack

Consider these two statements: i) Blackbox tests can be created without seeing the implementation of a function. ii) Whitebox tests can be created without seeing the implementation of a function. Which one of these statements most accurately describes the truth values of i) and ii)?

Consider these two statements: i) Only constructors can have initialization lists. ii) A class can have multiple constructors and multiple destructors. Which one of these statements most accurately describes the truth values of i) and ii)?

Consider these two statements: i) Immutable objects have no setters. ii) A non-const getter will always cause a compiler error. Which one of these statements most accurately describes the truth values of i) and ii)?

Consider these two statements: i) For a child class to be able to re-implement a method it inherits from a parent class, the method must be declared virtual in the parent class. ii) For a child class to be able to re-implement a method it inherits from a parent class, the method must be declared virtual in the child class. Which one of these statements most accurately describes the truth values of i) and ii)?

What type of memory is allocated at compile time?

Which of the following correctly defines a derived class in C++?

What access specifier makes base class members inaccessible in a derived class?

What is the primary purpose of the this pointer in C++?

What happens when a base class method is overridden in a derived class?

In a UML class diagram, what does a solid line with a hollow triangle arrowhead represent?

A class can inherit from multiple base classes in C++.

The this pointer can be used in static member functions.

Virtual functions allow for dynamic (runtime) polymorphism in C++.

What is the difference between public, protected, and private inheritance?

Why do we use the this pointer in C++?

What is method overriding, and how does it relate to polymorphism?

Which of the following correctly defines an abstract method in C++?

Which statement about an abstract class is true?

What does it mean to instantiate a class?

Why should classes that are meant to be inherited have a virtual destructor?

Which of the following best describes the Liskov Substitution Principle (LSP)?

Which of the following correctly defines a namespace alias?

An abstract class can have non-pure virtual functions.

A class with at least one pure virtual function cannot be instantiated.

The global namespace in C++ refers to any namespace declared inside a function.

Function overloading means defining multiple functions with the same name but different return types.

The Single Definition Rule (SDR) ensures that a function or variable can only be defined once in a program.

What is an abstract base class?

Why should a class intended for inheritance have a virtual destructor?

What is a function signature in C++?

What is the difference between a declaration and a definition in C++?

What is the purpose of a namespace alias?

What is the purpose of the throw keyword in C++?

Which keyword is used to handle exceptions in C++?

What is a runtime error in C++?

What happens when an exception is thrown but not caught?

How does the call stack behave when an exception is thrown?

The try block is mandatory when using throw in C++.

A destructor is always called before an exception is propagated up the call stack.

A catch block can catch multiple types of exceptions.

Global variable flags can be used to signal an error state without using exceptions.

An exception can only be caught in the same function where it was thrown.

What is the purpose of the try block in C++?

How does the call stack behave when an exception occurs?

What happens if an exception is thrown inside a destructor?

What is the advantage of using global variable flags for error handling?

Consider these two statements: i) An abstract class is a class with at least one abstract method. ii) The methods of an abstract class must all be public.

Consider these two statements:

i) A class diagram shows the inheritance relations between classes in a class hierarchy. ii) For any two classes A and B, either A inherits from B, or B inherits from A.

Consider these two statements:

i) A class can inherit from 0 other classes. ii) A class could have 10 other classes inherit from it.

Consider these two statements:

i) If class A publicly inherits from class B, then private methods in B will be inherited as private in A. ii) If class A publicly inherits from class B, then public methods in B will be inherited as public in A.

Consider the following code fragment:

 class Flag;

Consider these two statements:

i) The fragment declares a class named Flag. ii) The fragment defines a class named Flag.

Consider these two statements:

i) Constructors must have an initialization list. ii) Destructors can take 1 or more input parameters.

Consider these two statements:

i) Destructors are virtual by default. ii) Destructors are abstract by default.

Consider these two statements:

i) Setters can be virtual. ii) Getters can be virtual.

Consider these two classes:

class Person { public: virtual int get_age() const = 0; virtual ~Person() { } };

class Student : public Person { int age; int grade; public: Student(int a, int g) : age(a), grade(g) { }

int get_age() const { return age; }
int get_grade() const { return grade; }

};

Suppose p is a pointer of type Person* and s is a pointer of type Student*, and both p and s point to valid objects in a correct program. Which of these statements cause a compiler error?

s = p; // statement A p = s; // statement B

Consider this code fragment:

class Person { int age; public: void print_age() { cout << ???; } }

What can ??? be replaced by so that the print_age() correctly prints age.

Select all the choices that work.

Consider these two statements:

i) A single using statement can give access to a exactly one function in a namespace. ii) A single using statement can give access to every function in a namespace.

Consider these two statements:

i) In C++, std is a namespace. ii) In C++, cout is a namespace.

All virtual methods must have an implementation in the class where they are defined.

Consider these two statements:

i) All virtual methods must also be abstract. ii) All abstract methods must also be public.

Consider these two statements:

i) Every C++ function must be defined exactly once. ii) Every C++ function must be declared exactly once.

Suppose a function throws an exception that is not caught by a try/catch block anywhere in the program. Which one of these statements is true?

Consider these two statements:

i) Recursive functions generally use less memory than equivalent non-recursive functions. ii) Recursive functions generally run faster than equivalent non-recursive functions.

Consider this function:

void hi() { hi(); cout << "Hello!\n"; }

What is printed when hi() is called? Assume the compiler applies no optimizations.

Consider these two statements:

i) Constructors can be const. ii) Destructors can be const.

Which one of these statements is most accurate?

If function f always throws a std::runtime_error exception, what value does example() return?

int example() { int n = 5; try { f(); // always throws a std::runtime_error exception n++; } catch (std::runtime_error e) { n--; } return n; }

Consider this function:

void f() { f(); }

What happens when you call f()? Assume the compiler applies no optimizations.

Suppose class A inherits from class B. Select all the true statements.

A function is tail-recursive if the last thing it does it recursively call itself. Select all the tail-recursive functions.

The following single-line code fragment calls the default constructor for the programmer-defined class Folder:

Folder root;

Suppose class Student inherits from the class Person, and p is a pointer of type Person* that points to a valid Person object. Suppose function f is defined like this:

void f(Student* s) { // ... }

Does calling f(p) always result in a compile-time error?

Consider these two statements:

i) Any piece of C++ code that uses loops can be re-written into code that does the same thing using recursion instead (without any loops). ii) Any piece of C++ code that uses recursion can be re-written into code that does the same thing using loops instead (without any recursion).

Consider these two statements:

i) Only virtual methods can be inherited. ii) Only public methods can be inherited.

Consider using this function to compute fib(50):

int fib(int n) { if (n == 1) { return 1; } else if (n == 2) { return 1; } else { return fib(n - 1) + fib(n - 2); } }

Which one of these statements is true?

Consider this function:

int p(int a, int n) { if (n < 0) cmpt::error("n must be >= 0");

if (a == 0 && n == 0) return 1;
if (a == 0 && n != 0) return 0;
if (a != 0 && n == 0) return 1;
if (a == 1) return 1;

return a * p(a, n - 1);

}

Is p tail recursive?

Consider this function:

int index_of_max(const vector& v) { int mi = 0; for(int i = 1; i < v.size(); i++) { if (v[i] > v[mi]) { mi = i; // line A } } return mi; }

If v has 10,000 randomly chosen and randomly ordered ints, how many times would you expect line A to be called?

Suppose v is a non-empty vector of size n. Does this pseudocode correctly calculate the max value of v?

m = 0 for i = 1 to n - 1 do if v[i] > m then m = v[i] end end

Consider these two statements:

i) Every C++ function must be defined exactly once. ii) Every C++ function must be declared exactly once

Given values v[0], v[1], ..., v[a-1], and a target value b, linear search finds an index c that satisfies which expression?

Suppose v is a vector that contains n > 0 randomly chosen and randomly ordered ints. v has no duplicates.

If there is a 50% chance that the target value x is somewhere in v, what is the expected average number of comparisons linear search does to either find x, or determine that x is not in v?

Insertion sort works by dividing a vector into two parts, sorting the two parts, and then combining the two sorted parts together.

When sorting the same large vector of randomly ordered ints:

Suppose A is sorted vector of size m > 0, and B is a sorted vector of size n > 0.

About how many comparisons are needed to merge A and B into a new vector?

Suppose you have a vector of 1000 different ints in ascending sorted order. If you use binary search to look for a given element in the vector, about how many comparisons are done in the worst case?

About how many comparisons are needed to test if a vector of 50 ints is in ascending sorted order?

Suppose v is a vector of n randomly ordered ints with no duplicates.

In the worst case, about how many comparisons does linear insertion sort do to sort v?

About how many comparison would insertion sort do to sort a list of 500 elements?

The following is a correct specification of the standard merge function (as it might be used by mergesort):

// Pre-condition: // v.size() == w.size() // Post-condition: // returns a new vector that contains all the elements in v and w (even duplicates) // in ascending sorted order. vector merge(const vector& v, const vector& w)

When sorting the same large vector of randomly ordered ints:

Suppose v is a vector of n randomly ordered ints with no duplicates.

In the worst case, about how many comparisons does mergesort do to sort v?

It is currently unknown if there is an O(n^k) worst-case algorithm for solving the traveling sales problem, where k is a fixed positive integer constant.

Select all the expressions that are in O(n)

In the worst case, how many comparisons does mergesort do on a vector of n items? Choose the tightest expression.

The tightest O-notation expression describing the the sum of O(n) and O(n^2) and O(n^3)

Consider these statements:

i) sorting is an NP-complete problem ii) the traveling salesman problem is an NP-complete problem

Suppose algorithm A has a running time of O(n). If A takes 5 seconds to process 5000 items, about how long would you expect A to take to process 10,000 items?

Mergesort sorts a vector by dividing it into two separate parts, independently sorting each part, and then merging the two sorted parts.

What is the worst-case running-time for the fastest algorithm that solves the traveling salesman problem, where n is the number of cities?

Suppose A is a vector of n ints. If you run mergesort on A followed by 1000 calls to binary search, what is the O-notation expression that best describes the total worst-case running time of those operations?

What computational problem was Alan Turing the first one to solve in the 1930s?

Select all the expressions that are in O(n^2)

Consider this function:

template <typename T> void swap(T& a, T& b) { T temp = a; a = b; b = temp; }

For this to work correctly, if the type T is a user-define class then T must have a default constructor.

In the worst case, how many comparisons does linear insertion sort do on a vector of n items? Choose the tightest expression.

In the worst case, how many comparisons does linear search do on a vector of n items? Choose the tightest expression.

For linear search, what is the usual key operation that is counted when determining it's run-time performance?

In the worst case, how many comparisons does binary search do on a vector of n items? Choose the tightest expression.

Write a cout statement that prints the address of variable a

Suppose p is a pointer to an int. Write a cout statement that prints the int p points to

the following code fragment does not compile: int x = new int(5); cout << x;

Suppose m is a pointer to a double on the free store. Write a statement that deletes the memory m points to

Suppose arr is a pointer to a double array on the free store. Write a statement that deletes the memory arr points to

True or false: the following code fragment does not compile: string s = "cat"; string t = "dog"; string* a = &s; string* b = &t; a = b; b = a;

True or false: the following code fragment causes a memory leak if executed: string s = "cold"; string* p = &s; p = nullptr;

True or false: the following function compiles, and has no memory leak or other run-time error: void f() { int a = 5; int* p = &a; cout << a; delete p; }

it is an error to delete a pointer whose value is nullptr

Suppose arr is an array of 10 int values all initialized to 0. What does cout << arr[10] print?

every object has at least one (possibly empty) constructor.

every object has at least one (possibly empty) destructor.

initialization lists can be used with any method in an object.

a default constructor takes no inputs.

by default, methods and variables in a class are private.

an object’s destructor is called automatically when the object goes out of scope, or is deleted.

a class can define more than one constructor

a class can define more than one destructor.

if you create a class called Fraction to represent fractions, then you can define a custom operator+ for adding Fraction objects

all objects are classes, but not all classes are objects

What is the general name (not g++!) of the program that converts a C++ source code file (e.g. a .cpp file) into object code?

What is the general name (not g++!) of the program that converts a C++ object code file into an executable file?

What is the usual file name extension for C++ header files?

Write a complete C++ program that prints "Hello, world!" on cout and does not have a using statement.

in the worst case, linear search has to do 1000 comparisons when searching through a vector of n=1000 numbers.

binary search only works on sorted data

it’s usually faster to do a linear search on a vector of n numbers than it is to first sort that data and then do a binary search on it.

What is the name we use for a class, such as PQueue, where all the methods are public and virtual, and at least one method is =0?

Explain what =0 at the end of some method headers means here.

Explain what the virtual keyword means here

why would a class include a virtual destructor?

Define a new class named Heap that derives (i.e. inherits) from PQueue. You don't need to implement any methods or variables: just show how to do the inheritance in the class header line.