Object-Oriented Programming and Data Structures
25 Questions
2 Views

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</p> Signup and view all the answers

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

    <p>True</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

    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

    Description

    Explore the fundamentals of Object-Oriented Programming (OOP) and the key principles that drive it, including Encapsulation, Abstraction, Inheritance, and Polymorphism. This quiz also covers essential data structures and concepts like recursion and Big-O notation for analyzing algorithmic complexity.

    More Like This

    Use Quizgecko on...
    Browser
    Open
    Browser
    Browser