Object-Oriented Programming and Data Structures

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to Lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

What is a class in object-oriented programming?

A blueprint for creating objects, grouping attributes and methods.

Which of the following are principles of Object-Oriented Programming (OOP)?

  • Inheritance (correct)
  • Polymorphism (correct)
  • Encapsulation (correct)
  • Abstraction (correct)
  • Iteration

What is encapsulation in OOP?

Grouping data and methods within a class, hiding internal details.

What is abstraction in OOP?

<p>Hiding complex implementation details and exposing only necessary functionality.</p> Signup and view all the answers

What is inheritance in OOP?

<p>Creating new classes derived from existing ones, inheriting attributes and methods.</p> Signup and view all the answers

What is polymorphism in OOP?

<p>Allowing methods in different classes to share the same name but behave differently.</p> Signup and view all the answers

What is recursion?

<p>A function calling itself to solve smaller instances of a problem, with a base case to stop the recursion.</p> Signup and view all the answers

What is Big-O notation used for?

<p>Describing how runtime or space requirements grow with input size.</p> Signup and view all the answers

O(1) represents linear time complexity.

<p>False (B)</p> Signup and view all the answers

Traversing a list has a time complexity of O(n).

<p>True (A)</p> Signup and view all the answers

Which algorithms typically have a time complexity of O(n log n)?

<p>Divide-and-conquer algorithms like Merge Sort.</p> Signup and view all the answers

What is a common example of an algorithm with O(n^2) time complexity?

<p>Bubble Sort.</p> Signup and view all the answers

How does Merge Sort work?

<p>It uses a divide-and-conquer approach, splitting the array, recursively sorting the halves, and merging the sorted halves.</p> Signup and view all the answers

Explain how Quick Sort works.

<p>It selects a pivot, partitions the array around it, and recursively sorts the partitions.</p> Signup and view all the answers

What is a stack data structure?

<p>A linear data structure following the Last In, First Out (LIFO) principle.</p> Signup and view all the answers

What is a linked list data structure?

<p>A sequential structure where each node contains data and a pointer to the next node.</p> Signup and view all the answers

What is the difference between a singly linked list and a doubly linked list?

<p>A singly linked list has one pointer per node while a doubly linked list has pointers to both the next and previous nodes.</p> Signup and view all the answers

What is a circular linked list?

<p>A linked list where the last node points back to the head.</p> Signup and view all the answers

What is a binary tree?

<p>A tree with at most two children per node.</p> Signup and view all the answers

What is a binary search tree (BST)?

<p>A binary search tree that ensures the left child is smaller than the parent, which is smaller than the right child.</p> Signup and view all the answers

Explain the concept of hashing.

<p>Hashing maps keys to indices in a hash table using a hash function.</p> Signup and view all the answers

How does a Breadth-First Search (BFS) explore a graph?

<p>It explores the graph level by level.</p> Signup and view all the answers

Explain how a Depth-First Search (DFS) explores a graph?

<p>It explores as deeply as possible before backtracking.</p> Signup and view all the answers

What is a scapegoat tree?

<p>A self-balancing binary search tree that rebuilds itself when the tree becomes unbalanced.</p> Signup and view all the answers

What is the A* algorithm?

<p>A pathfinding algorithm that combines the cost from the start node (g(n)) and the estimated cost to the goal (h(n)).</p> Signup and view all the answers

Flashcards

Classes

Blueprints for creating objects in OOP. Group attributes (data) and methods (functions).

Object-Oriented Programming (OOP)

Programming paradigm based on Encapsulation, Abstraction, Inheritance, and Polymorphism.

Encapsulation

Grouping data and methods in a class, hiding internal details.

Abstraction

Hiding complex implementation, exposing only necessary functionality.

Signup and view all the flashcards

Inheritance

Creating new classes based on existing ones.

Signup and view all the flashcards

Polymorphism

Methods with the same name but different behaviors across classes.

Signup and view all the flashcards

Recursion

A function calling itself to solve smaller instances of a problem.

Signup and view all the flashcards

Complexity (Big-O)

How runtime or space requirements grow with input size.

Signup and view all the flashcards

O(1)

Constant time. Accessing an array element.

Signup and view all the flashcards

O(n)

Linear time. Traversing a list.

Signup and view all the flashcards

O(n log n)

Divide-and-conquer algorithms like Merge Sort.

Signup and view all the flashcards

O(n^2)

Quadratic time, e.g., Bubble Sort.

Signup and view all the flashcards

Merge Sort

Divides, sorts, and merges. O(n log n).

Signup and view all the flashcards

Quick Sort

Divide-and-conquer, average O(n log n), worst O(n^2).

Signup and view all the flashcards

Stack

LIFO (Last-In, First-Out) data structure.

Signup and view all the flashcards

Linked List

Sequential structure with nodes linked by pointers.

Signup and view all the flashcards

Singly Linked List

Each node points to the next.

Signup and view all the flashcards

Doubly Linked List

Nodes point to both next and previous.

Signup and view all the flashcards

Study Notes

Object-Oriented Programming (OOP) Fundamentals

  • OOP is based on four key principles: Encapsulation, Abstraction, Inheritance, and Polymorphism.
  • Encapsulation: Bundles data (attributes) and methods (functions) within a class, hiding internal details.
  • Abstraction: Simplifies complex implementations by exposing only necessary functionality.
  • Inheritance: Creates new classes (derived classes) based on existing classes (base classes), inheriting properties and behaviors.
  • Polymorphism: Allows methods with the same name to have different behaviors in different classes.

Data Structures

  • Classes: Blueprints for creating objects, combining attributes and methods.
  • Recursion: A function calling itself to solve smaller instances of a problem, requiring a base case.
  • Complexity: Big-O notation describes how runtime/space requirements scale with input size.
    • O(1): Constant time (e.g., accessing array element).
    • O(n): Linear time (e.g., traversing a list).
    • O(n log n): Divide-and-conquer algorithms (e.g., Merge Sort).
    • O(n^2): Quadratic time (e.g., Bubble Sort).
  • Merge Sort: Divide-and-conquer; sorts by splitting, sorting sub-arrays, and merging them. O(n log n) time complexity.
  • Quick Sort: Divide-and-conquer; uses a pivot to partition the array and recursively sorts partitions. Average O(n log n), but worst-case O(n^2).
  • Stack: LIFO (Last-In, First-Out) data structure; uses Push (add) and Pop (remove).
  • Linked List: Sequential data structure where each node points to the next.
    • Singly Linked List: Single pointer per node.
    • Doubly Linked List: Pointers to both the next and previous node.
    • Circular Linked List: Last node points back to the first.
  • Trees: Hierarchical structures with nodes connected by edges.
    • Binary Tree: At most two children per node.
    • Binary Search Tree (BST): Left child < parent < right child.
    • Heap: Specialized binary tree; Max-Heap (parent > children), Min-Heap (parent < children).
  • Hashing: Maps keys to indices in a hash table using a hash function.
  • Graphs: Consist of vertices (nodes) and edges (connections).
    • BFS (Breadth-First Search): Explores level by level.
    • DFS (Depth-First Search): Explores as deeply as possible before backtracking.
  • Scapegoat Tree: Self-balancing binary search tree; rebuilds part of the tree when unbalanced to maintain efficiency.
  • A Search:* Pathfinding algorithm using cost functions (g(n), h(n), f(n)) to estimate optimal paths.

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Quiz Team

More Like This

Use Quizgecko on...
Browser
Open
Browser
Browser