WorksheetsQR Code Attendance Procedures Quiz
Total questions: 20
Worksheet time: 10mins
Which of the following is an advantage of linked ADTs over their array-based counterparts?
Resizing is not needed
Requires resizing frequently
Consumes more memory compared to a mostly full array
No random access
What is a disadvantage of linked ADTs compared to array-based ADTs?
Consumes more memory compared to a mostly full array
O(1) initialisation
Saves more memory with mostly empty slots
Allows random access
Why might a linked ADT save more memory than an array-based ADT?
Because it saves more memory compared to an array ADT with mostly empty slots
Because it always uses less memory than any array
Because it allows random access
Because it requires resizing
Which of the following statements about random access is true for linked ADTs?
Linked ADTs do not support random access, which is an issue for List ADT but not for Stack & Queues
Linked ADTs support random access for all ADTs
Linked ADTs support random access only for Stack ADT
Linked ADTs support random access only for Queue ADT
A student is designing a data structure for a list that will frequently change in size and may have many empty slots if implemented as an array. Which data structure would be more memory efficient and why?
Linked ADT, because it saves more memory compared to an array ADT with mostly empty slots
Array-based ADT, because it always uses less memory
Array-based ADT, because it allows random access
Linked ADT, because it requires resizing
What is the main difference in the add operation between Separate Chaining and Linear Probing techniques in hash tables?
Separate Chaining uses a binary search tree, while Linear Probing uses a linked list.
Separate Chaining traverses a linked list at the hashed index, while Linear Probing searches for the next empty position linearly.
Separate Chaining uses linear search, while Linear Probing uses binary search.
Separate Chaining and Linear Probing both use the same method to resolve collisions.
What is the time complexity of the add operation for both Separate Chaining and Linear Probing in the worst case?
O(1)
O(hash(k) + n*comp)
O(n2)
O(log n)
Which of the following statements is true regarding the comparison of complexities between Separate Chaining and Linear Probing add operations?
Linear Probing always has better complexity than Separate Chaining.
Separate Chaining always has better complexity than Linear Probing.
Both techniques have the same complexity for the add operation.
Neither technique can be analysed for complexity.
In Separate Chaining, what is the purpose of traversing the linked list at the hashed index during the add operation?
To find the maximum value in the list.
To ensure the input key does not already exist in the list.
To sort the elements in the list.
To delete duplicate elements.
If the hashed index is already occupied in Linear Probing, what is the next step in the add operation?
Rehash the key using a different function.
Traverse the linked list at that index.
Linearly probe to the next empty position.
Discard the new key.
What is the time complexity of the serve() operation in a linked queue in both best and worst cases?
O(1)
O(n)
O(log n)
O(n2)
When the append() method is called on an empty linked queue, what does it do?
It sets self.front and self.rear to be the new node
It removes the front node
It updates self.front to its next element
It sets self.rear to None
Which of the following statements is true about the time complexity of serve() and append() in linked queues?
Both have O(1) time complexity in best and worst cases
Both have O(n) time complexity in best and worst cases
Serve() is O(1), but append() is O(n)
Append() is O(1), but serve() is O(n)
Are the time complexities of serve() and append() in linked queues better than those in default circular queues?
No, they are not better
Yes, they are better
They are significantly worse
They are unpredictable
Why do serve() and append() operations in linked queues have O(1) complexity?
Because they only involve constant time operations to the rear/front pointer
Because they require traversing the entire queue
Because they use recursion
Because they sort the queue
Which of the following statements best describes why the default QuickSort algorithm is considered unstable?
It always maintains the original order of equal elements.
It partitions arrays chaotically, performing swaps without tracking the original order.
It merges subarrays by always considering the right subarray first.
It sorts elements by converting them into tuples.
What makes MergeSort a stable sorting algorithm?
It always swaps elements with equal values.
It merges subarrays by considering the left subarray first if two elements are equal.
It partitions arrays randomly.
It does not maintain the relative order of equal elements.
How can QuickSort be made stable?
By always swapping the largest element first.
By converting the list of elements into a list of tuples (element, index) and comparing by both element and index.
By merging subarrays in reverse order.
By ignoring the original order of elements.
In a scenario where stability is important, which sorting algorithm would be a better choice by default?
QuickSort
MergeSort
Bubble Sort
HeapSort
Suppose you have a list of student records with equal scores. Why would you prefer a stable sorting algorithm in this case?
To ensure the fastest sorting time.
To maintain the original order of students with equal scores.
To use less memory during sorting.
To randomly shuffle the records.
