Lista de exercícios de Estruturas de dados com respostas

Qual estrutura de dados funciona segundo o princípio "último a entrar, primeiro a sair" (LIFO)?

1. APilha (stack)
2. BFila (queue)
3. CTabela hash
4. DLista encadeada

Um grafo é formado por:

1. AVértices (nós) conectados por arestas
2. BApenas chaves e hashes
3. CApenas uma raiz e folhas
4. DLinhas e colunas

A altura de uma árvore é comumente definida como:

1. AO número de folhas da árvore
2. BO número de filhos da raiz
3. CO número total de nós da árvore, contando a raiz e todas as folhas
4. DO número de arestas no caminho mais longo da raiz até uma folha

Como se encontra a menor chave em uma árvore binária de busca?

1. ASeguindo os filhos direitos a partir da raiz até não haver filho direito
2. BVisitando todas as folhas e comparando-as
3. COlhando apenas a raiz
4. DSeguindo os filhos esquerdos a partir da raiz até não haver filho esquerdo

Que condição de balanceamento uma árvore AVL mantém em todo nó?

1. AAs duas subárvores de todo nó têm exatamente o mesmo número de nós
2. BAs alturas das subárvores esquerda e direita diferem no máximo em 1
3. CTodas as folhas estão exatamente na mesma profundidade
4. DTodo nó é colorido de vermelho ou preto

Por que percorrer um array costuma ser muito mais rápido na prática do que percorrer uma lista encadeada do mesmo tamanho?

1. AOs elementos do array são contíguos, então aproveitam bem o cache da CPU
2. BArrays usam menos instruções para comparar valores
3. CListas encadeadas sempre armazenam os elementos em disco
4. DPercorrer um array é O(1) no total, enquanto percorrer uma lista encadeada é O(n)

Uma árvore de Fenwick (binary indexed tree) sobre um array de n números permite quais operações em O(log n)?

1. AEncontrar a mediana em O(1)
2. BInserir elementos em qualquer posição
3. CConsultas de soma de prefixo e atualizações de um único elemento
4. DOrdenar o array e fazer busca binária

Sem união por posto nem compressão de caminho, qual é o custo no pior caso de um único find em uma estrutura union-find com n elementos?

1. AO(1)
2. BO(n)
3. CO(log n)
4. DO(α(n))