Estrutura de Dados (uni2)

Prévia do material em texto

Exercícios Estrutura de Dados (Unidade 2) Deixe seu like 
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? 
 
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. 
 
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? 
 
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? 
 
Percorrer elementos, inserir elemento, remover elemento e buscar elemento. 
 
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? 
 
No início da lista, em alguma posição intermediária e no final da lista. 
 
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? 
 
Verificar se existe espaço, adicionar o contador de itens e alocar um espaço para inserir um novo 
elemento. 
 
6. 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? 
 
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. 
 
7. 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? 
 
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. 
 
8. 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? 
 
De forma intuitiva, a inserção é feita de forma direta O(1), enquanto a remoção depende de 
percorrer (n) elementos na lista. 
 
9. 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? 
 
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. 
 
10. 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? 
 
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. 
 
11. 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? 
 
11 e 29. 
 
12. 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: 
 
o número 14 é o primeiro elemento a ser removido da pilha. 
 
13. 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? 
 
Push(x), que insere o elemento x no topo da pilha sem sobrepor nenhum elemento. 
 
14. 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: 
 
 
A sequência correta de comandos executados para se chegar ao estado final 
foi: 
 
Pop(), Pop(), Push(9), Push(3). 
 
15. 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? 
 
8. 
 
16. 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)? 
 
Fila. 
 
17. 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? 
 
estaVazia(). 
 
18. 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? 
 
ABCD. 
19. 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? 
 
['abacaxi', 'uva', 'pêra', 'amora']. 
 
20. 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? 
 
Documentos esperando para serem impressos em uma impressora.