Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — FADURPE 2024

Indexação de matriz em vetor unidimensional (row-major)

Gabarito: letra A. Dada uma matriz M de n linhas e m colunas, armazenada em ordem row-major (linhas consecutivas) num vetor A indexado a partir de 0, com os índices de M iniciando em 1, a conversão correta do índice k de A para as coordenadas (i, j) de M é:

• i = k DIV m + 1 (divisão inteira de k por m fornece quantas linhas completas foram percorridas; somando 1 obtém-se o número da linha)

• j = k MOD m + 1 (resto da divisão indica a posição dentro da linha; somando 1 obtém-se o número da coluna)

A fórmula da alternativa A reproduz exatamente essa lógica. Vamos analisar cada alternativa.

Alternativa A — ✅ Correta ⟵ GABARITO

Define corretamente i = k DIV m + 1 e j = k MOD m + 1. Exemplo: m=3, k=0 → i=1, j=1; k=1 → i=1, j=2; k=3 → i=2, j=1. Perfeito.

Alternativa B — ❌ Incorreta

i = (k+1) DIV m e j = (k+1) MOD m. Para k=0: (1 DIV m)=0 → i=0 (inválido, pois i deve começar em 1); j=(1 MOD m)=1 → j=1. Além disso, para k = m-1: (m DIV m)=1 → i=1, mas j=(m MOD m)=0 → coluna 0 (inválido). Portanto, não gera índices a partir de 1 corretamente.

Alternativa C — ❌ Incorreta

i = k MOD n + 1 e j = k DIV m + 1. Usar MOD n para obter a linha é incorreto: o número de elementos por linha é m, não n. Por exemplo, n=2, m=3, k=0: i = 0 MOD 2 +1 = 1, j = 0 DIV 3 +1 = 1 (ok). Mas k=3: i = 3 MOD 2 +1 = 2, j = 3 DIV 3 +1 = 2 → posição (2,2), quando deveria ser (2,1) (a 4ª posição está na 2ª linha, 1ª coluna). A fórmula falha.

Alternativa D — ❌ Incorreta

i = (k+1) MOD m e j = (k+1) DIV n. Troca os papeis: a linha é obtida pelo resto da divisão por m (incorreto) e a coluna pela divisão por n (também incorreto). Além disso, o acréscimo de 1 antes da operação desloca os índices. Exemplo: m=3, n=2, k=0 → i = 1 MOD 3 =1, j = 1 DIV 2 =0 → coluna 0 (inválida).

Alternativa E — ❌ Incorreta

i = (k+1) MOD n e j = (k+1) DIV m. Semelhante à D, mas troca n e m posicionalmente. k=0, m=3, n=2: i = 1 MOD 2 =1, j = 1 DIV 3 =0 → coluna 0. Para k=2: (3 MOD 2)=1, (3 DIV 3)=1 → i=1, j=1, mas deveria ser (1,3). Portanto, errada.

A chave da questão é lembrar que, no armazenamento row-major, cada linha tem m elementos; o índice k do vetor corresponde a percorrer as linhas inteiras (k DIV m) e a posição dentro da linha (k MOD m). Como os índices da matriz começam em 1, adiciona-se 1 a ambos os resultados.