Data structures worksheet with answers

How are the elements of an array stored in memory?

1. AIn one contiguous block, one after another
2. BIn random locations chosen by a hash
3. CIn a tree of memory pages
4. DScattered, linked by pointers

What is the max-heap property?

1. AEvery left child's key is greater than or equal to its right sibling's key
2. BEvery parent's key is greater than or equal to its children's keys
3. CThe keys are sorted from left to right
4. DAll leaves contain the maximum key

Which operation is O(1) for an array but O(n) for a singly linked list?

1. AAccessing the element at index i
2. BReading the first element
3. CInserting at the head
4. DRemoving the head element

A road network has 100,000 junctions, each connected to about 4 others. Which representation is most suitable?

1. AA single sorted array of vertices
2. BAdjacency matrix
3. CA binary heap of edges
4. DAdjacency list

A binary tree has root 1 with left child 2 and right child 3; node 2 has children 4 (left) and 5 (right). What is the preorder traversal?

1. A1 2 3 4 5
2. B4 5 2 3 1
3. C4 2 5 1 3
4. D1 2 4 5 3

AVL trees and red-black trees guarantee:

1. AConstant-time search in every case
2. BThat no node has two children
3. CO(log n) height through rebalancing
4. DThat keys are stored in insertion order

In the BST with root 50, left subtree 30 (children 20, 40) and right subtree 70 (children 60, 80), the root is deleted using the in-order successor. Which key becomes the new root?

1. A70
2. B80
3. C40
4. D60

A Fenwick tree (binary indexed tree) over an array of n numbers supports which operations in O(log n)?

1. AInserting elements at any position
2. BFinding the median in O(1)
3. CPrefix-sum queries and single-element updates
4. DSorting the array and binary search