StudyFox
कीमतेंब्लॉगएक्सटेंशनमुफ़्त टूल
  • कीमतें
  • ब्लॉग
  • एक्सटेंशन
  • मुफ़्त टूल
  • शुरू करेंसाइन इन
StudyFox

अपने नोट्स, PDF और स्लाइड्स को फ़्लैशकार्ड, क्विज़, नोट्स और माइंड मैप में बदलें।

StudyFox खोलें

स्टडी टूल्स

  • होमवर्क हेल्पर
  • नोट मेकर
  • फ़्लैशकार्ड मेकर
  • क्विज़ मेकर
  • माइंड मैप मेकर

प्रोडक्ट

  • कीमतें
  • Chrome एक्सटेंशन
  • मुफ़्त एक्सटेंशन
  • स्टडी सेट देखें
  • ब्लॉग

सहायता

  • सहायता केंद्र
  • संपर्क करें
  • गोपनीयता नीति
  • सेवा की शर्तें

तुलना करें

  • Chegg का विकल्प
  • Course Hero का विकल्प
  • Coursology का विकल्प
  • Photomath का विकल्प
  • Gauthmath का विकल्प
  • PhotoSolve का विकल्प
  • CollegeTools का विकल्प
  • Transcript का विकल्प
  • SmartSolve का विकल्प
  • Homeworkify का विकल्प
  • AnswersAi का विकल्प
  • StudyX का विकल्प
  • Quizlet का विकल्प
  • Anki का विकल्प
  • Knowt का विकल्प
  • Brainscape का विकल्प
  • सभी तुलनाएँ

© 2026 StudyFox AI. सर्वाधिकार सुरक्षित।

  • X
  • Discord
  • Instagram
ExploreEngineering & TechComputer ScienceData Structures Quiz: Applied Design and Complexity (Hard)

Quiz · Hard

Data Structures Quiz: Applied Design and Complexity (Hard)

Multi-step questions on heap operations, AVL rotations, hash table behavior, LRU caches and choosing the right structure.

by Kill h.18 questionsCreated Nov 20, 2026, 08:26 PM
Computer Science· Data StructuresTags#data-structures#design#complexity#quiz

18 questions

  1. 1

    You maintain a stream of numbers and must report the 3rd largest after each insertion. Which approach has the best time per insertion?

    • A

      Keep a sorted array and insert each number

    • B

      Keep a max-heap of all numbers and pop 3 each time

    • Keep a min-heap of size 3

    • D

      Store everything in a hash set

    A min-heap of size 3 holds the three largest; its root is the 3rd largest. Each update costs O(log 3) = O(1). A sorted array insert is O(n); popping 3 from a max-heap each time and pushing back is O(log n) but with more work and no benefit.

  2. 2

    Building a binary heap from an unsorted array of n elements using bottom-up heapify takes:

    • O(n)

    • B

      O(log n)

    • C

      O(n log n)

    • D

      O(n²)

    Most nodes sit near the leaves and sift down only a few levels; the sum of the work is O(n). Inserting n items one at a time is O(n log n).

  3. 3

    A hash table with chaining and a poor hash function sends every key to the same bucket. What is the lookup cost for n keys?

    • A

      O(1)

    • B

      O(log n)

    • C

      O(n²)

    • O(n)

    All keys form one chain, so lookup scans the list. Some implementations convert long chains to balanced trees to get O(log n), but classic chaining is O(n).

  4. 4

    A hash table using open addressing with linear probing is 90% full. What is the main performance problem?

    • A

      Hash values become non-uniform

    • Long probe sequences caused by clustering

    • C

      The table cannot store new keys until it is rehashed

    • D

      Lookups become O(1) worst case

    As the load factor approaches 1, runs of occupied slots grow and probes lengthen quickly. Tables are resized well before they are full. The table can still store keys until it is completely full.

  5. 5

    An LRU cache must support get and put in O(1). Which design works?

    • A

      A queue only

    • B

      A min-heap keyed by timestamp

    • A hash map plus a doubly linked list

    • D

      A sorted array

    The map finds a node in O(1); the doubly linked list lets you unlink the node and move it to the front, or drop the tail, in O(1). A heap would cost O(log n) per update.

  6. 6

    The recurrence for the worst-case height of an AVL tree with n nodes gives which bound?

    • Θ(log n)

    • B

      Θ(n)

    • C

      Θ(√n)

    • D

      Θ(n log n)

    The minimum number of nodes in an AVL tree of height h grows like a Fibonacci number, so h is at most about 1.44 log₂ n. That is still O(log n).

  7. 7

    Which sequence of insertions into an empty AVL tree triggers a single left rotation at the root?

    • A

      30, 20, 10

    • B

      20, 10, 30

    • C

      10, 30, 20

    • 10, 20, 30

    Inserting 10, 20, 30 builds a right-leaning chain (Right Right case), fixed by one left rotation, giving 20 as root. 30, 20, 10 is the mirror (right rotation). 10, 30, 20 is a Right Left case needing a double rotation.

  8. 8

    In a max-heap stored in a 1-indexed array, the element at index 12 has children at which indices?

    • A

      13 and 14

    • 24 and 25

    • C

      6 and 7

    • D

      23 and 24

    With 1-indexing, children of i are 2i and 2i + 1: 24 and 25. Index 6 is the parent of index 12, not a child.

  9. 9

    The max-heap in the figure is stored as the array [100, 19, 36, 17, 3, 25, 1, 2, 7]. After extract-max, which array results? (Move the last element to the root, then sift down.)

    • A

      [19, 36, 25, 17, 3, 7, 1, 2]

    • B

      [36, 19, 25, 17, 3, 1, 7, 2]

    • [36, 19, 25, 17, 3, 7, 1, 2]

    • D

      [7, 19, 36, 17, 3, 25, 1, 2]

    Move 7 to the root: [7, 19, 36, 17, 3, 25, 1, 2]. Sift down: the larger child of 7 is 36, swap → [36, 19, 7, ...]. Now 7 at index 2 has children 25 and 1: swap with 25 → [36, 19, 25, 17, 3, 7, 1, 2]. Image: Ermishin, CC BY-SA 3.0, via Wikimedia Commons.

  10. 10

    Which statement about Union-Find with path compression and union by rank is correct?

    • Operations take O(α(n)) amortized, nearly constant

    • B

      Find is O(n) in the worst case, always

    • C

      It supports deleting elements in O(1)

    • D

      It stores edges as an adjacency matrix

    With both optimizations the amortized cost per operation is the inverse Ackermann function, below 5 for any practical n. It does not support deleting elements from a set efficiently.

  11. 11

    A queue is implemented with a singly linked list that keeps only a head pointer. Enqueue at the tail and dequeue at the head. What are the costs?

    • A

      Enqueue O(1), dequeue O(1)

    • B

      Enqueue O(1), dequeue O(n)

    • C

      Both O(n)

    • Enqueue O(n), dequeue O(1)

    Without a tail pointer, reaching the tail requires walking the list: O(n). Keeping a tail pointer makes both operations O(1). Dequeue at the head is always O(1).

  12. 12

    Which structure supports insert, delete and finding the predecessor of a key in O(log n) worst case?

    • A

      Hash table

    • Balanced BST

    • C

      Unsorted array

    • D

      Stack

    A balanced BST keeps keys ordered, so the predecessor is a tree walk. A hash table has no ordering, and arrays cost O(n) for inserts or scans.

  13. 13

    A graph has 6 vertices and is a tree. How many edges does it have?

    • A

      6

    • B

      7

    • 5

    • D

      15

    A tree on n vertices has exactly n − 1 edges: 5. A complete graph on 6 vertices has 15 edges.

  14. 14

    Why does a breadth-first search mark vertices as visited when they are added to the queue rather than when they are removed?

    • Otherwise a vertex can be enqueued several times

    • B

      To save memory

    • C

      Because BFS needs a stack

    • D

      To find cycles

    If marking waits until dequeue, a vertex reachable from several frontier nodes enters the queue multiple times, wasting work and in dense graphs inflating the queue. Marking on enqueue keeps each vertex in the queue at most once.

  15. 15

    What does the red-black tree rule 'every path from a node to its NIL leaves has the same number of black nodes' guarantee?

    • A

      The tree is perfectly balanced

    • B

      All leaves are black

    • C

      The tree has no red nodes below the root

    • The longest path is at most twice the shortest

    Because red nodes cannot be adjacent, a path can at most alternate black and red, so no path is more than twice as long as another. The tree is not perfectly balanced. Image: Cburnett, CC BY-SA 3.0, via Wikimedia Commons.

  16. 16

    You must check whether a very large set of URLs has been crawled, accepting a small chance of falsely saying 'seen' but never falsely saying 'not seen'. Which structure fits?

    • A

      Stack

    • Bloom filter

    • C

      Min-heap

    • D

      Doubly linked list

    A Bloom filter uses bit arrays and several hash functions: no false negatives, tunable false positives, tiny memory. The others do not give set membership.

  17. 17

    Given h(k) = k mod 7 and linear probing, keys 15, 22 and 8 are inserted in that order into an empty table. In which slot does 8 end up?

    • A

      1

    • B

      2

    • 3

    • D

      4

    All three hash to slot 1. 15 takes slot 1, 22 probes to slot 2, 8 probes 1, 2, then settles at slot 3.

  18. 18

    In which situation is an adjacency matrix a better choice than an adjacency list?

    • A dense graph where you test for edges between arbitrary pairs often

    • B

      A sparse graph with millions of vertices

    • C

      A graph that must be traversed with DFS only

    • D

      A tree with n − 1 edges

    The matrix answers 'is there an edge (u, v)?' in O(1) and its V² memory is justified when E is close to V². For sparse graphs it wastes memory.