AMCAT Basic Data Structures 2 ā Questions and Answers
Question 1: Which operation on a singly linked list has O(n) time complexity in the worst case?
- Inserting at the head
- Deleting the head node
- Accessing an element by index (Correct answer)
- Checking if the list is empty
Correct answer: Accessing an element by index
Accessing by index requires traversing from the head, taking O(n) time in the worst case.
Question 2: What is the maximum number of elements that can be stored in a 2D array declared as int a[4][5]?
- 9
- 20 (Correct answer)
- 25
- 16
Correct answer: 20
A 2D array of dimensions 4Ć5 holds 4*5 = 20 elements.
Question 3: In a doubly linked list, each node contains:
- Only data and one pointer
- Data and two pointers (next and previous) (Correct answer)
- Only two pointers
- Data and a key-value pair
Correct answer: Data and two pointers (next and previous)
Each node in a doubly linked list stores data plus pointers to both the next and previous nodes.
Question 4: Which data structure uses a LIFO (Last In, First Out) access pattern?
- Queue
- Stack (Correct answer)
- Deque
- Priority Queue
Correct answer: Stack
A stack follows LIFO ā the last element pushed is the first one popped.
Question 5: What is the time complexity for inserting an element at the beginning of a dynamic array (ArrayList)?
- O(1)
- O(log n)
- O(n) (Correct answer)
- O(nĀ²)
Correct answer: O(n)
Inserting at the beginning requires shifting all existing elements one position to the right, which is O(n).
Question 6: Which of the following is NOT a linear data structure?
- Array
- Linked List
- Queue
- Binary Tree (Correct answer)
Correct answer: Binary Tree
A binary tree is a hierarchical (non-linear) structure, unlike arrays, linked lists, and queues.
Question 7: In a circular linked list, the last node's next pointer points to:
- NULL
- Itself
- The head node (Correct answer)
- The second node
Correct answer: The head node
In a circular linked list, the last node's next pointer wraps back to the head, forming a circle.
AMCAT Basic Data Structures 2
Which operation on a singly linked list has O(n) time complexity in the worst case?