IT IT Data Structures and Algorithms 1 ā Questions and Answers
Question 1: What is the time complexity of searching for an element in a balanced binary search tree (BST)?
- O(n)
- O(log n) (Correct answer)
- O(nĀ²)
- O(1)
Correct answer: O(log n)
A balanced BST halves the search space at each step, yielding O(log n) search time.
Question 2: Which data structure operates on a Last-In, First-Out (LIFO) principle?
- Queue
- Linked List
- Stack (Correct answer)
- Heap
Correct answer: Stack
A stack removes elements in the reverse order they were added, following the LIFO principle.
Question 3: What algorithm technique solves a problem by breaking it into overlapping subproblems and storing their results?
- Greedy Algorithm
- Divide and Conquer
- Dynamic Programming (Correct answer)
- Backtracking
Correct answer: Dynamic Programming
Dynamic programming uses memoization or tabulation to avoid recomputing overlapping subproblems.
Question 4: In a hash table, what is a collision?
- When the table is full
- When two keys map to the same index (Correct answer)
- When a key is deleted
- When the hash function returns null
Correct answer: When two keys map to the same index
A collision occurs when the hash function maps two different keys to the same bucket index.
Question 5: Which sorting algorithm has an average-case time complexity of O(n log n)?
- Bubble Sort
- Insertion Sort
- Selection Sort
- Merge Sort (Correct answer)
Correct answer: Merge Sort
Merge Sort recursively divides and merges arrays, consistently achieving O(n log n) on average.
Question 6: What type of linked list allows traversal in both forward and backward directions?
- Singly Linked List
- Circular Linked List
- Doubly Linked List (Correct answer)
- Skip List
Correct answer: Doubly Linked List
A doubly linked list has both a next and a previous pointer on each node, enabling bidirectional traversal.
IT IT Data Structures and Algorithms 1
What is the time complexity of searching for an element in a balanced binary search tree (BST)?