Para a questão, entre as seguintes estruturas de dados:

1. Árvore de busca balanceada
2. Árvore de busca não balanceada
3. Vetor de elementos ordenados
4. Lista ligada de elementos ordenados
5. Lista duplamente ligada de elementos ordenados

Quantas permitem percorrer os elementos tanto em ordem crescente quanto decrescente em \( O(n) \) tempo e \( O(n) \) espaço adicional, no pior caso?

Para a questão, entre as seguintes estruturas de dados:

1. Árvore de busca balanceada
2. Árvore de busca não balanceada
3. Vetor de elementos ordenados
4. Lista ligada de elementos ordenados
5. Lista duplamente ligada de elementos ordenados

Quantas permitem percorrer os elementos tanto em ordem crescente quanto decrescente em \( O(n) \) tempo e \( O(\log n) \) espaço adicional, no pior caso?

Sobre as estruturas listadas abaixo (árvores balanceadas, listas), quais destas estruturas de dados NÃO podem ser concatenadas em O(1), mantendo as propriedades indicadas em cada alternativa?

Definição da operação de Partição:

Entrada: uma lista ordenada de números, e um valor pivô. Saída: a mesma lista reordenada. Tal que sigam a seguinte ordenação: valores menores que pivô, seguidos de valores iguais a pivô, seguidos de valores maiores que pivô.

Por exemplo:

Entrada: {3, 4, 2, 9, 4, 5, 2, 8}, pivo 5

Saída: {3, 4, 2, 4, 2, 5, 9, 8}

Partição é usada para implementar a função Quicksort.

Se alguma opção de a) a d) for falsa, marque-a. Caso contrário, marque e).

Considere as definições:

public class SuperClass {
    public int op(int a, int b) { return a - b; }
}
public class SubClass extends SuperClass {
    public int op(int a, int b) { return a + b; }
}
// código Cliente de SuperClass e SubClass
SuperClass supC = new SuperClass( ); // linha 01
SubClass subC = new SubClass( );    // linha 02
x1 = supC.op(6,4);                  // linha 03
supC = subC;                        // linha 04
x2 = supC.op(6,4);                  // linha 05

Assinale a alternativa mais correta sobre os valores de x1 e x2 depois da execução do pseudo-código acima.

Sobre o padrão de projeto Iterator, onde, ao invés de percorrer uma estrutura com índices e ponteiros, há um objeto Iterator, com operações similares a begin, end, next. Suponha que várias estruturas de dados em uma biblioteca implementem Iterator.

Uma sintaxe comum para percorrer todos os itens de uma estrutura de dados E é:

tipo::iterator it;
for (it = E.begin(); it != E.end(); ++it) {
  // algum código onde o valor de cada item é acessado com *it
}

onde 'tipo' é um tipo apropriado de estrutura de dados, por exemplo, std::vector<string>.

Marque a opção FALSA.

Para a questão, defina \( G_{n \times n} \) como um grafo não dirigido 2D grid com 4-vizinhança da seguinte forma:

cada vértice é identificado com uma coordenada inteira 2D, de (1,1) até (n,n); há n x n vértices, correspondendo a todos os valores de (1,1) até (n,n); em cada vértice incidem até 4 arestas, a saber, para um vértice (i,j)

(i,j) ↔ (i-1,j)

(i,j) ↔ (i+1,j)

(i,j) ↔ (i ,j-1)

(i,j) ↔ (i ,j+1)

onde as arestas não existem se alguma coordenada é < 1 ou > n. A Figura 1 (a seguir) mostra um exemplo para n = 5

Suponha que os vizinhos de um vértice, durante a execução do DFS, são sempre listados na ordem Norte, Leste, Sul, Oeste, onde os pontos cardeais correspondem a uma realização do grafo sobre um sistema de coordenadas da forma trivial: o vértice (i,j) será colocado na coordenada (i,j), a primeira coordenada corresponde ao eixo Oeste (-) Leste (+), e a segunda ao eixo Sul (-) Norte (+), ainda correspondendo à figura anterior.

Suponha que o DFS inicia no vértice (1,1), e aplicamos a operação de contração sobre a árvore de busca DFS. Podemos afirmar:

Para a questão, defina \( G_{n \times n} \) como um grafo não dirigido 2D grid com 4-vizinhança da seguinte forma:

cada vértice é identificado com uma coordenada inteira 2D, de (1,1) até (n,n); há n x n vértices, correspondendo a todos os valores de (1,1) até (n,n); em cada vértice incidem até 4 arestas, a saber, para um vértice (i,j)

(i,j) ↔ (i-1,j)

(i,j) ↔ (i+1,j)

(i,j) ↔ (i ,j-1)

(i,j) ↔ (i ,j+1)

onde as arestas não existem se alguma coordenada é < 1 ou > n. A Figura 1 (a seguir) mostra um exemplo para n = 5

Ao aplicar o algoritmo DFS a \( G_{n \times n} \) para obter uma árvore de busca, contendo apenas as arestas entre sucessor e antecessor na busca DFS, podemos afirmar sobre esta árvore:

Para a questão, defina \( G_{n \times n} \) como um grafo não dirigido 2D grid com 4-vizinhança da seguinte forma:

cada vértice é identificado com uma coordenada inteira 2D, de (1,1) até (n,n); há n x n vértices, correspondendo a todos os valores de (1,1) até (n,n); em cada vértice incidem até 4 arestas, a saber, para um vértice (i,j)

(i,j) ↔ (i-1,j)

(i,j) ↔ (i+1,j)

(i,j) ↔ (i ,j-1)

(i,j) ↔ (i ,j+1)

onde as arestas não existem se alguma coordenada é < 1 ou > n. A Figura 1 (a seguir) mostra um exemplo para n = 5

Defina uma operação de 'contração' da seguinte forma:

para cada vértice u de grau 2

se u foi deletado, ignore e continue o 'para'.

v1 e v2 são os 2 vizinhos de u

se não existe aresta (v1,v2)

adicione ao grafo uma aresta (v1,v2)

delete u, (u,v1), (u,v2)

Se aplicarmos a operação de contração a \( G_{nxn} \), gerando um grafo \( G'_{nxn} \), quantos vértices e arestas a menos terá \( G'_{nxn} \) em relação ao grafo original, supondo n maior que 10:

Para a questão, defina \( G_{n \times n} \) como um grafo não dirigido 2D grid com 4-vizinhança da seguinte forma:

cada vértice é identificado com uma coordenada inteira 2D, de (1,1) até (n,n); há n x n vértices, correspondendo a todos os valores de (1,1) até (n,n); em cada vértice incidem até 4 arestas, a saber, para um vértice (i,j)

(i,j) ↔ (i-1,j)

(i,j) ↔ (i+1,j)

(i,j) ↔ (i ,j-1)

(i,j) ↔ (i ,j+1)

onde as arestas não existem se alguma coordenada é < 1 ou > n. A Figura 1 (a seguir) mostra um exemplo para n = 5

Marque a resposta mais exata e precisa. O número de arestas em \( G_{n \times n} \) é: