Arrays as a data structure

ACompressed recap

🧾

An ADT fixes operations and behaviour; a data structure implements it. Arrays give O(1) access but O(n) insertion and deletion (shifting), O(n) unsorted search and O(log n) binary search on sorted data. Addresses: subtract lower bounds; row-major multiplies the row offset by the column count, column-major the column offset by the row count; 3-D row-major uses i·n₂n₃ + j·n₃ + k.

BMerged rule card

3.1 Arrays as a data structure: the ADT idea; address calculation (row-major, column-major, non-zero lower bounds); cost of insert, delete and search

• ADT = operations + behaviour; data structure = an implementation.
• Array: access O(1); insert/delete at p O(n − p); search O(n), sorted O(log n).
• Row-major: B + ((i − l₁)·n₂ + (j − l₂))·w; column-major: B + ((j − l₂)·n₁ + (i − l₁))·w.
• nₖ = uₖ − lₖ + 1; 3-D row-major: B + (i·n₂n₃ + j·n₃ + k)·w (from 0).
• Binary search: sorted only; ⌊log₂ n⌋ + 1 probes.

CInterleaved GATE-style questions

Q1NAT2 marksAddress

int A[1..8][1..12] (4 bytes) row-major from 3000. Address of A[4][9]?

Numerical answer: ________

Q2NAT2 marksAddress

The same array column-major from 3000. Address of A[4][9]?

Numerical answer: ________

Q3NAT1 markElements

How many elements does A[−3 … 5][2 … 6] have?

Numerical answer: ________

Q4MCQ1 markCosts

Inserting at the front of an array of n elements costs:

• (A) O(n)
• (B) O(log n)
• (C) O(1)
• (D) O(n²)

Q5MCQ2 marksBinary search

Binary search for 11 in {1, 3, 5, 7, 9, 11, 13} probes which positions (0-based)?

• (A) 0, 1, 2, 3, 4, 5
• (B) 3, 4, 5
• (C) 3, 5
• (D) 6, 5

Q6NAT2 marks3-D

char C[4][5][6] (indices from 0, 1 byte) is row-major from 0. What is the address of C[3][2][1]?

Numerical answer: ________

Q7MSQ1 markFacts

Which are true?

• (A) Binary search works on unsorted arrays.
• (B) Column-major address uses the number of rows.
• (C) C stores 2-D arrays in row-major order.
• (D) Deleting the last element of an array needs no shifting.

Q8MCQ1 markADT vs structure

Which is a data structure rather than an ADT?

• (A) “a list whose items have positions”
• (B) an array of 100 ints in consecutive memory
• (C) “a collection supporting insert, delete, search”
• (D) “a collection where the last item added is removed first”

DAnswer Vault