Lista de exercícios de Estruturas de dados com respostas

Qual operação é O(1) em um array, mas O(n) em uma lista simplesmente encadeada?

1. AAcessar o elemento no índice i
2. BLer o primeiro elemento
3. CInserir no início
4. DRemover o elemento do início

Onde fica o menor elemento de um min-heap binário?

1. AEm qualquer folha, que precisa ser procurada
2. BNa folha mais à esquerda
3. CNa última posição do array
4. DNa raiz

Qual é a característica que define um conjunto (set) como tipo abstrato de dados?

1. AArmazena pares chave–valor
2. BArmazena elementos em ordem crescente
3. CPermite acesso apenas por uma das pontas
4. DArmazena elementos sem duplicatas

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. A4 2 5 1 3
2. B4 5 2 3 1
3. C1 2 3 4 5
4. D1 2 4 5 3

Em um heap binário armazenado em um array a partir do índice 0, onde está o pai do nó no índice i?

1. ANo índice i − 1
2. BNo índice ⌊(i − 1) / 2⌋
3. CNo índice 2i + 1
4. DNo índice ⌊i / 2⌋ + 1

Quanto tempo leva verificar se a aresta (u, v) existe usando uma matriz de adjacência?

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

Inserir uma chave em uma árvore AVL deixa a subárvore esquerda de um nó alta demais, e a nova chave foi para a subárvore esquerda do seu filho esquerdo (caso esquerda-esquerda). Qual correção é aplicada?

1. AUma rotação simples à esquerda no nó desbalanceado
2. BUma rotação simples à direita no nó desbalanceado
3. CUma rotação à esquerda no filho e depois uma à direita no nó
4. DRecolorir o nó e o seu filho

Quais são os custos de tempo e de espaço extra para inverter no próprio lugar uma lista simplesmente encadeada?

1. ATempo O(n) e espaço extra O(1)
2. BTempo O(n) e espaço extra O(n)
3. CTempo O(n log n) e espaço extra O(1)
4. DTempo O(1) e espaço extra O(1)