Estrutura em Pyton

Prévia do material em texto

1a 
 Questão 
Acerto: 1,0 / 1,0 
 
Em Python é possível implementar um array utilizando o tipo padrão list. Essa implementação permite o uso das 
seguintes funções para inserir e remover um elemento, respectivamente: 
 
 append, remove/pop. 
 
insert, delete/pop. 
 
insert, remove/destroy. 
 
append, pop/delete. 
 
impose, remove/destroy. 
 
 
Explicação: 
Em Python a função append insere um elemento ao final da lista. As funções "remove" e "pop" podem remover um elemento, de 
maneiras diferentes. Remove tira um elemento conhecido usando o seu conteúdo, já pop remove um elemento usando seu índice, 
ou seja, a sua posição na lista. 
 
 
2a 
 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 é: 
 
 fat(n)=n*fat(n-1) 
 
par(n)=par(n) 
 
fib(n)=n-1 + n-2 
 
fat(1)=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. 
 
 
 
 
 
3a 
 Questão 
Acerto: 0,0 / 1,0 
 
O método de ordenação da bolha, ou Bubblesort (BS) tem complexidade de pior caso O(n2) e melhor caso O(n). 
Suponha que exista um algoritmo de ordenação MS que tem complexidade de melhor caso O(nlog n) e de pior caso 
O(nlog n). Podemos afirmar que: 
 
 
Para uma única entrada de tamanho grande, MS executará em menos tempo que BS. 
 Para uma única entrada de tamanho grande, BS executará em menos tempo que MS. 
 Para um grande conjunto de entradas variadas de tamanho grande, MS executará em menos tempo que BS, 
em média. 
 
Para um grande conjunto de entradas variadas de tamanho grande, BS executará em menos tempo que MS, 
em média. 
 
MS e BS são igualmente eficientes em ordenar elementos, independente da entrada ou seu tamanho. 
 
 
Explicação: 
Pela natureza do tratamento de complexidade de algoritmos e o uso da notação O, a única afirmativa verdadeira é a de que em 
média, com um grande número de entradas distintas e de tamanho grande, MS executará mais rápido que BS pois sua 
complexidade assintótica O(nlogn) é melhor que a de BS O(n2). 
A afirmação inversa está errada pelo mesmo argumento, O(nlogn) é melhor que O(n2). 
As afirmações que tratam de uma única entrada são falsas, pois você sempre pode escolher uma entrada que seja de melhor caso 
para um dos algoritmos e seja ruim para o outro. 
Por fim, a afirmação de que ambos são igualmente eficientes é desmentida pelo pior caso. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
4a 
 Questão 
Acerto: 1,0 / 1,0 
 
Uma Deque é uma estrutura de dados mais generalista que as pilhas e filas. Para implementá-la de forma eficiente, 
você pode usar: 
 
 
Lista contígua com 1 variável: início. 
 
Fila com 2 variáveis: início e final. 
 
Pilha com 1 variável: topo. 
 
Lista simplesmente encadeada com nó cabeça. 
 Lista duplamente encadeada com 2 variáveis: início e final. 
 
 
Explicação: 
Para implementar uma deque eficientemente, você precisa ter um ponteiro para o início e o final da deque, permitindo inserções e 
remoções em ambas as pontas com complexidade O(1) , sem a necessidade de percorrer a estrutura, o que seria O(n). 
Além disso, a fila é uma especialização da deque. Ou seja, toda fila é um deque, mas nem toda deque é uma fila. Podemos assim 
eliminar a resposta contendo fila. A resposta restante que possui 2 variáveis é a correta. Lista duplamente encadeada. Ela permite 
a inserção e remoção nas extremidades com complexidade O(1). 
A lista contígua e a simplesmente encadeada com nó cabeça levariam a operação de inserção e remoção ao final da fila terem 
complexidade O(n) por precisarem percorrer toda a estrutura, sendo também descartadas. 
 
 
5a 
 Questão 
Acerto: 1,0 / 1,0 
 
Em uma implementação da estrutura de dados do tipo fila, você possui um espaço de memória contíguo a ela alocada 
com capacidade para M nós. A variável da fila é F, e duas variáveis guardam os índices do início e final da fila (inicioF e 
finalF). Em uma implementação otimizada de F, como podemos identificar que a fila está cheia? 
 
 
InicioF== finalF 
 
InicioF==finalF + 1 
 InicioF==(finalF+1)mod M 
 
InicioF = M 
 
FinalF== M 
 
 
Explicação: 
Em uma implementação otimizada da fila, é usado um sistema modular, onde o início e o final da fila se movem a cada inserção e 
remoção. A cada inserção, finalF aumenta em 1, até o máximo M, depois volta para 0 e assim por diante. A cada remoção inícioF 
aumenta em 1, até o máximo M e depois volta a 0. dessa forma a fila está cheia quando (finalF+1)modM é igual a inicio. 
 
 
6a 
 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. 
 
Lista duplamente encadeada. 
 
Lista em alocação contígua. 
 
Fila. 
 
Lista simplesmente 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. 
 
 
7a 
 Questão 
Acerto: 0,0 / 1,0 
 
Seja a seguinte Árvore Binária. Marque a opção correta: 
 
 
 
A quantidade de nós da árvore é de n ¿ 1, sem considerar o nó raiz. 
 A árvore acima possui raiz de valor 3. 
 A quantidade de folhas da árvore é 4. 
 
Não é possível inserir nós filhos ao nó 70. 
 
É possível inserir mais um filho a esquerda no nó de valor 90. 
 
 
Explicação: 
A quantidade de folhas da árvore é 4, ou seja, são aqueles nós que possuem grau zero. 
 
 
8a 
 Questão 
Acerto: 1,0 / 1,0 
 
Marque a opção correta acerca da visita In-Ordem, usada em percursos de árvores binárias de busca: 
 
 
O percurso in-ordem inicia a visita pela raiz da árvore, depois visita as sub-árvores a esquerda e depois as sub-
árvores à direita em ordem assimétrica. 
 
O percurso in-ordem inicia a visita pela raiz da árvore, depois visita as sub-árvores a esquerda e depois as sub-
árvores à direita em ordem simétrica, terminando pela raiz principal. 
 
O percurso in-ordem inicia a visita pela raiz da árvore, depois visita as sub-árvores a esquerda e depois as sub-
árvores à direita em ordem simétrica. 
 
O percurso in-ordem inicia a visita nas sub-árvores a direita, depois visita a raiz da árvore e depois as sub-árvores 
à esquerda em ordem simétrica. 
 O percurso in-ordem inicia a visita nas sub-árvores a esquerda em ordem simétrica, depois visita a raiz da árvore 
e depois as sub-árvores à direita em ordem simétrica. 
 
 
Explicação: 
O percurso em ordem simétrica (In-ordem) é definido como se segue. A partir da raiz r da árvore T, percorre-se a árvore da 
seguinte forma: 
1 - percorre-se a sub-árvoresesquerda de T, em ordem simétrica e 
2 - visita-se a raiz; 
3 - percorre-se a sub-árvores direita de T, em ordem simétrica. 
 
 
9a 
 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, III, IV e V são corretas. 
 
I, II, 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. 
 
 
10a 
 Questão 
Acerto: 1,0 / 1,0 
 
Existem vários tipos diferentes de árvores de busca, como árvores binárias, AVL e árvores B. Nesse sentido, marque a 
opção correta sobre os procedimentos de rotação em árvores AVL: 
 
 Uma rotação simples à esquerda de um nó x acontece quando um desbalanceamento de x acontece à direita. 
 
Uma rotação simples à esquerda de um nó x acontece quando um desbalanceamento de x acontece à 
esquerda. 
 
Uma rotação simples à direita de um nó x acontece quando um desbalanceamento de x acontece à direita. 
 
Uma rotação dupla à esquerda de um nó x acontece quando um desbalanceamento de x acontece à esquerda. 
 
Uma rotação dupla à direita de um nó x acontece quando um desbalanceamento de x acontece à direita. 
 
 
Explicação: 
Em uma árvore AVL, uma rotação simples à esquerda de um nó acontece quando um desbalanceamento de acontece à direita. 
Se um nó desbalanceia para um lado, ele deve rotacionar de forma inversa para ficar balanceado.