Data Structures - Final Review 2026

what is a class?

a class is a user-defined data type composed of built-in types, functions, and other user-defined types, essentially serving as a blueprint for creating objects

• parts used to define a data type are called members

what is a pointer?

variable that stores the memory address of another value

• similar to an address book or GPS coords.

what is a memory leak?

occurs when a program allocates memory but DOESN’T free it

• causes memory to remain allocated even after the variable is destroyed

• mainly occur with DMA

what is a dangling pointer?

a pointer that points to a memory location that has already been freed

int* ptr = new int[6];

delete ptr; //dangling

cout « *ptr; //CRASH

what is a reference variable?

a reference variable is an alias of an existing variable with the use of the & operator

• once initialized, it cannot be changed

• cannot have a NULL value

• ref variable must be initialized when created

what is the compilation process? give a brief description of each step with a diagram

1. preprocessing - handles directives such as #include & #define

2. compilation - translates preprocessed code into assembly code

3. assembler - converts assembly code to machine code

4. linking - combines object & library files into an executable file

what is debugging? list 4 debugging methods & describe them

the process of finding, isolating, and resolving coding errors/bugs

• divide and conquer

• rubber duck

• brute force

• automated

what is unit testing?

test-driven development (TDD) approach that tests INDIVIDUAL UNITS of code, CHECKING the smallest possible components to ensure they WORK CORRECTLY

what is a test bench?

a separate program whose purpose is to check if the function is returning the correct value

what is a self-referential structure?

a self-referential structure is a structure which points to itself

use case: linked list

struct Node {

int data;

Node* next;

};

what is hashing?

The process of converting a large input into a smaller, fixed-size output that can be used as an index in a table.

• applies hash functions to transform input data

• computes an index or position to store an item in a hash table

write pseudocode for the Adler-32 hashing function

hashfunction(key)

{

a=1;

b = 0;

for (c : key)

{

a= (a + c) % 65521

b = (b + a) % 65521

}

return ((b « 16) | a)% N

}

code an example of a memory leak

void memLeakExample() {

int *ptr = new int[5];

}

code an example of a dangling pointer

void danglingpointerexample() {

int *ptr = new int[5];

delete[] ptr;

ptr = NULL; //fix it

}

code an example of a reference variable

int num1 = 10;

int& ref_num1= num1;

code an example of a self-ref structure

struct selfref {

int data;

struct selfref *next;

};

time complexity defnition

the number of operations needed to run an algorithm on large amounts of data

space complexity definition

the total space used by an algorithm relative to the input

what are the 3 different components of hashing?

1. key

2. hash function

3. hash table

key - component of hashing

a string or int that is provided as input to the hash function

hash function - component of hashing

mathematical formulas that transform input data into a fixed-size value

hash table - component of hashing

stores values associated with specific keys by using a hash function to compute an index in the array

• allows data to be stored and accessed in an associative manner

• each key maps to a particular position in the array

A queue can be implemented using a linked list with which operations?

• adding at tail & receiving from head

• adding at head & retrieving from tail

a stack can be implemented using a linked list with which operations?

• adding at head & retrieving from head

• adding at tail & retrieving from tail

collision (hashing)

occurs when two different keys produce the same hash index

collision resolution (hashing)

• chaining (linked lists at each index)

• open addressing (finding the next empty spot)

• double hashing, linear and quadratic probing, hash table resizing

what is an undirected graph? draw an example

AB = BA

• no directed lines

what is a weighted graph?

a graph in which each edge is assigned a weight

what is a connected graph & a disconnected graph?

• connected graph: all vertices are connected

• disconnected graph: at least one vertex is disconnected

what is a complete graph? give an example

meaning of incident, isolated, and adjacent

incident - if two edges touch

isolated - no touching

adjacent - if there is an edge between two vertices

degree of a vertex

the number of neighbors a vertex has

walk

must be valid

trail

a walk with no repeated edges

path

a walk with no repeated edges or vertices

what is graph isomorphism? give an example

• same # of vertices

• same # of edges

• # same degree sequence

what is a cyclic graph? give an example

a graph with at least ONE cycle

what is a circuit? give an example

closed walk ; starts and ends at the same vertex

• can repeat vertices

• CANNOT repeat edges

what is a euler circuit? give an example

every edge appears exactly ONCE

what is a euler trail? give an example

contains every edge exactly ONCE

• can only contain 2 odd deg vertices at beg or end

what is a hamiltonian cycle? give an example

a cycle that includes every vertex

what is a hamiltonian path? give an example

valid walk that contains every vertex exactly ONCE

what is a planar graph? give an example

a graph with no edge crossings

what is graph coloring?

explain the greedy graph coloring method with an example

what is a subgraph? explain with an example

a graph within another graph, contains the same vertices and edges, just doesn’t include the entire graph

what is an adjacency matrix?

0 & 1 corresponding to relationship

what is an adjacency list?

list in ascending order

1 → 2,3,4

explain Djikstra’s Algorithm

explain the Bellman-Ford Algorithm

what is topological sorting?

what is a tree?

a graph that is connected but has no cycles

• only one unique path between any two vertices

what is a spanning tree?

subgraph that includes all the vertices of G and connects them using the minimum possible number of edges.

what is a minimum spanning tree?

what is Prim’s Algorithm?

what is Kruskal’s Algorithm

what is a rooted tree?

a tree with a root

what is a free tree?

what is inorder traversal? give an example

what is preorder traversal? give an example

what is postorder traversal? give an example

what is level-order traversal? give an example

what is a binary tree? give an example

hierarchical data structure in which each node can have at most two children (left an right)

what is a binary search tree? give na example

all nodes left of a given node are smaller, while all nodes in the right of a given node are bigger

what is a balanced binary tree? give an example

explain insertion in a BST

explain deletion in a BST

what is a B-tree?

what is an AVL tree?

a self-balancing binary search tree in which the height difference between the left and right subtrees of any node is at most one

explain insertion in an AVL tree

explain deletion in an AVL tree

explain BFS (breadth-first search)

start traversing from a selected node (source) and explore all nodes at the present depth prior to moving on to the nodes at the next depth level

explain DFS (depth-first search)

start traversing from a selected node (source) and explore as far as possible along each branch before backtracking.