Data Structures Quiz
22 Questions
0 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 does the 'push' operation do in a stack?

  • It adds an item to the top of the stack. (correct)
  • It adds an item to the bottom of the stack.
  • It removes an item from the top of the stack.
  • It returns the total number of items on the stack.

    • Which error condition occurs when attempting to pop from an empty stack?

  • Stack Underflow (correct)
  • Boundary Condition Error
  • Null Pointer Exception
  • Stack Overflow

    • How does a queue differ from a stack in terms of item removal?

  • The last item added is the first to be removed.
  • Items are removed randomly.
  • Items are removed in the order they were added. (correct)
  • Items can only be removed from the middle.

    • Which operation is associated with a queue but not with a stack?

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

    What type of graph traversal algorithm visits all vertices by exploring as far as possible along each branch before backtracking?

    <p>Depth-First Search</p> Signup and view all the answers

    What is the primary characteristic of a stack data structure?

    <p>Items are processed in a last in, first out manner.</p> Signup and view all the answers

    Which of the following is a real-world application of a stack?

    <p>Storing web browser history.</p> Signup and view all the answers

    What defines a queue data structure?

    <p>Items are added to the end and removed from the beginning.</p> Signup and view all the answers

    Which scenario best describes the use of a priority queue?

    <p>Handling emergency responses where urgent cases must be addressed first.</p> Signup and view all the answers

    In a stack implemented with linked nodes, what does the 'head' point to?

    <p>The last item added to the stack.</p> Signup and view all the answers

    How does a compiler utilize a stack during function calls?

    <p>To manage local variables and return addresses.</p> Signup and view all the answers

    What type of structure would typically be used to implement a priority queue?

    <p>A linked-list of queues.</p> Signup and view all the answers

    What does it mean when a queue is full?

    <p>The queue allows no more elements to be added.</p> Signup and view all the answers

    In a linked list implementation of a queue, where does an element get added?

    <p>At the end of the list.</p> Signup and view all the answers

    Which operation is performed to remove an element from a queue?

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

    What kind of communication does the Unix operating system implement using queues?

    <p>Inter-Process Cooperation (IPC)</p> Signup and view all the answers

    What is a common use of queues in real-world applications?

    <p>Buffering file inputs and outputs.</p> Signup and view all the answers

    Which data structure consists of nodes that are interconnected?

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

    What is NOT a parameter you would typically analyze in queuing theory?

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

    Which term describes the process of adding an element to a queue?

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

    Which of the following statements about FIFO is true?

    <p>Elements are removed in the order they were added.</p> Signup and view all the answers

    For which of the following scenarios would a queue be the most appropriate data structure to use?

    <p>Managing print jobs in a printer.</p> Signup and view all the answers

    Study Notes

    Stacks

    • Stacks follow LIFO (Last-In, First-Out)
    • Items are added (pushed) and removed (popped) from the top.
    • A stack of books is a real-world example.
    • Stack operations include:
      • push: Adds an item to the top
      • pop: Removes and returns the top item
      • top: Returns the top item without removing it
      • size: Returns the number of items
      • isEmpty: Returns True if empty, False otherwise
    • Stack implementations:
      • Arrays: Fixed size, can waste memory if not large enough to hold all items
      • Linked Lists: Dynamic memory, expands as needed
    • Time complexity (Big O):
      • push/pop/top/size: O(1) (constant time)

    Queues

    • Queues follow FIFO (First-In, First-Out)
    • Items are added (enqueued) to the rear, and removed (dequeued) from the front.
    • A line at a store is a real-world example.
    • Queue operations include:
      • enqueue: Adds an item to the rear
      • dequeue: Removes and returns the front item
      • first: Returns the front item without removing it
      • last: Returns the last item without removing it
      • size: Returns the number of items
      • isEmpty: Returns True if empty, False otherwise
    • Queue implementations:
      • Use Arrays that can be circular for queue, this may eliminate wasted memory or inefficient memory allocation
      • Linked Lists
    • Time complexity (Big O):
      • enqueue/dequeue/first/last/size: O(1) (constant time)

    Priority Queues

    • Priority queues are like queues but elements have priorities.
    • Higher-priority elements are serviced first.
    • Airport ticket counters are an example.

    Graphs

    • A graph is a non-linear data structure with nodes and edges.
    • Nodes are often called vertices, edges are the connections.
    • Graphs can be directed or undirected (with or without arrowed edge associations).
    • Edges can specify weights or weights can be assigned.
    • Graph terminology includes:
      • Vertex: A node in the graph
      • Edge: A connection between two vertices. An edge can be labeled or not.
      • Directed graph: Edge connections are directional
      • Undirected graph: Edge connections are non-directional
      • Loop: An edge connecting a vertex to itself
      • Path: A sequence of connected vertices.
      • Simple graph: No loops or multiple edges between the same two vertices
      • Weighted graph: Edges has weight
    • Graph implementation includes:
      • Adjacency Matrix
        • Use with true/false values to indicate if an edge exists; otherwise use weighted numeric values
        • A 2D array can be used.
      • Adjacency List
        • An array of linked lists
    • Graph traversal methods include:
      • Depth-First Search (DFS): Uses a stack to visit nodes—going deep as far as you can—then backtrack and visit other paths
      • Breadth-First Search (BFS): Uses a queue, visits all adjacent nodes of a given node before going to the next node levels.
    • Graph algorithms include:
      • Path finding (Determining if a path exists)
      • Shortest path algorithms (Dijkstra's algorithm): Find the shortest weighted path from a source to all or selected destination vertices

    Studying That Suits You

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

    Quiz Team

    Related Documents

    CSC 1061 Week 14 Stacks, Queues & Graphs PDF

    Description

    Test your knowledge of data structures with this quiz that covers important concepts such as stacks and queues. Answer questions related to operations like 'push' and 'pop', and understand the differences in item removal between these structures. Delve into graph traversal algorithms and challenge your understanding.

    More Like This

    Use Quizgecko on...
    Browser
    Open
    Browser
    Browser