Question

PERGUNTA 1.1. Qual das alternativas a seguir apresenta apenas estruturas lineares?

Árvores AVL e grafos.

Filas, pilhas e grafos.

Filas, pilhas e árvores.

Filas, pilhas e listas encadeadas.

Vetores, listas encadeadas e árvores.

*PERGUNTA 1.2. Sobre as estruturas de dados pilha e fila, assinale a alternativa correta.*

O comportamento de uma pilha é semelhante ao comportamento do botão "desfazer" de editores de texto, em que, ao acionar o botão, o último caractere inserido é o primeiro a ser removido. Uma fila, pelo contrário, tem comportamento semelhante ao botão "refazer" no mesmo editor de texto, em que supondo que clicamos no botão "desfazer" três vezes para apagar três caracteres (A, B e C, nessa ordem, por exemplo), ao clicar no "refazer", o primeiro elemento "desfeito" será o primeiro refeito (o caractere A será inserido novamente).

Na implementação de uma pilha, precisamos de uma variável para indicar a cabeça (topo) da pilha, local onde ocorrerão as inserções e remoções. Na implementação de uma fila, pelo contrário, precisamos de duas variáveis para indicar a posição da frente e de trás da fila, dado que na frente da fila removemos elementos e atrás da fila inserimos elementos.

Com uma pilha, implementamos situações em que precisamos garantir acesso justo a um recurso compartilhado, uma pilha de impressão, por exemplo, em que documentos de vários usuários são enviados para a impressora.

Com uma fila, podemos implementar situações em que queremos garantir que certas estruturas estão balanceadas, o que é muito comum em linguagens de programação (escopo, chamada de funções, ...). Um exemplo minimalista é a verificação de parênteses, colchetes e chaves aninhados em uma string, tarefa tipicamente solucionada com o uso de filas.

Uma pilha é uma estrutura linear, dado que inserções e remoções e acessos ocorrem sempre no topo da pilha. Por outro lado, a fila não é uma estrutura linear, dado que remoções ocorrem no final da fila e inserções ocorrem no início.

*PERGUNTA 1.3. Sobre tabela hash, assinale a alternativa correta.*

Em uma tabela hash, temos uma função de espalhamento que mapeia uma determinada chave para um endereço de memória. Do ponto de vista teórico, isso permitiria obter o conteúdo desejado acessando este endereço de memória. Entretanto, do ponto de vista prático, não é possível converter chaves em endereço de memória, o que impede a implementação de tabelas hash.

Em um cenário ideal sem colisões, implementar uma tabela se resumiria a criar uma função de espalhamento para indicar em qual posição de memória um elemento seria alocado. Em um cenário prático, a quantidade de colisões normalmente força o desenvolvedor a assumir que todos os elementos serão mapeados para uma mesma posição de memória. Por isso, costuma-se dizer que buscas em tabela hash não são melhores que buscas sequenciais.

Ao implementar uma tabela hash internamente como um vetor e assumindo um cenário com colisões, o tratamento dessas colisões pode usar um espaço de memória adicional ou pode usar o espaço de memória do próprio vetor. Um exemplo de tratamento de colisões que usa um espaço de memória adicional é o encadeamento separado, e um exemplo de tratamento de colisões que usa o espaço do próprio vetor é o teste linear.

Para tratar colisões, podemos usar uma estrutura interna como um vetor com tamanho muito maior do que o número de elementos que queremos adicionar. Como o vetor é muito grande, colisões não existirão e será possível gerar algoritmos mais simplificados.

As tabelas hash são estruturas muito úteis para fazer inserção, remoção e busca de maneira eficiente. No caso da implementação interna como um vetor, mesmo com o tratamento usando teste linear que pode formar clusters de números um do lado do outro, é possível fazer uma busca eficiente usando o algoritmo de busca binária.

*PERGUNTA 1.4. Sobre o grafo apresentado a seguir, assinale a alternativa verdadeira.*

Imagem sem legenda

Uma possível busca em largura, iniciando no vértice B, poderia visitar os vértices na seguinte ordem: B, C, D, A, E.

Uma possível busca em profundidade, iniciando no vértice C, poderia visitar os vértices na seguinte ordem: C, A, E, D, B.

Uma busca em largura neste grafo utilizando o algoritmo visto em aula, iria utilizar uma pilha para gerenciar os backtrackings.

Uma possível busca em largura, iniciando no vértice E, poderia visitar os vértices na seguinte ordem: E, C, A, B, D.

Uma possível busca em profundidade, iniciando no vértice D, poderia visitar os vértices na seguinte ordem: D, C, E, A, B.

*PERGUNTA 2. Dado o trecho de código mostrado a seguir:*

*PERGUNTA 3 NECESSITA DE RESPOSTA ESCRITA EM FOLHA . Dada a árvore AVL a seguir:*

Answer 1

Resposta:

Filas, pilhas e listas encadeadas.

Explicação:

Answer 2

Resposta:

Linhas 24 e 25 retornam: 8 e 3;

Linhas 6 a 9: cria a função e atribui o valor 8.

Linhas 10 a 13: criam a função e atribui o valor da variável.

Explicação: