ESTRUTURADE DADOS QUIZ 1

Prévia do material em texto

• Pergunta 1 
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 2 
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 3 
1 em 1 pontos 
 
Uma árvore binária de busca com todos os nós balanceados pode ser denominada 
AVL, e as operações de rotação são necessárias após a operação de inserção de um 
novo elemento resultar em desbalanceamento de algum nó da árvore. Nesse contexto, 
tomando uma árvore vazia, qual alternativa apresenta uma sequência de valores que, 
quando inseridos, dispensa a aplicação de qualquer operação de rotação e resulta em 
uma árvore AVL? 
 
Resposta Selecionada: c. 
46, 32, 54, 40, 51, 18, 60. 
Respostas: a. 
60, 54, 51, 46, 40, 32, 18. 
 b. 
 
18, 32, 40, 46, 51, 54, 60. 
 c. 
46, 32, 54, 40, 51, 18, 60. 
 d. 
46, 54, 60, 32, 18, 40, 51. 
 e. 
46, 32, 18, 54, 40, 60, 51. 
Comentário 
da resposta: 
Alternativa C. 
A alternativa a) resulta, nas três primeiras inserções (60, 54, 51), em 
uma árvore com raiz desbalanceada; isso também ocorre com as 
alternativas b), d) e e). Apenas a alternativa c) resulta em uma árvore 
AVL sem operações de rotação, com a raiz 46 com os filhos 32 e 54, o 
elemento 32 com os filhos 18 e 40 e o elemento 54 com os filhos 51 e 
60. 
 
• Pergunta 4 
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 5 
1 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, qual é a alternativa 
que apresenta o resultado obtido com as operações a seguir sobre uma lista 
vazia: ins(10), ins(11), ins(12), ins(13), rem(), rem(), ins(21), ins(22), ins(23), rem(), rem(), 
rem(), ins(100)? 
 
Resposta Selecionada: e. 
(100, 11, 10) 
Respostas: a. 
(10, 11, 12, 13, 21, 22, 23, 100) 
 b. 
(100, 23, 22, 21, 13, 12, 11, 10) 
 c. 
(10, 11, 21, 100) 
 d. 
(100, 12, 13) 
 e. 
(100, 11, 10) 
Comentário da resposta: Alternativa E 
A execução das operações sobre a lista vazia é a seguinte: 
ins(10) 10, 
ins(11) 11,10, 
ins(12) 12,11,10, 
ins(13) 13,12,11, 10, 
12,11,10 rem() 13, 
11,10 rem() 12, 
ins(21) 21,11,10, 
ins(22) 22,21,11,10, 
ins(23) 23,22,21,11,10, 
22,21,11,10 rem() 23, 
21,11,10 rem() 22, 
11,10 rem() 21, 
ins(100) 100,11,10, que é sequência final. 
 
 
• Pergunta 6 
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 7 
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 8 
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 9 
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 10 
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.