Estruturas de Dados Básicas (Listas, Pilhas e Filas) Flashcards
Em uma lista simplesmente encadeada, cada nó aponta para o próximo nó na lista, e o último nó aponta para null. Verdadeiro ou falso? Justifique se for falso.
Verdadeiro
Em uma lista simplesmente encadeada, a inserção de um novo nó é sempre feita no final da lista. Verdadeiro ou falso? Justifique se for falso.
Falso. A inserção de um novo nó pode ser feita no início, no meio ou no final da lista.
Cite duas vantagens de usar uma lista simplesmente encadeada em vez de um vetor.
- Uma lista encadeada permite inserções e remoções eficientes de elementos em qualquer parte da lista (sem a necessidade de realocar os elementos), enquanto um vetor requer deslocamento de elementos em operações de inserção e remoção no meio.
- Uma lista encadeada permite que os elementos sejam alocados na memória de maneira aleatória enquanto um vetor necessariamente aloca os elementos de forma contínua.
Qual das opções descreve melhor a principal característica de uma lista simplesmente encadeada?
a) Cada nó tem um ponteiro para o próximo e para o anterior.
b) Cada nó tem apenas um ponteiro para o próximo nó.
c) Cada nó contém múltiplos ponteiros para vários nós.
d) A lista tem um tamanho fixo.
b) Cada nó tem apenas um ponteiro para o próximo nó.
Em uma lista duplamente encadeada, cada nó tem ponteiros tanto para o próximo nó quanto para o nó anterior. Verdadeiro ou falso? Justifique se for falso.
Verdadeiro
Qual é a principal vantagem de uma lista duplamente encadeada em relação a uma lista simplesmente encadeada?
a) Uso mais eficiente de memória.
b) Acesso direto a elementos.
c) Permite navegação eficiente em ambas as direções.
d) A lista é mais fácil de implementar.
c) Permite navegação eficiente em ambas as direções.
A remoção de um nó em uma lista duplamente encadeada é mais eficiente do que em uma lista simplesmente encadeada, pois não é necessário percorrer a lista para encontrar o nó anterior. Verdadeiro ou falso? Justifique se for falso.
Verdadeiro. Em uma lista duplamente encadeada, cada nó tem um ponteiro para o nó anterior, permitindo a remoção de um nó de forma mais eficiente.
Qual a principal desvantagem de uma lista duplamente encadeada em comparação com uma lista simplesmente encadeada?
A principal desvantagem é o maior uso de memória, pois cada nó precisa armazenar dois ponteiros (um para o próximo e outro para o anterior), o que aumenta o custo de armazenamento em comparação com uma lista simplesmente encadeada.
Em uma lista simplesmente encadeada, os nós são armazenados de forma contígua na memória. Verdadeiro ou Falso? Justifique se for falso.
Falso. Os nós em uma lista simplesmente encadeada não são armazenados de forma contígua; cada nó armazena um ponteiro para o próximo nó, permitindo que a lista seja dinâmica.
Qual das operações a seguir é realizada de forma eficiente (O(log n) ou superior) em uma lista simplesmente encadeada?
a) Acesso ao elemento no meio da lista.
b) Inserção no final da lista (sem referência ao último nó).
c) Remoção de um nó no meio da lista.
d) Acesso ao primeiro elemento.
d) Acesso ao primeiro elemento.
Justificativa: O acesso ao primeiro elemento é eficiente em uma lista simplesmente encadeada, já que ele está sempre no início da lista e pode ser acessado diretamente, independente do tamanho da lista.
A inserção de um novo nó em uma lista simplesmente encadeada exige percorrer a lista até encontrar a posição correta. Verdadeiro ou falso? Justifique se for falso.
Verdadeiro
Como uma lista simplesmente encadeada pode ser usada para representar uma fila?
Uma lista simplesmente encadeada pode ser usada para representar uma fila, onde a inserção de elementos ocorre no final da lista (enqueue) e a remoção ocorre no início (dequeue), mantendo a ordem FIFO.
Qual das opções abaixo é uma vantagem da lista duplamente encadeada em relação à lista simplesmente encadeada?
a) Menor uso de memória.
b) Acesso direto ao meio da lista.
c) Menor complexidade de implementação.
d) Menor complexidade de código nas operações de remoção.
d) Menor complexidade de código nas operações de remoção.
Uma lista encadeada é a melhor estrutura de dados para acessar elementos aleatórios diretamente. Verdadeiro ou falso? Justifique se for falso.
Falso. A lista encadeada não é eficiente para acesso aleatório, pois é necessário percorrer a lista até encontrar o elemento desejado (O(n)). Um array, por outro lado, consegue encontrar o elemento em O(1) se souber a posição em que ele está.
Qual das opções a seguir é uma vantagem de uma lista encadeada sobre um array?
a) Acesso direto aos elementos.
b) Menor uso de memória.
c) Facilidade para inserção e remoção de elementos em qualquer posição.
d) Menor complexidade na busca de elementos.
c) Facilidade para inserção e remoção de elementos em qualquer posição.
Justificativa: A lista encadeada permite inserções e remoções em qualquer posição de forma eficiente, enquanto em um array essas operações podem ser mais lentas e requerer deslocamento de elementos.
Uma lista encadeada é mais eficiente do que um array quando há muitas inserções e remoções no meio da estrutura. Verdadeiro ou falso? Justifique se for falso.
Verdadeiro. A lista encadeada permite inserções e remoções no meio da estrutura com complexidade O(1), enquanto em um array essas operações têm complexidade O(n) devido ao deslocamento de elementos.
Em qual das seguintes situações uma lista encadeada seria a estrutura de dados mais adequada?
a) Acesso rápido a qualquer elemento da lista.
b) Armazenamento de dados onde a ordem de acesso não importa.
c) Frequentemente adicionar e remover elementos do meio da estrutura.
d) Garantir que a estrutura de dados tenha um tamanho fixo.
c) Frequentemente adicionar e remover elementos do meio da estrutura.
Justificativa: A lista encadeada é eficiente para operações de inserção e remoção no meio da estrutura, sem a necessidade de mover elementos como em um array.
Uma fila pode ser usada para gerenciar tarefas em segundo plano, mas uma lista seria mais eficiente, pois permite inserções e remoções no início e no final. Verdadeiro ou falso? Justifique se for falso
Falso. A fila é mais adequada para gerenciar tarefas em segundo plano, pois segue a política FIFO, enquanto a lista não é eficiente para operações de inserção e remoção nos dois extremos sem a manipulação adequada.
Em que cenário uma pilha seria mais adequada do que uma lista encadeada?
a) Quando os elementos precisam ser acessados em ordem aleatória.
b) Quando as operações de inserção e remoção precisam ser rápidas e ocorrer apenas no topo da estrutura.
c) Quando a ordem de elementos deve ser preservada.
d) Quando é necessário um acesso eficiente ao meio da estrutura.
b) Quando as operações de inserção e remoção precisam ser rápidas e ocorrer apenas no topo da estrutura.
Justificativa: A pilha é eficiente para operações LIFO no topo da estrutura.
Qual das seguintes operações é realizada em uma fila?
a) Push
b) Pop
c) Enqueue
d) Dequeue
c) Enqueue
Em uma fila, a operação de inserção de elementos é chamada de “enqueue”.
Em uma fila, a operação de remoção de um elemento é realizada no final da fila. Verdadeiro ou falso? Justifique se for falso.
Falso. A operação de remoção de elementos em uma fila ocorre no início (front) da fila, seguindo a política FIFO.
Explique a diferença entre uma fila e uma pilha.
A principal diferença é que em uma fila os elementos seguem a política FIFO (First In, First Out), ou seja, o primeiro a entrar é o primeiro a sair. Em uma pilha, os elementos seguem a política LIFO (Last In, First Out), ou seja, o último a entrar é o primeiro a sair.
Qual operação não é associada a uma pilha?
a) Push
b) Pop
c) Enqueue
d) Peek
c) Enqueue
Justificativa: A operação “enqueue” é associada a filas, não a pilhas.Em uma fila, a operação de inserção de elementos é chamada de “enqueue”.
A operação de “pop” em uma pilha remove o último elemento inserido e o retorna. Verdadeiro ou Falso? Justifique se for falso.
Verdadeiro. A operação de remover um elemento da pilha é conhecida popularmente como pop.
Qual das opções a seguir é a principal limitação de uma fila simples?
a) Não permite remoção de elementos do final.
b) Não permite remoção de elementos no início.
c) Não pode ser implementada com arrays.
d) Não permite ordenação de elementos.
d) Não permite ordenação de elementos.
Justificativa: Em uma fila simples, a ordem dos elementos é baseada na ordem de entrada, não sendo possível ordená-los diretamente na fila.
Uma fila simples é uma estrutura de dados eficiente (O(log n) ou melhor) quando se deseja acessar o último elemento adicionado. Verdadeiro ou falso? Justifique.
Falso. A fila não é eficiente para acessar o último elemento, pois ela segue a política FIFO e a remoção ocorre no início da fila. Ou seja, para acessar o último elemento, é necessário percorrer todos os elementos na fila e por isso a complexidade é O(n).
Em uma aplicação que simula atendimento ao cliente, devemos usar filas ou pilhas? Justifique.
Filas, pois idealmente, o primeiro cliente a chegar é o primeiro a ser atendido, seguindo a política FIFO (First In, First Out).
Em uma pilha, a operação de “push” é usada para remover elementos da estrutura. Verdadeiro ou falso? Justifique se for falso
Falso. A operação “push” é utilizada para inserir elementos na pilha, enquanto “pop” é usada para removê-los.
Qual é a complexidade temporal das operações de “push” e “pop” em uma pilha construída de forma otimizada?
a) O(n)
b) O(log n)
c) O(1)
d) O(n log n)
c) O(1)
Considere uma pilha implementada da seguinte forma:
- A pilha é implementada como uma lista (ou array)
- A inserção e a remoção são realizadas no final da lista
- Na linguagem de programação escolhida, para inserir (ou remover) um elemento no final de uma lista (ou array), é necessário percorrer todos os elementos para então inserir o elemento ao final.
Nesse contexto, qual será a complexidade das funções push e pop? Justifique.
Push e pop serão ambas O(n) pois inserir ou remover um elemento na lista envolve passar por todos os elementos que já estão nela.
Considere uma pilha implementada da seguinte forma:
- A pilha é implementada como uma lista (ou array)
- A inserção e a remoção são realizadas no início da lista
- Na linguagem de programação escolhida, inserir (ou remover) um elemento no início de uma lista (ou array) gasta tempo constante, independente do tamanho do array.
Nesse contexto, qual será a complexidade das funções push e pop? Justifique.
O(1). Visto que inserir e remover no início da pilha pode ser feito em tempo constante, as operações de push e pop serão realizadas em tempo constante.
Qual é o principal uso de uma fila em um sistema de impressão?
a) Organizar documentos por ordem de prioridade.
b) Imprimir os documentos mais recentes primeiro.
c) Organizar documentos na ordem em que foram enviados para impressão.
d) Armazenar documentos temporariamente.
c) Organizar documentos na ordem em que foram enviados para impressão.
Justificativa: A fila é ideal para gerenciar impressões na ordem de chegada, garantindo que o primeiro documento enviado seja o primeiro a ser impresso.
Qual das seguintes situações é mais adequada para o uso de uma fila?
a) Navegação em um histórico de páginas da web.
b) Execução de tarefas em segundo plano, onde a ordem de chegada é importante.
c) Armazenamento de dados temporários.
d) Verificação de expressões matemáticas balanceadas.
b) Execução de tarefas em segundo plano, onde a ordem de chegada é importante.
Justificativa: Fila é ideal quando é necessário processar tarefas na ordem em que foram recebidas (FIFO).
Em qual das situações a seguir uma pilha seria mais útil?
a) Processamento de tarefas em ordem de chegada.
b) Armazenamento de dados em ordem crescente.
c) Armazenamento de variáveis em chamadas de função recursiva.
d) Implementação de um sistema de filas de espera.
c) Armazenamento de variáveis em chamadas de função recursiva.
Justificativa: Pilhas são usadas para armazenar variáveis locais e endereços de retorno durante a execução de funções recursivas.
Construa um algoritmo simples usando pilhas para verificar se uma expressão possui parênteses balanceados ou não.
- Ao encontrar um símbolo de abre parênteses “(“, insira-o na pilha.
- Ao encontrar um símbolo de fecha parênteses “)”, remova o último abre parênteses inserido na pilha.
- Se em algum momento for encontrado um símbolo de fecha parênteses e a pilha estiver vazia, retorne falso.
- Se ao final da expressão, a pilha estiver vazia, retorne verdadeiro. Caso contrário, retorne falso.
Qual das seguintes operações é mais eficiente em uma pilha?
a) Inserir um elemento no meio da pilha.
b) Remover um elemento do meio da pilha.
c) Inserir ou remover um elemento do topo da pilha.
d) Acessar um elemento do fundo da pilha.
c) Inserir ou remover um elemento do topo da pilha.
Justificativa: A pilha é projetada para permitir inserção e remoção eficientes apenas no topo (operações O(1)).
Em qual dos seguintes cenários a pilha seria mais adequada do que a fila?
a) Processamento de tarefas em que a ordem de chegada é importante.
b) Implementação de um histórico de navegação de páginas da web.
c) Armazenamento de arquivos em um sistema de arquivos.
d) Desfazer uma ação em um aplicativo.
d) Desfazer uma ação em um aplicativo.
Justificativa: A pilha é ideal para armazenar ações anteriores, permitindo desfazer a última ação, que segue a política LIFO.
