Unit 1: Introduction, Arrays, Sorting and Searching - Practice Quiz

1 What is an algorithm?

2 What does complexity analysis primarily measure?

3 What does a time-space trade-off mean?

4 What does Omega notation describe for an algorithm?

5 What does Theta notation represent?

6 Which notation is commonly used to express an asymptotic upper bound?

7 Which of the following is a linear data structure?

8 How are elements organized in a linear array?

9 How are the elements of a standard one-dimensional array usually stored in memory?

10 What is array traversal?

11 When an element is inserted at the beginning of an array, what may need to happen?

12 When an array element is deleted from the middle, what commonly fills the empty position?

13 What is the purpose of sorting an array?

14 What is the main goal of searching an array?

15 What does merging two arrays produce?

16 What is the typical time complexity of accessing an array element by its index?

17 What does bubble sort repeatedly compare?

18 How does insertion sort build the sorted portion of an array?

19 In ascending selection sort, which element is usually selected during each pass?

20 Which statement correctly distinguishes binary search from linear search?

21 A list ADT specifies operations such as insertion, deletion, and retrieval but does not specify how elements are stored. Which statement best describes this distinction?

22 What is the time complexity of the following code?

for i = 1 to n:
for j = 1 to i:
process(A[j])

23 An application repeatedly tests whether values occur in a fixed array. Which approach uses extra space to reduce the average lookup time?

24 If , which option gives the tightest asymptotic lower bound listed?

25 An algorithm performs exactly primitive operations for sufficiently large . What is its tight asymptotic complexity?

26 For , which option is the tightest Big O bound listed?

27 A linear array has a lower index bound of and an upper index bound of . How many elements can it store?

28 An integer array begins at address , each element occupies bytes, and indexing starts at . What is the address of ?

29 An algorithm visits each element of an array of size once and performs constant-time work per element. If the array size doubles, what happens asymptotically to the running time?

30 A linear array currently contains elements at indices through . To insert a new value at index while preserving order, how many existing elements must be shifted?

31 An array contains elements at indices through . If the element at index is deleted while preserving order, how many elements must be shifted left?

32 A sorting method must preserve the original relative order of records having equal keys. Which property is required?

33 A fixed unsorted array of elements will receive many search queries. Which strategy has the better asymptotic total time when the number of queries is large?

34 Two sorted arrays contain and elements. Using the standard two-pointer merge, what is the maximum number of element comparisons needed?

35 A dynamic array doubles its capacity whenever it becomes full. What are the amortized and worst-case time complexities of appending one element?

36 Using ascending bubble sort, what is the array after one complete left-to-right pass over ?

37 How many element shifts does insertion sort perform when sorting in ascending order?

38 What is the array after the first two passes of ascending selection sort on ?

39 A successful linear search is performed on an array of elements. If the target is equally likely to be at any position, what is the expected number of comparisons?

40 Binary search uses on a sorted array indexed from to . How many comparisons are made when searching for the value at index ?

41 An algorithm has best-case time and worst-case time . Its average-case time is under one particular input distribution. Which conclusion is guaranteed independently of the input distribution?

42 What is the tight asymptotic running time of the following loop nest, assuming the innermost body takes constant time?

for i = 1 to n

for j = 1 to i

for k = 1; k <= j; k = 2*k

constant-time operation

43 A static set contains distinct keys from a universe of size . Implementation D uses a direct-address table, while implementation S uses a sorted array. Ignoring the storage of the keys themselves, which comparison correctly describes their worst-case membership queries and auxiliary space?

44 Define when is a power of two and otherwise. Which is the strongest asymptotic lower bound among the following choices that holds for every sufficiently large integer ?

45 For powers of two, let and . What is the tight asymptotic solution?

46 Let for . Which option is the tightest valid Big O bound listed?

47 A circular queue is implemented in an array of capacity , reserving one empty cell. front points to the first element and rear to the next insertion cell. Initially, front = 6 and rear = 2. After three dequeues followed by four enqueues, what are the final indices and number of stored elements, assuming no operation fails?

48 A two-dimensional array is stored in row-major order. Each element occupies bytes, and the address of is . What is the address of ?

49 A row-major integer array is traversed once. A cache line holds consecutive integers. The cache is initially empty, fully associative, uses LRU, and holds lines. Ignoring all other memory traffic, how many cache misses occur for row-wise and column-wise traversal, respectively?

50 An array initially contains elements. Exactly elements are then inserted one at a time at index , with all existing elements shifted right for each insertion. How many element shifts are performed in total?

51 A contiguous array initially has elements. The first element is deleted times in succession, where , and each deletion shifts every remaining element left. What is the total number of shifts?

52 The array contains each integer from to exactly once. What is the minimum number of arbitrary element swaps required to sort it?

53 A sorted array of length may contain duplicates. An algorithm must return every index whose value equals . If there are matches, what is the optimal worst-case running time in the comparison model?

54 Two sorted arrays of lengths and are merged using the standard two-pointer algorithm. What are the minimum and maximum possible numbers of key comparisons?

55 A dynamic array starts with capacity and doubles whenever an append finds it full. Appending writes the new element once, and resizing copies every existing element once. If exactly elements are appended, how many total element writes, including copies, occur?

56 Standard left-to-right bubble sort uses a shrinking unsorted boundary and stops early after a pass with no swaps. On the input , how many key comparisons and swaps are performed?

57 Insertion sort is run on for . Counting only comparisons between the key and an array element, how many such comparisons and element shifts occur?

58 Selection sort repeatedly finds the minimum of the unsorted suffix and swaps only when that minimum is not already in position. On a reverse-sorted array of distinct elements, how many key comparisons and swaps occur?

59 A linear search examines an array of length . The search is successful with probability , and conditional on success, the target position is uniformly distributed among the indices. What is the expected number of key comparisons?

60 Consider lower-bound binary search on a sorted array using the half-open interval [low, high). It updates low = mid + 1 when A[mid] < x; otherwise it updates high = mid. Which invariant is sufficient to prove that the final low is the first index whose value is at least ?