Implementação de Estruturas de Dados Lineares
98 Questions
0 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Qual é o principal problema com o uso de arrays para armazenar coleções de elementos?

  • Arrays têm tamanho fixo, dificultando a expansão. (correct)
  • Arrays exigem muito espaço de memória, tornando-os ineficientes.
  • Arrays não podem ser modificados após sua criação.
  • Arrays são muito complexos de implementar.

    • Quando se trata de inserir ou remover elementos em posições intermediárias, arrays, em comparação às listas ligadas, são:

  • Menos eficientes, pois a operação exige a criação de novo array.
  • Mais lentos, pois podem exigir o deslocamento de vários elementos. (correct)
  • Mais rápidos, especialmente para grandes quantidades de dados.
  • Equivalentes em termos de desempenho, com pouca diferença perceptível.

    • Qual das seguintes características NÃO é uma vantagem das listas ligadas em relação aos arrays?

  • Inserção e remoção eficientes em qualquer posição.
  • Capacidade de redimensionamento dinâmico.
  • Acesso rápido a elementos específicos por índice. (correct)
  • Memória alocada dinamicamente, conforme necessário.

    • O que cada nodo numa lista ligada simples (SLL) armazena, além do elemento?

    <p>Um ponteiro para o nodo seguinte. (B)</p> Signup and view all the answers

    As listas ligadas, em relação aos arrays, podem ser consideradas uma estrutura de dados:

    <p>Dinâmicas, com tamanho variável. (B)</p> Signup and view all the answers

    A classe Node, definida como genérica e interna à classe SLL, serve para:

    <p>Representar um nodo na lista ligada, capaz de armazenar qualquer tipo de elemento. (B)</p> Signup and view all the answers

    Qual é a principal diferença entre a SLL (Lista Ligada Simples) e a DLL (Lista Ligada Dupla)?

    <p>A SLL contém ponteiros para o próximo nodo, a DLL também contém ponteiros para o nodo anterior. (A)</p> Signup and view all the answers

    Em relação à capacidade de armazenamento, qual das seguintes afirmações sobre as listas ligadas é CORRETA?

    <p>A capacidade é limitada pela quantidade de memória disponível no sistema. (A)</p> Signup and view all the answers

    Qual é a operação mais ineficiente em uma lista simplesmente ligada (SLL)?

    <p>Remover o último nodo da lista (A)</p> Signup and view all the answers

    Como é chamado o apontador que referencia o nodo anterior em uma lista duplamente ligada (DLL)?

    <p>prev (D)</p> Signup and view all the answers

    Qual é a complexidade operacional da inserção e remoção em uma lista simplesmente ligada (SLL) quando se trata do início da lista?

    <p>O(1) (C)</p> Signup and view all the answers

    Quais nodos especiais são frequentemente adicionados em uma lista duplamente ligada (DLL) para simplificar operações de inserção e remoção?

    <p>Nodos header e trailer (C)</p> Signup and view all the answers

    O que acontece quando o apontador head de uma lista simplesmente ligada (SLL) é movido para o nodo seguinte?

    <p>O nodo anterior é imediatamente coletado como lixo. (D)</p> Signup and view all the answers

    Qual estrutura de dados permite percorrer nodos em ambas as direções?

    <p>Lista duplamente ligada (DLL) (A)</p> Signup and view all the answers

    Qual das seguintes opções representa um ponto fraco de uma lista simplesmente ligada (SLL) comparada a uma lista duplamente ligada (DLL)?

    <p>Impossibilidade de percorrer a lista em ambas as direções (A)</p> Signup and view all the answers

    Por que a remoção do último nodo em uma lista simplesmente ligada (SLL) é considerada uma operação ineficiente?

    <p>Porque requer percorrer a lista até o penúltimo nodo (D)</p> Signup and view all the answers

    Qual é o motivo para incluir os atributos tail e size na classe SLL?

    <p>A inclusão de <code>tail</code> e <code>size</code> torna a implementação dos métodos de inserção e remoção mais eficiente. (A)</p> Signup and view all the answers

    Qual é o primeiro passo para inserir um elemento no início de uma SLL?

    <p>Criar o novo nodo e atribuir a ele o elemento a ser inserido. (C)</p> Signup and view all the answers

    Qual é o último passo para inserir um elemento no fim da SLL?

    <p>Atualizar o atributo <code>size</code> da lista para aumentar o tamanho da lista em 1. (A)</p> Signup and view all the answers

    No contexto da inserção de um elemento no fim da SLL, qual é a função do passo 5?

    <p>Atualizar o ponteiro <code>tail</code> para apontar para o novo nodo. (A)</p> Signup and view all the answers

    Qual dos seguintes passos não é necessário para inserir um elemento no início de uma SLL?

    <p>Atualizar o ponteiro <code>tail</code> da lista para apontar para o novo nodo. (B)</p> Signup and view all the answers

    Qual dos seguintes NÃO é um atributo da classe SLL?

    <p>length (C)</p> Signup and view all the answers

    Por que a inclusão de tail e size na classe SLL torna alguns métodos mais eficientes?

    <p>Isso reduz o número de iterações necessárias para encontrar o último nodo da lista. (A)</p> Signup and view all the answers

    Qual seria a principal dificuldade em implementar uma lista ligada simples (SLL) sem o atributo tail?

    <p>Seria necessário iterar pela lista inteira para encontrar o último nodo. (A)</p> Signup and view all the answers

    Qual é o comportamento de uma stack na manipulação de dados?

    <p>LIFO (Last In, First Out) (A)</p> Signup and view all the answers

    Qual operação não pertence às funcionalidades básicas de uma fila (queue)?

    <p>push(objeto) (A)</p> Signup and view all the answers

    O que acontece quando um objeto é inserido em uma queue?

    <p>É colocado no fim da fila (D)</p> Signup and view all the answers

    Qual método de uma queue devolve o objeto que está na frente sem removê-lo?

    <p>first() (B)</p> Signup and view all the answers

    Qual dos seguintes métodos retorna a quantidade de objetos em uma queue?

    <p>size() (B)</p> Signup and view all the answers

    Qual das seguintes operações é responsável por adicionar elementos a uma fila?

    <p>enqueue() (D)</p> Signup and view all the answers

    Qual das seguintes afirmações sobre as filas (Queue) é INCORRETA?

    <p>Os métodos poll() e peek() lançam exceções quando a fila está vazia. (A)</p> Signup and view all the answers

    Qual método na interface java.util.Queue é correspondente ao método que remove um elemento e lança uma exceção se a fila estiver vazia?

    <p>remove() (A)</p> Signup and view all the answers

    Qual é a principal diferença entre a implementação de uma fila estática e uma fila dinâmica?

    <p>Fila estática usa um array, fila dinâmica usa listas ligadas. (B)</p> Signup and view all the answers

    O que acontece quando tentamos adicionar um elemento a uma fila estática cheia usando o método add()?

    <p>Lança uma IllegalStateException. (D)</p> Signup and view all the answers

    Qual é a finalidade dos métodos poll() e peek() na implementação de filas?

    <p>Devolver e remover elementos, retornando null para filas vazias. (B)</p> Signup and view all the answers

    Em uma fila, o que indica a posição do próximo elemento a ser removido?

    <p>O índice do primeiro elemento. (D)</p> Signup and view all the answers

    Qual é a principal aplicação de uma fila na computação?

    <p>Gerenciamento de filas de espera. (D)</p> Signup and view all the answers

    Qual é a principal limitação de uma stack estática?

    <p>O tamanho deve ser definido inicialmente e não pode ser alterado. (C)</p> Signup and view all the answers

    Qual é a principal vantagem de uma stack dinâmica sobre uma stack estática?

    <p>A memória utilizada é ajustada conforme necessário. (D)</p> Signup and view all the answers

    Na implementação de uma stack dinâmica usando uma lista ligada simples, qual o método utilizado para acessar o elemento do topo?

    <p>top() (B)</p> Signup and view all the answers

    Na implementação de uma stack dinâmica, qual o atributo da classe utilizada para armazenar os elementos?

    <p>SinglyLinkedList (C)</p> Signup and view all the answers

    Quando se considera a política de inserção e remoção em uma stack dinâmica, como são feitos estes processos?

    <p>Through push() for insertion and pop() for removal. (A)</p> Signup and view all the answers

    Qual é uma característica comum de uma stack dinâmica implementada com uma lista ligada simples?

    <p>O acesso aos elementos ocorre pelo início da lista. (B)</p> Signup and view all the answers

    Para que serve a classe LinkedStack na implementação de uma stack dinâmica?

    <p>Mapear os métodos da SinglyLinkedList para a interface Stack. (A)</p> Signup and view all the answers

    Qual método é usado para remover o elemento do topo em uma stack dinâmica?

    <p>pop() (B)</p> Signup and view all the answers

    Como é alterada a posição do primeiro elemento de uma fila após a remoção de um elemento?

    <p>f = (f+1) % N; (D)</p> Signup and view all the answers

    Qual é a principal característica de uma Deque em comparação a uma Queue?

    <p>A Deque suporta a inserção e remoção em ambas as extremidades. (C)</p> Signup and view all the answers

    Qual das seguintes implementações permite que uma fila tenha um comportamento semelhante a uma lista ligada simples?

    <p>LinkedQueue (B)</p> Signup and view all the answers

    Qual é a operação realizada pelo algoritmo dequeue quando a fila está vazia?

    <p>Retorna um objeto nulo. (D)</p> Signup and view all the answers

    Qual das seguintes situações pode ser modelada mais eficientemente por uma Deque do que por uma Queue tradicional?

    <p>A lista de espera em um restaurante onde clientes podem ser retirados e colocados novamente no início. (C)</p> Signup and view all the answers

    O que acontece com o tamanho da fila após a execução bem-sucedida do algoritmo dequeue?

    <p>O tamanho diminui em um. (D)</p> Signup and view all the answers

    Qual das seguintes afirmações é verdadeira sobre o funcionamento de uma Deque?

    <p>Ela pode atuar como uma Stack ou uma Queue. (D)</p> Signup and view all the answers

    De acordo com a estrutura de uma Queue estática, o que é necessário para a remoção de um elemento?

    <p>Um índice que aponta para o primeiro elemento. (D)</p> Signup and view all the answers

    O que acontece ao inserir um elemento no início de uma deque quando ela está cheia?

    <p>Uma exceção IllegalStateException é lançada. (C)</p> Signup and view all the answers

    Qual método é responsável por decrementar o número de elementos na deque após remover o último elemento?

    <p>removeLast() (B)</p> Signup and view all the answers

    Qual é a função do método last() na implementação de uma deque?

    <p>Devolve o último elemento da deque. (B)</p> Signup and view all the answers

    Qual dos métodos da interface Iterator verifica se existe mais elementos a serem iterados?

    <p>hasNext() (C)</p> Signup and view all the answers

    O que acontece quando o método next() é chamado numa coleção ao usar a interface Iterator?

    <p>Ele devolve o próximo elemento e avança para o seguinte. (B)</p> Signup and view all the answers

    Qual é o requisito básico para que uma coleção se torne iterável?

    <p>A coleção deve implementar a interface Iterable. (C)</p> Signup and view all the answers

    O que um iterador específico deve retornar ao ser chamado?

    <p>Um iterador do tipo Iterator. (A)</p> Signup and view all the answers

    Qual é a principal finalidade do método iterator() na interface Iterable?

    <p>Devolver um iterador para a coleção. (D)</p> Signup and view all the answers

    Como devem ser definidas as classes internas para os iteradores específicos?

    <p>Devem implementar a interface java.util.Iterator. (B)</p> Signup and view all the answers

    O que deve refletir a interface Stack para garantir que qualquer stack seja iterável?

    <p>A interface Stack deve estender a interface Iterable. (D)</p> Signup and view all the answers

    Qual das seguintes coleções não foi mencionada como exemplo na implementação de iteradores?

    <p>ArrayMap. (A)</p> Signup and view all the answers

    Qual é a característica de um 'lazy iterator' em comparação a outros estilos de iteradores?

    <p>Carrega elementos sob demanda. (C)</p> Signup and view all the answers

    Qual é o primeiro passo ao tornar as coleções como ArrayStack e LinkedStack iteráveis?

    <p>Implementar a interface Iterable na coleção. (C)</p> Signup and view all the answers

    Qual é a principal razão para tornar a lista ligada iterável na implementação da coleção LinkedStack?

    <p>Para permitir que a coleção LinkedStack seja usada com loops <code>for</code> e <code>foreach</code>. (B)</p> Signup and view all the answers

    Como é que a coleção LinkedStack, que usa uma lista ligada internamente, consegue suportar a iteração?

    <p>Implementando a interface <code>Iterator</code> e fornecendo métodos para acessar os nodos da lista ligada. (D)</p> Signup and view all the answers

    Qual é a principal vantagem de tornar a lista ligada iterável no contexto da implementação de coleções baseadas em listas ligadas?

    <p>Simplifica a implementação de coleções iteráveis com base em listas ligadas. (A)</p> Signup and view all the answers

    Qual é a interface que as coleções iteráveis devem implementar para permitir a iteração?

    <p><code>Iterable</code> (C)</p> Signup and view all the answers

    Em qual das seguintes situações a implementação de iteradores para listas ligadas seria particularmente útil?

    <p>Quando se pretende iterar sobre todos os elementos da lista ligada, um por um. (C)</p> Signup and view all the answers

    Qual das seguintes afirmações é verdadeira sobre a relação entre a interface Stack e a interface Iterable ?

    <p>A interface <code>Stack</code> herda da interface <code>Iterable</code> para tornar as coleções <code>Stack</code> iteráveis. (C)</p> Signup and view all the answers

    Qual é a principal diferença entre a iteração sobre uma coleção ArrayQueue e uma coleção ArrayDeque usando um iterador?

    <p>A iteração para <code>ArrayDeque</code> oferece mais flexibilidade, permitindo a iteração em ambas as direções (frente e trás). (A)</p> Signup and view all the answers

    Qual é o principal benefício de usar iteradores para iterar sobre coleções em geral?

    <p>Os iteradores simplificam a iteração sobre coleções, abstraindo os detalhes da implementação interna. (A)</p> Signup and view all the answers

    No contexto apresentado, qual é o significado da palavra chave protected aplicada aos métodos addBetween e remove?

    <p>Os métodos agora podem ser acessados por classes dentro do mesmo pacote e por subclasses da classe <code>SortedDoublyLinkedList</code>. (A)</p> Signup and view all the answers

    A frase "Felizmente, o Java permite-nos impor este tipo de restrição..." refere-se a qual restrição?

    <p>A restrição de que o tipo de dados <code>E</code> utilizado na classe <code>SortedDoublyLinkedList</code> deve implementar a interface <code>Comparable</code>. (A)</p> Signup and view all the answers

    Na classe SortedDoublyLinkedList, qual é o propósito do método ceilingNode(e)?

    <p>Encontrar o nó que contém o elemento <code>e</code> ou o nó seguinte a ele. (B)</p> Signup and view all the answers

    Por que a restrição extends Comparable é aplicada ao parâmetro tipo E na classe SortedDoublyLinkedList?

    <p>Para garantir que os objetos do tipo <code>E</code> possam ser comparados usando o método <code>compareTo()</code>. (B)</p> Signup and view all the answers

    No código do método put(e), o que o bloco else faz?

    <p>Insere o elemento <code>e</code> na lista, mantendo a ordem crescente, antes do nó <code>n</code>. (A)</p> Signup and view all the answers

    Qual é a principal vantagem de utilizar uma SortedDoublyLinkedList em comparação com uma DoublyLinkedList?

    <p>A <code>SortedDoublyLinkedList</code> garante que os elementos sejam armazenados em ordem crescente, simplificando a busca por elementos específicos. (A)</p> Signup and view all the answers

    Qual é o objetivo do método remove(e) na classe SortedDoublyLinkedList?

    <p>Remover o elemento <code>e</code> da lista, se existir, e retornar o elemento removido. (D)</p> Signup and view all the answers

    Com base no trecho do código fornecido, qual é o tipo de estrutura de dados implementada pela classe SortedDoublyLinkedList?

    <p>Lista ligada duplamente ordenada. (A)</p> Signup and view all the answers

    Em relação à iterabilidade da SortedDoublyLinkedList, o que significa a frase "já é uma estrutura iterável"?

    <p>A classe SortedDoublyLinkedList herda o método <code>iterator()</code> da classe DoublyLinkedList, que por sua vez implementa <code>Iterable</code>. (A)</p> Signup and view all the answers

    Por que a afirmação "Assume-se (por herança) como implementadora da interface Iterable" é verdadeira para a SortedDoublyLinkedList?

    <p>A classe SortedDoublyLinkedList herda o método <code>iterator()</code> da classe <code>DoublyLinkedList</code>, que implementa a interface <code>Iterable</code>. (A)</p> Signup and view all the answers

    De acordo com o contexto fornecido, qual o objetivo da classe Entry?

    <p>Representar um par chave-valor, sendo genérica para diferentes tipos de dados. (D)</p> Signup and view all the answers

    Qual a razão para que a chave da classe Entry seja comparável (necessariamente comparável)?

    <p>Para permitir a ordenação dos nodos na <code>SortedDoublyLinkedList</code>. (A)</p> Signup and view all the answers

    Qual a principal diferença entre a interface Map do Java e a versão simplificada apresentada no texto?

    <p>A versão simplificada possui menos métodos que a interface <code>Map</code> original do Java. (B)</p> Signup and view all the answers

    Qual a principal função do header e do trailer na lista ligada duplamente ordenada (SortedDoublyLinkedList)?

    <p>Oferecer um ponto de referência para percorrer a lista em ambas as direções. (A)</p> Signup and view all the answers

    A partir do texto, qual a característica essencial para que uma lista ligada duplamente ordenada (SortedDoublyLinkedList) funcione corretamente?

    <p>A capacidade de ordenar os elementos da lista em ordem crescente ou decrescente. (D)</p> Signup and view all the answers

    Que tipo de classe é a classe AbstractMap?

    <p>Uma classe abstrata que implementa parcialmente a interface <code>Map</code>. (A)</p> Signup and view all the answers

    O que a classe interna Entry faz?

    <p>Armazena as chaves e valores de um dicionário. (C)</p> Signup and view all the answers

    Qual é a vantagem de usar uma classe abstrata como AbstractMap?

    <p>Permite a criação de diferentes tipos de dicionários sem a necessidade de reimplementar métodos comuns. (A)</p> Signup and view all the answers

    Qual é a função do método isEmpty() na classe AbstractMap?

    <p>Verifica se o dicionário está vazio. (B)</p> Signup and view all the answers

    Qual é a razão para a classe Entry implementar a interface Comparable?

    <p>Permitir que os pares chave/valor sejam ordenados em um dicionário. (D)</p> Signup and view all the answers

    Qual dos seguintes métodos NÃO está definido na interface Map?

    <p>clear() (D)</p> Signup and view all the answers

    Qual é a finalidade do método put() na interface Map?

    <p>Inserir um novo par chave/valor no dicionário. (D)</p> Signup and view all the answers

    O que acontece quando o método setValue() é chamado em um objeto Entry?

    <p>O valor associado à chave é modificado. (D)</p> Signup and view all the answers

    Qual dos seguintes NÃO é um motivo para coleções ordenadas serem utilizadas em dicionários?

    <p>A ordenação torna desnecessária a busca por valores, pois a chave determina diretamente a posição do elemento. (D)</p> Signup and view all the answers

    Study Notes

    Implementação de Estruturas de Dados Lineares

    • As estruturas de dados lineares incluem listas ligadas, Stacks, Queues, Deques, Maps, Iteradores e Comparadores.
    • Os arrays são estruturas de dados de baixo nível, adequadas para guardar coleções de elementos de forma linear. No entanto, possuem capacidade fixa, o que pode ser um inconveniente se a coleção precisar de crescer ou diminuir. As operações de inserção e remoção no meio da estrutura podem ser morosas.
    • As listas ligadas oferecem uma alternativa dinâmica aos arrays. A capacidade da lista pode mudar de forma adaptável com a adição ou remoção de elementos. As operações de inserção e remoção de elementos no meio da lista não são morosas.
    • A lista ligada simples (Singly Linked List - SLL) se organiza com uma sequência de nodos. Cada nodo armazena um elemento e um apontador para o próximo nodo.
    • A classe Node é definida como genérica e interna à classe SLL, permitindo acomodar diferentes tipos de dados.
    • As listas duplamente ligadas (Doubly Linked Lists - DLL) podem ser percorridas em ambos os sentidos. Cada nodo armazena um elemento, um apontador para o nodo anterior (prev) e um apontador para o nodo seguinte (next).
    • Há nodos sentinelas (header e trailer) adicionados às DLL para facilitar operações nos extremos da lista, mesmo quando a lista está vazia.
    • A inserção é uma operação eficiente nas listas ligadas, uma vez que não é necessário deslocar elementos.
    • No entanto, a remoção de um elemento não é tão eficiente quanto a inserção.
    • As operações de inserção e remoção em listas ligadas são geralmente de complexidade O(1), exceto quando a operação visa um determinado elemento no meio da lista, onde podem ter complexidade O(n). Em listas duplamente ligadas esse tempo é ainda mais eficiente. As operações nos extremos O(1) em SLL e DLL.
    • As operações de inserção e remoção em listas ligadas são geralmente de complexidade O(1) nos extremos, e de O(n) no interior da lista. Em listas duplamente ligadas, as operações nos extremos também são O(1).

    Studying That Suits You

    Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

    Quiz Team

    Related Documents

    Implementação de Estruturas de Dados Lineares PDF
    Estruturas Lineares - Stacks (PDF)
    Iteração da ArrayQueue e ArrayDeque PDF

    Description

    Este quiz explora as estruturas de dados lineares, como listas ligadas, Stacks e Queues. Você aprenderá sobre as vantagens das listas ligadas em comparação aos arrays e como as operações de inserção e remoção funcionam de maneira eficiente. Teste seu conhecimento sobre as diferentes implementações e suas características.

    More Like This

    Use Quizgecko on...
    Browser
    Open
    Browser
    Browser