Simulado 2 - Estrutura de dados

Prévia do material em texto

Simulado 
1 - Seja a seguinte árvore de expressões aritméticas abaixo. 
 
O resultado da visita em prefixo dessa árvore é: 
R- + A * B C 
2 Seja a seguinte função em Python para percurso em uma árvore binária implementada em Python. Marque a opção 
correta de qual percurso em árvores se trata essa função: 
 
R – Percurso Pré-ordem. 
3 - Árvores de busca são organizadas de forma hierárquica, onde cada nó é um objeto que contém informação e 
cada nó filho é uma subdivisão da informação contida no nó pai. Sobre árvores binárias de busca, marque a opção 
correta. 
R - Seja T uma árvore binária completa com n > 0 nós. Então T possui altura mínima e h = 1 + [log n]. 
4 - Ao usar a biblioteca numpy para criar arrays, existem diversas facilidades que um programador pode utilizar, 
como funções específicas para somar todos os elementos, encontrar valores mínimo e máximo dos elementos, entre 
outros. 
Entretanto uma desvantagem de usar array da biblioteca numpy é: 
 R - Todos os elementos devem ter o mesmo tamanho. 
5 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? . 
R – 32 e 224. 
6 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) 
R – 100n + 5log n 
 
 
7 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: 
R - O(n), O(n) e O(n). 
8 - Uma árvore binária de busca auto balanceada é uma estrutura de dados avançada, que otimiza os tempos de 
inserção, deleção e busca. Um módulo Python que implementa e executa essas atividades eficientemente é 
a sbbst (do inglês, self-balancing binary search tree). A complexidade de espaço do módulo sbbst: 
R- 0(n). 
9 - Uma Deque é uma estrutura de dados mais generalista que as pilhas e filas. Para implementá-la de forma 
eficiente, você pode usar: 
R Lista duplamente encadeada com 2 variáveis: início e final. 
10 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 é: 
R - O(n2) significa que as operações variam em proporção quadrática à entrada.