Lista de exercícios de Estruturas de dados com respostas

Em uma árvore, o que são nós irmãos?

1. ANós que não têm filhos
2. BUm nó e o seu pai
3. CNós na mesma profundidade em subárvores diferentes
4. DNós que têm o mesmo pai

Qual é o nome da operação de pilha que adiciona um elemento no topo?

1. APop
2. BEnqueue
3. CPeek
4. DPush

Em que ordem um percurso em pré-ordem (preorder) de uma árvore binária visita os nós?

1. ANível por nível a partir do topo
2. BSubárvore esquerda, depois nó, depois subárvore direita
3. CNó, depois subárvore esquerda, depois subárvore direita
4. DSubárvore esquerda, depois subárvore direita, depois nó

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

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

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 pré-ordem?

1. A1 2 4 5 3
2. B1 2 3 4 5
3. C4 5 2 3 1
4. D4 2 5 1 3

Quantos nós tem uma árvore binária perfeita de altura h, com a altura contada em arestas?

1. A2^h+1 − 1
2. B2h + 1
3. C2^h
4. Dh²

A complexidade de tempo de decrease-key em um heap binário (dada a posição do elemento) é:

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

Por que um servidor pode escolher sua função hash ao acaso a partir de uma família universal?

1. APara tornar muito improvável que um atacante escolha muitas chaves que colidam entre si
2. BPara eliminar a necessidade de redimensionar a tabela
3. CPara manter a tabela hash ordenada
4. DPara garantir que duas chaves nunca colidam, quaisquer que sejam as chaves enviadas por um atacante