Questão 66230

Durante um curso de formação continuada, um grupo de professores de computação discute estratégias para ensinar estruturas de dados de forma mais significativa. A professora orientadora, Dra. Ana, critica a abordagem comum de simplesmente apresentar as estruturas (pilha, fila, lista, árvore, grafo) e suas implementações. Ela argumenta que os alunos precisam compreender os 'trade-offs' envolvidos na escolha de uma estrutura em detrimento de outra. Para ilustrar, ela cita um trecho de um blog de engenharia de software: "A escolha da estrutura de dados correta é frequentemente o fator mais crítico no desempenho de um sistema. Não se trata de qual estrutura é 'melhor' em absoluto, mas qual é a mais adequada para um padrão de acesso específico. Um `array` (ou lista em Python) oferece acesso $O(1)$ a um elemento pelo seu índice, mas a inserção ou remoção de um elemento no meio da estrutura é $O(n)$, pois exige o deslocamento dos elementos subsequentes. Uma lista duplamente encadeada, por outro lado, permite a inserção/remoção em $O(1)$ (se o nó for conhecido), mas o acesso a um elemento pelo índice é $O(n)$, pois requer percorrer a lista desde o início. Compreender essa troca entre velocidade de acesso e velocidade de modificação é fundamental." Dra. Ana, então, propõe um problema aos professores: "Vocês estão projetando um editor de texto. Qual estrutura de dados seria a mais apropriada para armazenar os caracteres do documento, e por quê?"

Considerando o problema proposto e o referencial teórico sobre trade-offs, avalie as asserções a seguir:

I. Um `array` ou lista simples seria a escolha ideal, pois a operação mais comum em um editor de texto é a leitura sequencial, e o acesso por índice, embora não tão frequente, é rápido.

II. Uma estrutura de dados chamada 'Gap Buffer' ou uma 'Rope' (corda), que são otimizações sobre listas ou árvores, seriam mais adequadas. O Gap Buffer, por exemplo, usa um `array` com um espaço vazio (gap) na posição do cursor, tornando as inserções e deleções locais (digitação) operações de tempo amortizado $O(1)$, pois apenas o gap precisa ser movido.

III. Uma lista duplamente encadeada seria uma escolha superior a um `array` simples, pois as operações de inserção e deleção de caracteres, que são extremamente frequentes, teriam complexidade $O(1)$, superando a desvantagem do acesso lento por índice, que é uma operação rara em editores de texto.

É correto o que se afirma em: