Teste sobre Lista encadeada

Pergunta 1: O acesso a um elemento em uma lista encadeada é direto por índice, com complexidade de tempo O(1), tornando-o mais eficiente que em arrays.

A. Sim

B. Não

Explicação: O material de estudo afirma que o acesso a um elemento em uma lista encadeada é sequencial, com complexidade de tempo O(n), enquanto em arrays o acesso é direto por índice (O(1)). Portanto, a afirmação de que o acesso em listas encadeadas é direto por índice e mais eficiente que em arrays está incorreta.

Pergunta 2: A remoção de um nó do início de uma lista encadeada simplesmente tem uma complexidade de tempo de O(1).

A. Sim

B. Não

Explicação: Para remover o nó do início de uma lista simplesmente encadeada, a cabeça da lista é atualizada para apontar para o segundo nó. Esta operação envolve um número constante de passos, independentemente do tamanho da lista, resultando em uma complexidade de tempo O(1).

Pergunta 3: De acordo com o material de estudo, quais são os dois campos principais que um nó (ou elemento) tipicamente contém em uma lista encadeada?

A. O endereço de memória do nó e o tipo de dados que ele armazena.

B. Dados (o valor ou informação) e um ponteiro (ou referência) para o próximo nó.

C. Um campo para o valor do nó e um campo para o nó anterior na sequência.

D. O índice da sua posição na lista e o tamanho total da lista encadeada.

Explicação: O material de estudo afirma que cada nó tipicamente contém dois campos principais: 'Dados: O valor ou a informação que o nó armazena' e 'Ponteiro (ou Referência): Um campo que armazena o endereço de memória do próximo nó na sequência'.

Pergunta 4: De acordo com o material de estudo, qual das operações de inserção em uma lista encadeada é a mais eficiente e por quê?

A. Inserção no fim da lista, pois é possível adicionar o novo nó diretamente sem percorrer a lista.

B. Inserção em posição específica, pois apenas um nó adjacente precisa ser alterado para incluir o novo elemento.

C. Inserção no início da lista, pois envolve um número constante de operações, independentemente do tamanho da lista.

D. Inserção no fim da lista (O(1)), mas apenas se mantivermos um ponteiro para a cauda; caso contrário, é O(n).

Explicação: O material de estudo afirma que a 'Inserção no Início da Lista (O(1))' é a operação mais eficiente. Ele explica que um novo nó é criado, seu ponteiro 'próximo' aponta para a cabeça atual, e a cabeça é atualizada para o novo nó. A complexidade de tempo é O(1) porque envolve um número constante de operações, independentemente do tamanho da lista. A inserção no fim da lista sem ponteiro para a cauda e a inserção em posição específica são O(n). A inserção no fim da lista com ponteiro para a cauda é O(1), mas a pergunta busca a 'mais eficiente' dentre as operações descritas como a principal forma de inserção sem condições adicionais explícitas como 'com ponteiro para cauda'.

Pergunta 5: A remoção de um nó de uma lista duplamente encadeada, quando o nó a ser removido (N_alvo) não é conhecido previamente, possui uma complexidade de tempo O(1).

A. Sim

B. Não

Explicação: A remoção de um nó em uma lista duplamente encadeada é O(1) *se o N_alvo já for conhecido*. No cenário em que o N_alvo não é conhecido previamente, seria necessário percorrer a lista para encontrá-lo, o que implicaria uma complexidade de tempo O(n), e não O(1).