Lista de exercícios de Estruturas de dados com respostas

Em um grafo não direcionado, o que é o grau de um vértice?

1. AO número de arestas ligadas a ele
2. BO comprimento do caminho mais longo a partir dele
3. CO número de vértices do grafo
4. DSua posição na lista de adjacência

Na representação de um grafo por lista de adjacência, o que é armazenado para cada vértice?

1. AUma lista dos seus vértices vizinhos
2. BO número total de arestas do grafo
3. CO caminho mínimo até todos os outros vértices
4. DUma linha de V valores booleanos

Uma tabela hash armazena dados como:

1. AUma string de tamanho fixo
2. BApenas uma lista ordenada
3. CPares chave–valor localizados por uma função hash
4. DUma árvore com chaves ordenadas

Quanta memória uma matriz de adjacência usa para um grafo com V vértices?

1. AO(V + E)
2. BO(V²)
3. CO(E)
4. DO(log V)

Uma rede rodoviária tem 100,000 cruzamentos, cada um ligado a cerca de 4 outros. Qual representação é mais adequada?

1. AMatriz de adjacência
2. BLista de adjacência
3. CUm único array ordenado de vértices
4. DUm heap binário de arestas

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

1. ANo nó mais à esquerda da sua subárvore direita
2. BNo nó mais à direita da sua subárvore esquerda
3. CSempre no seu pai
4. DSempre no seu filho direito

Que garantia as regras da árvore rubro-negra dão sobre a altura de uma árvore com n chaves?

1. AA altura é no máximo n / 2
2. BA altura é exatamente log₂ n
3. CA altura é no máximo log₂ n + 1
4. DA altura é no máximo 2 log₂(n + 1)

Qual estrutura de dados permite um cache LRU (least recently used) com get e put em O(1)?

1. AApenas uma árvore binária de busca
2. BUm único array ordenado
3. CApenas uma pilha
4. DUm hash map combinado com uma lista duplamente encadeada