Lista de exercícios de Estruturas de dados com respostas

A altura de uma árvore é comumente definida como:

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

Qual estrutura é normalmente usada para implementar uma fila de prioridade?

1. AUma string
2. BUm heap
3. CUma lista simplesmente encadeada sem ordem
4. DUma pilha

Qual operação é lenta em um array, mas rápida no início de uma lista encadeada?

1. ALer o último elemento pelo índice
2. BObter o tamanho de um array de tamanho fixo
3. CAcessar o 5º elemento
4. DInserir no início

Um nó de uma árvore binária de busca tem subárvore direita. Onde está o seu sucessor em ordem?

1. ASempre no seu pai
2. BSempre no seu filho direito
3. CNo nó mais à direita da sua subárvore esquerda
4. DNo nó mais à esquerda da sua subárvore direita

Uma árvore binária tem raiz 1 com filho esquerdo 2 e filho direito 3; o nó 2 tem filhos 4 (esquerdo) e 5 (direito). Qual é o percurso em pós-ordem?

1. A4 5 2 3 1
2. B5 4 3 2 1
3. C1 2 4 5 3
4. D4 2 5 1 3

O que acontece quando uma tabela hash faz rehash depois que o fator de carga passa de um limite?

1. ASó as chaves que colidiram são movidas para uma nova lista de overflow no fim da tabela
2. BAs chaves existentes são ordenadas no próprio lugar
3. CAs chaves mais antigas são apagadas para abrir espaço
4. DUma tabela maior é alocada e todas as chaves são inseridas de novo

Qual afirmação sobre o heapsort está correta?

1. AÉ estável e precisa de O(n) de memória extra
2. BPrecisa de uma árvore binária de busca como armazenamento extra, então usa O(n) de memória adicional
3. CRoda em tempo O(n) para qualquer entrada
4. DOrdena no próprio lugar em O(n log n) no pior caso, mas não é estável

Você precisa guardar os k menores valores de um fluxo de n números usando O(k) de memória. Qual abordagem funciona em tempo O(n log k)?

1. AUm max-heap de tamanho k, substituindo a raiz quando chega um valor menor
2. BUma fila FIFO com os últimos k valores
3. CUm min-heap com todos os n valores, do qual os k menores são removidos no final
4. DUm array ordenado com todos os n valores