Simulado02 - ESTRUTURA DE DADOS EM PYTHON

Prévia do material em texto

1a 
 Questão 
Acerto: 1,0 / 1,0 
 
O uso de funções recursivas pode facilitar a implementação de diversos algoritmos. Toda recursão 
depende de dois elementos: o caso base e o passo recursivo. Dentre as opções a seguir, a que 
apresenta um passo recursivo é: 
 
 
par(n)=par(n) 
 
fat(1)=1 
 
fib(n)=n-1 + n-2 
 fat(n)=n*fat(n-1) 
 
f(n)=g(n-1) 
 
 
Explicação: 
O passo recursivo é o elemento que faz o cálculo da função recursiva mover-se em direção ao resultado. Deve 
envolver a chamada da própria função com um valor diferente de entrada. Isso só acontece na resposta 
correta: fat(n)=n*fat(n-1) , passo recursivo da função de cálculo de fatorial. 
fat(1)=1 é o caso base dessa mesma função. par(n)=par(n) é uma tautologia, e não uma recursão. As demais 
respostas são funções que não chamam a si mesmas, não podendo ser passos recursivos. 
 
 
2a 
 Questão 
Acerto: 1,0 / 1,0 
 
Um vetor está armazenado em memória no endereço-base 24. Considerando que uma palavra em 
memória ocupa 1 byte, e esse vetor é constituído por elementos que ocupam 4 palavras, qual é o 
endereço de memória ocupado pelos elementos de índices 2 e 50 respectivamente? . 
 
 
32 e 220 
 32 e 224 
 
28 e 224 
 
28 e 220 
 
26 e 74 
 
 
Explicação: 
Para calcular o endereço absoluto em memória você deve utilizar a fórmula A=B+t*i . No caso B é o endereço 
base (24), t é o tamanho de cada elemento (4) e i é o índice do elemento (2 e 50). Aplicando a fórmula 
temos 32=24+2*4 e 224=24+50*4 
 
 
3a 
 Questão 
Acerto: 0,0 / 1,0 
 
No contexto de complexidade de algoritmos, usualmente é utilizada a notação O para representar as 
complexidades assintóticas analisadas. Dentre as afirmações a seguir, a correta é: 
 
 O(n2) significa que as operações variam em proporção quadrática à entrada. 
 
O(n) significa que para n=50 o algoritmo realizará 50 operações no pior caso. 
 O(n) significa que as operações variam em proporção logarítmica à entrada. 
 
c -O(log n) significa que para n=64 o algoritmo realizará 6 operações no pior caso. 
 
O(n) significa que para n=50 o algoritmo executará no máximo 50 operações. 
 
 
Explicação: 
Com o uso da notação O, simplificamos o número de operações, ignorando multiplicadores constantes do termo 
dominante e todos os termos de menor complexidade. Por exemplo, 5n2+3 é O(n2), mas n2 também é O(n2). 
Dessa forma, não é possível calcular exatamente o número de operações quando se usa a notação O. Apenas 
podemos fazer afirmações sobre a proporcionalidade ao tamanho da entrada n. Assim, a resposta correta é que 
O(n2) é proporcional ao quadrado da entrada. 
 
 
4a 
 Questão 
Acerto: 0,0 / 1,0 
 
Suponha que você está implementando um programa que precisa armazenar dados ordenados em uma 
estrutura para serem tratados posteriormente, na ordem em que foram recebidos. Haverá uma grande 
quantidade de recebimentos e tratamento de dados, mas o tamanho esperado da estrutura não deve 
variar muito. Qual tipo de estrutura de dado é a melhor nessa situação? 
 
 Pilha. 
 Fila. 
 
Lista duplamente encadeada. 
 
Lista simplesmente encadeada. 
 
Lista em alocação contígua. 
 
 
Explicação: 
A fila permite o tratamento de nós usando a política requerida, FIFO ¿ ¿first in first out¿ -. Além disso, as 
operações de inserção e remoção são O(1), ou seja, de complexidade constante, a melhor possível. Isso condiz 
com o requisito de que haverá muitas operações desse tipo. Por fim, o fato de a estrutura não variar muito em 
tamanho permite o uso de uma alocação contígua e otimizada para a fila usando lógica circular e variáveis para o 
início e final da fila. A pilha não obedece a lógica FIFO e as listas tem complexidade de inserção e remoção O(n) 
sendo muito piores que a fila, principalmente quando o número desses tipos de operação é grande. 
 
 
5a 
 Questão 
Acerto: 1,0 / 1,0 
 
Uma lista L em alocação contígua está armazenada em memória no endereço 32. L possui elementos de 
2 bytes cada e no momento contém [10, 20, 30, 40] . Os elementos 5 e 50 serão inseridos em sequência. 
Em que endereços eles serão inseridos, respectivamente, caso a lista não seja ordenada, e caso a lista 
seja ordenada? 
 
 
Não ordenada: 36, 37; ordenada: 32, 37. 
 Não ordenada: 40, 42; ordenada: 32, 42. 
 
Não ordenada: 32, 34; ordenada: 32, 34. 
 
Não ordenada: 36, 37; ordenada: 32, 33. 
 
Não ordenada: 40, 42; ordenada: 40, 42. 
 
 
Explicação: 
A inserção na lista não ordenada ocorre ao final da lista, o 5o elemento será inserido na posição L[4] ou seja 
endereço 32 + 4 * 2 = 40 . O elemento seguinte L[5] será inserido no endereço 32 + 5 * 2 = 42. Já no caso 
ordenado, o primeiro elemento deverá ser inserido na primeira posição L[0], endereço 32. Todos os demais 
elementos serão deslocados uma posição. O segundo elemento será inserido ao final da lista em L[4]. Ou seja, 
endereço 32 + 4 * 2 = 42 (levando em conta o deslocamento) . Solução é, portanto: 40,42, 32,42. 
 
 
6a 
 Questão 
Acerto: 1,0 / 1,0 
 
Uma Lista pode ser implementada de forma contígua ou encadeada. No caso de uma lista implementada 
de forma contígua, as complexidades de pior caso de busca, inserção e remoção são respectivamente: 
 
 
O(n), O(1) e O(n). 
 
O(log n), O(n) e O(n). 
 
O(1), O(n) e O(n). 
 O(n), O(n) e O(n). 
 
O(n), O(n) e O(1). 
 
 
Explicação: 
A busca é O(n) pois no pior caso você terá que percorrer toda a lista sequencialmente até encontrar o último 
elemento. Já a inserção, no seu pior caso, colocará um elemento no início da lista, obrigando todos os demais a 
serem deslocados uma posição, levando O(n) operações. 
A remoção também tem nesse seu pior caso, remover o primeiro elemento, o que obrigará todos os demais a 
serem ¿puxados¿ uma posição levando tempo O(n). 
Esse custo pode ser diminuído caso você implemente uma variável que indique o início da lista, mesmo assim, ao 
remover um elemento exatamente do meio da lista, você precisará mover n/2 elementos, o que ainda é um custo 
linear. 
 
 
7a 
 Questão 
Acerto: 1,0 / 1,0 
 
A raiz é o ponto de partida para acessar todos os elementos de uma árvore. Marque a opção correta 
acerca dos principais conceitos de árvore binária de busca: 
 
 
O objetivo principal da estrutura de dados árvore binária de busca é ordenar uma lista sem a 
preocupação de implementar de forma eficientemente. 
 
Novas chaves maiores que a raiz sempre serão inseridas à esquerda. 
 
Qualquer nó pode ter um número arbitrário de nós, sempre maior que 2. 
 Em todas as estruturas de dados onde se realiza busca, inserção e remoção não são admitidas 
duplicidade de chaves. Isto também inclui as árvores binárias de busca. 
 
Dado um nó qualquer da árvore binária, todos os nós à direita dele são menores ou iguais a ele. 
 
 
Explicação: 
O grau máximo de um nó em uma árvore binária é 2. A unicidade de chave é um pressuposto para estruturas de 
busca. O objetivo principal de uma árvore binária de busca é implementar os algoritmos de busca, inserção e 
remoção de forma otimizada. Chaves maiores que a raiz devem ser inseridas à direita. Dado qualquer nó de uma 
árvore binária de busca, deve valer recursivamente a propriedade de que as chaves contidas à esquerda são 
menores que a raiz e a direita maiores. 
 
 
8a 
 Questão 
Acerto: 0,0 / 1,0 
 
Seja a seguinte árvore de expressões aritméticas abaixo. 
 
O resultado da visita em prefixo dessa árvore é: 
 
 
A + B * C 
 
A * B + C 
 A + * B C 
 + A * B C 
 
A + ( B * C ) 
 
 
Explicação: 
O percurso em prefixo é definido recursivamente. A partir da raiz r da árvore de expressões aritméticas T, percorre-
se a árvore de da seguinte forma: 
1 - visita-se a raiz; 
2 - percorre-se a sub-árvores esquerda de T, em prefixo e 
3 - percorre-se a sub-árvores direita de T, em prefixo. 
O resultado da visita é representado abaixo: 
 
 
 
9aQuestão 
Acerto: 1,0 / 1,0 
 
Seja as seguintes afirmações sobre árvores binárias: 
I - Os nós que não possuem filhos são chamados de nós folhas. 
II - O nó raiz é um nó na árvore que não possui antecessor (ou não tem pai). 
III - As árvores binárias são estruturas não lineares. 
Estão corretas as afirmativas: 
 
 I, II e III. 
 
I, apenas. 
 
III, apenas. 
 
I e II, apenas. 
 
II e III, apenas. 
 
 
Explicação: 
Os nós que são folhas não possuem apontamentos para outros nós, ou seja, não possuem filhos. Por outro lado, 
um nó raiz não possui pai, ou seja, não tem apontadores antecessores. Árvores binárias são estruturas que não 
possuem linearidade. 
 
 
10a 
 Questão 
Acerto: 1,0 / 1,0 
 
Seja a seguinte árvore AVL abaixo. Com a inserção da chave 90, marque a opção que indica 
exatamente o que acontecerá com a árvore resultante após essa inserção: 
 
 
 
A árvore resultante irá desbalancear à esquerda do nó de chave 10. 
 
A árvore resultante irá desbalancear à direita do nó de chave 80. 
 
A árvore resultante irá manter o balanceamento geral da árvore. 
 
A árvore resultante irá desbalancear à direita do nó de chave 40. 
 A árvore resultante irá desbalancear à esquerda do nó de chave 60. 
 
 
Explicação: 
Ao inserir o nó de chave 90, ele é maior que o nó 80, sendo assim, inserido ao lado direito de 80, causando 
desbalanceamento do nó 60 que tem altura da subárvore direita 2 e esquerda 0.