ICQ3-Linear DS

CSCI 3230A Data Structures - Fall 2024 In-class Quiz Notes

Quiz Overview

• Total Points: 10

• Time Limit: 30 minutes

• Instructions:

  • No Resources: Ensure that no books, notes, or electronic devices are allowed during the quiz.

  • No Collaboration: Each student must work independently without discussing questions or answers with peers.

  • MCQ Selection Must Be Unambiguous: Answer choices should not allow for ambiguity to ensure clarity in assessment.

Questions Overview

Q1: Linked Lists

• Question: Linked lists are best suited for which of the following cases?

• Options:

  • (a) Relatively permanent, big data collections: This indicates that linked lists may not be the most efficient structure for data that does not frequently change.

  • (b) Constantly changing size of the data structure: Linked lists allow for dynamic memory allocation, which makes them ideal for scenarios where data size frequently changes.

  • (c) For both options A and B: Suggesting that linked lists can serve both stable and dynamic data situations.

  • (d) None of these: Indicates that none of the previous statements apply.

Q2: Stack Data Structure Classification

• Question: A Stack data structure belongs to which of the following categories?

• Options:

  • (a) FIFO (First In, First Out): Indicates a queue system where the first element added is the first to be removed.

  • (b) LIFO (Last In, First Out): Correctly defines a stack, where the last element added is the first to be removed.

  • (c) LILO (Last In, Last Out): Not a common classification for stacks.

  • (d) FILO (First In, Last Out): Another term for LIFO, used interchangeably in some contexts.

Q3: Run-time Complexity in Stack Conversions

• Question: In conversion from prefix to postfix using stack data-structure, if operators and operands are pushed and popped exactly once, then the run-time complexity is:

• Options:

  • (a) O(1): Indicates constant time complexity which is not suitable for this operation.

  • (b) O(n): Correct, as n refers to the number of elements in the expression.

  • (c) O(n log n): Implies the use of sorting algorithms, not applicable here.

  • (d) O(n^2): Implies quadratic complexity which is incorrect for this task.

Q4: Implementing Queue with Stacks

• Task: Implement a queue using two instances of a stack.

• Analysis:

  • You can implement the queue (q) using two stacks (s1 and s2) to manage the elements effectively.

  • Methods to implement the operations:

    1. By making enQueue operation costly:

    • Ensure the oldest entered element is at the top of s1, making it available for dequeuing.

    • Use s2 to manage the order of elements when adding to s1, transferring elements when necessary.

    2. By making deQueue operation costly:

    • Push new elements onto s1.

    • For deQueue operation, transfer elements from s1 to s2 if s2 is empty to retrieve elements in the correct order, preserving their sequence.

• Bonus Question:

  • Provide pseudo or actual code for both enQueue and deQueue operations for the chosen implementation method:

    • enQueue: Push element onto s1.

    • deQueue: If s2 is empty, transfer elements from s1 to s2, then pop from s2.

• Complexities: Mention time and space complexities for both enQueue and deQueue operations to show efficiency.