CPE 212 Homework 3 Review: Data Structures and Software Design

Vocabulary flashcards covering object-oriented design concepts, queues, stacks, recursion, and binary search trees from CPE 212 Homework 3.

Object-Oriented Analysis and Design (OOAD)

A software design approach that focuses on objects which combine data and behavior/processes into a single unit.

Traditional Design

A software design approach that keeps the focus on functions and processes, separating the data from procedures.

Use Case Diagrams

Diagrams used in OOAD to outline the system's functionality and the interactions between the users and the system itself.

Gold-Plating

Adding extra, non-requested features to a project; prevented by comparing the completed project against requested requirements and removing extras, or cross-checking feature requirements prior to implementation.

Overloaded Function Identification

The mechanism by which the compiler identifies overloaded functions by examining their number, type, and order of parameters.

Generic Programming

A programming paradigm that keeps code generic, allowing it to be reused elsewhere and facilitating easier code maintenance.

Sequential (Array) List

A list implementation stored in contiguous memory that has fast and efficient random access and a fixed size, but is more difficult to delete or insert items within.

Linked List

A list implementation stored in nodes connected by pointers that has dynamic size and is efficient at inserting new items.

Shallow Copy

A copy operation that copies pointer addresses and shares the same data between variables.

Deep Copy

A copy operation that creates new memory and copies the data into that memory, rendering it completely separate from the original.

Push and Pop

Stack operations governed by LIFO where Push adds items to the top and Pop removes items from the top.

Defensive Code

Programming techniques designed to keep execution within expected bounds, primarily incorporated via exception handling and input validation.

Activation Record (Stack Frame)

A structure that stores parameters, return addresses, saved registers, and function call information.

Infinite Recursion

An unbounded recursive execution that occurs due to: 1. No base case, 2. Skipping past the base case, or 3. Making no progress towards the base case.

Enqueue and Dequeue

Simple queue operations where Enqueue adds elements to the rear and Dequeue removes elements from the front.

Fixed Front Queue

A queue implementation where the front remains at index $0$, requiring all other items/elements to shift when an element is removed.

Floating Front Queue

A queue implementation where the front pointer moves forward as elements are removed.

Circular Queue

A reusable queue structure that wraps around, allowing items to be removed from the front and added to the rear within a allocated space as long as it is not full.

Priority Queue Implementations

Two distinct design approaches: faster deletion by sorting during insertion, or faster insertion by sorting during deletion.

Non-linear Data Structure (Tree)

A data structure organized hierarchically rather than sequentially, where a single node can have multiple child nodes.

Root

The top node of a tree.

Parent Node

A node in a tree that has one or more child nodes below it.

Child Node

A node in a tree stemming from a parent node above it.

Subtree

A tree formed by a node and all of its descendants, where that node functions as the root of the subtree.

Leaf Node

A tree node without any children.

Siblings

Nodes in a tree structure that share the same parent node.

Level Node Capacity Calculation

The maximum number of nodes at level $N$ given by $X^N$, where $X$ is the number of children per parent (e.g., $2^N$ for binary trees, and $4^3 = 64$ at level $3$ with $4$ children per parent).

Minimum Tree Height

A tree calculation expressed as $\log_2(N) = \log(N)$.

Full Binary Tree

A binary tree in which every node has either $2$ children or $0$ children.

Complete Binary Tree

A binary tree in which every level is filled except for the last, which fills from left to right.

Degenerate Binary Tree

A binary tree in which every node has only $1$ child.

Balanced Binary Tree

An asymmetrical binary tree where the heights of the left and right subtrees differ by at most $1$ at each node.

Skewed Binary Tree

A binary tree in which all nodes lean to one side.

Perfect Binary Tree

A binary tree where all nodes have exactly $2$ children and all leaves are situated at the same level.

Binary Search Tree (BST)

A tree where the left subtree contains only nodes with keys less than the root's key, the right subtree contains only nodes with keys greater than the root's key, and all subtrees are themselves binary search trees.

Pre-order Traversal

A binary search tree traversal that visits nodes in the order: $\text{Root} \rightarrow \text{Left} \rightarrow \text{Right}$.

In-order Traversal

A binary search tree traversal that visits nodes in the order: $\text{Left} \rightarrow \text{Root} \rightarrow \text{Right}$.

Post-order Traversal

A binary search tree traversal that visits nodes in the order: $\text{Left} \rightarrow \text{Right} \rightarrow \text{Root}$.

BST Search Operation

A procedure starting at the root to check if a node matches the target key; if not, traverses left if smaller or right if larger, repeating until found or searched entirely.

BST Delete Operation

A node deletion procedure: delete directly if a leaf; replace with its child if it has $1$ child; or replace with its in-order successor and delete the successor if it has $2$ children.