Data Structures and Time Complexity Quiz
24 Questions
4 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 the worst-case time complexity of Quick Sort?

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

    • Which of the following is NOT a characteristic of divide and conquer algorithms?

  • They combine the solutions of the subproblems.
  • They can be solved in linear time. (correct)
  • They break a problem into smaller subproblems.
  • They solve the subproblems recursively.

    • In the context of sorting algorithms, which one is considered in-place?

  • Merge Sort
  • Quick Sort (correct)
  • Heap Sort
  • Counting Sort

    • What is one reason why Merge Sort is often preferred over other sorting algorithms for large datasets?

    <p>It is stable and performs well with large datasets.</p> Signup and view all the answers

    Which of the following data structures is considered linear?

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

    Which step is NOT part of the divide and conquer paradigm?

    <p>Conquer — change the problems</p> Signup and view all the answers

    Which algorithm utilizes the property of having a worst-case time complexity of O(k+n)?

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

    In recursive algorithms, what is meant by the base case?

    <p>The condition that terminates the recursion.</p> Signup and view all the answers

    What is the function used to remove an element from a stack?

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

    Which attribute of a stack allows access to the most recently added element?

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

    In which tree traversal method is the root node visited last?

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

    Which properties are characteristic of a red-black tree?

    <p>Each path from root to leaf has the same number of black nodes.</p> Signup and view all the answers

    What are the two functions that add and remove elements from a queue?

    <p>Enqueue and dequeue</p> Signup and view all the answers

    What is the binary search tree property regarding keys?

    <p>All keys must be unique.</p> Signup and view all the answers

    During the stack operation for '123+45**+', what does the stack contain immediately after the operation of '5*4'?

    <p>1, 20</p> Signup and view all the answers

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

    <p>To serve as a marker or boundary.</p> Signup and view all the answers

    Which of the following sorting algorithms is an example of a stable sorting algorithm?

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

    What characterizes an in-place sorting algorithm?

    <p>Sorts elements using the same array as input</p> Signup and view all the answers

    Which of the following statements is true regarding unstable sorting algorithms?

    <p>The order of equal elements may change in the output.</p> Signup and view all the answers

    What is the main purpose of the C array in the Counting-Sort algorithm?

    <p>To count the occurrences of each unique element</p> Signup and view all the answers

    In the Max-Heap structure, what must be true about the parent and child nodes?

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

    What is a characteristic feature of an unstable sorting algorithm when sorting elements?

    <p>It may rearrange equal elements in a different order.</p> Signup and view all the answers

    Which of the following sorting algorithms is classified as not in-place due to its requirement for additional memory?

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

    In the context of Quick sort, what is the significance of the pivot point?

    <p>It facilitates splitting the array into two approximately equal parts.</p> Signup and view all the answers

    Study Notes

    Time Complexity

    • Insertion Sort - Worst case time complexity is O(n^2)
    • Merge Sort - Worst case and best case time complexity is O(nlogn)
    • Heap Sort - Worst case and best case time complexity is O(nlogn)
    • Quick Sort - Worst case time complexity is O(n^2), best case time complexity is O(nlogn)
    • Counting Sort - Time complexity is O(k+n)
    • Searching Hash Table - Worst case time complexity is O(n), best case time complexity is O(1)
    • BST Tree-Search - Time complexity is O(h) - where h is the height of the tree (effectively O(logn))
    • BST Insert/Delete - Time complexity is O(h) - where h is the height of the tree (effectively O(logn))
    • Inorder, postorder, preorder search - Time complexity is O(n)

    Data Structures

    • Linear Data Structures:
      • Linked List
      • Arrays
      • Stacks & Queues
    • Non Linear Data Structures:
      • Trees
      • Graphs
      • Hash tables

    Recursion

    • When a problem breaks itself down into smaller objects.
    • Calls upon itself.
    • Example: Factorials

    Divide and Conquer

    • Algorithms that utilize divide and conquer:
      • Merge sort
      • Quick sort
      • Heap sort
    • Steps of divide and conquer:
      • Divide - break into smaller problems
      • Conquer - recursively solve the problem
      • Combine - combine the solutions

    Merge Sort

    • Merge(A,p,q,r) - Takes a given array and splits it into two arrays
      • Left sub-array and right sub-array
      • Completes them independently and combines itself back into a whole array in an ordered sequence.
      • Splits into two sub-arrays (left and right), continues to break the sub-arrays array into individual "chunks" elements, compares, rearranges, and combines, until it sorts both left and right sub-array.
      • Merge sort extensively utilizes sentinel nodes for efficiency.

    In-Place Sorting

    • Sorting algorithms that do not need extra memory to sort the elements, it sorts in the same array as the input.
    • Examples: Insertion sort, quick sort

    Not In-Place Sorting

    • Requires additional memory - may use an extra array to store elements.
    • Example: Merge sort

    Stable vs Unstable Sorting

    • Stable Sorting:

      • When the numbers/elements with the same value appear in the same order in the output as it did in the input.
      • Important when the order of equal elements has significant meanings.
      • Examples: Insertion sort, merge sort.

    • Unstable Sorting:

      • Output values are not preserved as it would be in stable sorting, so the input order is different than the output order for elements that are the same.
      • Faster because it's not necessarily ensuring the elements that are the same are in the same order, faster > accuracy.
      • Examples: Heap sort and quick sort.

    Max-Heapify

    • Max-Heapify(A,i) - Takes an input array and creates sub arrays (left and right)
      • Each element of the array goes down the left or right sub array and is placed in order by index to sort them and satisfy the property of a max heap.
      • You check if the left child is less than or equal to the value of the parent.

    Max Heap Property

    • The parent must be greater than or equal to the child.
      • A[Parent(i)] >= A[i]
      • Min heap is the reverse.

    Partition (Quick Sort)

    • Partition(A,p,r) Takes a given array, splits it into two arrays, and places it back together with similar elements, similar to merge sort.

    Quick Sort Best Case Time Complexity

    • Achieved when the pivot point ensures the split is practically equal, resulting in a time complexity of O(nlogn).

    Counting Sort Arrays

    • A is contains the input array.
    • B is the output array.
    • C is the extra storage array used for counting occurrences of elements in the input array.

    Stacks

    • Uses a Last In First Out policy (LIFO).

    Queues

    • Uses a First In First Out policy (FIFO).

    Evaluate Stack Operation

    • 123+45**+
      1. Push 1 to the stack.
      2. Push 2 to stack.
      3. Push 3 to stack.
      4. Encounter a plus sign, so we pop the previous two elements.
      5. Do addition - 2+3=5 and push 5 to the stack (stack is now 1,5).
      6. Push 4.
      7. Push 5 (stack is now 1,5,4,5).
      8. Encounter a '*' - pop the previous two elements (4 and 5) and multiply.
      9. Push 20 to the stack (stack is now 1,5,20).
      10. Encounter a '*' - pop 20 and 5 and multiply.
      11. Push 100 to the stack.
      12. Encounter a '+' - pop the previous two elements (100,1).
      13. Add 100 and 1, and push 101 to the stack.

    Stack Operations

    • Push - adds to the stack.
    • Pop - removes from the stack.

    Stack Attribute

    • Top - keeps track of the most recent element pushed into the stack.

    Queue Operations

    • Enqueue - add to the queue.
    • Dequeue - remove from the queue.

    Queue Attributes

    • Head - keeps track of the index of the first element in the queue.
    • Tail - keeps track of the index of the next location a new element can be inserted.

    Doubly Linked List

    • Contains a pointer to the previous and next node in the list.

    List-Insert and List-Delete

    • List-Insert - Inserts an element into the list.
    • List-Delete - Deletes an element from the list.

    Tree Structure Attributes

    • Key: Unique identifier for each node.
    • Parent: Node directly above a given node.
    • Left: Pointer to the left child node.
    • Right: Pointer to the right child node.
    • Edge: Connection between nodes.
    • Siblings: Nodes at the same level with the same parent.
    • Nodes: Each element of the tree structure.
    • Leaves: Nodes with no children.
    • Root: Topmost node in the tree.

    Binary Search Tree Property

    • The key of the left child of any node is less than or equal to the key of its parent.
    • The key of the right child of any node is greater than or equal to the key of its parent.

    Binary Search Tree Traversal

    • Inorder traversal: 25, 30, 35, 40, 45, 50, 60
    • Preorder traversal: 40, 30, 25, 35, 50, 45, 60
    • Postorder traversal: 25, 35, 30, 45, 60, 50, 40

    Tree Height and Depth

    • Height: 2
    • Depth: 2
    • Performs a search through the tree in an iterative (loop) manner.

    Inserting a Node into a Tree

    • Follows the binary search tree property.

    Transplating a Node in a Tree

    • Used for deleting nodes in a tree.

    Red-Black Tree Properties

    • Every node has a color (red or black).
    • The root is black.
    • Every leaf (NIL) is black.
    • If a node is red, both its children are black.
    • For each node, all paths from the node to descendant leaves contain the same number of black nodes.

    Sentinel

    • A marker or boundary in a data structure.
    • Used for clarity and efficiency in Merge Sort and Red-Black Tree algorithms.

    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 data structures and their time complexities with this quiz. You'll explore various sorting algorithms, their performance, and characteristics of linear and non-linear data structures. Challenge yourself and solidify your understanding of fundamental concepts in computer science.

    More Like This

    Use Quizgecko on...
    Browser
    Open
    Browser
    Browser