English
Menu

Data Structures and Algorithms

Learn data structures and algorithms with multiple-choice questions: time complexity and Big-O notation, arrays and linked lists, stacks and queues, hash tables, binary search, how sorting algorithms work and their stability, binary search trees and heaps, graph search and shortest paths, and recursion, dynamic programming and greedy algorithms, including how they relate to caches and GPUs.

Practice 10 questionsRandom questions from this topic · about 5 minutes Practice this topicAll questions in this topic, in random order Weak questionsRetry only the questions you last got wrong

Pseudocode Runner and Tracer →

Sorting algorithm visualizer →

Dijkstra's algorithm calculator →

Binary search tree and heap visualizer →

Hash table calculator →

Time complexity (Big-O) comparison tool →

Reverse Polish notation converter →

Data Structures and Algorithms: key points

Programs that solve the same problem can differ in speed by orders of magnitude as the data grows, depending on the data structures and algorithms they use. Estimating how the work grows with time complexity and choosing structures that fit how the data is used are the starting points for fast programs.

This topic covers basic data structures such as arrays and linked lists, stacks and queues, hash tables, binary search trees and heaps, and graph representations, along with binary search; sorting algorithms such as bubble, selection, insertion, merge, quick and heap sort; breadth-first search, depth-first search and Dijkstra's algorithm; and recursion, dynamic programming and greedy algorithms, mainly through calculation questions that trace each step. It also helps with the algorithms section of IT certification exams such as Japan's Fundamental and Applied Information Technology Engineer Examinations. In addition, it covers the link to hardware performance, such as cache-friendly data layouts and parallel sorting on GPUs.

All Data Structures and Algorithms questions (40)
  1. For an array of n elements, what is the time complexity of comparing every pair of distinct elements exactly once (a double loop that compares element i with every element after it, advancing i one step at a time)?
  2. A program with O(n²) time complexity takes 0.5 seconds for 1,000 data items. About how long will it take for 4,000 items?
  3. A linear search compares the elements of an array of 100 distinct values one by one from the front to find a target. If the target is always in the array and is equally likely to be at any position, what is the average number of comparisons?
  4. Compared with an array, which is a correct description of a linked list (a list in which each element holds a pointer to the next element)?
  5. On an empty stack, the operations push 1, push 2, pop, push 3, push 4, pop, pop are performed in this order. In what order are the values removed by pop?
  6. Elements A, B and C are added to an empty queue in this order. Then one element is removed, D is added and one is removed, and E is added and one is removed. In what order are the elements removed?
  7. The expression “3 4 + 2 * 5 −” in reverse Polish notation (postfix notation) is evaluated by pushing each number onto a stack and, for each operator, popping two values, computing the result and pushing it back. What is the result? The left operand of an operator is the value that was pushed earlier.
  8. Which is the correct description of a collision in a hash table?
  9. Keys 10, 17, 24 and 3 are stored in this order in a hash table of size 7 (positions 0 to 6) with the hash function h(k) = k mod 7. Collisions are resolved by linear probing, which moves forward one position at a time (wrapping from 6 to 0) to find a free slot. At which position is key 3 stored?
  10. Which correctly compares chaining (linking the elements at the same position into a linked list) and open addressing (finding another free position within the table) as ways to resolve hash table collisions? The load factor is the number of stored elements divided by the table size.
  11. Which is a prerequisite for using binary search, which compares the target with the middle element and halves the search range each time?
  12. A binary search is performed on 1,000 distinct values sorted in ascending order. If one comparison tells you whether the values are equal, smaller or larger, what is the maximum number of comparisons, counting both successful and unsuccessful searches?
  13. A binary search looks for 38 in the ascending array a[0] to a[9] = 3, 8, 12, 17, 23, 31, 38, 45, 52, 60. The search range starts with lo = 0 and hi = 9, and the middle position is (lo + hi) ÷ 2 rounded down. Which lists, in order, the elements compared with 38?
  14. The array 5, 3, 8, 1, 4 is sorted in ascending order with bubble sort. What is the array after one pass, in which neighboring elements are compared from the front to the end and swapped whenever the left one is larger?
  15. The array 29, 10, 14, 37, 13 is sorted in ascending order with selection sort, which finds the minimum of the unsorted part and swaps it with the first element of the unsorted part. What is the array after this step has been done twice?
  16. An array of 10 elements is sorted in ascending order with insertion sort. Each element from the second one on is taken out and compared with the elements to its left, starting with its left neighbor, until an element less than or equal to it is found or the front is reached. How many comparisons are made when the array is already in ascending order, and when it is in descending order?
  17. Which sorting algorithm is O(n log n) even in the worst case and sorts with almost no extra memory such as a work array?
  18. The (name, score) records (A, 80), (B, 70), (C, 80), (D, 70) are in this order. If they are sorted by score in ascending order with a stable sort, in what order do the names appear?
  19. Which is a typical case in which quicksort takes O(n²) time?
  20. In merge sort, the two sorted runs 1, 4, 7, 9 and 2, 3, 8, 10 are merged into one by repeatedly comparing their front elements and outputting the smaller. When one run is empty, the rest of the other is output without comparisons. How many comparisons are made?
  21. A binary heap is stored in an array a[0], a[1], a[2], … with the root at a[0], filling each level from left to right starting at the top. Which are the children and the parent of a[4]?
  22. A max-heap, in which each parent's value is at least as large as its children's, is stored in an array with the root at a[0]. 45 is added to the heap 50, 30, 40, 10, 20, 35 by placing it at the end and then swapping it with its parent as long as it is larger than the parent. What is the resulting array?
  23. When a binary search tree is traversed in in-order (visiting the left subtree, then the node, then the right subtree), how are the values of the visited nodes ordered? Assume all values are distinct.
  24. The values 50, 30, 70, 20, 40, 60, 80 are inserted in this order into an empty binary search tree. In what order are the nodes visited when the tree is traversed in post-order (left subtree, right subtree, then the node)?
  25. The values 1, 2, 3, …, 1000 are inserted in this order into an empty binary search tree (no rebalancing is done). When searching this tree for 1000, how many nodes are compared, starting from the root, before it is found?
  26. What is the main reason that B-trees (including B+ trees), rather than binary search trees, are widely used for indexes in databases and file systems?
  27. Which is an appropriate way to store in memory a sparse graph, one with few edges compared with its number of vertices, such as a road network with about 1 million vertices and 3 million edges?
  28. In a graph whose edges have no weights, you want to find the smallest number of edges from a starting vertex to every other vertex. Which pair of search method and data structure is suitable?
  29. In an undirected graph, the neighbors of each vertex are A: B, C / B: A, D, E / C: A, F / D: B / E: B, F / F: C, E. A recursive depth-first search starts from vertex A. The neighbors are examined in the order listed, and as soon as an unvisited vertex is found, the search moves to it. In what order are the vertices visited?
  30. In an undirected graph, the edge weights (distances) are S−A: 4, S−B: 1, A−B: 2, A−C: 1, B−C: 5, C−T: 3 and A−T: 6. Which shows the shortest path from S to T found by Dijkstra's algorithm and its length?
  31. Which condition on the graph is required for Dijkstra's algorithm to find correct shortest paths?
  32. Tasks A to E have the ordering constraints “A before C”, “B before C”, “C before D”, “B before E” and “E before D”. Which order satisfies all the constraints (a result of topological sorting)?
  33. A function f(x, y) is defined as “if y is 0, return x; otherwise return f(y, x mod y)”. When f(84, 36) is called, what is the return value, and how many times is f called, including the first call?
  34. A function fib(n) for Fibonacci numbers is defined recursively as “if n is 1 or less, return n; otherwise return fib(n−1) + fib(n−2)”. When fib(5) is called, how many times is fib called, including the first call?
  35. You pay 8 yen with coins of 1 yen, 4 yen and 6 yen. Which correctly relates the number of coins chosen by a greedy algorithm, which uses as many of the largest coin as possible first, to the minimum number of coins?
  36. A knapsack with capacity 8 is filled with items chosen from four items with (weight, value) of (2, 3), (3, 4), (4, 5) and (5, 6). There is only one of each item and items cannot be split. What is the maximum total value with a total weight of 8 or less?
  37. Which is a characteristic of the Boyer-Moore algorithm for finding a pattern in a string?
  38. A dynamic array, when an element is added while it is full, allocates a new area with twice the capacity and copies all elements into it. If 1,000 elements are added one at a time to an empty array of capacity 1, how many element copies are made in total?
  39. For a hash table with many elements kept at a load factor of about 0.5, which is the most appropriate reason that open addressing with linear probing tends to be faster than chaining (linking elements with linked lists)?
  40. Sorting methods with a fixed sequence of compare-exchange steps (sorting networks), such as bitonic sort, are sometimes used for sorting on parallel hardware such as GPUs. Why?

Books on Data Structures and Algorithms Ad

As an Amazon Associate I earn from qualifying purchases.

Other topics in Computer systems