CS 113 - Final Exam Study Guide Flashcards

This set of vocabulary flashcards covers key concepts from the CS 113 Final Exam Study Guide, including data structures, search and sort algorithms, recursion, and tree properties.

LIFO (Last-In First-Out)

A principle where the most recently added element is the first one to be removed, followed by the Stack data structure.

FIFO (First-In First-Out)

A principle where elements are removed in the same order they were added, followed by the Queue data structure.

Stack

A data structure that follows the LIFO principle, best suited for implementing undo operations.

pop()

A Java Stack method that removes and returns the top element.

poll()

A Queue method that retrieves and removes the head element.

Deque

A data structure that allows insertion and deletion at both the front and the rear ends.

Recursion

A programming technique where a method calls itself until a base case is reached.

Base case

The stopping condition in recursion; without it, the program results in infinite recursion or stack overflow.

Inorder Traversal

A tree traversal method that visits the left subtree, the root, and then the right subtree.

Preorder Traversal

A tree traversal method that visits the root node before its subtrees.

Postorder Traversal

A tree traversal method that visits subtrees before the root node.

Binary Search Tree (BST) Average Case

The average-case time complexity of searching a binary search tree is $O(\text{log } n)$.

Priority Queue

A data structure that always removes the highest-priority element first.

Max-heap

A priority queue implementation where the root element is always the largest element.

Hashing

A process that converts data into an index value for storage or retrieval.

HashMap

A Java class that implements a hash table using key-value pairs, with an average-case lookup complexity of $O(1)$.

Collision

An occurrence in hashing where two different keys map to the same index value.

Hash Table Worst-Case

The searching time in a poorly distributed hash table where complexity reaches $O(n)$.

Selection Sort

A sorting algorithm that repeatedly finds the minimum element; it is inefficient for large datasets with a worst-case time complexity of $O(n^2)$.

Quick Sort

A sorting algorithm that works by partitioning elements around a pivot, with an average-case time complexity of $O(n \text{ log } n)$, and a worst-case of $O(n^2)$.

AVL Tree

A self-balancing binary search tree that maintains balance using rotations.

Balance Factor

The height difference between the left and right subtrees of an AVL node.

Right Rotation

The specific AVL tree rotation used to fix a left-left imbalance.

Left Rotation

The specific AVL tree rotation used to fix a right-right imbalance.

peek()

An operation that allows viewing the top element of a stack or the head of a queue without removing it.

Root Node

The top-most node in a tree structure.

Leaf Node

A node in a tree that has no children.

Pivot

A specific element in Quick Sort used to partition data into two sub-groups.

Dequeue

The operation of removing an element from the front of a queue.