1Which of the following defines the worst-case time complexity of an algorithm?
A.Omega Notation
B.Big O Notation
C.Theta Notation
D.Beta Notation
Correct Answer: Big O Notation
Explanation:
Big O notation (O) describes the upper bound of the time complexity, representing the worst-case scenario.
Incorrect! Try again.
2What is the time complexity of accessing an element at a specific index in an array?
A.O(log n)
B.O(n^2)
C.O(n)
D.O(1)
Correct Answer: O(1)
Explanation:
Arrays store elements in contiguous memory locations, allowing constant time access O(1) using the index.
Incorrect! Try again.
3Which notation represents the lower bound of an algorithm's running time?
A.Theta Notation
B.Little o Notation
C.Big O Notation
D.Omega Notation
Correct Answer: Omega Notation
Explanation:
Omega notation (Ω) represents the lower bound, indicating the best-case running time of an algorithm.
Incorrect! Try again.
4In the context of algorithm analysis, what does the Space-Time trade-off imply?
A.Improving time complexity always improves space complexity
B.Reducing time complexity often increases space complexity
C.Algorithms always require equal time and space
D.Time and space complexity are unrelated
Correct Answer: Reducing time complexity often increases space complexity
Explanation:
The Space-Time trade-off suggests that an algorithm can often be made faster by using more memory (space), or can use less memory by running slower.
Incorrect! Try again.
5What is the formula to calculate the memory address of the k-th element in a linear array with base address B and word size W (assuming lower bound is LB)?
A.Address(k) = B + (k - LB) / W
B.Address(k) = W + B * (k - LB)
C.Address(k) = B + W * (k + LB)
D.Address(k) = B + W * (k - LB)
Correct Answer: Address(k) = B + W * (k - LB)
Explanation:
The standard formula for 1D array address calculation is Base Address + Word Size * (Index - Lower Bound).
Incorrect! Try again.
6Which of the following is a linear data structure?
A.Heap
B.Array
C.Graph
D.Tree
Correct Answer: Array
Explanation:
An array is a linear data structure because elements are arranged sequentially in memory.
Incorrect! Try again.
7What is the worst-case time complexity of inserting an element at the beginning of an array of size n?
A.O(n log n)
B.O(n)
C.O(1)
D.O(log n)
Correct Answer: O(n)
Explanation:
Inserting at the beginning requires shifting all existing n elements one position to the right, resulting in O(n) complexity.
Incorrect! Try again.
8Which sorting algorithm works by repeatedly swapping adjacent elements if they are in the wrong order?
A.Bubble Sort
B.Insertion Sort
C.Selection Sort
D.Merge Sort
Correct Answer: Bubble Sort
Explanation:
Bubble Sort works by repeatedly stepping through the list, comparing adjacent elements and swapping them if they are in the wrong order.
Incorrect! Try again.
9What is the worst-case time complexity of Bubble Sort?
A.O(n)
B.O(n log n)
C.O(n^2)
D.O(1)
Correct Answer: O(n^2)
Explanation:
In the worst case (reverse sorted), Bubble Sort requires nested loops iterating n times, leading to O(n^2) complexity.
Incorrect! Try again.
10Which searching algorithm requires the array to be sorted beforehand?
A.Hashing
B.Breadth-First Search
C.Binary Search
D.Linear Search
Correct Answer: Binary Search
Explanation:
Binary Search operates by dividing the search interval in half, which mathematically requires the data to be sorted.
Incorrect! Try again.
11What is the worst-case time complexity of Linear Search?
A.O(n^2)
B.O(1)
C.O(log n)
D.O(n)
Correct Answer: O(n)
Explanation:
In the worst case, the element being searched for is at the last position or not present at all, requiring n comparisons.
Incorrect! Try again.
12What is the best-case time complexity of an optimized Bubble Sort (using a flag)?
A.O(1)
B.O(n)
C.O(n^2)
D.O(log n)
Correct Answer: O(n)
Explanation:
If the array is already sorted, an optimized Bubble Sort with a flag checks one pass (n comparisons) and stops, taking O(n) time.
Incorrect! Try again.
13In Selection Sort, how many swaps are performed in the worst case for an array of size n?
A.O(n)
B.O(n^2)
C.O(log n)
D.O(1)
Correct Answer: O(n)
Explanation:
Selection sort performs exactly one swap per pass (placing the minimum found element). For n elements, it performs O(n) swaps.
Incorrect! Try again.
14Which notation represents the tight bound (both upper and lower) of an algorithm?
A.Little o
B.Omega
C.Theta
D.Big O
Correct Answer: Theta
Explanation:
Theta notation (Θ) bounds a function from above and below, providing a tight bound on the asymptotic behavior.
Incorrect! Try again.
15What is the time complexity of Binary Search?
A.O(log n)
B.O(n^2)
C.O(n)
D.O(1)
Correct Answer: O(log n)
Explanation:
Binary search divides the search space by half in every step, resulting in logarithmic time complexity O(log n).
Incorrect! Try again.
16In Insertion Sort, what is the time complexity when the input array is already sorted?
A.O(n^2)
B.O(n log n)
C.O(1)
D.O(n)
Correct Answer: O(n)
Explanation:
Insertion sort is adaptive; if the array is sorted, the inner while loop condition fails immediately, resulting in O(n) comparisons.
Incorrect! Try again.
17Which operation is NOT efficiently supported by a standard array?
A.Traversal
B.Random Access
C.Updating an element
D.Insertion in the middle
Correct Answer: Insertion in the middle
Explanation:
Insertion in the middle requires shifting elements to create space, making it an O(n) operation, which is inefficient compared to O(1) access.
Incorrect! Try again.
18What is the space complexity of Bubble Sort?
A.O(log n)
B.O(1)
C.O(n)
D.O(n^2)
Correct Answer: O(1)
Explanation:
Bubble Sort is an in-place sorting algorithm requiring only a constant amount of extra auxiliary space.
Incorrect! Try again.
19How is the middle element calculated in Binary Search to avoid integer overflow?
A.mid = low + high
B.mid = low + (high - low) / 2
C.mid = (high - low) / 2
D.mid = (low + high) / 2
Correct Answer: mid = low + (high - low) / 2
Explanation:
The formula 'low + (high - low) / 2' is mathematically equivalent to average but prevents overflow if low + high exceeds the maximum integer limit.
Incorrect! Try again.
20Which sorting algorithm is considered 'stable' among the following?
A.Heap Sort
B.Bubble Sort
C.Selection Sort
D.Quick Sort
Correct Answer: Bubble Sort
Explanation:
Bubble Sort is stable because it does not swap elements of equal value, preserving their original relative order.
Incorrect! Try again.
21What is the worst-case complexity of Selection Sort?
A.O(n!)
B.O(n^2)
C.O(n log n)
D.O(n)
Correct Answer: O(n^2)
Explanation:
Selection Sort involves two nested loops regardless of the data order, resulting in O(n^2) comparisons in all cases.
Incorrect! Try again.
22Which of the following describes an algorithm that runs in constant time?
A.O(1)
B.O(n^2)
C.O(n)
D.O(log n)
Correct Answer: O(1)
Explanation:
O(1) denotes constant time complexity, meaning the execution time does not depend on the input size.
Incorrect! Try again.
23Which sorting technique acts like sorting a hand of playing cards?
A.Bubble Sort
B.Merge Sort
C.Selection Sort
D.Insertion Sort
Correct Answer: Insertion Sort
Explanation:
Insertion sort works by taking one element at a time and inserting it into its correct position among the already sorted elements, similar to arranging cards.
Incorrect! Try again.
24What is the complexity of merging two sorted arrays of size M and N?
A.O(M + N)
B.O(1)
C.O(log(M + N))
D.O(M * N)
Correct Answer: O(M + N)
Explanation:
Merging two sorted arrays involves traversing both arrays once, resulting in a linear time complexity relative to the sum of their sizes.
Incorrect! Try again.
25Traversing an array means:
A.Deleting an element
B.Searching for an element
C.Accessing each element exactly once
D.Sorting the array
Correct Answer: Accessing each element exactly once
Explanation:
Traversal involves visiting every element in the data structure exactly once to perform a specific operation (like printing).
Incorrect! Try again.
26In row-major order, elements of a 2D array are stored:
A.Row by row
B.Randomly
C.Diagonally
D.Column by column
Correct Answer: Row by row
Explanation:
Row-major order stores consecutive elements of a row next to each other in memory.
Incorrect! Try again.
27The minimum number of comparisons required to find the minimum and maximum element in an array of size n is:
A.n
B.1.5n
C.2n
D.n^2
Correct Answer: 1.5n
Explanation:
By comparing elements in pairs, one can find min and max with approximately 3n/2 (1.5n) comparisons, which is more efficient than 2n - 2.
Incorrect! Try again.
28Linear search is highly inefficient for:
A.Large arrays
B.Unsorted arrays
C.Small arrays
D.Linked Lists
Correct Answer: Large arrays
Explanation:
For very large arrays, the O(n) complexity of linear search makes it significantly slower than O(log n) binary search.
Incorrect! Try again.
29What does 'n' usually represent in complexity analysis?
A.Number of variables
B.Input size
C.Number of iterations
D.CPU speed
Correct Answer: Input size
Explanation:
In asymptotic analysis, 'n' typically represents the size of the input data (e.g., number of elements in an array).
Incorrect! Try again.
30If an algorithm has a time complexity of O(n^2), doubling the input size increases the time by:
A.It remains same
B.8 times
C.4 times
D.2 times
Correct Answer: 4 times
Explanation:
Since (2n)^2 = 4n^2, doubling the input size quadruples the running time for a quadratic algorithm.
Incorrect! Try again.
31Which algorithm is generally preferred for small datasets due to low overhead?
A.Insertion Sort
B.Heap Sort
C.Quick Sort
D.Merge Sort
Correct Answer: Insertion Sort
Explanation:
Insertion Sort has a small constant factor and low overhead, making it faster than O(n log n) algorithms for very small n.
Incorrect! Try again.
32The operation of processing each element in the list is known as:
A.Merging
B.Inserting
C.Traversal
D.Sorting
Correct Answer: Traversal
Explanation:
Traversal is the specific term for visiting and processing every node or element in a data structure.
Incorrect! Try again.
33What is the output of a Binary Search if the element is not found?
A.The array size
B.The last element
C.A failure indicator (e.g., -1)
D.The middle index
Correct Answer: A failure indicator (e.g., -1)
Explanation:
Standard searching algorithms return a specific value like -1 or NULL to indicate that the target key was not present in the dataset.
Incorrect! Try again.
34Selection sort is NOT an adaptive sorting algorithm. What does this mean?
A.Its time complexity depends on the initial order of elements
B.It uses extra space
C.Its time complexity is the same regardless of initial order
D.It cannot handle duplicates
Correct Answer: Its time complexity is the same regardless of initial order
Explanation:
Non-adaptive means the algorithm performs the same amount of work (O(n^2) comparisons) even if the array is already sorted.
Incorrect! Try again.
35Which of the following is an application of Binary Search?
A.Sorting an array
B.Printing all elements
C.Finding a path in a maze
D.Debugging code (bisecting)
Correct Answer: Debugging code (bisecting)
Explanation:
Binary search logic is used in debugging to isolate the section of code causing an error (bisection method).
Incorrect! Try again.
36What is the maximum number of comparisons in a Binary Search for an array of size 32?
A.32
B.6
C.5
D.16
Correct Answer: 6
Explanation:
The max comparisons are floor(log2(32)) + 1 = 5 + 1 = 6 (or simply log2(32) comparisons to reach size 1, plus check).
Incorrect! Try again.
37In an array A[1...N], the index of the first element is:
A.0
B.N
C.1
D.-1
Correct Answer: 1
Explanation:
The notation A[1...N] explicitly specifies a 1-based indexing system.
Incorrect! Try again.
38Deleting an element from the end of a linear array takes:
A.O(n)
B.O(log n)
C.O(1)
D.O(n^2)
Correct Answer: O(1)
Explanation:
Deletion at the end simply involves reducing the size counter of the array, requiring no shifting of elements.
Incorrect! Try again.
39Which case typically determines the Big O complexity of an algorithm?
A.Null Case
B.Average Case
C.Best Case
D.Worst Case
Correct Answer: Worst Case
Explanation:
Big O provides the upper bound guarantee, so it is defined by the worst-case scenario.
Incorrect! Try again.
40Which data structure is static in nature?
A.Array
B.Stack (Dynamic)
C.Linked List
D.Queue (Dynamic)
Correct Answer: Array
Explanation:
Standard arrays have a fixed size defined at compile-time or allocation-time and cannot grow or shrink dynamically.
Incorrect! Try again.
41In Bubble Sort, after the first pass, which element is guaranteed to be in its correct position?
A.The largest element
B.No element
C.The middle element
D.The smallest element
Correct Answer: The largest element
Explanation:
Bubble sort pushes the largest element to the end of the array in the first pass (assuming ascending sort).
Incorrect! Try again.
42How many passes are required to sort an array of size n using Insertion Sort in the worst case?
A.n-1
B.n+1
C.n
D.n/2
Correct Answer: n-1
Explanation:
Insertion sort starts from the second element (index 1) and iterates to the end, requiring n-1 passes.
Incorrect! Try again.
43What is the average case time complexity of Linear Search?
A.O(n/2) which is O(n)
B.O(log n)
C.O(1)
D.O(n^2)
Correct Answer: O(n/2) which is O(n)
Explanation:
On average, the element might be in the middle, requiring n/2 comparisons. Constants are dropped in Big O, so it is O(n).
Incorrect! Try again.
44Space complexity refers to:
A.The time taken to compile
B.The amount of RAM used during execution
C.The amount of hard disk space used
D.The number of lines of code
Correct Answer: The amount of RAM used during execution
Explanation:
Space complexity measures the amount of working storage (memory) an algorithm needs to run.
Incorrect! Try again.
45Which of the following algorithms is In-Place?
A.Radix Sort
B.Merge Sort (standard)
C.Counting Sort
D.Insertion Sort
Correct Answer: Insertion Sort
Explanation:
Insertion sort rearranges elements within the array itself without needing significant auxiliary storage.
Incorrect! Try again.
46For a sorted array, which operation is slower in a Linear Search compared to Binary Search?
A.None
B.Finding a random element
C.Finding the first element
D.Traversing
Correct Answer: Finding a random element
Explanation:
Finding a specific random element in a sorted array takes O(n) in Linear Search but O(log n) in Binary Search.
Incorrect! Try again.
47If Base address is 1000, W=2, and Index=5 (0-based indexing), what is the address?
A.1010
B.1012
C.1008
D.1005
Correct Answer: 1010
Explanation:
Address = Base + (Index W) = 1000 + (5 2) = 1010.
Incorrect! Try again.
48Which loop structure primarily characterizes an O(n^2) complexity?
A.Two separate for loops
B.A recursive function dividing input by 2
C.Two nested for loops
D.A single for loop
Correct Answer: Two nested for loops
Explanation:
Nested loops, where the inner loop runs 'n' times for each of the 'n' iterations of the outer loop, result in n * n operations.
Incorrect! Try again.
49In Selection Sort, the minimum element is swapped with:
A.The adjacent element
B.The last element
C.The element at the beginning of the unsorted subarray
D.The middle element
Correct Answer: The element at the beginning of the unsorted subarray
Explanation:
Selection sort finds the minimum in the unsorted portion and places it at the end of the sorted portion (beginning of unsorted).
Incorrect! Try again.
50A recursive algorithm's space complexity depends largely on:
A.The loop counter
B.The recursion stack depth
C.The size of the array
D.The number of variables
Correct Answer: The recursion stack depth
Explanation:
Each recursive call adds a frame to the call stack. The maximum depth of this stack determines the auxiliary space complexity.
Incorrect! Try again.
Did this save you a night before the exam?
LPU Notes is free, and it stays free. Ads cover part of the server bill.
The rest comes out of a student's own pocket: the domain, the storage,
and keeping the site up through the weeks everyone needs it at once.
The payment button didn't load. An ad blocker or a filtered network is the usual reason.
to try again.
Nothing here is ever locked, and nothing unlocks. Chip in only if it was worth it.
What it pays for →