B.S.W.E. Bachelor of Software Engineering Algorithms & Data Structures 2 — Questions and Answers
Question 1: What property defines a binary search tree (BST)?
- Every node must have exactly two children
- Left subtree values are smaller and right subtree values are larger than each node (Correct answer)
- A sorted array is stored as a tree structure
- Only leaf nodes contain data values
Correct answer: Left subtree values are smaller and right subtree values are larger than each node
A BST ensures each node's left subtree contains only smaller values and the right subtree contains only larger values, enabling O(log n) average search.
Question 2: What is dynamic programming?
- Programming that modifies itself at runtime
- An optimization technique solving problems by breaking them into overlapping subproblems and caching results (Correct answer)
- A programming paradigm like object-oriented design
- Real-time data stream processing
Correct answer: An optimization technique solving problems by breaking them into overlapping subproblems and caching results
Dynamic programming solves problems by breaking them into overlapping subproblems, storing results (memoization) to avoid redundant computation.
Question 3: What is the time complexity of merge sort in all cases?
- O(n²)
- O(n log n) (Correct answer)
- O(log n)
- O(n)
Correct answer: O(n log n)
Merge sort guarantees O(n log n) in best, average, and worst cases because it always divides the array in half and merges linearly.
Question 4: What distinguishes breadth-first search (BFS) from depth-first search (DFS)?
- BFS visits nodes randomly; DFS visits them sorted
- BFS visits all neighbors at the current level before going deeper; DFS goes as deep as possible first (Correct answer)
- BFS only works on trees; DFS only works on graphs
- BFS uses a stack; DFS uses a queue
Correct answer: BFS visits all neighbors at the current level before going deeper; DFS goes as deep as possible first
BFS explores a graph level by level using a queue, visiting all nodes at depth d before any node at depth d+1.
Question 5: What is a linked list?
- A dynamically resizing array
- A linear data structure where each node contains data and a pointer to the next node (Correct answer)
- A hash table with sorted integer keys
- A tree with exactly one root and one level
Correct answer: A linear data structure where each node contains data and a pointer to the next node
A linked list is a chain of nodes where each node stores data and a reference (pointer) to the next node in the sequence.
Question 6: What does Big O notation describe in algorithm analysis?
- The quality score of production code
- The upper bound of an algorithm's time or space complexity as input size grows (Correct answer)
- The number of known bugs in a codebase
- The required network bandwidth for an application
Correct answer: The upper bound of an algorithm's time or space complexity as input size grows
Big O notation describes the upper bound of an algorithm's growth rate in time or space relative to input size, ignoring constants.
B.S.W.E. Bachelor of Software Engineering Algorithms & Data Structures 2
What property defines a binary search tree (BST)?