Simulado03 - 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 é: 
 
 
fib(n)=n-1 + n-2 
 
par(n)=par(n) 
 
fat(1)=1 
 
f(n)=g(n-1) 
 fat(n)=n*fat(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 
 
A complexidade computacional é uma abstração para facilitar a comparação de algoritmos de forma 
independente do ambiente de execução e de variações na sua entrada. As complexidades podem ser 
representadas pelo número de operações requeridas. Dentre as seguintes complexidades de pior caso, 
representadas pelo seu número de operações, qual é a melhor? (menos operações) 
 
 100n + 5log n 
 
2n 
 
(nlog n)/2 
 
2n2 
 
nlog n + 500 
 
 
Explicação: 
O conceito de complexidade é assintótico, ou seja, o que importa é quando o tamanho da entrada n cresce 
arbitrariamente. Por isso, os termos dominantes de cada resposta são os únicos relevantes. 500n é 
assintoticamente menor que n2, por exemplo, pois para n acima de 500 o quadrado de n será maior que 500n. 
Dessa forma podemos ordenar em forma crescente de complexidade os termos dominantes das respostas: n, 
nlog n, n2, 2n. O menor deles é n, logo a resposta correta é 100n+5log n. 
 
 
3a 
 Questão 
Acerto: 1,0 / 1,0 
 
Dada a seguinte matriz M, inicializada com o código: 
M=[[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]] 
O código em Python para imprimir cada elemento da coluna iniciada pelo elemento 3 é: 
1 2 3 4 
5 6 7 8 
9 10 11 12 
13 14 15 16 
 
 
 
for coluna in M: 
 print(coluna) 
 
print(M[2]) 
 for linha in M: 
 print(linha[2]) 
 
for linha in M: 
 print(linha[3]) 
 
for linha in M: 
 print(linha) 
 
 
Explicação: 
O laço deve percorrer uma coluna, iterando linha a linha e extraindo dela o seu terceiro elemento, ou seja linha[2]. 
A resposta correta itera pelas linhas e imprime o elemento [2] de cada uma. 
Dentre as respostas erradas, apenas escrever ¿print(linha)¿ imprimirá cada linha como um todo, resultando na 
impressão de toda a matriz, linha a linha. 
A resposta "print(coluna)" terá o mesmo resultado pois para o código linha e coluna são apenas nomes escolhidos 
pelo programador. Poderia ser i, aux ou qualquer outra variável escolhida. 
Já "print(linha[3])" está com o índice errado, imprimindo os elementos da coluna iniciada por 4. E ¿print(M[2])¿ 
imprime toda a linha iniciada por 9. 
 
 
4a 
 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: 32, 34; ordenada: 32, 34. 
 
Não ordenada: 36, 37; ordenada: 32, 33. 
 
Não ordenada: 36, 37; ordenada: 32, 37. 
 Não ordenada: 40, 42; ordenada: 32, 42. 
 
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. 
 
 
5a 
 Questão 
Acerto: 1,0 / 1,0 
 
Suponha que você está implementando um programa que precisa armazenar dados ordenados em uma 
estrutura para serem tratados posteriormente, na ordem inversa à 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 dados é a melhor nessa situação? 
 
 Pilha. 
 
Fila. 
 
Lista simplesmente encadeada. 
 
Lista em alocação contígua. 
 
Lista duplamente encadeada. 
 
 
Explicação: 
A pilha permite o tratamento de nós usando a política requerida, FILO ¿ ¿first in last 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 pilha. A fila não obedece a lógica FILO e as 
listas têm complexidade de inserção e remoção O(n) sendo muito piores que a pilha, principalmente quando o 
número desses tipos de operação é grande. 
 
 
6a 
 Questão 
Acerto: 1,0 / 1,0 
 
Uma lista L encadeada e ordenada está armazenada em memória seguindo o exemplo abaixo. Após a remoção do 
nó de chave 3, quais alterações terão ocorrido? 
 
 
 
O conteúdo armazenado no endereço 32 será apagado. 
 
O endereço 32 terá seu campo próximo apontando para 24. 
 
L terá sido apagada. 
 A variável L apontará para 128. 
 
O endereço 24 conterá a chave 5 e próximo 64. 
 
 
Explicação: 
A remoção solicitada é do primeiro elemento da lista encadeada. Para realizar esse tipo de remoção, basta apontar a variável 
que guarda o primeiro elemento (L) para o endereço do segundo elemento. Este endereço está armazenado no campo 
próximo do primeiro elemento. Ou seja, a variável L deverá apontar para 128. 
A resposta endereço 24 conterá a chave 5 está errada pois na lista encadeada, os elementos não precisam ser puxados após 
uma remoção. 
A resposta endereço 32 terá seu campo próximo alterado está errada, pois isso adicionaria um elemento ao final da lista, no 
caso tornando-a circular. 
As demais respostas estão erradas pois nada será apagado. 
 
 
7a 
 Questão 
Acerto: 0,0 / 1,0 
 
Seja a seguinte árvore binária. Analise as afirmativas e marque a correta. 
 
 
 
Ao buscar pelo nó 45 na árvore acima, um algoritmo de busca em Python irá realizar 
sempre O(n) passos. Isto ocorre uma vez que é necessário analisar todos os nós da árvore para 
encontrar o nó 45. 
 
Supondo que a árvore em questão é uma árvore binária de busca, a inserção de um novo nó 
com chave 47 pode ser feita em qualquer subárvore vazia. 
 
É possível inserir mais um nó filho ao nó 30. 
 A figura ilustra uma árvore binária de busca porque para todos os nós vale a seguinte 
propriedade: os nós contidos na subárvores esquerda são menores que a raiz e os contidos na 
subárvore direita são maiores. 
 A árvore acima possui 4 nós folhas. 
 
 
Explicação: 
A árvore é uma árvore binária de busca porque dado um nó qualquer da árvore, os nós contidos na subárvore 
esquerda são menores que a raiz e os a direita, maiores que a raiz. A busca só seria executada em O(n) caso a 
árvore fosse uma árvore zig zag. 47 só poderia ser inserido à direita de 45. A árvore tem 3 folhas. Arvores 
binárias só podem ter nós com grau 2. 
 
 
8a 
 Questão 
Acerto: 1,0 / 1,0 
 
As árvores de busca são estruturas de dados que armazenam elementos de forma hierárquica, 
permitindo uma busca eficiente em grandes conjuntos de dados. Marque a opção correta acerca das 
estruturas de dados Árvores e ÁrvoresBinárias: 
 
 
As folhas estão sempre no nível 1 da árvore. 
 
A raiz está no maior nível da árvore. 
 
Nas Árvores Binárias de Busca cada nó deve ter exatamente 2 filhos. 
 
Os nós de uma árvore que possuem grau zero são chamados de raiz. 
 Ao acessar uma árvore, deve-se acessar pela referência a sua raiz. 
 
 
Explicação: 
A forma comum de representar uma árvore em memória é utilizando alocação dinâmica. Não representamos a 
árvore como um todo, mas sim uma referência para sua raiz que guarda a chave (dado) e uma referência para a 
raiz das sub-árvores esquerda e direita. Um nó pode ter 0, 1 ou 2 filhos. As folhas podem estar em qualquer nível. 
A raiz pode ter grau zero quando é raiz e folha simultaneamente. A raiz está sempre no nível 1. 
 
 
9a 
 Questão 
Acerto: 1,0 / 1,0 
 
Em uma Árvore B, temos que: Cada nó contém no mínimo m registros (m+1 descendentes) e no máximo 
2m registros (e 2m+1 descendentes), exceto o nó que é raiz que pode conter entre 1 e 2m registros e 
todos os nós folhas aparecem no mesmo nível. Sobre Árvores B, é correto afirmar: 
 
 
O particionamento de nós em uma Árvore B ocorre quando a chave do registro a ser inserido 
contém um valor(conteúdo) intermediário entre os valores das chaves dos registros contidos no 
mesmo nó. 
 
O particionamento de nós em uma Árvore B ocorre quando um registro precisa ser buscado em 
um nó com 2m + 1 registros. 
 
O particionamento de nós ocorre quando é necessário diminuir a altura da árvore. 
 O particionamento de nós em uma Árvore B ocorre quando um registro precisa ser inserido em 
um nó com 2m registros. 
 
O particionamento de nós em uma Árvore B ocorre quando um registro precisa ser inserido em 
um nó com menos de 2m registros. 
 
 
Explicação: 
O particionamento de nós em uma Árvore B ocorre quando um registro precisa ser inserido em um nó com 2m 
registros. 
 
 
10a 
 Questão 
Acerto: 1,0 / 1,0 
 
As afirmativas abaixo são feitas com base na estrutura de dados "Árvore Binária de Busca". Em relação 
ao algoritmo de busca em uma árvore binária de busca, analise as afirmativas abaixo: 
I -A complexidade da busca é definida pela altura da árvore binária de busca. No pior caso O(n). 
II - A busca é definida de forma recursiva, parte da raiz, comparando a chave buscada com a 
armazenada na raiz, caso seja igual temos o sucesso da busca, caso contrário, se a chave buscada for 
menor, devemos proceder recursivamente no ramo esquerdo, se a chave buscada for maior, proceder 
recursivamente no ramo direito. 
III - Sempre é necessário percorrer toda a árvore no algoritmo de busca. Em todos os casos, mesmo em 
árvores completas. 
IV - A condição de parada da busca é encontrar a chave buscada ou ter que descer por um ramo vazio. 
V - É possível escrever o algoritmo da busca de forma não recursiva. 
 
 I, II, IV e V são corretas. 
 
II, III, IV e V são corretas. 
 
I, II, III e IV são corretas. 
 
I, II, III, IV e V são corretas. 
 
I, III, IV e V são corretas. 
 
 
Explicação: 
A afirmativa III é incorreta, não é necessário percorrer todos os nós da árvore se ela estiver perfeitamente 
balanceada.