Estrutura de dados

Prévia do material em texto

Introdução aos tipos abstratos de dados 
 
1. O tipo de dado que representa números é muito utilizado em programação; logo, é 
sua correta utilização durante o desenvolvimento de uma aplicação é fundamental. 
Suponha que você esteja analisando os tipos de dados para a implementação de uma 
aplicação voltada à contabilidade. Durante essa análise, você questiona qual tipo de 
dados uma variável deve utilizar para representar o número 10, visando à redução do 
custo de memória do computador. 
Você acertou! 
A. Int. 
O tipo int é utilizado exclusivamente para números naturais. 
O char é utilizado para representar um caractere. As demais opções (long int, 
double e float) fazem uso de mais memória em comparação ao int. 
2. Os tipos de dados booleanos têm características específicas em relação aos outros tipos 
de variáveis. A partir dessa afirmação, identifique a alternativa que apresenta um exemplo 
de dados booleanos: 
Você acertou! 
A. Verdadeiro ou falso. 
Dados booleanos são utilizados exclusivamente para demonstrar um estado em 
contraposição a outro, como verdadeiro/falso. 
O tipo booleano não poderá receber valores numéricos ou palavras, como as demais opções 
(Rua Paulista; 2,5; 10; 01/12/2019). 
3. Programas de computador fazem uso de diversas variáveis e operações. Em qual momento 
uma variável ocupa a memória do computador? 
Você acertou! 
C. Durante a execução do programa. 
As variáveis somente existem quando o programa está em execução, pois nesse momento 
está sendo utilizado um bloco de memória do computador. 
Durante a finalização do programa, a memória deverá ser liberada, e não alocada. Durante o 
desenvolvimento do programa ou a compilação, é verificada a estrutura do código, e não a 
alocação da variável em memória. 
4. A utilização de variáveis que consomem pouca memória é de suma importância para o 
desenvolvimento de aplicações com hardware limitado. Por isso, você precisa poupar 
memória no sistema de presença de uma universidade, na qual os computadores utilizados 
serão reciclados pelos alunos de anos iniciais. A partir das informações anteriores, qual tipo 
de variável deve ser utilizado para representar uma única letra do alfabeto visando à redução 
do custo de memória do computador? 
Você acertou! 
B. Char. 
Para a representação de um único caractere, seja ele uma letra, um símbolo ou um número, 
usa-se o tipo char. 
O tipo string é capaz de representar uma lista de elementos maiores que um caractere. Os 
tipos int, float e double são utilizados para representar números. 
5. Durante o desenvolvimento de uma aplicação, faz-se uso de diferentes tipos de dados. Na 
definição de tipos abstratos de dados (TAD), faz-se referência ao par (v,o). Qual é o 
significado desse par? 
Você acertou! 
C. (variável, operação). 
Formalmente, pode-se definir TAD como um par (v,o), em que ‘v’ representa uma ou mais 
variáveis, e ‘o’ , uma ou mais operações. 
 
 
Listas sequenciais: estáticas e dinâmicas 
 
1. A linguagem Python possibilita a armazenagem de diferentes tipos de dados em um 
mesmo vetor. A partir desse contexto, um programador implementou o seguinte código: 
#declaração do vetor 
Aluno = ['A',20,60,'casa',3] 
print(Aluno[-1]) 
Qual será a saída do programa? 
Você acertou! 
E. 3. 
Em Pyhon, o programador poderá acessar cada elemento de forma individual e circular, 
logo, a posição -1 representa o último elemento do vetor. 
Posição ==> Conteúdo 
0 ou -5 ==> A 
1 ou -4 ==> 20 
2 ou -3 ==> 60 
3 ou -2 ==> casa 
4 ou -1 ==> 3 
 
2. A linguagem Python possibilita o acesso direto a um elemento de um vetor. O índice de 
acesso tem o comportamento circular. A partir dessa afirmação, no vetor abaixo, qual o 
índice correspondente à primeira posição 0 (zero)? vetor = ['A','B','C','D','E'] 
Você acertou! 
C. -5. 
A posição correspontende à posição zero é a -5, de acordo com a tabela abaixo: 
Posição ==> Conteúdo 
0 ou -5 ==> A 
1 ou -4 ==> B 
2 ou -3 ==> C 
3 ou -2 ==> D 
4 ou -1 ==> E 
3. O vetor deverá corresponder a uma lista de elementos na qual cada nodo deverá 
armazenar uma informação. A partir dessa informação, qual é a posição ocupada pelo último 
elemento do vetor a seguir? vetor = [1,2,5,7,9] 
Você acertou! 
B. 4. 
As posições de um vetor são numerados a partir do valor zero, sendo zero para o primeiro 
elemento e, consequentemente, aos demais elementos do vetor. 
Posição ==> Conteúdo 
0 ou -5 ==> 1 
1 ou -4 ==> 2 
2 ou -3 ==> 5 
3 ou -2 ==> 7 
4 ou -1 ==> 9 
4. A lista encadeada é muito utilizada para armazenar um número indefinido de elementos. 
Em uma lista encadeada simples, cada nodo possui duas informações. Quais são elas? 
Você acertou! 
A. Conteúdo e índice do próximo nodo. 
Uma lista encadeada simples possui sempre o seu conteúdo e o seu endereço de memória 
(índice) do próximo nodo. Os nodos não têm o conhecimento do seu respectivo lugar na lista, 
ou seja, não sabem a sua origem ou nodo anterior, pois não armazenam essa informação; são 
independentes e desconhecem o tamanho da lista. 
5. As listas encadeadas simples e os vetores têm diversas vantagens e desvantagens 
comparadas entre si. Qual das informações a seguir é uma vantagem das listas encadeadas 
simples, se comparada a vetores? 
Você acertou! 
C. Têm o seu tamanho flexível em tempo de execução. 
As listas encadeadas simples têm em seu nodo o seu respectivo conteúdo e o endereço de 
memória do próximo, logo ocupam mais memória que um vetor; poderão aceitar elementos 
durante a sua utilização definidos pelo usuário, desde tipos primitivos a abstratos, criados pelo 
programador; e, por não terem tamanho fixo ou previamente definido, não poderão ser 
listadas por comando for predeterminado, havendo a necessidade de adicionar um break. 
Listas encadeadas simples 
1. A análise e o desenvolvimento de algoritmos com o uso de listas encadeadas são de suma 
importância no desenvolvimento de uma aplicação. Durante essa ação, o desenvolvedor 
precisa realizar a análise prévia dos códigos de uma determinada aplicação para iniciar seu 
desenvolvimento. 
Analise o algoritmo a seguir e marque a alternativa que representa seu significado: 
def acao(self,item): 
 atual = self.inicio 
 status = False 
 while atual != None and not status: 
 if atual.dado()==item: 
 status = True 
 else: 
 atual = atual.prox() 
 return status 
Você acertou! 
C. Procura um elemento na lista. 
O algoritmo inicia com o apontamento para o início da lista e declara uma variável como 
Falso. No segundo momento (comando While), percorre a lista enquanto não chegar ao 
seu final e o status for diferente de Falso. Dentro do laço com o comando IF, verifica se 
o dado recebido na função encontra-se no Nodo; caso afirmativo, troca o status para True, 
informando que encontrou o valor. 
Ao final, retorna o status se encontrou ou não o conteúdo na lista. 
2. A lista simplesmente encadeada é uma lista do tipo dinâmica e apresenta vantagens em 
relação a listas estáticas, como vetores. A partir da afirmação anterior, marque a opção que 
informa uma das vantagens das listas simplesmente encadeadas. 
Você acertou! 
B. Permitem variação de seu tamanho em tempo de execução. 
Uma lista simplesmente encadeada permite o aumento e a redução do número de 
elementos em tempo de execução, sem precisar alocar posições contínuas de memória, como 
corre em listas estáticas. Na lista encadeada não existe busca de acordo com a indexação, pois 
a pesquisa é realizada sequencialmente a partir do primeiro elemento, Nodo. A inserção e a 
remoção de elementos podem ser realizadas em qualquer posição, sem a necessidade de 
reordenação dos demais elementos, mas, apesar disso, requerem percorrer nodo a nodo até 
sua posição. 
 
3. A análise e o desenvolvimento de algoritmos com o uso de listas encadeadas são de suma 
importância no desenvolvimento de uma aplicação. Durante essa ação, o desenvolvedor 
precisa realizar a análise prévia dos códigos de uma determinada aplicação para iniciar seu 
desenvolvimento. Analiseo algoritmo a seguir e marque a alternativa que representa seu 
significado: 
 
 
1 def acao (self,item) 
2 temp = No(item) 
3 temp.prox(self.ini) 
4 self.ini = temp 
Você acertou! 
B. Adiciona um novo elemento no início da lista. 
A função, na linha 1, recebe como parâmetro um valor que será utilizado internamente. Na 
linha 2, realiza a criação de um No com o dado recebido. Na linha 3, realiza a atualização do 
ponteiro prox para o primeiro elemento da lista. Na linha 4, adiciona o ponteiro do início da 
lista para o novo No, inserindo o elemento sempre no início da lista. 
4. A lista simplesmente encadeada é uma lista do tipo dinâmica e apresenta vantagens em 
relação a listas estáticas, como vetores. A partir dessa afirmação, marque a opção que 
informa um tipo de lista em que é mais apropriado utilizar listas simplesmente encadeadas 
em detrimento de listas do tipo estáticas, como vetores. 
Você acertou! 
C. Listas grandes que realizam diversas inserções em diferentes posições. 
Uma lista simplesmente encadeada é recomendada para utilização em grandes listas, que 
podem ter muitas inserções e exclusões em quaisquer posições, cujo tamanho é indefinido. 
Por ser uma lista dinâmica, não tem sua pesquisa indexada e a varredura ocorre apenas em 
uma direção, pois possui somente o apontamento para o próximo elemento da lista. 
5. As listas simplesmente encadeadas possuem características únicas em seus nodos, 
diferentemente das listas estáticas. Em relação a essas características únicas, leia as 
alternativas a seguir e selecione a correta. 
Você acertou! 
D. O nodo tem seu conteúdo definido pelo usuário e um ponteiro para o próximo elemento. 
Uma lista simplesmente encadeada possui em seu nodo uma variável com a posição de 
memória do próximo elemento, bem como seu respectivo conteúdo. Devido a essa 
característica, seu armazenamento não precisa ser linear em memória, pois armazena a 
localização do próximo nodo. 
 
Implementação de listas encadeadas simples 
1. A análise de códigos é de suma importância para o desenvolvimento de um programador, 
sendo uma das tarefas mais comuns no seu dia a dia, seja na compreensão do 
desenvolvimento complementar, seja durante os seus estudos. 
Realize a análise do código a seguir e assinale a alternativa que contém o seu objetivo: 
def Metodo(self): 
atual = self.inicio 
self.inicio = atual.proximo 
Você acertou! 
C. Realizar a exclusão do primeiro nodo. 
Método que realiza a remoção do primeiro elemento: 
def Remove_Inicio(self): 
#Realiza a atribuição do início da lista para um o nodo atual. 
atual = self.inicio 
#Atualiza o primeiro elemento da lista para o elemento posterior ao primeiro nodo, excluindo 
o nodo inicial. 
self.inicio = atual.proximo 
 
 
 
 
2. As operações de manipulação de uma lista simplesmente encadeada permitem a 
manipulação de seus nodos durante sua execução. Analise o código a seguir e informe qual 
o seu objetivo: 
def Metodo(self): 
atual = self.inicio 
if self.inicio == None: 
 print("none") 
else: 
 while atual != None: 
 print(atual) 
 atual = atual.proximo 
Você acertou! 
C. Realizar a impressão de uma lista. 
#Realiza a impressão de todos os elementos de uma lista def Impressão(self): 
#Ponteiro atual recebe o início da lista: 
atual = self.inicio 
#verifica se a lista encontra-se vazia e informa o usuário if self.inicio == None: 
print("none") 
#Caso a lista tenha conteúdo, percorre toda a lista e imprime em cada interação o seu 
respectivo conteúdo. else: 
while atual != None: 
print(atual) 
atual = atual.proximo 
3. O desenvolvimento de listas encadeadas pode ser realizado de diversas formas, com ou 
sem o uso de bibliotecas. O método da biblioteca de listas chamado append(Elemento) realiza 
qual função no código? 
Você acertou! 
B. Adiciona um elemento ao final da lista. 
#Código em Python: 
 # Lista de letras 
 letras= ['A', 'H', 'T'] 
 # Metodo que adiciona a letra D no final da lista 
 animais.append('D') 
 # imprime a nova lista 
 print('Atualização da lista: ', letras) 
#Saída do programa 
 # Atualização da lista: ['A', 'H', 'T','D'] 
4. As bibliotecas utilizadas em programação auxiliam no desenvolvimento de listas 
simplesmente encadeadas. O método da biblioteca de listas chamado index(Elemento) realiza 
qual função no código? 
Você acertou! 
D. Retorna à posição da primeira ocorrência do elemento na lista. 
• #Código em Python: 
 # Lista de letras 
 letras = ['A', 'G', 'P','G'] 
 # imprime a lista 
 print(letras) 
 # Retorna e imprime a posição da primeira ocorrência do elemento G 
print(letras.index('G')) 
#Saída do programa 
 # ['A', 'G', 'P','G'] 
 #1 
5. Os métodos para a criação das classes nodo, lista encadeada, verificação de lista vazia, 
adicionar e remover posição na lista são elementos básicos no que se refere à implementação 
de listas encadeadas simples. Analise o código a seguir e informe qual o seu objetivo: 
def Metodo(Lista): 
 if Lista.inicio == None : 
 return True 
 else: 
 return False 
Você acertou! 
C.Verificar se a lista está vazia. 
#Método que verifica se a lista está Vazia, Caso positivo Retorna True caso contrário False. 
def ListaVazia(Lista): 
# Verifica se o ponteiro para o início da lista está vazio, se positivo retorna True, logo lista 
vazia. 
if Lista.inicio == None : 
return True 
#Caso o item anterior seja falso, retorna Falso, logo lista contém itens na lista. 
 else: 
return False 
 
 
Listas encadeadas duplas 
1. Uma lista duplamente encadeada tem como estrutura duas referências, o que permite que 
a lista seja percorrida em dois sentidos: do início ao fim e do fim ao início. Atendendo a essa 
propriedade, dos exemplos a seguir, quais se aplicam para uma lista duplamente encadeada? 
Você acertou! 
B. Sistemas de paginação web, comandos de desfazer (CTRL + Z) e refazer (CTRL + SHIFT + 
Z) operações, lista de espera de compras e visualizador de imagens. 
As listas duplamente encadeadas são bem aplicadas em problemas em que seja 
necessário realizar operações de navegação entre elementos do início ao fim e do fim para o 
início, como no caso de sistemas de paginação web, comandos de desfazer (CTRL + Z) e 
refazer (CTRL + SHIFT + Z) operações, lista de espera de compras, visualizador de imagens 
e playlist de músicas. 
Os exemplos sistema de georreferenciamento, sorteio de número aleatório, fila de 
atendimento, paginação unilateral, soma de dois números e ordenação de números não 
necessitam dessa estrutura de dados, além de não ser possível armazenar dados não 
sequenciais nessas listas. 
 
 
2. As listas duplamente encadeadas apresentam algumas características que precisam ser 
bem definidas para o seu adequado funcionamento. Quais são essas características? 
Você acertou! 
A. Definir um ponteiro para o primeiro e o último elemento da lista; o ponteiro anterior, 
referente ao primeiro elemento da lista, aponta para um endereço NULO; e o último 
elemento aponta para um endereço NULO. 
Uma lista duplamente encadeada pode armazenar tanto dados primitivos como estruturas de 
dados abstratos, e não necessita de ordenação em seus elementos. As principais 
características para o seu bom funcionamento são: 
Definir um ponteiro para o primeiro e o último elemento da lista; o ponteiro anterior, 
referente ao primeiro elemento da lista, aponta para um endereço NULO; e o último elemento 
aponta para um endereço NULO. 
3. Com uma lista duplamente encadeada implementada sobre um vetor ou alocação 
dinâmica, é possível definir algumas ações para o gerenciamento dos elementos contidos 
nela. Quais são essas ações? 
Você acertou! 
E. Percorrer elementos, inserir elemento, remover elemento e buscar elemento. 
Para gerenciar os dados de uma lista duplamente encadeada, as ações definidas são: percorrer 
elementos, inserir elemento, remover elemento e buscar elemento. As demais ações citadas 
são possíveis de se realizar com pequenasoperações, sem necessidade de implantá-las 
na lista. 
4. Entre as ações de uma lista duplamente encadeada, está a inserção. A inserção de um 
elemento em uma lista dupla pode ser realizada de três maneiras. Quais são essas maneiras? 
Você acertou! 
C. No início da lista, em alguma posição intermediária e no final da lista. 
Sempre que algum elemento for adicionado à lista, é importante que sejam mantidas as 
ligações de referências dos apontadores para os elementos anteriores e posteriores. Logo, é 
possível realizar a inserção de três formas: no início da lista, em alguma posição intermediária 
e no final da lista. 
As demais operações, tais como ordenadamente e aleatoriamente, não são formas de 
inserção, mas sim de possíveis operações. 
5. Cada projeto carrega sua particularidade, assim, uma lista pode conter vários métodos 
associados a ela, alguns mais conhecidos, como: criar uma lista vazia, verificar se a lista está 
vazia, verificar se a lista está cheia, entre outros. Nesse contexto, para a inserção de um 
elemento nas listas duplamente encadeadas, quais critérios devem ser atendidos? 
Você acertou! 
A. Verificar se existe espaço, adicionar o contador de itens e alocar um espaço para inserir 
um novo elemento. 
A inserção de elementos nas listas duplamente encadeadas pode ser realizada de três formas: 
início, intermédio e final. Além disso, deve atender a alguns critérios, tais como: verificar se 
existe espaço para inserir um novo elemento; acomodar um espaço para inserir um novo item 
e assegurar que os outros elementos não ficarão com uma referência vazia, a menos que os 
elementos sejam incluídos no final da lista; e adicionar o contador de itens. As outras opções 
citadas são critérios desnecessários. 
 
Implementação de listas encadeadas duplas 
 
1. Existem várias formas de implementar as listas duplas. Entre os tipos, há as listas duplas 
com cabeça fixa. Logo, qual seria a vantagem em utilizar listas com cabeça fixas? 
Você acertou! 
A. Listas com cabeça fixa permitem e carregam sempre seu valor em seu início, não 
necessitando de ponteiros como início e fim. 
Listas com cabeça fixa não precisam recorrer a mais elementos de uma lista, como os 
ponteiros nomeados como início e fim, por exemplo, para poder percorrê-la, pois seu 
endereço já carrega o início da lista consigo. 
Logo, o endereço nomeado como cabeça fixa não deve também conter nenhuma informação, 
sendo apenas uma sentinela para acessar o primeiro elemento que contenha informação em 
uma lista. 
Uma das propriedades das listas de cabeça fixa é que seu ponteiro anterior aponte para 
uma referência nula. Além disso, funções básicas de inserção, remoção e impressão, etc., 
permanecem. 
 
 
2. As listas duplas são vistas como vias de mão dupla, em que é possível percorrê-las em duas 
direções. Uma vez implementada, como transformá-la em uma lista circular? 
Você acertou! 
D. Para que uma lista dupla seja circular, o endereço de próximo do último elemento deve 
apontar para o primeiro, e o endereço nulo apontado pelo ponteiro anterior do primeiro 
elemento, deve apontar para o último. 
O que diferencia as listas circulares de outras é que nelas o último elemento aponta para o 
primeiro e vice-versa, em caso de ponteiros duplos, não fazendo referência a endereços 
nulos, mesmo que exista apenas um elemento. 
3. Fazer a análise de um algoritmo, por natureza, envolve entender a sua complexidade. 
Por que as funções de inserção têm complexidade O(1) e remoção O(n) para os piores casos? 
Você acertou! 
B. De forma intuitiva, a inserção é feita de forma direta O(1), enquanto a remoção depende 
de percorrer (n) elementos na lista. 
Antes da remoção, é realizada a busca do elemento, tendo no pior caso que percorrer uma 
somatória de elementos, ou seja, por todos os elementos; enquanto a inserção é feita de 
modo direto, sem a necessidade de passar por nenhum elemento anterior, justamente pelos 
ponteiros de referência início e fim. 
4. Os problemas computacionais têm entradas bem estabelecidas, restrições e condições 
que satisfazem os valores de saída. As listas duplamente encadeadas podem ser usadas de 
acordo com a necessidade de cada problema, devido aos aspectos de uma lista. 
As listas podem ter diferentes aspectos, quais são esses aspectos? 
Você acertou! 
E. Tipo de informação: pode armazenar qualquer tipo de informação; ordem dos 
elementos: conforme a política de negócio; homogeneidade da informação: os elementos de 
uma lista podem ser representados pelo mesmo tipo de dado ou armazenar tipos de dados 
diferentes. 
As listas podem ter diferentes aspectos, tais como: 
Tipo de informação: neste caso, a lista pode armazenar qualquer tipo de informação, como 
nome, endereço, contatos, entre outros elementos existentes no mundo real. 
Ordem dos elementos: aqui, varia conforme a política de negócio, podendo estar em ordem 
de inserção, em ordem crescente ou decrescente, etc. 
Homogeneidade da informação: todos os elementos de uma lista podem ser representados 
pelo mesmo tipo de dado (inteiro, string ou uma classe criada), ou armazenar tipos de dados 
diferentes. Em linguagens fracamente tipadas, como Python e PHP, por exemplo, este 
comportamento é visto com maior naturalidade. 
Os demais aspectos não fazem ou não são comportamentos de uma lista duplamente 
encadeada: tipo do problema, complexidade, forma da lista ou linguagem de programação. 
5. Entre os diversos tipos de listas duplamente encadeadas, existe uma versão chamada de 
lista encadeada XOR. Em relação a uma lista duplamente encadeada simples, qual a principal 
característica de uma lista encadeada XOR? 
Você acertou! 
C. Armazenar endereços de memória reais; cada nó armazena o XOR dos endereços dos nós 
anteriores e dos próximos, necessitando de apenas um espaço de memória. 
Uma versão com eficiência de memória da lista duplamente vinculada pode ser criada usando 
apenas um espaço para o campo de endereço em cada nó. Essa lista vinculada duplamente 
eficiente em memória é chamada de lista vinculada XOR ou memória eficiente, pois a lista usa 
a operação XOR bit a bit para economizar espaço para um endereço. 
As listas duplamente encadeadas seguem a propriedade que, a partir de um determinado 
elemento, seja possível tanto avançar quanto voltar, logo, as outras opções estão incorretas. 
 
 
Implementação de Pilhas em Python 
1. A pilha é uma estrutura que permite a inserção e a remoção dos dados utilizando-se de 
regras predefinidas. Essas operações são realizadas por meio de duas funções: push e pop. 
Sabendo disso, considere que um programa tenha uma pilha a, inicialmente vazia, e que as 
seguintes operações foram realizadas: PUSH(a, 10); PUSH(a, 5); PUSH(a, 3); PUSH(a, 50); 
POP(a); PUSH(a, 11); PUSH(a, 9); PUSH(a,20); POP(a); POP(a). 
Ao final, quais serão o topo da pilha e o somatório dos elementos ainda dentro da pilha, 
respectivamente? 
Você acertou! 
B. 11 e 29. 
Considerando a execução de cada um dos comandos na sequência apresentada, 11 é o valor 
final do topo, e a somatória dos elementos restantes será: 11+3+5+10= 29. 
2. Sabendo que a pilha é uma estrutura que utiliza um único caminho para a entrada e a saída 
de seus elementos, sendo esse o topo da pilha, considere que os números 10, 11, 12, 13 e 
14 foram inseridos nessa ordem. Então, nesse caso: 
Você acertou! 
C. o número 14 é o primeiro elemento a ser removido da pilha. 
Como a pilha utiliza-se do modelo last in, first out, e o número 14 foi o último a ser inserido, 
ele é o primeiro a ser removido. 
3. Estruturas de dados, como pilhas e filas, são utilizadas em diversas aplicações, tendo cada 
uma delas comandos e funções específicas para a manipulação dos elementos que as 
compõem. Assim sendo, qual método é de uso da estrutura de pilha? 
Você acertou! 
C. Push(x), que insere o elemento x no topo da pilha sem sobrepor nenhum elemento. 
Push(x) é a função correta para a inserção de novos elementos em uma pilha, sem a 
sobreposição dos elementos já existentes, ajustando o novoelemento com os demais na 
pilha. 
Stack() cria uma pilha vazia. 
Dequeue() remove e retorna o item do início da fila. Um item não pode ser retirado de uma 
fila vazia. 
Pop() remove e retorna o item superior da pilha se a pilha não estiver vazia. 
Top() não é uma função válida em Python. 
 
 
 
 
 
 
 
 
 
 
 
4. mas Todas as estruturas de dados têm o que chamamos de local para entrada e saída de 
dados, e com as pilhas não é diferente, sendo esse local o seu topo. Sabendo disso, considere 
os estados inicial e final da pilha apresentada a seguir: 
 
 
 
 
 
 
 
 
 
 
 
 
Você acertou! 
A. Pop(), Pop(), Push(9), Push(3). 
Se todos os comandos forem executados nesta mesma ordem - Pop(), Pop(), Push(9), Push(3), 
a pilha será exibida no estado final, sendo removidos os itens 2 e 8, e inseridos 3 e 9. 
5. Px é uma pilha com 5 posições, v(1) a v(5), na qual v(5) é o topo. De v(1) até v(5), a pilha Px 
está preenchida, respectivamente, com os símbolos Q5, Q3, Q1, Q4, Q2. Há mais duas pilhas, 
inicialmente vazias, Py e Pz, com o mesmo tamanho. Qual é a quantidade mínima de 
movimentos entre as três pilhas para que a pilha Px, originalmente cheia, esteja preenchida 
de v(5) até v(1), respectivamente, com os símbolos Q1, Q2, Q3, Q4, Q5? 
Você acertou! 
C. 8. 
Seguindo as especificações dos movimentos, a quantidade mínima de movimentos entre as 
três pilhas para que elas cheguem ao preenchimento desejado de Px é de 8 movimentos. 
 
Implementação de Filas em Python 
1. Existem diferentes tipos de estruturas que são utilizadas para organizar dados. Qual 
dessas estruturas é representada como uma lista linear de elementos nos quais a exclusão 
pode ser feita de uma extremidade (início) e a inserção pode ocorrer apenas na outra 
extremidade (fim)? 
Você acertou! 
A. Fila. 
A lista linear de elementos nos quais a exclusão é feita na parte frontal e a inserção na parte 
traseira é chamada de fila, a qual utiliza o modelo first in, first out, FIFO. 
As pilhas utilizam o princípio LIFO, last in, first out, em que há inserção em apenas uma 
extremidade. 
Árvores tem os nós acessados por meio de busca direta, não seguindo o princípio FIFO. 
Em listas vinculadas aponta-se um ponteiro para os elementos que se deseja incluir/remover, 
não sendo utilizado, assim, o princípio FIFO das filas. 
Arrays têm seus elementos inseridos por meio de busca direta, não utilizando o princípio FIFO 
das filas. 
2. Existe um conjunto de operações básicas que podem ser realizadas sobre filas; algumas 
operações permitem manipulação, enquanto outras apenas retornam consultas sobre as 
filas. Entre as operações a seguir, qual delas retorna um valor booleano? 
Você acertou! 
C. estaVazia(). 
A operação que retorna um booleano é a estaVazia(), que retorna True se a fila estiver vazia, 
e False caso contrário. 
A operação tamanho() devolve um inteiro, com a quantidade de itens na fila. 
A operação primeiro() retorna (mas não remove) uma referência ao primeiro elemento da fila. 
Já a operação fila() cria uma fila vazia, enquanto a operação enfilera(item) adiciona um item 
no final da fila. 
3. Em cada estrutura de dados é utilizado um processo para inserção e remoção de 
elementos. Todo tipo de estrutura, seja fila, pilha ou árvore, tem funções que auxiliam nesse 
processo. Sendo assim, se os elementos A, B, C e D forem colocados nesta ordem em uma 
fila e excluídos um de cada vez, em que ordem serão removidos? 
Você acertou! 
C. ABCD. 
A fila segue a abordagem FIFO, ou seja, abordagem primeiro a entrar, primeiro a sair. Portanto, 
a ordem dos elementos de remoção é ABCD, a mesma ordem em que foram inseridos. 
DCBA representaria uma pilha, que segue a abordagem LIFO, na qual o último a entrar é o 
primeiro a sair. 
As alternativas DCAB, ABDC e ACDB poderiam ser implementadas com árvores ou listas, por 
exemplo. 
4. Python disponibiliza diversas bibliotecas que facilitam a manipulação de diferentes 
estruturas de dados. Utilizando a biblioteca Python queue, com a seguinte implementação: 
 
import queue 
f = queue.Queue() 
f.put("abacate") 
f.put("amora") 
f.put("abacaxi") 
f.put_nowait("uva") 
f.get() 
f.get_nowait() 
f.put("pêra") 
f.put("amora") 
print(list(f.queue)) 
Qual seria a fila resultante? 
Você acertou! 
E. ['abacaxi', 'uva', 'pêra', 'amora']. 
O código em questão faz a criação de uma fila de nome f (f = queue.Queue()), depois adiciona 
3 elementos na fila (abacate, amora, abacaxi). 
Então, com os comandos get e get_nowait, os dois primeiros elementos são removidos da fila 
(abacate, depois amora) e, por fim, outros dois elementos são adicionados (pêra e amora), 
sendo assim, a fila resultante é ['abacaxi', 'uva', 'pêra', 'amora']. 
O resultado [] é uma lista vazia, e teria sido obtido se fosse parado na segunda linha de código. 
O resultado ['abacate', 'amora', 'abacaxi', 'uva', 'pêra', 'amora'] só seria possível se não 
houvesse os dois comandos de remoção da fila (get e get_nowait). 
O resultado ['abacate'] só seria possível se fosse parado na terceira linha, e adicionado 
somente mais uma linha de impressão. 
Por fim, o resultado ['abacate', 'amora', 'abacaxi', 'uva'] só seria possível se, após inserir “uva”, 
fosse finalizado com uma linha de impressão. 
5. Há diversas situações no cotidiano que poderiam ser representadas por diferentes 
estruturas de dados, como filas, pilhas, árvores, deques, entre outras. Entre as situações 
reportadas a seguir, qual melhor se encaixa com a estrutura do tipo fila? 
Você acertou! 
C. Documentos esperando para serem impressos em uma impressora. 
Documentos esperando para serem impressos em uma impressora melhor representam a 
estrutura de fila, em que o primeiro a ser enviado será o primeiro a ser impresso (first in, first 
out). 
Uma torre com pratos sobrepostos em uma mesa pode ser representada por uma pilha. 
A visualização do resultado da Copa do Mundo pode ser feita utilizando uma árvore, visto que 
o conjunto de times que passa para a próxima fase vai reduzindo até chegar ao campeão, que 
será o nodo raiz da árvore. 
Por fim, a relação de filmes indicados ao Oscar, assim como uma lista de itens a serem 
comprados no supermercado poderia ser implementada com uma lista comum. 
 
Implementação de Deques em Python 
1. Existem diferentes estruturas de dados que podem ser usadas para estruturar algoritmos 
que resolvam problemas relacionados a containers de dados, e a escolha de qual usar 
depende do problema a ser resolvido. Entre as opções a seguir, qual delas melhor define uma 
deque? 
Você acertou! 
A. Uma estrutura com inserção/exclusão possível nos extremos frontal e traseiro da fila. 
Deque é uma estrutura que permite inserir e remover tanto pela cabeça quanto pela 
cauda. Em pilhas, é possível inserir e remover apenas em uma das extremidades. Nas filas, é 
possível inserir apenas em uma extremidade e remover apenas na outra extremidade. Já as 
árvores são hierárquicas, e os dados são inseridos iniciando-se pelo nó raiz. Em deques, não 
há a obrigatoriedade de inserir e recuperar dados de forma ordenada: eles podem ser inseridos 
na ordem em que forem gerados. 
2. Usando a biblioteca Collections, é possível aproveitar alguns métodos já prontos para a 
manipulação de deques. Após executar o código abaixo, qual seria o resultado esperado na 
impressão? 
import collections 
d = collections.deque('abcd') 
d.appendleft('d') 
print (d) 
Você acertou! 
E. Inclusão do ‘d’ à esquerda. 
O resultado do print será: deque(['d', 'a', 'b', 'c', 'd']), incluindo um ‘d’ à esquerda da deque que 
foi criada inicialmente. Para incluir à direita, o comando da linha 3 deveria ser d.append('d'). 
Para remover o ‘d’, o comando seria d.pop(); para imprimir a letra ‘d’, o comando na quarta 
linha seria print ('d'); e, para imprimir a deque inicial, o comando print (d) deveria ser movido 
para a terceira linha. 
3. Entre os métodos já implementados na biblioteca Collections, estão métodos para 
remoção dos elementos em uma deque. Considere que inicializamos uma dequeda seguinte 
forma: d = collections.deque('6598732') Qual comando utilizamos para remover o elemento 
2? 
Você acertou! 
C. d.pop(). 
Para remover o elemento 2, utilizamos o comando d.pop(), pois ele está à direita na 
deque. Esse comando não recebe parâmetros; portanto, não podemos colocar dentro do 
parêntese o valor a ser removido. Por esse motivo, as alternativas d.pop(2) e d.popright(2) 
estão incorretas. Adicionalmente, o comando popright() não existe na sintaxe, visto que, como 
a eliminação padrão em uma fila é pela direita, o comando, nesses casos, é o pop(). Ao 
utilizarmos o comando d.popleft(), seria eliminado o primeiro elemento da esquerda, ou seja, 
o 6, e não o 2, como pede o enunciado. 
4. A linguagem de programação Python facilita a manipulação de estruturas de dados a partir 
do uso de bibliotecas com comandos que, em poucas linhas, ajudam a inserir, remover, fazer 
consultas, entre outras funcionalidades. Utilizando a biblioteca Collections, qual seria a 
deque resultante da seguinte sequência de operações? 
import collections 
d = collections.deque() 
d.extend('abcd') 
d.pop() 
d.append('j') 
d.appendleft('z') 
d.pop() 
print (d) 
Você acertou! 
A. deque(['z', 'a', 'b', 'c']). 
Após a criação da deque com os elementos 'abcd', foi removido o 'd', adicionado o 'j' à direita, 
adicionado o 'z' à esquerda e removido o 'j'. Dessa forma, o resultado é deque(['z', 'a', 'b', 
'c']). Se, no lugar do comando pop da linha 7, tivéssemos o comando d.reverse(), o resultado 
seria deque(['j', 'c', 'b', 'a', 'z']). Se houvesse um d.clear()no lugar do comando pop da linha 7, o 
resultado seria uma deque vazia: deque([]). Esta deque(['a', 'b', 'c', 'd']) é o resultado inicial, 
após o comando extend da linha 2, que é usado para adicionar múltiplos valores à direita da 
fila. Esta deque(['z', 'a', 'b', 'c', 'j']) seria resultante se não houvesse o d.pop()da linha 7, que 
removeu o 'j'. 
5. A computação simula o mundo real, criando ambientes e estruturas baseados no 
funcionamento de processos já existentes no dia a dia. Qual dos seguintes cenários do 
mundo real você associaria a uma estrutura de dados do tipo deque? 
Você acertou! 
C. Check-in de embarque em um voo nacional. 
A oferta de serviços com base na prioridade do cliente, como o check-in em um voo, é um 
exemplo que pode ser implementado usando-se deques. As crianças em fila para andar no 
carrossel podem ser um exemplo de filas simples, em que não é necessário priorização. Uma 
árvore pode representar a hierarquia em uma empresa, e uma coleção de revistas sobrepostas 
pode ser representada por uma pilha. 
 
Métodos de pesquisa em listas: sequencial, binária e tabelas 
hash 
1. A busca sequencial é uma técnica simples e intuitiva para buscar elementos em vetores 
ou listas. Tendo a informação de que os dados estão ordenados de forma crescente, qual 
otimização você pode aplicar na busca sequencial? 
Você acertou! 
D. Parar a execução e informar que o valor não existe, quando o valor atual for maior que o 
buscado. 
O desempenho de pior caso da busca sequencial pode ser otimizado sabendo-se que o vetor 
está ordenado. Para tanto, continua-se a buscar um elemento enquanto o elemento atual for 
maior que o buscado. No momento em que ele for menor, sabe-se que o vetor é ordenado e, 
no futuro, não será possível encontrar outro elemento maior. O contrário não é verdade, pois, 
caso seja encontrado um valor menor que o buscado, ainda é possível achar valores maiores 
no futuro. Funções hash podem ser utilizadas apenas em tabelas hash. Ainda, descobrir a 
posição de um elemento sem buscar em várias posições do vetor também só é possível em 
tabelas hash. 
2. A busca binária é uma técnica eficiente para buscar elementos em vetores ou listas. A 
única restrição desse método é que o vetor ou a lista estejam ordenados. Das seguintes 
sequências de acessos em um vetor, qual é válida em uma execução de busca binária? 
Você acertou! 
C. 5, 2, 1. 
Em cada iteração da busca binária, o elemento do meio do intervalo atual é acessado. Nesse 
sentido, para acessar a posição 1, é necessário que o tamanho do intervalo seja 2. Assumindo 
que o vetor tivesse tamanho 2, não seria possível nas alternativas (1, 2, 5) e (1, 5, 2) acessar 
elementos maiores que 2 após esse primeiro acesso. No caso da alternativa (5, 7, 3), o 
problema vai quando o elemento 5 é acessado e logo todos os menores que 5 são ignorados, 
mas, logo após, o número 3 é acessado. O mesmo ocorre na alternativa (5, 2, 8). Portanto, a 
alternativa correta é (5, 2, 1), um vetor de tamanho 10; o primeiro acesso é o 5, após a metade 
é o 2 e, por fim, o 1. 
3. Tabelas hash são estruturas muito eficientes utilizadas por diversas linguagens de 
programação e serviços. Entender seu funcionamento é crucial para o desenvolvedor, o qual 
deverá decidir o tamanho da tabela e a função hash que otimiza o desempenho de 
determinada aplicação. Considere uma tabela hash de 5 posições (de 1 a 5, aceitando 
repetições) e uma função hash que representa a i-ésima letra do alfabeto com o número i. 
Quantas colisões ocorrem após a inserção das chaves: A, B, A, C, A, E? 
Você acertou! 
B. 2. 
Uma tabela hash de 5 posições tem índices de 1 a 5. A função hash converte um caractere 
para um índice de acordo com a ordem no alfabeto. Por exemplo, a letra A é 1, a letra B é 2, 
e assim por diante. Nesse sentido, colisões vão ocorrer apenas quando a mesma letra for 
inserida. Como foi inserida três vezes a letra A, e as colisões ocorrem a partir da segunda 
inserção, o total de colisões é 2: a segunda inserção da letra A e a terceira. 
4. Métodos de busca são muito utilizados em milhares de sistemas e aplicações reais. O 
projetista e o desenvolvedor devem ter muito conhecimento sobre seu funcionamento e 
também sobre as vantagens e desvantagens de cada método. 
Para uma aplicação que realiza muitas inserções e atualizações nos dados, qual é o método 
mais indicado? 
Você acertou! 
D. Tabela hash implementada com vetores e listas para tratar colisões. 
A busca sequencial tem um custo muito alto e só é indicada para aplicações com vetores 
pequenos que realizam poucas buscas. A binária, por outro lado, pode ser eficiente, 
dependendo do caso: inserir dados sempre ordenados aumenta o custo da inserção, que, no 
caso de aplicação com muitas inserções e atualizações nos dados, é um ponto importante; 
ordenar apenas quando atualizar vai aumentar o custo das atualizações, que também são 
muito recorrentes nesse caso. Já uma lista encadeada não permite encontrar os elementos de 
forma veloz, pois é necessário percorrê-la do início ao fim. Assim, a resposta correta 
é tabela hash, pois, dada uma chave, é possível inserir e atualizar apenas computando a 
função hash, que tem baixo custo. 
5. Uma das maneiras de avaliar o melhor método para uma aplicação é analisar a 
complexidade de pior e melhor caso dos métodos e constatar com as entradas da aplicação-
alvo. Para tanto, é necessário conhecimento sobre ordens assintóticas. Nesse sentido, qual 
é a complexidade de pior caso das buscas sequencial, binária e na tabela hash, 
respectivamente? 
Você acertou! 
C. O(n), O(log2 n), O(K). 
Para calcular a complexidade de pior caso, deve-se pensar na pior entrada possível para o 
programa. No caso da busca sequencial, como se tem um laço que vai de 1 até N, o pior caso 
é percorrer esse laço N vezes. Nesse sentido, a complexidade da busca sequencial é O(n). 
Quando se fala da busca binária, ela é mais eficiente, pois a cada iteração elimina metade do 
intervalo. Essa eliminação de metade do vetor por vez remete a uma árvore binária, por isso 
o nome da busca. Nesse caso, a complexidade de tempo é O(log2 n). Por fim, a 
tabela hash tem uma complexidade de melhor caso de O(1); entretanto, no pior caso, podem 
ocorrer K colisões, e uma lista encadeada será percorrida até o K-ésimo elemento. Logo, 
complexidade O(K). 
 
Ordenação de dados - Métodos simples 
1. O algoritmo de ordenação por bolha é o mais simples e intuitivo.O seu funcionamento se 
baseia em comparar todos os elementos, dois a dois, do inicio ao fim da lista ou vetor. Essa 
operação é repetida enquanto ocorrerem trocas entre elementos. Dado o vetor [22, 11, 7, 
46, 29], após duas rodadas de execução do algoritmo de ordenação por bolha, ordenando de 
forma decrescente, qual será o estado do vetor? 
Você acertou! 
A. 22, 46, 29, 11, 7. 
O algoritmo de ordenação por bolha compara elementos dois a dois da esquerda para a direita. 
Nesse exercício, o objetivo é ordenar de forma decrescente, ou seja, quando a comparação 
for feita, caso o elemento na posição i for menor que o da posição i + 1, é realizada a troca 
de posição entre os elementos. 
Na primeira rodada vai comparar 22 com 11 e não trocar. Após, compara 11 com 7 e também 
não troca. Agora, quando compara 7 com 46 vai trocar e, após 7 com 29, troca novamente. 
Na primeira rodada tem-se: [22, 11, 46, 29, 7]. 
Na segunda rodada compara-se 22 com 11 e não troca. Logo após, troca 11 por 46 e 11 por 
29. Finalmente, compara 11 com 7 e não troca. O estado do vetor na segunda rodada é [22, 
46, 29, 11, 7]. 
2. A ideia principal do algoritmo de ordenação por inserção é como em um jogo de cartas. 
Quando você recebe uma nova carta, já ordena ela de alguma maneira. Vamos assumir que 
você está jogando cartas e tem a seguinte lista de cartas na mão: [Q, J, Q, J]. Quantas trocas 
serão feitas caso você ordene as cartas de forma ascendente, baseando-se no algoritmo de 
ordenação por inserção? 
Você acertou! 
C. 3. 
Na primeira rodada, o escolhido será o J (2.º elemento), o qual será comparado com o Q (1.º 
elemento). Uma vez que J é menor que Q lexicograficamente, ambos são trocados de 
posição (1 troca). O estado do vetor após a primeira rodada é [J, Q, Q, J]. 
Na segunda rodada, o escolhido é o Q (3.º elemento), que será comparado com outro Q (2.º 
elemento) e nada irá acontecer. 
Na terceira rodada, o escolhido é o J (4.º elemento), que será comparado com os dois Qs (3.º 
e 2.º elementos), sendo trocado (mais 2 trocas, totalizando 3). Ao fim dessa rodada, com 3 
trocas, o vetor está ordenado [J, J, Q, Q]. 
3. A ordenação por seleção busca o menor elemento da parte não ordenada do vetor em 
cada iteração e o coloca na sua posição correta. Quantas comparações e trocas são 
necessárias para ordenar o vetor [1, 5, 3, 9, 6] de forma crescente? 
Você acertou! 
D. 10 e 2. 
Na primeira rodada, o 1 será o menor e já está em sua posição correta. Serão 4 
comparações com os 4 elementos à direita do 1 e nenhuma troca. 
Na segunda rodada, o 5 será comparado com os 3 elementos à direita e uma troca será feita 
entre o 5 e o 3. 
Na terceira rodada, o 5 já estará na sua posição correta, logo, aconteceram 2 comparações e 
nenhuma troca. 
Ao final, na rodada quatro, o 9 será comparado com o 6, 1 comparação,e serão trocados, 
logo, uma troca. 
Somando 4 + 3 + 2 + 1 são 10 comparações e 2 trocas. 
4. Você foi contratado como consultor por uma empresa de desenvolvimento de sistemas. 
Um dos clientes solicitou o desenvolvimento de uma nova funcionalidade que permite 
ordenar os clientes por idade e renda. Essa funcionalidade será utilizada diversas vezes ao 
dia, o que indica que após uma ordenação, as outras só serão necessárias caso atualizações 
tenham sido feitas no banco de dados. Quantas comparações serão feitas pelo algoritmo de 
ordenação por bolha, caso a entrada seja uma lista de 10 elementos já ordenados? 
Você acertou! 
B. 9. 
Tomando como exemplo o vetor [1, 2, 3], com três elementos, o algoritmo de ordenação por 
bolha irá comparar 1 com 2, e 2 com 3, ou seja, 2 comparações, N - 1 elementos. Assim, é 
possível concluir que para um vetor já ordenado com 10 elementos, o algoritmo de ordenação 
por bolha irá fazer 9 comparações. 
5. Uma das maneiras de avaliar o melhor algoritmo de ordenação para determinada aplicação 
é analisando a sua complexidade de tempo. Você foi contratado para fazer essa análise. A 
primeira pergunta que seu chefe fez foi qual seria a complexidade de melhor e pior caso do 
algoritmo de ordenação em seleção, caso ele fosse executado M vezes consecutivas. O que 
você responderia? 
Você acertou! 
E. O(M * N2) e O(M * N2). 
O algoritmo de ordenação por seleção em cada iteração corrige a posição de um dos 
elementos do vetor. Para tanto, em cada iteração ele busca em toda lista pelo menor 
elemento ainda não processado. Isso ocorre tanto no caso de o vetor estar desordenado (pior 
caso) quanto no caso de estar ordenado (melhor caso). 
Nesse sentido, a complexidade de tempo de melhor e pior caso desse algoritmo é a mesma, 
O(N2).Entretanto, é preciso levar em consideração as M execuções citadas no enunciado. 
Nesse caso, serão repetidos M vezes a complexidade O(N2), ou seja, a complexidade final 
tanto de melhor quanto de pior caso é O(M * N2). 
 
Ordenação de dados com métodos eficientes e uso de Python 
1. O algoritmo de ordenação rápida utiliza um pivô para recursivamente ordenar o vetor. Em 
cada chamada da função de partição, os elementos menores que o pivô são colocados na 
esquerda e os maiores que o pivô na direita. Essa operação é repetida até que reste apenas 
um elemento. Dado o vetor [13, 87, 63, 91, 55] e o pivô 55, qual das opções a seguir é válida 
após a primeira execução da função partição? 
Você acertou! 
A. [13, 55, 63, 91, 87]. 
O algoritmo de ordenação rápida utiliza pivôs para ordenar o vetor. Nesse exercício, o objetivo 
é executar uma vez a função de partição utilizando o pivô 55. O vetor original é o [13, 87, 63, 
91, 55]. Da esquerda para a direita, os elementos menores que o pivô vão sendo armazenados, 
enquanto na direita os maiores que o pivô. O próprio pivô é inserido à direita dos menores 
elementos. No caso desse exemplo, o 13 é o único elemento menor que o pivô. O 55, que é 
o pivô, é trocado pelo 87, que é a primeira posição após o elemento menor. Nesse caso, o 
vetor após a primeira execução da função partição será [13, 55, 63, 91, 87]. 
 
 
 
2. A complexidade de tempo de melhor caso da ordenação rápida ocorre quando o elemento 
escolhido como pivô divide o vetor exatamente ao meio. No exemplo [M, Q, S, I, B], qual 
elemento escolhido como pivô resultaria no melhor caso de execução da ordenação rápida? 
Você acertou! 
E. M. 
O melhor caso da ordenação rápida ocorre quando o pivô escolhido é a mediana do vetor 
analisado. No exemplo do nosso vetor [M, Q, S, I, B], a mediana é o M, que dividiria o vetor 
em dois subvetores: [I, B] e [Q, S]. 
3. A ordenação por mistura ordena, de forma recursiva, sequências a partir de subsequências 
já ordenadas. Na fase de divisão, os elementos são recursivamente divididos. Dado o vetor 
[7, 4, 9, 5, 1], quantas chamadas recursivas serão feitas na fase de divisão? 
Você acertou! 
E. 8. 
O vetor original é o [7, 4, 9, 5, 1]. As duas primeiras chamadas recursivas serão [7, 4, 9] e [5, 
1]. Após, serão feitas mais quatro chamadas: [7, 4]; [9]; [5] e [1]. Por fim, mais duas chamadas 
serão feitas: [7] e [4]. O total de chamadas recursivas é 8. 
4. O melhor e o pior caso da ordenação por mistura é o mesmo, O(n log2 n). Dado um vetor 
totalmente desordenado [8, 7, 6, 5, 4, 3, 2, 1], qual será o estado do vetor após duas 
execuções da função merge? 
Você acertou! 
B. [7, 8, 5, 6, 4, 3, 2, 1]. 
Inicialmente, a ordenação por mistura irá dividir os elementos até chegar em vetores de 
tamanho um. Após, a fase de conquista começará e a função merge será utilizada. A recursão 
vai toda para a esquerda e a primeira execução do merge irá ordenar o vetor [8, 7], resultando 
em [7, 8, 6, 5, 4, 3, 2, 1]. Na segunda execução do merge, o vetor [6, 5] será ordenado. 
Resultando no vetor [7, 8, 5, 6, 4, 3, 2, 1]. 
5. A implementação dos algoritmos eficientes tem como base a técnica de divisão e 
conquista. Em ambas as ordenações, por mistura e rápida, o ponto-chave é a complexidade 
de tempo das funções de partição e de merge. Qual é a complexidade de tempo dessas 
funções quando executadas N vezes para um vetor de N posições? 
Vocêacertou! 
D. O(N2). 
A complexidade de ambos os algoritmos é Nlog2 N, sendo que log2 N é a altura da árvore de 
divisão e N é o custo de cada chamada, as funções partição e merge. A questão pergunta a 
complexidade de executar essas funções N vezes. O que resulta em N vezes O(N), ou seja, 
O(N2). 
 
Árvores: estruturas hierárquicas 
1. Alguns problemas requerem estruturas que possibilitem operações como inserção e 
remoção de maneira dinâmica, tais como as árvores. Em relação às árvores e suas vantagens 
em relação às demais estruturas, marque a alternativa correta. 
Você acertou! 
B. Árvores são consideradas eficientes para guardar informações, pois apresentam uma 
forma de organização não linear. 
Devido à topologia hierárquica das árvores, os dados podem ser localizados facilmente, 
quando comparadas a estruturas lineares, tais como listas, filas e pilhas. Além disso, 
normalmente os dados são alocados dinamicamente na memória. Sua forma e inserção pode 
respeitar algumas propriedades, mas não limita que sejam inseridas nas extremidades (início 
e fim). 
2. Considere que você precisa utilizar uma árvore binária e o TAD deve ter um campo para 
armazenar um número inteiro. Os nós podem ser representados na linguagem Python como 
uma classe com os seguintes atributos básicos: 
 
 
Você acertou! 
A. Número do nó, ponteiro para subárvore da direita e ponteiro para subárvore da esquerda. 
Um TAD para representar um nó, de maneira básica, precisa ter três campos: 
- um campo para armazenar a informação do nó e, como o enunciado cita inteiros, as 
alternativas com strings e listas (visto que é apenas uma informação) são eliminadas. 
- um campo para referenciar a subárvore da esquerda. 
- um campo para a subárvore da direita. Veja que também não precisa de lista e de ponteiro 
para o pai. 
3. Durante a implementação de um TAD hierárquico, será necessário conhecer alguns termos 
para projetar os métodos. Acerca das terminologias da estrutura de dados do tipo árvore, 
considere a imagem a seguir e marque a alternativa correta: 
 
Você acertou! 
C. O grau do nó E é 2. 
Alguns temos importantes para classificar as árvores são: 
- o grau de um nó que é dado pelo número de arestas que incidem neste nó. 
- a altura de uma árvore está relacionada ao seu nível máximo, essa árvore tem altura 3. 
- os nós folhas têm subárvore da direita e da esquerda vazias, ou seja, grau zero. 
- O nível de um nó é sua distância do nó raiz, logo o nó raiz tem nível igual a zero. 
Como você pode observar, essa árvore tem altura igual a três e seus nós folhas são D, G, H e 
F. O grau do nó C é um, já o grau do nó B e E é igual a dois. No segundo nível estão os nós D, 
E e F. 
 
 
 
 
 
4. Dada a seguinte árvore e considerando as propriedades de armazenamento de uma árvore 
binária, após a inserção do nó 9 e do nó 5, nessa ordem, pode-se afirmar que esses nós serão 
filhos dos nós: 
 
Você acertou! 
B. 9 será filho da esquerda do nó 10 e 5 será filho da direita do nó 4. 
Durante a inserção em uma árvore binária deve-se respeitar a propriedade em que os maiores 
valores são inseridos à direita e menores são inseridos à esquerda. Inicia-se a inserção pela 
raiz e essa propriedade é verificada em cada subárvore até encontrar o pai. Nesse exemplo, o 
9 será filho à esquerda do nó 10 e o 5 será filho à direita do nó 4. 
5. Caso você tivesse que indicar uma estrutura de dados apropriada para armazenar uma 
sequência de comandos HTML e verificar sua sintaxe antes de apresentar as informações 
no browser, qual estrutura você indicaria? 
Você acertou! 
E. Árvore 
A linguagem HTML verifica os comandos digitados, analisando se eles pertencem a uma 
determinada tag que o programador está usando e, para agilizar as consultas, as informações 
são organizadas de maneira hierárquica. Nesse caso, uma árvore seria a estrutura ideal. 
 
Caminhamento em árvore 
1. As árvores são estruturas de dados de grande contribuição, principalmente no que tange 
as expressões aritméticas, em que o percurso utilizado pode influenciar diretamente. O 
caminhamento em árvore é realizado de três formas, as quais variam conforme a posição de 
leitura do nó raiz, que podem ser: 
Você acertou! 
D. em-ordem, pós-ordem, pré-ordem. 
Os percursos realizados em árvores binárias variam em três tipos, conforme a posição de 
leitura do nó raiz, podendo ser pré-ordem, quando a raiz de cada subárvore é lida 
anteriormente às subárvores esquerda e direita. Quando somente a subárvore esquerda é 
visitada antes do nó raiz, dá-se o nome de percurso em-ordem. E quando tanto a subárvore 
esquerda como a direita são lidas anteriormente à raiz, atribui-se o percurso pós-ordem. 
2. Árvores binárias possibilitam maior organização dos elementos adicionados, o que facilita 
separar os elementos a cada nível de crescimento da árvore. Dada a seguinte lista de 
caracteres [P, R, O, G, R, A, M, A, D, O, R, U, M], como ficaria seu resultado final em uma 
leitura pós-ordem, caso seus valores fossem adicionados sequencialmente, do primeiro ao 
último elemento, em uma árvore binária? Para montar uma árvore binária, os elementos 
menores ou iguais ao nó mais abaixo entrará à esquerda; caso contrário, ficará à direita. 
Você acertou! 
B. A D A M O M G O R R U R P. 
 
3. Uma árvore binária que tenha como finalidade resolver problemas aritméticos, necessita 
que sua leitura seja feita de tal modo a combinar dois operandos para o operador da 
expressão. Exemplo: A + B. Portanto, como uma árvore deveria posicionar seus elementos e 
qual seria a melhor forma de leitura para que as operações ocorram? 
Você acertou! 
B. É preferível que os valores da operação aritmética estejam localizados à esquerda e à 
direita da raiz, desde que o operador seja raiz, e a leitura da árvore seja feita em-ordem. 
Em uma árvore binária, para avaliar expressões aritméticas, é importante organizá-la de tal 
forma que os operadores dividam simetricamente cada subexpressão, de modo a facilitar sua 
leitura. Tendo este objetivo em mente, é preferível que existam os operadores (soma, 
subtração, multiplicação e divisão), ocupando sempre a raiz, separando de forma mais 
simétrica os operandos (valores) da expressão, para uma leitura realizada em-ordem. 
4. O caminhamento de uma árvore binária influencia diretamente no resultado final de 
leitura de uma determinada sequência de símbolos, e pode se encontrar em 3 tipos, como 
percursos em pré-ordem, in-ordem e pós-ordem, variando, assim, a posição do valor raiz. 
Qual função a seguir descreve o percurso realizado em pós-ordem? 
Você acertou! 
A. def funcao(no): 
if atual != None: 
funcao(no.esquerdo) 
funcao(no.direito) 
print("Valor: {}.".format(no.valor)) 
A ordem dos elementos visitados em pós-ordem estabelece que os elementos da subárvore à 
esquerda serão visitados, seguidos dos elementos das subárvores à direita e, por fim, os 
elementos raízes. 
 
Mesmo que todas as funções apresentem recursividade, apenas a função com a impressão 
sucedendo às duas chamadas recursivas para as subárvores esquerda e direita imprimem o 
caminho pós-ordem. 
5. O modo como é feito o percurso determina como será o nível de prioridade de leitura dos 
elementos, podendo o nó raiz estar com prioridade (leitura em pré-ordem), ou os elementos 
da subárvore à esquerda (leitura in-ordem), ou os elementos da subárvore à esquerda 
seguido da leitura à direita (pós-ordem). Considerando a imagem a seguir, mostre a sequência 
de expressões resultantes, conforme os percursos de pré-ordem, em-ordem e pós-ordem, 
respectivamente. 
 
Você acertou! 
C. * 3 * 5 13 
3 * 5 * 13 
3 5 13 * * 
Os percursos variam conforme a sua modalidade, a qual está relacionada à posição de visita 
do nó raiz. Neste caso, onde é desejado obter as 3 formas de leitura, é possível identificar um 
padrão no posicionamento do operador aritmético, cujo posicionamento está mais à esquerda 
na leitura em pré-ordem: * 3 * 5 13; está mais simétrico na leitura em-ordem: 3 * 5 * 13; e 
mais à direita para a leituraem pós-ordem: 3 5 13 * *. 
 
Pesquisa binária 
1. A estrutura de dados de árvore apresenta grande versatilidade. Pode ser aplicada na 
solução de um leque de problemas, como em indexação de bancos de dados, em buscas, em 
estruturas de diretórios em sistemas de arquivos, entre outros. Considerando uma árvore 
binária de busca, qual destas é uma de suas propriedades? 
Você acertou! 
B. A subárvore esquerda de um nó contém os nós com chaves menores ou iguais que a do 
nó. 
Para uma árvore agir como uma árvore de busca, os valores armazenados em cada nó devem 
ser maiores que qualquer outro que esteja na subárvore esquerda e menores do que os salvos 
em subárvores à direita. Logo, a subárvore esquerda de um nó contém os nós com chaves 
menores ou iguais ao nó referente; a subárvore direita de um nó contém os nós com chaves 
maiores que o nó referente; e as subárvores esquerda e direita também devem ser uma árvore 
de pesquisa binária. 
De acordo com a propriedade de uma árvore de busca, uma subárvore à esquerda não pode 
receber chaves maiores que o nó. Além disso, em uma árvore binária de busca, cada nó pode 
ter, no máximo, dois filhos. Sobre o tipos e os valores armazenados nos nós, não exitem 
restrições: pode ser tanto uma string como um valor numérico qualquer, e, quando se trata de 
valores numéricos, também não existem restrições se o valor é positivo ou negativo. 
2. Uma árvore binária de busca é conhecida pela sua eficiência quando é necessária a 
pesquisa de algum valor, seguindo as regras de buscas, ramificando para a esquerda e para a 
direita. Sabendo disso, de acordo com a árvore na imagem, determine qual caminho a chave 
de busca percorreu para pesquisa do valor 87 e se este existe ou não. 
 
Você acertou! 
D. Visitou chave 70. 
Visitou chave 90. 
Visitou chave 83. 
Visitou chave 85. 
Visitou chave 89. 
Resultado: falha. 
Considerando que a raiz da árvore corresponde ao valor 70, para o número procurado (87), 
precisaremos caminhar pela subárvore à direita. Em seguida, será visitado nó de chave 90, 
porém o valor procurado ainda não é esse, e, como 87 é menor que 90, será explorada à 
subárvore à esquerda do nó de chave 90, resultando em uma visita ao nó de chave 83. Como 
87 é maior que 83, seguiremos à procura pela subárvore à direita desse nó, chegando ao nó 
de chave 85. O valor 87 é maior que 85, fazendo com que seja realizada a leitura ao último nó 
dessa ramificação: o nó de chave 89. 
Como não existem mais elementos a serem explorados a partir do nó de chave 89, o resultado 
obtido é de falha, pois o elemento 87 não existe. 
 
 
 
3. Sempre que vimos uma árvore, presumimos a ordem em que seus elementos foram 
adicionados. Dessa forma, conforme a imagem utilizada no exercício anterior, defina uma 
possível ordem do vetor que culminou na árvore apresentada, lembrando que o primeiro 
valor corresponde à raiz da árvore. 
 
Você acertou! 
B. [70,90,4,114,2,23,83,116,72,15,85,89,63]. 
Podemos verificar a ordem de cada elemento fazendo uma pequena inserção em uma árvore 
abstrata. Ao criar uma árvore binária sem balanceamento, temos sempre que considerar sua 
forma de organizar seus valores. Logo, se o valor 89, que é uma folha, for adicionado antes do 
valor 85, o valor 89 que antes não tinha nenhuma ramificação passará a ter o nó 85 como 
subárvore esquerda. 
Seguindo esse raciocínio, podemos estabelecer uma possível ordem como: 
[70,90,4,114,2,23,83,116,72,15,85,89,63]. 
4. Uma árvore binária de busca, como o próprio nome sugere, é uma estrutura de dados que 
armazena dados de maneira que permita a realização de busca binária. Essa busca segue 
o paradigma de divisão e conquista e acaba tendo uma eficiência melhor do que uma busca 
linear. Existem duas abordagens para realizar a implementação dessa busca: a 
implementação recursiva e iterativa. Qual a principal diferença entre essas implementações? 
Você acertou! 
C. Na abordagem recursiva, um nó definido como base nele próprio realiza a repetição dos 
seus passos invocando a si próprio, executando todos os seus passos novamente até 
encontrar o valor buscado. Diferentemente da busca recursiva, a busca iterativa considera 
as ramificações de maneira explícita de cada nó para percorrer seus nós, pois não há uma 
chamada interna para a mesma função. 
A abordagem recursiva realiza autorreferência, ou seja, ocorre quando algo é definido em 
termos de si mesmo. No caso da árvore, um nó é definido com base nele próprio até achar o 
valor buscado; já no método iterativo, a busca é realizada percorrendo explicitamente todos 
os nós da árvore até se encontrar o valor buscado. 
Além disso, apenas o método iterativo usa laços de repetição, como while e for. E, apesar de 
serem abordagens diferentes, ambas visitam os mesmos nós no processo de busca por 
determinado valor. 
5. Em termos de alocação de memória, podemos implementar uma árvore de busca binária 
utilizando alocação dinâmica ou alocação estática. Considerando a alocação estática, como 
ocorre a representação de uma árvore de pesquisa binária em um vetor? 
Você acertou! 
A. 1- O nó raiz deve ficar na posição inicial do vetor. 
 
2- Para cada nó em determinada posição i de um vetor, seu filho esquerdo ficará na posição 
2*i + 1, e seu filho direito ficará na posição 2*i + 2. 
As árvores também podem ser implementadas sob listas fixas ou estáticas, que ocorrem por 
meio da distribuição dos nós da árvore ao longo de um vetor (array). Essa distribuição ocorre 
da seguinte forma: o nó raiz será o primeiro elemento do vetor, e, para cada nó em 
determinada posição i do vetor, seu filho esquerdo ficará na posição 2*i + 1, e seu filho direito 
ficará na posição 2*i + 2. 
 
Balanceamento de árvore 
1. Uma das principais vantagens das árvores binárias em relação às demais estruturas de 
dados é a sua eficiência no processo de realizar buscas. A árvore AVL é conhecida por ter um 
resultado muito eficiente durante a operação de busca, pois realiza uma distribuição 
homogênea dos dados. Qual a ideia central ao fazer o balanceamento em uma árvore? 
Você acertou! 
A. A ideia central do balanceamento é que, para cada novo elemento adicionado ou 
removido da árvore, seja realizado uma reorganização para que a distribuição dos elementos 
conforme sua subárvore, continue homogênea. 
No que tange o balanceamento, a ideia central é que para cada novo elemento adicionado ou 
removido da árvore, seja realizada uma reorganização para que a distribuição dos elementos, 
conforme sua subárvore, continue homogênea. 
Em uma árvore AVL não existe a necessidade de as subárvores terem a mesma quantidade de 
nós, e seus nós não têm valores de pesos. Além disso, existe mais de um tipo de árvore 
balanceada, as quais têm um objetivo de retornar uma busca eficiente. 
2. As árvores AVL correspondem à família das árvores binárias, em que a distribuição dos 
elementos é feita de acordo com determinadas condições, as quais são necessárias para 
garantir o balanceamento da árvore. Em relação à altura de uma AVL, qual é a afirmação 
correta? 
Você acertou! 
D. A altura de uma árvore nula é igual a -1. 
Uma árvore balanceada é assim chamada por alguns critérios, sendo um deles, a altura: 
Altura: a altura de uma árvore é o nível máximo de suas folhas. Em algumas literaturas, é 
determinado como profundidade de uma árvore. A altura de uma árvore nula, por exemplo, é 
definida como –1, e uma árvore binária balanceada é uma árvore em que as alturas de suas 
subárvores (esquerda e direita) de todo nó nunca diferem em mais de 1. 
Quando a árvore tem apenas um elemento, sua altura é de zero. Logo, quando não tiver 
nenhum elemento, essa árvore é nula, e sua altura é -1. 
3. Uma árvore AVL é uma árvore binária muito utilizada para armazenamento de dados em 
memória. Cada nó de uma árvore AVL necessita da informação de altura, pois é fundamental 
para o processo de balanceamento. Para um nó folha, que tem uma altura igual a 1, sendo 
que essa árvore AVL tem 7 nós. Qual é a altura máxima que essa árvore podeter? 
Você acertou! 
D. 3. 
Para encontrar a altura máxima, os nós devem ser mínimos em cada nível. Supondo 
altura como 3, número mínimo de nós necessário: 
N (h) = N (h-1) + N (h-2) + 1 
N (3) = N (2) + N (1) + 1 = 4 + 2 + 1 = 7 
Logo, a altura máxima é 3. 
4. Uma árvore AVL tem as funções básicas como inserção, remoção e busca, assim como 
uma árvore simples. Considere a seguinte árvore AVL. Qual das alternativas a seguir é a 
árvore AVL atualizada após a inserção de 70? 
 
Você acertou! 
C. 
 
5. No processo de realizar o balanceamento de uma árvore AVL, após a exclusão ou inclusão 
são realizadas operações para realizar o balanceamento. Quais das seguintes operações são 
usadas pelas árvores AVL? 
Você acertou! 
A. Rotação à esquerda e rotação à direita. 
Para auxiliar no processo de balanceamento das árvores AVL, são utilizadas as operações de 
rotação à esquerda e à direita, com o objetivo de redistribuir os elementos de maneira 
homogênea. 
A operação de recoloração de nós pertence à árvore rubro-negra; não existe esse ajuste por 
altura de peso, e as funções de caminhamento têm apenas a função de percorrer os nós.