CS 10C Conceptual

Stacks/queues

100

What's the difference between a stack and a queue?

Queue: FILO 

Stack: FIFO

200

What's the benefit of having a heap as an array?

No holes, indexing of parent and child easy, no pointers!

300

How do you declare a queue as templated?

template<typename T>

queue {

public:

    T* array;

    const &T peek() const {};

400

What variables do you need to implement a queue (circular or not)?

front,

size,

maxSize

500

Why is resize O(1)? What would the run time be if we resized every time we input a node?

On average the run-time is O(1) because after n inserts the cost is n, so O(n)/n = 1.

O(n), since there is no more amortized cost.

Trees/Hash

100

Maximum height of a AVL tree given n nodes?

floor(1.5logn)

200

What helper function do you need to make a function recursive?

One with the node, one without.

300

LIGHTNING ROUND: 

What are the rules for a red-black tree?

Root must be a black node

There must be the same # of black nodes in each path (from root to leaf)

No two nodes in a row can be red.

(red nodes do not count towards the path #)

400

What does the linux pw manager store???????

The hash of your password!!!

500

What is the weird case when inserting into an AVL Tree and when does it happen?

When balance factors are opposite signs. (opposite directions) Rotate right on the parent node, then rotate left on the inserted node.

Data/run-time

100

Are these lines of code valid?

const int three = 3;

const int* pointer = (int*)three; 

Yes, but the address stored in pointer will be the value three holds.

200

What data type should you use to represent an adjacency matrix?

bool

300

LIGHTNING ROUND: 

All member functions of a linked list and their runtime? 

Insert (end) O(1)

Search O(n)

Delete(end) O(1) (any) O(n)

400

What is the run-time of a function that decreases the size of the problem by a factor of 4 each time it runs?

O(logn)

(not O(log₄n))

500

What's the run-time of QuickSort? 

O(nlogn) 

If not specified, go with the typical case

10B

100

What is the rule of 3?

If you declare any of the 3, you must declare them all (can use = delete): 

1. Destructor

2. Copy constructor

3. Copy assignment operator

200

What are the four flags you should check when getting input with cin? And when are they activate?

1. Bad - type (nonrecoverable) error

2. Fail - logical error or type error

3. EOF - if eof is reached after extraction

4. Good - no errors, value of the stream itself

300

How do you use delete?

delete after you use new, and if you've allocated an array of pointers use delete[].

400

How would you write a function header that passes in a vector and a string (what question should you be asking) and returns a size?

Do we modify the variables?

int size([const] vector<int> &usedVector, [const] string &usedString);

500

Secret graph question:

What is the run-time of Dijkstra's? Why?

O(n²). Check every edge for every node, n * n