2201-ESTRUTURA DE DADOS - QUIZ

Prévia do material em texto

• Pergunta 1 
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 2 
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 3 
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 4 
1 em 1 pontos 
 
A análise assintótica de algoritmos permite avaliar a eficiência por meio da comparação 
de uma função matemática que represente o comportamento do algoritmo com um 
conjunto básico de funções matemáticas. Qual alternativa apresenta essas funções? 
 
Resposta Selecionada: c. 
Constante, log, linear, NlogN, quadrática, cúbica e exponencial. 
Respostas: a. 
Trigonométricas e algébricas. 
 b. 
Transformada de Fourier e transformada de Laplace. 
 c. 
Constante, log, linear, NlogN, quadrática, cúbica e exponencial. 
 d. 
Derivadas das funções matemáticas. 
 e. 
Integrais, baseada em cálculo numérico. 
Comentário 
da resposta: 
Alternativa C. 
A utilização dos conceitos associados à análise assintótica e à notação 
de ordem de grandeza oferece uma poderosa ferramenta para 
comparação de algoritmos, pois, uma vez definida a função matemática 
que caracteriza um determinado algoritmo, esta pode ser enquadrada 
em um limitante superior de eficiência definido por outra função 
matemática básica e com características de eficiência conhecidas. São 
7 as principais funções matemáticas básicas aplicáveis nesse caso 
 
(GOODRICH; TAMASSIA, 2013): Constante, log, linear, NLogN, 
quadrática, cúbica e exponencial. 
 
• Pergunta 5 
1 em 1 pontos 
 
Um programador está implementando um sistema embarcado para um novo 
equipamento industrial e necessita utilizar um algoritmo a fim de organizar valores que 
sejam fáceis de implantar e, também, sejam suportados pelos recursos do controlador 
que ele está utilizando no sistema embarcado. Nesse contexto, ele já utilizou a 
estrutura de dados de uma árvore de busca binária (ABB) em outro projeto, conhece as 
características de implementação e sabe que, na ABB, existe sempre certa ordenação 
entre os nós-filhos (subárvores esquerda e direita) e o nó-pai; entretanto, essa 
característica não é eficiente quando os dados de entrada já possuem uma 
determinada ordenação e resolveu-se utilizar uma árvore de busca binária balanceada 
(AVL). Nesse contexto, qual é a característica adicional encontrada em uma árvore 
AVL que a diferencia de uma ABB? 
 
Resposta 
Selecionada: 
c. 
As alturas das subárvores direita e esquerda de qualquer nó 
diferem, no máximo, em uma unidade. 
Respostas: a. 
Um nó pode ter mais do que dois filhos. 
 b. 
Todo nó sempre tem dois filhos. 
 
c. 
As alturas das subárvores direita e esquerda de qualquer nó 
diferem, no máximo, em uma unidade. 
 d. 
A altura da árvore é sempre um número par. 
 e. 
A altura da árvore é sempre um número ímpar. 
Comentário da 
resposta: 
Alternativa C. 
Uma árvore binária T é denominada AVL quando, para qualquer nó 
de T, as alturas de suas subárvores esquerda e direita diferem em 
módulo de até uma unidade. 
 
 
• Pergunta 6 
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 7 
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 8 
1 em 1 pontos 
 
As estruturas de dados devem ser utilizadas pelos programadores para auxiliar no 
desenvolvimento de programas e devem ser aplicadas corretamente no tratamento dos 
problemas. Qual das alternativas representa uma estrutura composta por um conjunto 
de elementos lineares, organizados e encadeados em sequência e que, a priori, não 
sabemos o tamanho do conjunto? 
 
Resposta Selecionada: e. 
Lista ligada 
Respostas: a. 
Vetores 
 b. 
Matrizes 
 c. 
Constante numérica 
 d. 
Árvores 
 e. 
Lista ligada 
Comentário 
da resposta: 
Alternativa E 
A lista ligada é uma estrutura de dados composta por um conjunto de 
elementos denominados nós, organizados e encadeados em sequência 
e que pode ser representado como um tipo abstrato de dados (TAD) 
(GOODRICH; TAMASSIA, 2013; TENENBAUM; LANGSAM; 
AUGENSTEIN, 1995). A lista ligada pode ser aplicada em diversos 
problemas computacionais, principalmente aqueles em que não se sabe 
o tamanho do conjunto de dados. 
 
 
• Pergunta 9 
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 10 
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)