15 questions · 25 marks · 45 minutes. Negative marking on MCQ only: −1/3 mark for a wrong 1-mark MCQ, −2/3 for a wrong 2-mark MCQ. No negative marking for MSQ or NAT; MSQ has no partial credit.
Q1 · NAT · 1 mark(s) — bfr
B = 2048, R = 100, unspanned. bfr?
Numerical answer: ________
Q2 · NAT · 2 mark(s) — Blocks
r = 50,000, R = 100, B = 2048, spanned. Number of blocks?
Numerical answer: ________
Q3 · NAT · 1 mark(s) — Latency
Disk at 10,000 rpm. Average rotational latency in ms?
Numerical answer: ________
Q4 · NAT · 1 mark(s) — Binary search
A sorted file has 2,500 blocks. Block accesses for binary search on the ordering key?
Numerical answer: ________
Q5 · MCQ · 1 mark(s) — File organisation
A heap file is searched for a non-key value. The number of block accesses is:
- (A) b/2
- (B) b
- (C) 1
- (D) ⌈log₂ b⌉
Q6 · NAT · 2 mark(s) — Primary index
A file with 100,000 records, 20 records per block, sorted on its key. Primary index with bfrᵢ = 100, single level. Block accesses to find a record?
Numerical answer: ________
Q7 · NAT · 2 mark(s) — Secondary index
Same file, secondary index on another key field, bfrᵢ = 100, single level. Block accesses?
Numerical answer: ________
Q8 · NAT · 2 mark(s) — Multilevel
The secondary index above made multilevel (fo = 100). Block accesses?
Numerical answer: ________
Q9 · MCQ · 1 mark(s) — Index types
How many clustering indexes can a file have?
- (A) exactly 2
- (B) 0 or 1
- (C) any number
- (D) one per non-key field
Q10 · NAT · 2 mark(s) — B-tree order
B = 512, K = 8, P = 4, Pr = 6. B-tree order p (max children)?
Numerical answer: ________
Q11 · NAT · 2 mark(s) — B-tree splits
Max 2 keys per node. Insert 1, 2, 3, 4, 5, 6, 7 into an empty B-tree. How many splits?
Numerical answer: ________
Q12 · NAT · 2 mark(s) — B-tree bounds
B-tree of order 5, height 4 levels. Minimum number of keys?
Numerical answer: ________
Q13 · NAT · 2 mark(s) — B+ order
B = 1024, K = 10, P = 6. B+ internal order p?
Numerical answer: ________
Q14 · NAT · 2 mark(s) — B+ capacity
p = 64, p_leaf = 60, height 3. Maximum records?
Numerical answer: ________
Q15 · MCQ · 2 mark(s) — B+ insertion
In a B+ tree, an internal node overflows during an insertion. Its middle key:
- (A) is deleted
- (B) moves up to the parent and is removed from both halves
- (C) is copied up and kept in the node
- (D) moves down to a leaf
✓Answer Vault
Reveal answers when you’re ready
Q1 Answer: 20 · 1 mark(s)
⌊2048/100⌋.
Re-read: Lesson 5.1.1 — Storage basics: disk, blocks, block access cost, records, blocking factor, spanned vs unspanned
Q2 Answer: 2442 · 2 mark(s)
⌈5,000,000 / 2048⌉ = ⌈2441.4⌉.
Re-read: Lesson 5.1.1 — Storage basics: disk, blocks, block access cost, records, blocking factor, spanned vs unspanned
Q3 Answer: 3 · 1 mark(s)
6 ms per rotation, half = 3.
Re-read: Lesson 5.1.1 — Storage basics: disk, blocks, block access cost, records, blocking factor, spanned vs unspanned
Q4 Answer: 12 · 1 mark(s)
2¹² = 4096 ≥ 2500 > 2048.
Re-read: Lesson 5.2.1 — File organization: heap, sorted, hashed; cost of search/insert/delete
Q5 Answer: (B) · 1 mark(s)
All blocks must be read.
- (A) is wrong: Average for an existing key.
- (C) is wrong: Hashing.
- (D) is wrong: Sorted.
Re-read: Lesson 5.2.1 — File organization: heap, sorted, hashed; cost of search/insert/delete
Q6 Answer: 7 · 2 mark(s)
5,000 blocks → 50 index blocks; ⌈log₂ 50⌉ + 1 = 6 + 1.
Re-read: Lesson 5.3.2 — Primary, clustering, secondary indexes; counting index blocks and block accesses
Q7 Answer: 11 · 2 mark(s)
100,000 entries → 1,000 blocks; ⌈log₂ 1000⌉ + 1 = 10 + 1.
Re-read: Lesson 5.3.2 — Primary, clustering, secondary indexes; counting index blocks and block accesses
Q8 Answer: 4 · 2 mark(s)
1000 → 10 → 1: 3 levels + 1.
Re-read: Lesson 5.3.3 — Multilevel indexes; fan-out; logarithm primer
Q9 Answer: (B) · 1 mark(s)
At most one ordering field.
- (A) is wrong: No.
- (C) is wrong: Secondary indexes only.
- (D) is wrong: No.
Re-read: Lesson 5.3.2 — Primary, clustering, secondary indexes; counting index blocks and block accesses
Q10 Answer: 29 · 2 mark(s)
4p + 14(p − 1) ≤ 512 → 18p ≤ 526 → 29.
Re-read: Lesson 5.5.1 — B-tree structure and order (order conventions and the GATE trap)
Q11 Answer: 4 · 2 mark(s)
Same shape as the 10 … 70 trace.
Re-read: Lesson 5.5.2 — B-tree search and insertion with node splits
Q12 Answer: 53 · 2 mark(s)
2·3³ − 1.
Re-read: Lesson 5.5.3 — B-tree deletion basics; min/max keys; height bounds
Q13 Answer: 64 · 2 mark(s)
6p + 10(p − 1) ≤ 1024 → 16p ≤ 1034 → 64.
Re-read: Lesson 5.6.2 — B+ tree order from block size, key size and pointer size
Q14 Answer: 245760 · 2 mark(s)
64² × 60.
Re-read: Lesson 5.6.2 — B+ tree order from block size, key size and pointer size
Q15 Answer: (B) · 2 mark(s)
Internal splits move the separator.
- (A) is wrong: No.
- (C) is wrong: Copying happens for leaves.
- (D) is wrong: No.
Re-read: Lesson 5.6.3 — B+ tree insertion and deletion traces; height and capacity; B vs B+