cse 100 midterm 1

Which of the following are Data Structures? Select all that apply.

Stack

Linked List

Binary Search Tree (BST)

Array List

Priority Queue

Queue

Heap

• Linked List

• Binary Search Tree (BST)

• Array List

• Heap

Which of the following statements are true? Select all that apply.

A Queue is a First-In-First-Out (FIFO) collection

A Queue is a Last-In-First-Out (LIFO) collection

A Stack is a First-In-First-Out (FIFO) collection

A Stack is a Last-In-First-Out (LIFO) collection

A Queue can be implemented using a Linked List

A Stack can be implemented using a Linked List

A Queue can be implemented using an Array List

A Stack can be implemented using an Array List

• A Queue is a First-In-First-Out (FIFO) collection

• A Stack is a Last-In-First-Out (LIFO) collection

• A Queue can be implemented using a Linked List

• A Stack can be implemented using a Linked List

• A Queue can be implemented using an Array List

• A Stack can be implemented using an Array List

What is Niema's favorite video game?

Final Fantasy VII

Imagine you have the following code snippet:

int main() {

vector<int> varA;

vector<int> varB (42);

vector<int> varC = new vector<int>();

vector<int> varD = new vector<int>(42);

vector<string> varE;

vector<string> varF (42);

vector<string> varG = new vector<string>();

vector<string> ✶ varH = new vector<string>(42);

}

Which of the variables will need to be explicitly destroyed using the delete keyword? Select all that apply.

• varC

• varD

• varG

• varH

Imagine you run the following code snippet:

void zero (int x) {

x = 0;

}

int main() {

int myInt = 42;

zero(myInt);

cout<<<< myInt;

}

what is the output?

42

Imagine you run the following code snippet:

void zero (int & x) {

x = 0;

}

int main() {

int myInt = 42;

zero(myInt);

cout<<<< myInt;

}

what is the output?

0

void zero (int* x) {

*x = 0;

}

int main() {

int myInt = 42;

zero(&myInt);

cout<< myInt;

}

0

you're given this code:

while(itr != end) {

cout << *itr << endl;

++itr;

}

Which operators invoke versions overloaded by the iterator class to have meaning related to the internal state of the iterator? Select all that apply.

Checkbox options

<<

!=

++ (pre-increment)

* (dereference)

* (multiplication)

• ++ (pre-increment)

• !=

• * (dereference)

You're implementing an iterator class called VectorIterator that you want to use to iterate through a vector<int>. You're working on overloading the * (dereference) operator. So far, you've written the following code:

class VectorIterator {

private:

vector<int>* ptr;

int index;

public:

int operator*() const

{ // TODO

}

}

Which of the following lines of code should replace // TODO to correctly overload the * (dereference) operator?

this→index+=1;

return (*(this→ptr))[index]

return this→index

return this→ptr+index

return (*(this→ptr))[index]

You're implementing an iterator class for an Array List implementation. Each instance of your iterator class stores the indexof the element it's referring to. What is the tightest worst-case Big-O memory complexity of an iterator object referring to an element in an list that contains n total elements?

O(1)

You're implementing an iterator class for a Linked List implementation. Each instance of your iterator class stores a pointerto the element it's referring to. What is the tightest worst-case Big-O memory complexity of an iterator object referring to an element in an list that contains n total elements?

O(1)

You're implementing an iterator class for a Linked List implementation. Each instance of your iterator class stores the indexof the element it's referring to as well as a pointer to the head node. Which of the following statements is true?

There would be no problems and it would be just as efficient.

It would not be possible to implement a Linked List iterator with just the current index and a pointer to the head node.

The overloaded the ++ operator would likely be much slower (linear rather than constant time in number of elements).

The overloaded * (dereference) operator would likely be much slower (linear rather than constant time in number of elements).

None of the above

The overloaded * (dereference) operator would likely be much slower (linear rather than constant time in number of elements).

You want to determine if a given integer x appears in a sorted array with n elements. What is the tightest worst-case Big-O time complexity you can achieve?

O(log n)

You want to determine if a given integer x appears in a sorted Linked List with n elements. What is the tightest worst-case Big-O time complexity you can achieve?

O(n)

Which of the following statements are true? Select all that apply.

foo is O(1)

foo is O(log n)

foo is O(n)

foo is O(n log n)

foo is O(n²)

foo is O(n log n)

foo is O(n²)

You are given a vector<int> named sortedNums that is sorted in ascending order (i.e., smallest to largest). You create a Binary Search Tree (BST) by iterating through sortedNums and inserting each element:

BST Tree;

for( int nums: sortedNums) {

tree.insert(num);

}

In which of the following ways is the BST created by this process better than a Linked List?

This BST offers a faster average-case find operation.

This BST offers a faster average-case delete operation.

This BST offers a faster worst-case find operation.

This BST offers a faster worst-case delete operation.

None of the above

none of the above