ESTRUTURA DE DADOS

Prévia do material em texto

• 
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 2 
0 em 1 pontos 
 
Considerando o método removeInicio() (implementado em Java e disponível no 
material de aula), que remove um elemento do início de uma lista ligada e listado a 
seguir: 
 public Object removeInicio() 
 { 
 No auxiliar = this.inicio; // passo 1 da figura 4 
 this.inicio = auxiliar.getProximo(); // passo 2 da figura 4 
 return auxiliar.getElemento(); // passo 3 da figura 4 
 } 
Vamos assumir que estamos tratando uma lista de valores inteiros e que a 
operação removeInicio() é realizada duas vezes sobre as listas representadas nas 
alternativas a seguir. Indique em qual delas ocorrerá um exceção ou erro de execução 
do programa. 
 
Resposta Selecionada: a. 
(3, 9, 8, 10) 
Respostas: a. 
(3, 9, 8, 10) 
 b. 
(10, 8, 9, 3) 
 c. 
(10) 
 d. 
(100, 101, 102) 
 e. 
(102, 101) 
Comentário da 
resposta: 
Alternativa C 
A operação removeInicio() não realiza o teste de lista ligada vazia, 
sendo assim a primeira execução remove o valor 10 e deixa a lista 
vazia, a segunda execução resultará em exceção ou erro de execução. 
 
 
• Pergunta 3 
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 4 
0 em 1 pontos 
 
Considerando o conceito de árvore binária de busca ABB, podemos afirmar que: 
Resposta 
Selecionada: 
d. 
ABB são árvores que melhoram a eficiência da inserção e remoção 
de elementos. 
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 5 
0 em 1 pontos 
 
Considerando que um TAD lista ligada possui os operadores ins(valor), que insere valor 
no início da lista, e rem(), que remove valor do início da lista, e que a lista ligada já tem 
os dados (12, 23, 45, 11, 10, 23), qual das opções a seguir apresenta os comandos 
necessários para que a lista fique com a seguinte sequência de dados (0, 5, 
45,11,10,23)? 
 
Resposta Selecionada: e. 
rem(), rem(), rem(), rem(), rem(), ins(0), ins(5) 
Respostas: a. 
rem(), rem(), ins(5), ins(21), rem(), ins(0), ins(31), rem() 
 b. 
ins(0), ins(5) 
 c. 
rem(), rem(), rem(), ins(5), rem(), ins(0), ins(5) 
 d. 
ins(4), rem(), ins(5), ins(0) 
 e. 
rem(), rem(), rem(), rem(), rem(), ins(0), ins(5) 
Comentário da 
resposta: 
Alternativa A 
A execução das operações sobre a lista (12, 23, 45, 11, 10, 23) é 
a seguinte: 
(23, 45, 11, 10, 23) rem() 12, 
(45, 11, 10, 23) rem() 23, 
ins(5) (5, 45, 11, 10, 23), 
ins(21) (21, 5, 45, 11, 10, 23), 
(5, 45, 11, 10, 23) rem() 21, 
ins(0) (0, 5, 45, 11, 10, 23), 
ins(31) (31, 0, 5, 45, 11, 10, 23), 
 
(0, 5, 45, 11, 10, 23) rem() 31. 
Resultado final (0, 5, 45, 11, 10, 23) 
 
• Pergunta 6 
0 em 1 pontos 
 
A comparação da eficiência de algoritmos pode ser realizada pela comparação de 
funções matemáticas básicas com as funções que representam o comportamento do 
algoritmo, sempre considerando os tamanhos do conjunto de dados tratado pelos 
algoritmos. Qual é o nome dado a essa abordagem para comparação de eficiência em 
algoritmos? 
 
Resposta Selecionada: a. 
Estudos experimentais. 
Respostas: a. 
Estudos experimentais. 
 b. 
Experimento científico-matemático. 
 c. 
Análise amostral de dados. 
 d. 
Equipe de matemáticos especialistas. 
 e. 
Análise assintótica de algoritmos. 
Comentário 
da resposta: 
Alternativa E. 
A análise assintótica de algoritmos consiste em analisar um algoritmo e 
determinar, com base nas operações envolvidas em sua 
implementação, uma função matemática que represente o tempo de 
execução dele em função do tamanho do conjunto de dados, 
encontrando outra função matemática básica e bem conhecida 
(constante, quadrática, exponencial etc.) que se aproxime o melhor 
possível (de forma assintótica)da função definida para esse algoritmo. 
 
 
• Pergunta 7 
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 8 
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 9 
0 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: b. 
Formado por arestas não adjacentes. 
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 10 
0 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: b. 
Vetor de marcação e vetor simples. 
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.