Quiz - Estrutura de Dados

Prévia do material em texto

Pergunta 1 
1 em 1 pontos 
 
Considerando a estrutura de dados computacional árvore, as alternativas a seguir apresentam conjuntos de 
termos e palavras. Qual delas possui apenas termos ou palavras associadas diretamente à estrutura de dados 
árvore? 
 
Resposta Selecionada: c. Topo, nó, pai, filhos, raiz, folhas e ordenada. 
Respostas: a. Plantio, colheita e semente. 
 b. Arado, semente e drone. 
 c. Topo, nó, pai, filhos, raiz, folhas e ordenada. 
 d. Vaso, terra, poste e suporte. 
 e. Linear, encadeada e posição. 
Comentário 
da resposta: 
Alternativa C 
Os elementos de uma árvore são denominados nós, sendo que cada nó possui 
um nó-pai e zero ou mais nós-filhos. O nó do topo da árvore é denominado raiz, 
ocupa a posição mais elevada da árvore e não possui um nó-pai. Um nó é 
interno à árvore se tem um ou mais filhos, e os nós que não têm filhos são 
denominados externos ou folhas. Quando existe uma ordem entre os filhos dos 
nós de uma árvore, esta é denominada ordenada 
 
 
 
Pergunta 2 
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 3 
1 em 1 pontos 
 
Qual é a alternativa que melhor representa a função matemática associada ao tempo de execução do algoritmo 
a seguir? 
 
 int matriz [][] = new int [n][m]; 
 int i,j; 
 for (i=0;i<n;i++) 
 for (j=0;j<m;j++) 
 System.out.println(matriz[i][j]); 
 
 
Resposta Selecionada: c. f(n,m) = 4+3n+3n*m 
Respostas: a. f(n) = 4+n2 
 b. f(n,m) = n+mn 
 c. f(n,m) = 4+3n+3n*m 
 d. f(n,m) = m log n 
 e. f(n) = c 
Comentário da 
resposta: 
Alternativa C. 
Para a determinação da função, o algoritmo será escrito com algumas 
alterações, cujas operações básicas e importantes foram separadas e 
destacadas, e os tempos e o número de execuções, indicados. 
O resultado é a função f(n,m) = 4+3n+3n*m 
 
 
 
Pergunta 4 
1 em 1 pontos 
 
Uma empresa está formando uma equipe de desenvolvimento de software, e você foi contratado para organizar 
uma parte dos componentes básicos de software a serem utilizados pelos programadores da equipe e resolveu 
utilizar a proposta de tipo abstrato de dados como base para a proposta dos componentes. Neste contexto, 
escolha a alternativa que melhor se adapta a essa proposta. 
 
Resposta 
Selecionada: 
d. Para cada estrutura de dado a ser utilizada pela equipe, definir os dados a 
serem tratados e as operações definidas para eles. 
Respostas: a. Definir um conjunto completo de dados que sejam comuns a todos os 
componentes. 
 b. Utilizar apenas os tipos básicos de dados oferecidos pela linguagem de 
programação utilizada pela equipe. 
 c. Procurar tratar os requisitos dos clientes, sempre de forma abstrata, para 
obter uma solução abrangente. 
 d. Para cada estrutura de dado a ser utilizada pela equipe, definir os dados a 
serem tratados e as operações definidas para eles. 
 
 e. Utilizar apenas os componentes que forem validados pelo gerente e em 
acordo com o cliente. 
Comentário da 
resposta: 
Alternativa D. 
Um tipo abstrato de dados encapsula ou agrupa um conjunto de dados 
(estruturas de dados) associado a um elemento de computação, juntamente 
com os operadores (algoritmos) que atuam na modificação deles. 
 
 
Pergunta 5 
0 em 1 pontos 
 
O algoritmo de Djikstra foi idealizado por Edsger Djikstra, nos anos 1950, e, por meio de grafos ponderados, 
possibilita o caminho mais curto entre um vértice inicial e um vértice alcançável final, sendo muito utilizado em 
diversos problemas cotidianos de otimização de recursos e redução de custos. Entretanto, esse algoritmo 
oferece outro resultado muito importante. Qual? 
 
Resposta 
Selecionada: 
e. Contar o número de arestas. 
Respostas: a. Otimizar a criação do grafo. 
 b. O menor caminho entre o vértice inicial e todos os demais vértices 
alcançáveis do grafo. 
 c. Perceber se o grafo está com problemas estruturais. 
 d. Contar o número de vértices. 
 e. Contar o número de arestas. 
Comentário 
da resposta: 
Alternativa B. 
O algoritmo publicado pelo holandês Edsger Djikstra, em 1959, utiliza a 
representação baseada em matriz de adjacência de um grafo ponderado e 
possibilita encontrar o caminho mais curto entre um vértice inicialmente 
selecionado e todos os demais vértices alcançáveis a partir desse vértice inicial 
(LAFORE, 2004). O algoritmo retorna ao peso total do menor caminho entre os 
dois vértices, ou seja, a soma dos pesos de todas as arestas que formam o 
menor caminho. 
 
 
 
Pergunta 6 
1 em 1 pontos 
 
A criação de uma árvore binária de busca (ABB), com um conjunto de dados qualquer, pode não garantir uma 
busca eficiente nessa árvore; por exemplo, se os elementos inseridos estiverem com alguma ordenação, a 
árvore resultante pode ser muito semelhante a uma lista linear. Qual das alternativas a seguir representa a 
técnica de manutenção da ABB, que, mesmo com inserção e remoção de nós, visa a manter a eficiência do 
processo de busca de elementos? 
 
Resposta Selecionada: b. Balanceamento dos nós da árvore. 
Respostas: a. Retirada da ordenação. 
 b. Balanceamento dos nós da árvore. 
 c. Inserção ordenada dos nós. 
 d. Remoção ordenada dos nós. 
 e. Inversão de subárvores. 
Comentário 
da resposta: 
Alternativa B 
A criação de uma ABB pode não garantir uma busca eficiente, sendo 
interessante manter, de alguma forma, a árvore o mais completa possível, com 
os diversos níveis sempre preenchidos, ou seja, mantendo-a balanceada. 
De acordo com (TENENBAUM; LANGSAM; AUGENSTEIN, 1995, pg 526), “o 
balanceamento de um nó em uma árvore binária é definido como a altura de sua 
subárvore esquerda menos a altura de sua subárvore direita”, e uma árvore 
binária está balanceada se a diferença entre as alturas das subárvores esquerda 
e direita for menor ou igual a 1. 
 
 
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 
 
A implementação de um TAD grafo necessita que os dados associados a vértices e arestas sejam 
representados. Os vértices podem ser armazenados em um vetor com os dados associados aos vértices. Quais 
são as estruturas de dados comumente utilizadas para implementar os grafos e que permitem representar as 
arestas como ligações entre os vértices? 
 
Resposta Selecionada:a. Lista de adjacências e matriz de adjacências. 
Respostas: a. Lista de adjacências e matriz de adjacências. 
 b. Vetor de marcação e vetor simples. 
 c. Árvore binária e árvore binária de busca. 
 d. Variáveis estruturadas e registros. 
 e. Filas e pilhas. 
Comentário 
da resposta: 
Alternativa A. 
Duas estruturas de dados computacionais são comumente utilizadas na 
implementação de grafos: a lista de adjacências e a matriz de adjacências 
(GOODRICH; TAMASSIA, 2013). Na lista de adjacências, as arestas são 
armazenadas em um vetor de listas ligadas, e cada uma dessas listas armazena 
em seus nós as adjacências de cada vértice. Na implementação de um grafo 
com N vértices baseada em matriz de adjacências, utiliza-se um vetor 
bidimensional com N posições em cada dimensão (matriz NxN) para indicar a 
existência de uma aresta entre dois vértices. 
 
 
 
Pergunta 9 
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 10 
1 em 1 pontos 
 
A figura a seguir representa uma árvore AVL após a operação de inserção do elemento 8. Ela ficou 
desbalanceada, especificamente a raiz 31. Qual operação deve ser realizada para devolver o balanceamento da 
árvore? 
 
 
Resposta Selecionada: e. Rotação para a direita. 
Respostas: a. Rotacionar toda a árvore duas vezes. 
 b. Não fazer nada e deixar de ser árvore AVL. 
 c. Inserção de um novo elemento para balancear a árvore. 
 
 d. Remoção do novo elemento. 
 e. Rotação para a direita. 
Comentário 
da resposta: 
Alternativa E. 
Com a inserção do elemento 8, a subárvore esquerda da raiz 31 ficou com altura 
e resultou no acréscimo da altura 3. Como a subárvore direita da raiz 31 
continua com altura 1, temos uma diferença de alturas igual a 2, indicando a 
necessidade de balanceamento da árvore. A operação necessária para devolver 
o balanceamento à árvore é a rotação para a direita sobre a raiz 31.