Quiz Estrutura de dados

Prévia do material em texto

 Pergunta 1 
1 em 1 pontos 
 Considerando o conceito de árvore binária de busca ABB, podemos afirmar que: 
 
Resposta 
Selecionada: 
e. 
ABB viabiliza a utilização de estrutura hierárquica que melhoram a eficiência 
do processo de acesso aos dados armazenados. 
Respostas: a. 
ABB apenas implementa árvore binárias recursivamente. 
 
b. 
ABB não permite inserção e remoção de elementos, apenas a busca de 
elementos. 
 
c. 
ABB utiliza algoritmos de buscas lineares para melhorar o acesso aos 
elementos. 
 
d. 
ABB são árvores que melhoram a eficiência da inserção e remoção de 
elementos. 
 
e. 
ABB viabiliza a utilização de estrutura hierárquica que melhoram a eficiência 
do processo de acesso aos dados armazenados. 
Comentário da 
resposta: 
Alternativa E 
A árvore binária de busca (ABB) é uma estrutura de dados não linear que visa à 
melhoria na eficiência no processo de acesso aos dados armazenados, na qual 
os elementos seguem a seguinte organização (GOODRICH; TAMASSIA, 2013): 
 Todos os elementos da subárvore esquerda de um nó são sempre menores que o 
valor armazenado neste nó. 
 Todos os elementos da subárvore direita de um nó são sempre maiores que o valor 
armazenado neste nó. 
 
 
 
 Pergunta 2 
1 em 1 pontos 
 Um tipo abstrato de dados foi especificado para representar uma pilha, que é uma estrutura de 
dados formada por um conjunto sequencial de elementos, no qual o último elemento a entrar é o 
primeiro a sair do conjunto, e as operações são, basicamente, duas push (para colocar um 
elemento) e pop (para retirar um elemento). Considerando que um pilha esteja vazia, qual é a 
alternativa que representa os valores retirados da pilha na execução das operações: push(1), 
push(5), push(4), pop, push(6), push(3), pop, pop, pop, push(10), push(8), pop? 
 
Resposta Selecionada: b. 
4, 3, 6, 5 e 8. 
Respostas: a. 
8, 10, 3, 4, 5 e 1. 
 
b. 
4, 3, 6, 5 e 8. 
 
c. 
1, 5, 4, 6, 3 e 8. 
 
d. 
8 e 10. 
 
e. 
1, 5 e 4. 
Comentário 
da resposta: 
Alternativa B 
A execução das operações resulta na seguinte sequência de configuração: pilha: 
vazia; push 1 (1), push 5 (1,5); push 4 (1,5,4); (1,5) pop 4; push 6 (1,5,6); push 3 
(1,5,6,3); (1,5,6) pop 3; (1,5) pop 6; (1) pop 5; push 10 (1, 10); push 8 (1,10,8); 
(1,10) pop 8. Os valores retirados da pilha são: 4, 3, 6, 5, 8. 
 
 Pergunta 3 
1 em 1 pontos 
 Para a modelagem e a resolução de um problema associado à otimização de custos de produção, 
um analista utiliza grafos dirigidos e ponderados para examinar o processo de produção de certo 
produto e determinar alternativas que possam reduzir os custos. Após construir o grafo dirigido, 
ele notou que havia um caminho, começando em um vértice do grafo que permitia retornar a esse 
mesmo vértice. No relatório de análise, ele precisa colocar o nome correto desse tipo de caminho. 
Qual das alternativas denomina esse caminho? 
 
Resposta Selecionada: d. 
Um ciclo dirigido. 
Respostas: a. 
Aberto. 
 
b. 
Formado por arestas não adjacentes. 
 
c. 
Uma ligação de vértices. 
 
d. 
Um ciclo dirigido. 
 
e. 
Fechado. 
Comentário da 
resposta: 
Alternativa D. 
Quando um caminho de um grafo forma um ciclo (partindo de um vértice, é 
possível voltar a esse mesmo vértice), ele é denominado ciclo dirigido. Um 
 
dígrafo acíclico é aquele que não possui ciclo dirigido (GOODRICH; TAMASSIA, 
2013). 
 
 Pergunta 4 
1 em 1 pontos 
 As árvores podem ser classificadas em diversos tipos, sendo que a quantidade de filhos ligados a 
cada nó-pai e, também, o tipo de dado armazenado em cada um dos nós podem determinar essa 
classificação. Qual das alternativas a seguir representa uma árvore que permite um máximo de 
dois filhos para cada nó e é implementada com algoritmos recursivos muito compactos e simples 
para a sua manipulação? 
 
Resposta Selecionada: E. 
Árvores binárias. 
Respostas: A. 
Árvores gêmeas. 
 
B. 
Árvores separadas. 
 
C. 
Árvores completas. 
 
D. 
Árvores de seleção dupla. 
 
E. 
Árvores binárias. 
Comentário 
da resposta: 
Alternativa E 
A quantidade de filhos ligados a cada nó-pai e, também, o tipo de dado 
armazenado em cada um dos nós propiciam a classificação de diversos tipos de 
árvores, entre elas a mais significativa para as aplicações computacionais que é 
a árvore binária, a qual permite um máximo de dois filhos para cada nó, sendo 
implementada com algoritmos recursivos muito compactos e simples para a sua 
manipulação (TENENBAUM; LANGSAM; AUGENSTEIN, 1995). 
 
 
 Pergunta 5 
1 em 1 pontos 
 No tratamento das operações associadas ao TAD árvore AVL, após a inserção ou a remoção de 
um elemento, a árvore pode ficar desbalanceada e, nesse caso, as transformações devem ser 
realizadas na árvore para restaurar o balanceamento. Quais são essas operações? 
 
Resposta 
Selecionada: 
a. 
Rotação direita, rotação esquerda, rotação dupla direita, rotação dupla 
esquerda. 
Respostas: a. 
 
Rotação direita, rotação esquerda, rotação dupla direita, rotação dupla 
esquerda. 
 
b. 
Balanceamento simples e balanceamento completo. 
 
c. 
Criação de árvore adicional balanceada. 
 
d. 
Determinação da nova diferença entre as alturas das subárvores. 
 
e. 
Inversão das subárvores, troca de alturas, reposicionamento da raiz. 
Comentário da 
resposta: 
Alternativa A. 
As operações de rotação sobre uma árvore alteram o balanceamento desta, 
porém mantêm todas as suas características originais. São 4 tipos de rotação: 
rotação direita, rotação esquerda, rotação dupla direita e rotação dupla esquerda 
(SZWARCFITER; MARKENZON, 2010). 
 
 Pergunta 6 
1 em 1 pontos 
 Um programador é responsável pelo desenvolvimento de um sistema de vendas para uma 
empresa, a qual já possui uma versão de um sistema, porém este não atende mais aos requisitos 
do mercado, principalmente quanto à escalabilidade de operações e à confiabilidade de gestão de 
estoques, pois os principais algoritmos de busca e atualização de estoque fornecem respostas 
nos tempos exigidos pelas transações de venda de produtos na internet. O programador precisa 
comparar dois algoritmos utilizando o mesmo ambiente computacional e possui recursos (prazo e 
orçamento) para implementar as duas soluções. Assim, ele pretende avaliar o tempo de execução 
de cada uma das soluções aplicadas ao mesmo conjunto de dados (o qual atualmente causa 
problema no controle de estoque) e contabilizar o tempo real consumido por ambas, comparando 
os resultados para selecionar a mais eficiente. Qual das alternativas melhor representa essa 
abordagem de medida de eficiência de algoritmos? 
 
Resposta Selecionada: a. 
Estudos experimentais. 
Respostas: a. 
Estudos experimentais. 
 
b. 
Análise visual do programa. 
 
c. 
Simulação completa do sistema. 
 
d. 
Análise de componentes utilizados. 
 
 
e. 
Análise assintótica de algoritmos. 
Comentário 
da resposta: 
Alternativa A. 
Uma abordagem para a obtenção de um método de medida de eficiência de 
algoritmos visando à escolha entre possíveis soluções deve ser baseada em 
estudos experimentais que avaliem o tempo de execução de uma solução 
aplicada a diversos conjuntos de dados e contabilizem o tempo real consumido a 
cada amostra (TENENBAUM; LANGSAM; AUGENSTEIN, 1995). 
Nesse processo experimental para determinar uma possível dependência entre o 
tempo de execução e o volume de dados, faz-se necessário realizar diversos 
experimentos sobre amostras de dados diferenciadas por meio de uma análise 
fundamentada em elementos gráficos e em cálculos estatísticos, tanto em 
conjuntos de dados quanto no tamanho desses conjuntos, buscando afirmações 
razoáveis em relação ao tempo de execução de uma solução em função do 
tamanho dos dados. 
 
 Pergunta 7 
1 em 1 pontos 
 O TAD, árvore binária, implementa a operação, insere (valor) e pode ser utilizada para criar a 
árvore:Resposta Selecionada: d. 
Insere(88), insere(91), insere(70), insere(95), insere(99) 
Respostas: a. 
Insere(70), insere(88), insere(91), insere(95), insere(99) 
 
b. 
Insere(99), insere(95), insere(91), insere(88), insere(70) 
 
c. 
Insere(91), insere(95), Insere(99), insere(70), insere(88) 
 
d. 
Insere(88), insere(91), insere(70), insere(95), insere(99) 
 
e. 
Insere(70), insere(91), insere(95), insere(99), insere(88) 
 
Comentário da resposta: Alternativa D 
A execução das operações resulta na seguinte sequência de árvores: 
insere(88) 
 
insere(91) 
 
insere(70) 
 
insere(95) 
 
insere(99) 
 
 
 Pergunta 8 
1 em 1 pontos 
 No tratamento de árvores binárias de busca, na operação de eliminação ou remoção de um 
elemento da árvore, primeiramente, o elemento é localizado na árvore e, se for encontrado, 
podem ocorrer 3 situações distintas em função da quantidade de filhos do nó a ser removido. 
Neste contexto, qual das alternativas está correta? 
 
Resposta 
Selecionada: 
a. 
Quando o nó a ser removido não tiver filhos, temos a situação mais simples, 
mesmo que este nó seja a raiz. 
Respostas: a. 
Quando o nó a ser removido não tiver filhos, temos a situação mais simples, 
mesmo que este nó seja a raiz. 
 
b. 
A remoção de um nó com os dois filhos é facilmente resolvida, eliminando os 
dois filhos e o próprio nó. 
 
c. 
Quando um nó possui os dois filhos, não pode ser eliminado. 
 
d. 
Um nó que não possui filhos não pode ser eliminado, pois não possui um 
sucessor. 
 
e. 
Um nó que apresente apenas um dos filhos deve ser eliminado da árvore 
juntamente com o filho existente. 
Comentário da 
resposta: 
Alternativa A 
Quando o nó a ser removido é uma folha, ou seja, o nó não tem filhos, a 
remoção é simples e basta alterar o campo adequado do pai (filho esquerdo ou 
direito) para o valor nulo. Se o nó a ser removido é a raiz, esta deve ser alterada 
 
para nulo. 
 
 Pergunta 9 
1 em 1 pontos 
 
Na pesquisa em largura de um grafo (BFS), o princípio básico parte de um determinado vértice 
visitar todos os seus vértices adjacentes e, depois, procurar se ainda existe vértice não visitado 
e, recursivamente, visitar todos os adjacentes. No grafo a seguir, partindo do vértice A, qual é o 
caminho obtido se for aplicada a pesquisa em largura? 
 
 
 
Resposta Selecionada: e. 
A, B, C, D, F, E, G. 
Respostas: a. 
A, B, C, D, E, F, G. 
 
b. 
A, C, D, B, G, F, E. 
 
c. 
A, B, C, F, G, D, E. 
 
d. 
G, F, E, D, C, B, A. 
 
e. 
A, B, C, D, F, E, G. 
Comentário da 
resposta: 
Alternativa E. 
O algoritmo para realizar a operação BSF é o seguinte (LAFORE, 2004): 
• Selecione um vértice inicial, visite-o e torne-o atual. 
• Regra 1: Se possível, visite um próximo vértice adjacente ao vértice atual 
que ainda não tenha sido visitado; faça a marcação como visitado e insira na 
fila. 
• Regra 2: Se a regra 1 não puder ser seguida e se a fila não estiver vazia, 
retire um vértice da fila e o torne vértice atual. 
• Regra 3: Se a regra 2 não puder ser seguida em razão de a fila estar vazia, 
terminou o algoritmo. 
Seguindo as regras e partindo do vértice A, o caminho percorrido é A, B, C, D, 
F, E, G. 
 
 
 Pergunta 10 
1 em 1 pontos 
 A inserção em uma árvore binária de busca é, de um modo geral, um algoritmo bastante 
simplificado, pois o novo elemento é sempre inserido, criando: 
Resposta Selecionada: e. 
uma nova folha. 
Respostas: a. 
um filho esquerdo. 
 
b. 
um filho direito. 
 
c. 
uma nova raiz. 
 
d. 
um novo pai. 
 
e. 
uma nova folha. 
Comentário 
da resposta: 
Alternativa E 
A inserção de um novo elemento em uma ABB consiste em percorrer a árvore a 
partir da raiz, comparando o novo elemento com o nó apontado e, se o valor for 
menor, a operação é repetida recursivamente na subárvore esquerda e, se o 
valor for maior, na subárvore direita. O algoritmos termina quando for encontrado 
um valor igual, dispensando, assim, a inserção ou quando a subárvore 
pesquisada for nula; neste caso, o novo elemento é inserido no local da 
subárvore nula (TENENBAUM; LANGSAM; AUGENSTEIN, 1995). 
Observe que a inserção de um novo elemento em uma ABB ocorre sempre como 
uma nova folha da árvore (GOODRICH; TAMASSIA, 2013).