Data Structures and Algorithms Quiz
24 Questions
48 Views

Data Structures and Algorithms Quiz

Created by
@UnselfishNarrative

Podcast Beta

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Which of the following sorting algorithms is an example of in-place sorting?

  • Heap sort (correct)
  • Insertion sort (correct)
  • Merge sort
  • Counting sort

    • Stable sorting maintains the relative order of elements with equal values.

    True

    What is the main property that a max-heap must satisfy?

    The parent must be greater than or equal to the child.

    The _______ sorting algorithm requires an additional storage array to sort the elements.

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

    Match the sorting algorithm to its characteristic:

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

    Which algorithm is considered to utilize not in-place sorting?

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

    Heap sort guarantees that equal elements will maintain their input order.

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

    What is the best case time complexity of Quick sort?

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

    What is the worst-case time complexity of Quick Sort?

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

    Merge Sort utilizes the divide and conquer paradigm.

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

    What is the best-case time complexity of Counting Sort?

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

    The three steps of the divide and conquer paradigm are: divide, conquer, and ______.

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

    Match the sorting algorithms with their corresponding time complexities:

    <p>Insertion Sort = O(n^2) Merge Sort = O(nlogn) Heap Sort = O(nlogn) Counting Sort = O(k+n)</p> Signup and view all the answers

    Which of the following is a linear data structure?

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

    Recursion allows a function to call itself to solve smaller instances of the same problem.

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

    In-place sorting refers to sorting algorithms that sort the data without using additional ______.

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

    Which function is NOT used to add or remove elements from a stack?

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

    In a binary search tree, the key of the left child is greater than the parent key.

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

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

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

    The two functions that add and remove from a queue are __________ and __________.

    <p>enqueue, dequeue</p> Signup and view all the answers

    Match the following data structure attributes with their definitions:

    <p>Parent = The node above a given node in a tree Siblings = Nodes that share the same parent Leaves = Nodes with no children in a tree Root = The topmost node of the tree</p> Signup and view all the answers

    What is the max height of the tree mentioned in the content?

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

    Inorder traversal of a binary search tree visits nodes in ascending order.

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

    List the two attributes that keep track of the first element index and the next insertion index in a queue.

    <p>Head, Tail</p> Signup and view all the answers

    Study Notes

    Algorithm Time Complexities

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

    Data Structures

    • Linear Data Structures: Linked List, Arrays, Stacks, Queues
    • Non-Linear Data Structures: Trees, Graphs, Hash Tables

    Recursion

    • A problem is broken down into smaller, similar subproblems.
    • The function calls itself repeatedly until a base case is reached.
    • Example: Factorial calculation

    Divide and Conquer Paradigm

    • Three Steps:
      • Divide: Split the problem into smaller subproblems.
      • Conquer: Recursively solve the subproblems.
      • Combine: Merge the solutions of the subproblems.
    • Algorithms using Divide and Conquer: Merge Sort, Quick Sort, Heap Sort

    Merge Sort

    • Merge(A,p,q,r): Merges two sorted subarrays A[p..q] and A[q+1..r] into one sorted array.
      • Splits the array into two subarrays (left and right).
      • Recursively sorts the subarrays.
      • Merges the sorted subarrays by comparing elements and placing them in order into a new array.
      • Uses sentinel nodes as placeholders.

    Sorting Algorithms

    • In-Place Sorting: Sorting algorithms that modify the input array directly without using extra memory.
      • Examples: Insertion Sort, Quick Sort
    • Not In-Place Sorting: Sorting algorithms that require additional memory to store elements during sorting.
      • Example: Merge Sort

    Stable vs. Unstable Sorting

    • Stable Sorting: Preserves the relative order of elements with equal values in the output.
      • Examples: Insertion Sort, Merge Sort
    • Unstable Sorting: Does not preserve the relative order of elements with equal values. It can change the order of equal elements.
      • Examples: Heap Sort, Quick Sort

    Max-Heap

    • Property: Every node's value is greater than or equal to its children's values.
    • Max-Heapify(A,i): Maintains the max-heap property by sifting down an element at index i.
      • Compares the element at index i with its left and right children.
      • If the element is smaller than either child, it swaps with the larger child.
      • Recursively calls Max-Heapify on the subtree that was affected by the swap.

    Quick Sort

    • Partition(A,p,r): Chooses a pivot element and partitions the array around it.
      • Elements smaller than the pivot are placed to the left, and elements larger than the pivot are placed to the right.
      • Returns the final position of the pivot.
    • Best Case Time Complexity: Achieved when the pivot point splits the array into nearly equal subarrays in each recursive step.
      • O(n log n)

    Counting Sort

    • Arrays:
      • A: Input array.
      • B: Output array.
      • C: Auxiliary array used for counting the frequency of elements in the input array.

    Stack

    • Policy: Last In First Out (LIFO).
    • Functions:
      • Push: Adds an element to the top of the stack.
      • Pop: Removes and returns the top element from the stack.
    • Attribute: top: Keeps track of the index of the most recent element pushed into the stack.

    Queue

    • Policy: First In First Out (FIFO).
    • Functions:
      • Enqueue: Adds an element to the back of the queue.
      • Dequeue: Removes and returns the element at the front of the queue.
    • Attributes:
      • head: Index of the first element in the queue.
      • tail: Index of the next available location for insertion.

    Doubly Linked List

    • Attributes: Each node contains:
      • Data
      • Pointer to the previous node
      • Pointer to the next node

    List-Insert and List-Delete

    • List-Insert: Inserts a new node after a given node in the linked list.
    • List-Delete: Removes a given node from the linked list.

    Tree Structure

    • Attributes:
      • Key: Unique identifier for each node.
      • Parent: Node that contains the current node.
      • Left: Left child node.
      • Right: Right child node.
      • Edge: Connection between two nodes.
      • Siblings: Nodes with the same parent.
      • Nodes: Individual elements in the tree.
      • Leaves: Nodes with no children.
      • Root: Top node of the tree.

    Binary Search Tree Property

    • For every node x in the tree, the key of x is greater than or equal to the key of every node in the left subtree, and less than or equal to the key of every node in the right subtree.

    Tree Traversal

    • Inorder: Left subtree, root, right subtree.
    • Preorder: Root, left subtree, right subtree.
    • Postorder: Left subtree, right subtree, root.

    Red-Black Tree

    • Properties:
      • Every node is either red or black.
      • The root is black.
      • All leaves (NIL nodes) are black.
      • If a node is red, then both its children are black.
      • For every node, all simple paths from the node to descendant leaves contain the same number of black nodes.

    Sentinel

    • A marker or boundary node that signals the end of a structure or indicates a specific state.
    • Merge Sort: Used to mark the end of subarrays during merging.
    • Red-Black Tree: NIL nodes are sentinel nodes representing leaves in the tree.

    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 algorithm time complexities, data structures, and recursion concepts. This quiz covers essential topics such as sorting algorithms, searching techniques, and the divide and conquer paradigm. Prepare to challenge your understanding of foundational computer science principles!

    More Like This

    Use Quizgecko on...
    Browser
    Open
    Browser
    Browser