Free AMCAT Basic Data Structures Questions and Answers 1 — Questions and Answers
Question 1: What is the time complexity to access an element in an array by its index?
- O(n)
- O(1) (Correct answer)
- O(log n)
- O(n^2)
Correct answer: O(1)
Arrays provide direct, random access to elements using their index. The memory location is calculated directly from the base address and the index, which is a constant-time operation regardless of the array's size.
Question 2: Which data structure follows the Last-In, First-Out (LIFO) principle?
- Queue
- Array
- Stack (Correct answer)
- Linked List
Correct answer: Stack
A stack operates like a pile of plates. The last item added (pushed) is the first one to be removed (popped), which defines the LIFO principle.
Question 3: In a standard queue, where are new elements added?
- At the front
- At the rear (Correct answer)
- In the middle
- At any position
Correct answer: At the rear
A queue follows the First-In, First-Out (FIFO) principle. New elements are enqueued at the rear (or tail) and existing elements are dequeued from the front (or head).
Question 4: What is a potential issue with implementing a queue using a simple, fixed-size array?
- Elements can only be integers.
- It is not possible to implement.
- The queue has a fixed size and can become full. (Correct answer)
- Accessing elements is very slow.
Correct answer: The queue has a fixed size and can become full.
When a queue is implemented with a standard array, it has a predefined, fixed capacity. If the number of elements to be enqueued exceeds this capacity, an overflow condition occurs, and no more elements can be added.
Question 5: The operation of removing an element from a stack is called:
- Push
- Enqueue
- Pop (Correct answer)
- Dequeue
Correct answer: Pop
'Push' is the term for adding an element to a stack. 'Pop' is the term for removing the topmost element from the stack, following the LIFO principle.
Question 6: A circular queue is an improvement over a linear queue because it:
- Can store more elements in total.
- Allows faster access to elements.
- Utilizes the empty space in the array more efficiently. (Correct answer)
- Is easier to implement.
Correct answer: Utilizes the empty space in the array more efficiently.
In a linear queue implemented with an array, space at the beginning of the array becomes unusable after elements are dequeued. A circular queue overcomes this by wrapping around, allowing the rear to point to the start of the array if space is available, thus using memory more effectively.
Question 7: If the elements 'A', 'B', 'C', and 'D' are placed in a stack in that order, what will be the order of elements when they are popped?
- A, B, C, D
- A, C, B, D
- D, C, B, A (Correct answer)
- B, C, D, A
Correct answer: D, C, B, A
Due to the LIFO (Last-In, First-Out) nature of a stack, the last element pushed ('D') will be the first one popped. The sequence of popping will be the exact reverse of the pushing sequence.
Free AMCAT Basic Data Structures Questions and Answers 1
What is the time complexity to access an element in an array by its index?