1.Fácil
Na representação de um grafo por lista de adjacência, o que é armazenado para cada vértice?
- AUma linha de V valores booleanos
- BUma lista dos seus vértices vizinhos
- CO caminho mínimo até todos os outros vértices
- DO número total de arestas do grafo
2.Fácil
A profundidade de um nó em uma árvore é:
- AO número de nós da sua subárvore
- BO número de arestas desse nó até a folha mais profunda
- CO número de filhos desse nó
- DO número de arestas da raiz até esse nó
3.Fácil
Em uma árvore, o que são nós irmãos?
- AUm nó e o seu pai
- BNós na mesma profundidade em subárvores diferentes
- CNós que têm o mesmo pai
- DNós que não têm filhos
4.Média
Qual tipo abstrato de dados o algoritmo de Dijkstra usa para escolher o próximo vértice a processar?
- AUma pilha
- BUma fila de prioridade mínima
- CUm conjunto sem ordem
- DUma fila FIFO
5.Média
Uma fila é implementada com duas pilhas: push numa pilha "in" e pop numa pilha "out", reabastecida a partir de "in" quando está vazia. Qual é o custo amortizado por operação?
- AO(log n)
- BO(n²)
- CO(1)
- DO(n)
6.Média
O que é verdade sobre a matriz de adjacência de um grafo não direcionado?
- AA diagonal principal sempre contém uns
- BCada linha tem exatamente um 1
- CÉ simétrica em relação à diagonal principal
- DÉ sempre triangular superior
7.Difícil
Um nó AVL está desbalanceado porque a subárvore direita do seu filho esquerdo ficou alta demais (caso esquerda-direita). Qual correção é aplicada?
- AUma rotação simples à esquerda no nó
- BUma rotação à direita no filho esquerdo e depois uma à esquerda no nó
- CUma rotação à esquerda no filho esquerdo e depois uma à direita no nó
- DUma rotação simples à direita no nó
8.Difícil
Como detectar se uma lista simplesmente encadeada contém um ciclo usando O(1) de memória extra?
- AMover um ponteiro um passo e outro dois passos e verificar se eles se encontram
- BContar os nós até a contagem passar do campo de tamanho da lista
- CGuardar cada nó visitado em um conjunto hash
- DOrdenar a lista e procurar duplicatas
Gabarito
- 1. B · Uma lista dos seus vértices vizinhos
- 2. D · O número de arestas da raiz até esse nó
- 3. C · Nós que têm o mesmo pai
- 4. B · Uma fila de prioridade mínima
- 5. C · O(1)
- 6. C · É simétrica em relação à diagonal principal
- 7. C · Uma rotação à esquerda no filho esquerdo e depois uma à direita no nó
- 8. A · Mover um ponteiro um passo e outro dois passos e verificar se eles se encontram
Soluções completas passo a passo: pratique este tópico em examproblems.com.