Exercícios Estruturas de Dados

Prévia do material em texto

Lista de Exercícios - Análise e Desenvolvimento de
Sistemas
Disciplina: Estruturas de Dados e Algoritmos
Tema: Arrays, Pilhas, Filas, Árvores e Notação Big-O
Questão 1
Qual a diferença comportamental fundamental entre uma estrutura de dados do tipo Pilha (Stack) e uma
Fila (Queue)?
Na Pilha, as inserções e remoções ocorrem em extremidades opostas (FIFO), enquanto na Fila
ocorrem na mesma extremidade (LIFO).
Na Pilha, o último elemento inserido é o primeiro a ser removido (LIFO). Na Fila, o primeiro elemento
inserido é o primeiro a ser removido (FIFO).
Pilhas só armazenam tipos primitivos, enquanto Filas armazenam apenas objetos dinâmicos.
Não há diferença algorítmica, ambas processam dados aleatoriamente baseando-se em funções de
Hash.
Questão 2
Ao analisar a complexidade de tempo de um algoritmo usando a notação Big-O (Assintótica), o que
significa um algoritmo ser classificado como O(1)?
Significa que o algoritmo leva exatamente 1 segundo para ser executado.
Significa que o algoritmo só consegue processar 1 elemento de cada vez.
Significa que é um algoritmo de complexidade Constante: o tempo de execução não aumenta,
independente do crescimento da quantidade de dados (tamanho de entrada 'n').
Significa que é um algoritmo de complexidade Linear: o tempo cresce proporcionalmente ao tamanho
da entrada.
A. 
B. 
C. 
D. 
A. 
B. 
C. 
D. 
Questão 3
Considerando o armazenamento de dados em um Array padrão (Vetor tradicional em Java ou C) versus
uma Lista Encadeada (Linked List), assinale a correta:
Arrays armazenam dados em blocos contíguos de memória, permitindo acesso direto O(1) pelo
índice. Listas Encadeadas armazenam nós dispersos ligados por ponteiros.
Listas Encadeadas possuem tamanho estático definido na compilação, enquanto Arrays crescem
infinitamente sem necessidade de realocação.
Arrays sofrem com atrasos na leitura de dados no meio da estrutura em comparação com as Listas
Encadeadas.
Em Listas Encadeadas, para acessar o 100º elemento, basta acessar o índice [99] diretamente sem
percorrer os elementos anteriores.
Questão 4
Uma Árvore Binária de Busca (Binary Search Tree - BST) possui uma propriedade específica que
otimiza a busca de dados. Qual é essa propriedade?
A raiz sempre contém o maior valor da árvore.
Para cada nó, todos os elementos em sua subárvore esquerda são menores que o nó, e todos na
subárvore direita são maiores que o nó.
Cada nó pai deve possuir exatamente 3 filhos para balancear a memória.
Os nós folha (leaf) são conectados entre si formando uma fila circular bidirecional.
Questão 5
O algoritmo de ordenação Quick Sort é conhecido por sua eficiência prática. Qual é a estratégia
principal (paradigma) utilizada por ele?
Programação Dinâmica (Memorização de resultados anteriores).
Divisão e Conquista (Divide and Conquer), particionando o array ao redor de um elemento pivô.
Força Bruta (Brute Force), comparando cada elemento repetidas vezes.
Algoritmo Guloso (Greedy), escolhendo sempre o vizinho mais próximo.
Gabarito Comentado (Para Conferência)
1. Resposta: B. Pilha (Stack) = LIFO (Last In, First Out), como uma pilha de pratos reais. Fila (Queue)
= FIFO (First In, First Out), como uma fila de banco, quem chega primeiro é atendido primeiro.
A. 
B. 
C. 
D. 
A. 
B. 
C. 
D. 
A. 
B. 
C. 
D. 
2. Resposta: C. A complexidade O(1) indica eficiência máxima em relação ao tempo. Um exemplo de
O(1) é acessar um elemento de um array diretamente pelo índice `array[5]`, independentemente se o
array tem 10 ou 1 milhão de itens.
3. Resposta: A. Os Arrays ocupam um bloco de memória contíguo e têm tamanho fixo na criação, o
que os torna muito rápidos para leituras. As Listas Encadeadas alocam memória sob demanda via nós
e ponteiros, sendo mais flexíveis para inserções/remoções, mas exigem travessia O(n) para busca.
4. Resposta: B. A propriedade da BST é o que permite fazer buscas com complexidade logarítmica
O(log n) em média, pois a cada passo o algoritmo descarta metade da árvore, funcionando como uma
busca binária.
5. Resposta: B. O Quick Sort divide o problema escolhendo um 'pivô', agrupando elementos menores
à esquerda e maiores à direita, e resolvendo as partições recursivamente. É um dos algoritmos de
ordenação mais rápidos no mundo real.
	Lista de Exercícios - Análise e Desenvolvimento de Sistemas
	Questão 1
	Questão 2
	Questão 3
	Questão 4
	Questão 5
	Gabarito Comentado (Para Conferência)