Data Structures and Time Complexity Quiz
24 Questions
10 Views

Data Structures and Time Complexity Quiz

Created by
@CourteousSatire2150

Podcast Beta

Play an AI-generated podcast conversation about this lesson

Questions and Answers

What is the best case time complexity of Quick Sort?

  • O(n)
  • O(nlogn) (correct)
  • O(n^2)
  • O(logn)

    • Which of the following is a linear data structure?

  • Trees
  • Hash tables
  • Graphs
  • Stacks (correct)

    • What are the three steps that make up the divide and conquer paradigm?

  • Split, Solve, Join
  • Divide, Conquer, Combine (correct)
  • Divide, Solve, Merge
  • Break, Solve, Combine

    • Which algorithm is NOT considered to use the divide and conquer paradigm?

    <p>Insertion Sort</p> Signup and view all the answers

    What is the average time complexity for searching in a hash table?

    <p>O(1)</p> Signup and view all the answers

    What is a characteristic of in-place sorting algorithms?

    <p>They rearrange the elements within the same array.</p> Signup and view all the answers

    Which data structure is an example of a non-linear data structure?

    <p>Tree</p> Signup and view all the answers

    Which of these algorithms has the worst case time complexity of O(n^2)?

    <p>Insertion Sort</p> Signup and view all the answers

    What characterizes an in-place sorting algorithm?

    <p>It sorts elements in the same array as the input.</p> Signup and view all the answers

    Which of the following is an example of a non-in-place sorting algorithm?

    <p>Merge sort</p> Signup and view all the answers

    Which sorting algorithm is considered stable?

    <p>Merge sort</p> Signup and view all the answers

    What defines an unstable sorting algorithm?

    <p>It rearranges elements under all circumstances.</p> Signup and view all the answers

    Which of the following correctly describes the property of a max-heap?

    <p>Every parent node must be greater than or equal to its child nodes.</p> Signup and view all the answers

    What is the best-case time complexity of the Quicksort algorithm?

    <p>O(n log n)</p> Signup and view all the answers

    Which of the following arrays is used for Counting-Sort as storage?

    <p>C</p> Signup and view all the answers

    What policy governs the ordering in a Queue data structure?

    <p>First in first out</p> Signup and view all the answers

    What operation is performed when encountering a plus sign in the stack sequence described?

    <p>Pop the top two elements and add</p> Signup and view all the answers

    Which two functions are used to add and remove elements from a Stack?

    <p>Push and pop</p> Signup and view all the answers

    What attribute of a stack keeps track of the most recent element pushed?

    <p>Top</p> Signup and view all the answers

    In the given binary search tree traversal, what is the order for postorder traversal?

    <p>25, 35, 30, 45, 60, 50, 40</p> Signup and view all the answers

    Which two attributes keep track of a queue's first element and the next insertion position?

    <p>Head and tail</p> Signup and view all the answers

    What is the primary purpose of a sentinel in data structures like merge sort and red-black trees?

    <p>To mark boundaries in operations</p> Signup and view all the answers

    What is the binary search tree property regarding the keys of nodes?

    <p>The left child key must be less than the parent key</p> Signup and view all the answers

    What are the five properties that satisfy a red-black tree?

    <p>Coloring, balance, order, maximum height, and arrangement</p> Signup and view all the answers

    Study Notes

    Big O Time Complexity

    • Insertion Sort - Worst Case: O(n^2)
    • Merge Sort - Worst Case: O(nlogn)
    • Heap Sort - Worst Case: O(nlogn)
    • Quick Sort - Worst Case: O(n^2), Best Case: O(nlogn)
    • Counting Sort - Worst Case: O(k+n)
    • Searching Hash Table - Worst Case: O(n), Best Case: O(1)
    • BST Tree-Search - Worst Case: O(h) or O(logn)
    • BST Insert/Delete - Worst Case: O(h) or O(logn)
    • Inorder, postorder, preorder search - Worst Case: O(n)

    Data Structures

    • Linear Data Structures
      • Linked List
      • Arrays
      • Stacks and Queues
    • Non Linear Data Structures
      • Trees
      • Graphs
      • Hash Tables

    Recursion

    • Recursion is when a function calls itself to break down a problem into smaller components.
    • Example: Calculating factorials.

    Divide and Conquer Paradigm

    • This paradigm utilizes three steps:
      • Divide: Break the problem into smaller subproblems
      • Conquer: Recursively solve these subproblems
      • Combine: Combine the solutions to the subproblems to solve the original problem.
    • Algorithms using divide and conquer:
      • Merge Sort
      • Quick Sort
      • Heap Sort

    MergeSort

    • Merge sort algorithm uses sentinel nodes to ensure that the sorting process is correct.
    • The function Merge(A, p, q, r) takes an array A and splits it into two sub-arrays (left and right).
    • The MergeSort algorithm continues to recursively break the sub-arrays into individual "chunks" of elements, compares them, rearranges them, and combines them until both the left and right sub-arrays are sorted.

    Sorting

    • In-Place Sorting: Sorting algorithms that do not require extra memory and sort the elements in the same array as the input.
      • Examples: Insertion Sort, Quick Sort
    • Not In-Place Sorting: Algorithms that require additional memory, often using a separate array for storing elements.
      • Example: Merge Sort
    • Stable Sorting: Preserves the order of elements with the same value, maintaining the same order between input and output.
      • Examples: Insertion Sort, Merge Sort.
    • Unstable Sorting: Does not preserve the input order for elements with the same value; the output order is different from the input order.
      • Examples: Heap Sort, Quick Sort

    Max-Heapify

    • The Max-Heapify(A,i) function takes an input array and creates sub-arrays (left and right) for each element.
    • The function places each element in order by index, while satisfying the property of a max heap, where the parent node is always greater than or equal to its child nodes.

    QuickSort Partition

    • Partition(A, p, r) function is a key component of the QuickSort algorithm.
    • It selects a pivot element and partitions the array into two parts: elements less than the pivot and elements greater than the pivot.
    • The function returns the index of the pivot element.

    QuickSort Best Case

    • The best case for QuickSort happens when the pivot is chosen in a way that ensures a nearly equal split in each recursion.
    • This results in a time complexity of O(nlogn).

    Counting Sort

    • Counting Sort uses three arrays:
      • A: The input array to be sorted
      • B: The output array, which holds the sorted elements
      • C: An auxiliary array used for counting the occurrences of each element in the input array.

    Stacks

    • Stacks follow a Last In, First Out (LIFO) policy.
    • A stack has functions:
      • Push: Adds a new element to the top of the stack
      • Pop: Removes the top element from the stack
    • The attribute top keeps track of the most recently pushed element.

    Queues

    • Queues use a First In, First Out (FIFO) policy. The elements are added to the tail of the queue and removed from the head.
    • The attribute head stores the index of the first element in the queue, and the tail attribute stores the index of the next location where a new element can be inserted.

    Doubly Linked List

    • A Doubly Linked List is a linear data structure where each node contains:
      • Data
      • A pointer to the next node (next)
      • A pointer to the previous node (prev)

    Tree Structure Attributes

    • A tree structure consists of:
      • Key: Representation of the data associated with a node
      • Parent: The node above a given node in the hierarchy
      • Left: The node to the left of a given node
      • Right: The node to the right of a given node
      • Edge: The connection between two nodes
      • Siblings: Nodes with the same parent
      • Nodes: Fundamental building blocks of the tree
      • Leaves: Nodes with no children
      • Root: The top-most node in the tree

    Binary Search Tree Property

    • The binary search tree property enforces that the key of the left child of any node is less than or equal to the key of the parent node.
    • Also, the key of the right child is greater than the key of the parent node.

    Tree Traversal

    • Inorder Traversal: Visits the nodes in ascending order.
    • Preorder Traversal: Visits the root node first, followed by the left subtree, and then the right subtree.
    • Postorder Traversal: Visits the left subtree first, then the right subtree, and finally the root node.

    Red-Black Tree Properties

    • Red Black Trees must satisfy these five properties:
      • Property 1: Each node is either red or black.
      • Property 2: The root is black.
      • Property 3: All leaves (NIL) are black.
      • Property 4: If a node is red, then both its children are black.
      • Property 5: For each node, every simple path from the node to a descendant leaf has the same number of black nodes. .

    Sentinel

    • A sentinel is a marker or boundary node that signals the end of a data structure.
    • Sentinels are used to avoid checking for null nodes in algorithms like Merge Sort to simplify the process.
    • In Red-Black Trees, sentinels are used as null nodes, simplifying operations such as rotations and insertions.

    Studying That Suits You

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

    Quiz Team

    Related Documents

    Midterm Study Guide (1).docx

    Description

    Test your knowledge on Big O time complexity and various data structures with this quiz. Explore concepts such as sorting algorithms, linear and non-linear data structures, recursion, and the divide and conquer paradigm. Perfect for students looking to reinforce their understanding of algorithms and data organization.

    More Like This

    Use Quizgecko on...
    Browser
    Open
    Browser
    Browser