comp sci 2 exam 2

OU cs 2401

what is a node and what does it do?

• stores actual value(s)

• links to the next node in the sequence (and prev in doubly linked lists)

how is data organized in linked lists?

• data is stored by individual nodes that are connected by pointers

• unlike arrays, nodes are scattered across memory and are not contiguous

how are nodes kept in sequence?

• each node contains a pointer that points to the next node in the list

• the head pointer points to the first node and traversal is done by following these pointers

what are the advantages of linked lists over dynamic arrays?

• insertion and deletion: faster since you do not need to shift elements O(1)

• no resizing needed because linked lists grow/shrink dynamically without requiring reallocation of memory

what are the disadvantages of linked lists?

• random access is impossible, you need to traverse the list to access an element O(n) time complexity

• each node requires additional memory for storing pointers, which needs more space

adding and removing nodes in specific situations (first, last, single-node list, empty list)

1. first

   • adding: update head pointer to point to new node

   • removing: adjust the head pointer to point to the next node

2. last

   • adding: traverse to last node and update pointer to new node

   • removing: traverse to second-to-last node and set its pointer to nullptr

3. single-node

   • be careful of handling the head/tail pointers when both adding and removing

4. empty

   • initialize head pointer

what are the advantages and disadvantages of tail pointers?

• advantages: enables O(1) insertion at the end

• disadvantages: requires additional management to keep it updated

what are the differences between nodes in doubly linked lists and singly linked lists?

in doubly linked lists each node has two pointers, one to the next node and one to the previous

what are the advantages to doubly linked lists? disadvantages?

• advantages: easier to travel backwards, more efficient for certain operations (like deletion given a pointer to a node)

• disadvantages: higher memory usages because of the extra pointer

write a function that can travel a list.

Node* traveler = head;

while (traveler != NULL) {

cout << traveler -> data << endl;

traveler = traveler -> next;

}

this prints going forward, to go backward change next to prev.

why make something a template?

• allows a single class or function to work with any data type

• reduces code duplication by letting you use the same code with different data types

does template code compile on its own?

• no, because they are not useable until they are called with a specific type

  • this is why templates are typically written in header files

what do template headers and parameters look like?

header: template<typename T>

parameter: T is used as a placeholder for the variables that change

how do you make a template class and use it?

• define the class completely in the header file

  • or explicitly include the template for specific types

• during use, specify type when calling ex: Class<int>

what is an “unable to instantiate” error?

it occurs when an operation in the template is invalid for the provided type

when do you use <T> or <type>?

• T is used as a placeholder that will change depending on the data type

• type is used for more specific cases where the variable type does not change no matter the template type when called

what is the standard template library(STL)?

• a c++ library that provides generic data structures (like vectors, lists, and sets) and algorithms (like sort and search)

• it saves time by offering pre-built, and tested implementations

how do you code from STL?

• include the necessary header file (<vector>, <list>, etc.)

• use namespace std (or prefix std::)

what are the different types of containers?

vector, list, set, multiset, stack, queue, and priority queue

how does a vector work?

a vector is a dynamic array with fast and random access. adding/removing at the end is O(1), and elsewhere it is O(n)

how does a list (linked list) work?

efficient insertion and removal anywhere but there is no random access (must travel entire list to get to specific points)

how do sets work?

sets store unique elements in a sorted order. operations like insert and find are O(log n) because of the underlying balanced tree

how do multisets work?

similar to a set with elements in a sorted order and O(log n), but these allow duplicate elements

how do stacks work?

stacks are last in, first out (LIFO) with push, pop, and top operations

how do queues work?

queues are first in, first out (FIFO) with front, back, push, and pop operations

how do priority queues work?

elements are ordered by priority, with the highest-priority being accessible first

how would you make a child class?

class Parent{…};

class Child : public Parent {…};

what does a child class inherit from their parent class?

they can access public and protected members, while private members are not accessible directly, but are indirectly inherited

why use a protected section with class inheritance?

allows child classes to access members while still keeping them hidden from external code

what is a virtual function?

they enable runtime polymorphism by ensuring that the child class’s version is called instead of the parents

what is a purely virtual function?

a virtual function with =0 in its declaration ex:

virtual void func() = 0;

it makes the class abstract, meaning you cant instantiate it

how do you make a container that seems to store different types of objects (polymorphism)?

use a parent class pointer to store objects of the child class types

Parent* object = new Child();

what is slicing?

slicing occurs when assigning a child object to a parent object. doing this “slices off” the data that is specific to the child, leading to losing data

when would you use a parent or child class?

use child instead of parent when you need access to child-specific members

use parent instead of child when you only need things defined in the parent class

you can use a child where a parent is expected, but you cant use a parent where a child is expected

whats the difference between stacks and queues?

• stacks: last in first out, items are added and removed at the top only

• queues: first in first out, items are added at the back and removed from the front

what are the functions associated with stacks and queues?

stacks: push(add to top) top(see most recent element) pop(removes top) and size(get size)

queue: push(add to back) front(first element) back(see last) pop(remove front) size(get size)

do you need an iterator for stacks and queues?

no, they are accessed sequentially

what is the base case for recursion? why is it needed?

the condition at which recursion stops

to prevent infinite recursion and allow the function to end

what is the recursive call? why is it different from the initial call?

the part of the function that calls itself with modified parameters

the parameters in the recursive call are closer to the base case

show how a recursive function operates

example function:

int factorial(int n) {

if (n == 0) { // Base case

return 1;

} else { // Recursive case

return n * factorial(n - 1);

}

}

use a call stack diagram

1. visualize each recursive call as a new stack frame

2. track parameters, operations, and return values step-by-step until reaching base case

3. work backward through the stack as the function returns

ex: finding a factorial

1. initial call

   • factorial is called for the number 3

   • its not base case, so it calculates 3 × 2!

2. recursive call

   • 2! is called

   • not base case, so it calculates 2 × 1!

3. recursive call

   • 1! is called

   • not base case, so 1 × 0!

4. base case 0!

   • 0! is called

   • 1 is returned

working backward, multiply values that are split, so 1 × 1 × 2 × 3 which equals 6