Data Structures and Algorithms Review
24 Questions
5 Views

Data Structures and Algorithms Review

Created by
@FormidableSage

Podcast Beta

Play an AI-generated podcast conversation about this lesson

Questions and Answers

What is the best case time complexity for Quick Sort?

  • O(n)
  • O(n^2)
  • O(log n)
  • O(n log n) (correct)

    • Heap Sort operates with a time complexity of O(n) in the worst case.

    False

    What are two examples of linear data structures?

    Linked list, Arrays

    Merge Sort uses the ______ paradigm which involves dividing a problem into smaller subproblems.

    <p>divide and conquer</p> Signup and view all the answers

    Match the following algorithms with their time complexities:

    <p>Insertion Sort = O(n^2) Merge Sort = O(n log n) Counting Sort = O(k+n) Searching Hash Table = O(1) - O(n)</p> Signup and view all the answers

    Which of the following is NOT a step in the divide and conquer paradigm?

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

    Recursion is when a function calls upon itself to solve smaller instances of a problem.

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

    Provide an example of a sorting algorithm that utilizes in-place sorting.

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

    Which of the following sorting algorithms is not classified as in-place sorting?

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

    Stable sorting algorithms preserve the order of equal elements in the sorted output.

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

    What is the primary characteristic of a max-heap?

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

    In quicksort, the ______ ensures that the array is split into two virtually equal parts.

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

    Match the sorting algorithms with their characteristics:

    <p>Insertion sort = Stable sorting method Heap sort = Unstable sorting method Merge sort = Stable sorting method Quick sort = Unstable sorting method</p> Signup and view all the answers

    Which of the following arrays are used in Counting Sort?

    <p>All of the above</p> Signup and view all the answers

    A stack follows the First In First Out (FIFO) principle.

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

    How is the best case time complexity for quicksort achieved?

    <p>By ensuring the pivot point splits the array into two practically equal parts.</p> Signup and view all the answers

    What two functions add and remove elements from a stack?

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

    The attributes that track the index of the first element and the next insertion point in a queue are head and tail.

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

    What is the binary search tree property?

    <p>Y.key = x.key</p> Signup and view all the answers

    The _____ of a tree refers to the number of edges from the root to the deepest leaf.

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

    Match the data structure with its corresponding operation:

    <p>Stack = Push and Pop Queue = Enqueue and Dequeue Binary Search Tree = Insertion and Deletion Doubly Linked List = Forward and Backward Traversal</p> Signup and view all the answers

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

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

    In a red-black tree, a sentinel is used as a marker or boundary.

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

    Explain what a leaf is in the context of a tree structure.

    <p>A leaf is a node in a tree that has no children.</p> Signup and view all the answers

    Study Notes

    Time Complexities

    • 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 best case: O(1), worst case: O(n)
    • BST Tree-Search worst case: O(h)
    • BST Insert/Delete worst case: O(h)
    • Inorder, postorder, preorder search worst case: O(n)

    Data Structures

    • Linear data structures: linked lists, arrays, stacks, and queues
    • Non linear data structures: trees, graphs, hash tables

    Recursion

    • A problem is broken down into smaller subproblems.
    • The function calls upon itself.
    • Factorials are an example.

    Divide and Conquer

    • Divide: break down the problem into smaller subproblems
    • Conquer: recursively solve the subproblems.
    • Combine: combine solutions of subproblems

    Merge Sort

    • The Merge(A,p,q,r) pseudocode takes an array and splits it into two subarrays: a left and right subarray.
    • The left and right subarrays continue to split and sort until it reaches a single element.
    • Recursively merge the subarrays into a sorted array using sentinel nodes.

    Sorting Algorithms

    • In-place sorting algorithms do not require additional memory, instead sorting within the original input array.
    • Insertion sort and quick sort are examples of in-place sorting algorithms.
    • Non-in-place sorting algorithms require additional memory to sort elements.
    • Merge sort is an example of non-in-place sorting.
    • Stable sorting algorithms preserve the order of equal elements, as they appear in the input data.
    • Insertion sort and merge sort are examples of stable sorting algorithms.
    • Unstable sorting algorithms do not maintain the order of equal elements, leading to a different order in the output compared to the input.
    • Heap sort and quick sort are examples of unstable sorting algorithms.

    Max-Heapify

    • The Max-Heapify(A,i) pseudocode takes an array and creates left and right subarrays.
    • The function places each element in order by index, satisfying the max heap property.
    • The left child must be less than or equal to the value of the parent.

    Quick Sort

    • The Partition(A,p,r) pseudocode takes an array and rearranges elements such that the array elements to the left of a pivot point are less than the pivot, and elements to the right are greater.

    Achieving best-case time complexity in Quick Sort

    • The pivot point is placed in such a way as to ensure a relatively equal split of the array.
    • This results in O(nlogn) time complexity.

    Counting Sort

    • Counting sort utilizes three arrays:
      • 'A' is the input array - the elements to be sorted
      • 'B' is the output array - the sorted elements
      • 'C' is the auxiliary storage array, used to store the count of each element in the input array.

    Stacks

    • Stacks use the Last In, First Out (LIFO) policy.
    • This means the last element added to the stack is the first one removed.
    • The 'push' function adds an element to the top of the stack.
    • The 'pop' function removes an element from the top of the stack.
    • The 'top' attribute keeps track of the most recent element pushed onto the stack.

    Queues

    • Queues use the First In, First Out (FIFO) policy.
    • The first element added to the queue is the first one removed
    • The 'enqueue' function adds an element to the rear of the queue.
    • The 'dequeue' function removes an element from the front of the queue.
    • The 'head' attribute keeps track of the index of the first element.
    • The 'tail' attribute keeps track of 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 allowing traversal in both directions. Each node in the list has three attributes:
      • Data: The actual data stored in the node.
      • Previous: Pointer to the previous node in the list, allowing backward traversal.
      • Next: Pointer to the next node in the list, allowing forward traversal.

    List-Insert and List-Delete

    • The List-Insert pseudocode takes a linked list and inserts a new node at a specified location.
    • The List-Delete pseudocode takes a linked list and removes a node at a specified location.

    Tree Structure Attributes:

    • Key: A value that uniquely identifies each node in the tree.
    • Parent: Node that directly connects above a given node in the tree.
    • Left: Node that connects to the left of a given node in the tree.
    • Right: Node that connects to the right of a given node in the tree.
    • Edge: A connection between two nodes, representing the relationship between them.
    • Siblings: Nodes that share the same parent node.
    • Nodes: The individual elements of the tree.
    • Leaves: Nodes without any children.
    • Root: The topmost node in the tree, with no parent node.

    Binary Search Tree (BST) Property

    • The binary search tree property states that for any node in a binary search tree: all keys in the left subtree of that node are less than or equal to the key of that node, and all keys in the right subtree of that node are greater than or equal to the key of that node.

    Traversal Algorithms

    • Inorder traversal: Process the left subtree, then the root, then the right subtree.
    • Preorder traversal: Process the root, then the left subtree, then the right subtree..
    • Postorder traversal: Process the left subtree, then the right subtree, then the root.

    Tree Height and Depth

    • The height of a tree is the number of edges on the longest path from the root to a leaf.
    • The depth of a node is the number of edges on the path from the root to that node.
    • The Iterative-Tree-Search pseudocode searches for a node in a tree.

    Red-Black Tree

    • A red-black tree is a self-balancing binary search tree.
    • It utilizes the concept of color (red or black) to ensure balance and efficient search operations.
    • The properties that satisfy a red-black tree are:
      • Every node is either red or black.
      • The root is black.
      • All leaves (null nodes) are black.
      • If a node is red, then both its children are black.
      • For every node, all paths from that node to descendant leaves contain the same number of black nodes.

    Sentinel Node

    • A sentinel node is a special node that is used as a marker for a particular boundary. It is often used to handle boundary cases or to simplify algorithms.
    • In merge sort, a sentinel node is used to indicate the end of a subarray.
    • In red-black trees, a sentinel node is used as the root of the tree, facilitating efficient search operations and improving the handling of boundary conditions.

    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 time complexities, data structures, and concepts such as recursion and divide and conquer. This quiz covers insertion sort, merge sort, quick sort, and various data structures, providing a comprehensive overview of essential algorithms. Perfect for students preparing for exams or anyone interested in computer science.

    More Like This

    Use Quizgecko on...
    Browser
    Open
    Browser
    Browser