Estrutura de Dados

Ponteiros desempenham um papel crucial quando uma variável precisa ser acessada em diferentes partes de um programa. Nesse contexto, é comum encontrar diversos ponteiros distribuídos por várias seções do código, cada um apontando para a variável que contém os dados necessários. Uma vantagem significativa dessa abordagem é que, se esses dados forem alterados, não há preocupação, pois todos os ponteiros no programa estão direcionados para o endereço onde os dados atualizados residem. Essa flexibilidade oferecida pelos ponteiros é fundamental para garantir a eficiência e a consistência na manipulação de dados em diferentes partes do código.

Considerando o uso de ponteiros em estruturas de dados, analise o seguinte código em C:

#include <stdio.h>


int main() {

    int arr[5] = {1, 2, 3, 4, 5};

    int *ptr = arr;

    printf("%d\n", *ptr + 2);

    printf("%d\n", *(ptr + 2));

    printf("%d\n", ptr[2]);

    printf("%d\n", *ptr++);

    printf("%d\n", (*ptr)++);

    return 0;

}

Diante da análise realizada, assinale a alternativa que apresenta a saída impressa ao executar este código.

Em linguagens de programação podemos contar com operadores relacionais e lógicos, estes que são essenciais para comparar valores, facilitando a tomada de decisões baseadas em condições específicas. Eles verificam a relação entre dois operandos e resultam em um valor booleano (true ou false). Esses operadores são comumente usados em estruturas de controle de fluxo, como condicionais if e laços for e while, para guiar a execução do programa de acordo com as condições avaliadas.

Compreender o uso correto dos operadores relacionais é essencial para desenvolver algoritmos eficazes e garantir que as comparações lógicas sejam realizadas com precisão, sendo assim, assinale a alternativa que apresenta o operador lógico sobre MAIOR ou IGUAL.

Os ponteiros são elementos fundamentais na linguagem C, conferindo-lhe uma notável flexibilidade e poder. Eles funcionam como variáveis especiais tendo a propriedade especial de "apontar" para uma variável. Essa capacidade de apontar para diferentes tipos de variáveis, como inteiros, pontos flutuantes, duplos, entre outros, confere aos ponteiros uma versatilidade excepcional.

Com base em nossos estudos, assinale a alternativa que apresenta a função do operador de referência (&) em estruturas de dados utilizando ponteiros em linguagem C.

Leia o trecho a seguir: 

Vetores (ou arrays) são uma das estruturas de dados mais fundamentais na programação em C++. Eles permitem armazenar múltiplos valores em uma única variável, usando um índice para acessar cada valor individualmente. A posição de cada elemento no vetor é indicada por um índice numérico, começando do zero. Vetores são particularmente úteis quando você precisa armazenar uma coleção de dados e acessar esses dados de forma eficiente através de um índice. Dessa forma, os vetores são estruturas de dados [preencher 1].

Os termos [preencher 1] é corretamente substituído por:

Os vetores são estruturas de dados fundamentais em C++, amplamente utilizadas para armazenar coleções de elementos do mesmo tipo em uma sequência contínua de memória. A definição de um vetor envolve a especificação de seu tamanho e tipo de dados dos elementos que ele irá armazenar. Uma das principais vantagens dos vetores é a capacidade de acessar diretamente qualquer elemento utilizando um índice, o que permite operações rápidas e eficientes. 


Com base no contexto apresentado, veja o trecho de código a seguir:


 

#include <iostream>

using namespace std;

 

int main() {

    int vetor[5] = {10, 20, 30, 40, 50};

    int soma = 0;    

    for(int i = 0; i < 5; i++) {

        soma += vetor[i];

    }    

    cout << "A soma dos elementos do vetor é: " << soma << endl;

    return 0;

}

Diante do código apresentado, assinale a alternativa que apresenta qual será a saída do programa acima quando executado.

Em C++, os ponteiros e as referências são conceitos essenciais na manipulação de endereços de memória. Ponteiros são variáveis que armazenam o endereço de outra variável, permitindo a manipulação direta dos dados em diferentes locais de memória. Referências, por outro lado, são aliases para variáveis existentes e devem ser inicializadas no momento da declaração.

Diante disso, assinale a alternativa que descreve a diferença entre ponteiros e referências em C++.

Para ser implementada, a pilha requer um vetor e uma variável que indique seu tamanho máximo e esta variável pode levar o nome de tam, por exemplo. Ao definir este limite, a pilha só pode contemplar a quantidade de elementos informada nesta variável e para saber quando excede o limite, é necessário saber a quantidade de elementos em dado momento.

Observe as alternativas e escolha a que identifica quantos elementos estão na pilha.

No desenvolvimento de software, um dos conceitos fundamentais na programação orientada a objetos é a modularização do código. Este processo envolve a separação da visão lógica de uma estrutura de dados da sua implementação concreta. Para alcançar essa modularização, é essencial isolar a implementação da interface pública, permitindo que a complexidade interna seja escondida dos usuários da classe. Esta prática não apenas melhora a manutenção do código, mas também promove a reutilização de componentes.

Neste sentido, assinale a alternativa que identifique o termo que representa a ação de ocultamento citada no enunciado:

A pilha é uma das estruturas de dados mais simples que existe, ela permite o acesso aos seus elementos somente a partir do topo, ou seja, quando o elemento entra na pilha, ele passa a ser o canal para manipulação dos dados por ser o único acesso. Isso significa que a retirada de elementos acontece inversamente à forma de como foram colocados, ou seja, o primeiro a sair é o último elemento que entrou na pilha.

Em relação ao que foi citado no enunciado, assinale a alternativa que demonstra a parte do código responsável pela impressão. 

Quando a fila é implementada com um vetor, o espaço para alocar os elementos é adjacente. Isso significa que os elementos são adicionados no fim e removidos do início da fila, e para que isso aconteça é preciso conhecê-la identificando a presença de elementos.

Avalie as alternativas e assinale a que representa as respectivas operações para uma fila, ao ser implementada. 

Na criação da classe Time, a definição de seus atributos é crucial para representar as características de um objeto de tempo. Dentro do arquivo de cabeçalho (.h), os atributos são definidos na seção privada, enquanto os métodos que permitem acessar e modificar esses atributos são definidos na seção pública. 

Diante disso, assinale a alternativa que apresenta um atributo típico definido na seção privada da classe Time. 

Imagine que você está organizando uma fila de atendimento em uma loja. Cada cliente na fila é representado por um cartão, e cada cartão possui uma indicação de quem é o próximo cliente. Esse sistema permite que você facilmente adicione novos clientes ao final da fila ou remova o primeiro cliente após ser atendido.

Qual das seguintes opções compreende a vantagem desse sistema de organização em comparação a um sistema onde todos os cartões estão alinhados em uma única linha e você precisa deslocar todos os cartões ao adicionar ou remover um cliente?

Uma das vantagens em se trabalhar com listas encadeadas é sua versatilidade em poder incluir e remover elementos da lista a qualquer momento. Remover um nó de uma lista encadeada envolve atualizar as referências para garantir a continuidade da lista. O processo de remoção pode variar dependendo da posição do nó a ser removido.

Assinale a alternativa que identifica corretamente o procedimento para remover um nó do meio de uma lista encadeada.

Uma lista encadeada é uma estrutura de dados composta por nós, onde cada nó contém informações sobre a sequência de nós a ser percorrida. Ao contrário de arrays, listas encadeadas não armazenam elementos em posições contíguas na memória, mas sim as posições de apontamentos para os demais nós.

Com base no contexto apresentado e nos materiais de estudos, identifique a alternativa correta que define a principal característica das listas encadeadas. 

Listas circularmente encadeadas são uma variação das listas encadeadas em que o último nó aponta para o primeiro nó, formando um ciclo. Essa estrutura possui algumas vantagens sobre as demais listas quando estamos falando de acesso rápido ao final da lista e para percorrer a uma lista de modo inverso (de trás para frente) se for necessário.

Com relação a este contexto e sobre o conteúdo estudado, avalie as asserções a seguir e a relação proposta entre elas:

I. Listas circularmente encadeadas são úteis para implementar estruturas que requerem iteração contínua sobre os elementos.

PORQUE  

II. Em uma lista circularmente encadeada, o último nó aponta para o primeiro nó, permitindo um acesso contínuo aos elementos sem a necessidade de redefinir o ponto inicial após atingir o final da lista.

A respeito dessas asserções assinale a alternativa correta:

As listas encadeadas são estruturas de dados fundamentais que oferecem uma maneira flexível de armazenar e organizar dados na memória. Diferente das listas sequenciais, as listas encadeadas permitem a inserção e remoção de elementos de forma mais eficiente em termos de alocação de memória.

Considerando a definição e as características de uma lista encadeada, qual das opções abaixo identifica corretamente uma vantagem de usar listas encadeadas em vez de listas sequenciais?

Imagine que você está organizando uma pilha de pratos em uma cozinha. Sempre que um novo prato é lavado, ele é colocado no topo da pilha. Da mesma forma, quando alguém precisa de um prato, ele é retirado do topo da pilha. Isso garante que o prato mais recentemente lavado seja o primeiro a ser utilizado, enquanto os pratos lavados anteriormente permanecem embaixo. Essa organização é eficiente e permite fácil acesso ao prato mais limpo.

Qual das seguintes afirmações interpreta corretamente a operação de inserção (push) em uma pilha implementada com listas encadeadas, considerando as particularidades de gerenciamento de memória e desempenho?

Uma pilha é uma estrutura de dados onde a inserção e a remoção de elementos ocorrem sempre no topo. Ao criar um algoritmo que implementa esta estrutura de dados em uma listas encadeadas, algumas operações básicas são utilizadas para manipular seus elementos na estrutura a ser desenvolvida.

Complete as lacunas abaixo com as palavras corretas que representam as operações básicas de uma pilha.

A operação de inserção de um novo elemento no topo da pilha é chamada de [preencher 1], enquanto a operação de remoção do elemento no topo é chamada de [preencher 2]. A operação que permite visualizar o elemento no topo da pilha sem removê-lo é chamada de [preencher 3] .

Os termos [preencher 1], [preencher 2] e [preencher 3] são corretamente substituídos por:

Na implementação de uma fila utilizando lista encadeada, os métodos de inserção e remoção são fundamentais para o funcionamento correto da estrutura. Essa organização garante a propriedade FIFO (First In, First Out), essencial para diversas aplicações como gerenciamento de tarefas em sistemas operacionais e processamento de dados em buffers. Complete as lacunas na seguinte descrição sobre os métodos de inserção e remoção em uma fila utilizando lista encadeada. 

O método [preencher 1] adiciona um novo nó ao [preencher 2] da fila, atualizando o ponteiro [preencher 3] para apontar para este novo nó. 

Os termos [preencher 1], [preencher 2] e [preencher 3] são corretamente substituídos por:

A implementação de uma pilha utilizando uma lista encadeada que requer a criação de uma estrutura de nó onde é informado os próximos elementos da pilha e funções para realizar operações de inserção (push) um novo elemento na pilha e remoção (pop) de um elemento da pilha já existente.

Complete o código em C++ para implementar as operações básicas (push e pop) de uma pilha utilizando uma lista encadeada. Preencha os espaços em branco indicados por /* ... */ para que o código funcione corretamente.

#include <iostream>

// Estrutura do nó

struct Node {

    int data;

    Node* next;

};

// Classe Pilha com Lista Encadeada

class Stack {

private:

    Node* top;

public:

    Stack() {

        top = nullptr;

    }

    void push(int value) {

        Node* newNode = new Node();

        newNode->data = value;

        newNode->next = /* ... */;

        top = newNode;

    }

    void pop() {

        if (top == nullptr) {

            std::cout << "Stack Underflow" << std::endl;

            return;

        }

        Node* temp = top;

        top = /* ... */;

        delete temp;

    }

}

O preenchimento correto se afirma em:

A função de hash desempenha um papel crucial na determinação da posição de armazenamento dos dados em uma tabela hash. Esta que é eficiente é essencial para minimizar colisões, que acontecem quando duas chaves distintas produzem o mesmo índice. Compreender o propósito e o funcionamento da função de hash é fundamental para o uso eficaz das tabelas hash.



Com base no contexto apresentado, assinale a alternativa que identifica corretamente o propósito da função de hash em uma tabela hash.

Em uma tabela hash, as colisões ocorrem quando duas chaves diferentes são mapeadas para o mesmo índice do array. Diversas técnicas podem ser utilizadas para resolver essas colisões. Entre essas técnicas, o endereçamento aberto é amplamente utilizado. 


Assinale a alternativa que responde corretamente como o endereçamento aberto resolve colisões em uma tabela hash. 

A eficiência de uma função de dispersão é determinada por várias condições essenciais para o bom funcionamento de uma tabela de dispersão. Essas condições garantem que as chaves sejam distribuídas de maneira uniforme e que o número de colisões seja minimizado.

Com relação às características e desafios na implementação de funções de dispersão, analise as asserções a seguir e a relação proposta entre elas:

I. Uma boa função de dispersão deve ser uniforme, ou seja, deve garantir que todos os compartimentos da tabela tenham a mesma probabilidade de serem escolhidos.

PORQUE

II. A uniformidade de uma função de dispersão é difícil de ser testada na prática devido à distribuição desconhecida das chaves.

A respeito dessas asserções, assinale a alternativa correta:

Na implementação de tabelas hash, é importante compreender a criação de métodos construtores e de acesso para manipulação dos dados. Suponhamos que a classe Aluno está sendo implementada com dois construtores, um sem parâmetros e outro com parâmetros, além de métodos de acesso (getters) para o RA e o nome.

Considere a implementação da classe Aluno na tabela hash, leia as seguintes alternativas e assinale qual delas descreve corretamente a aplicação do método construtor sem parâmetros.

No estudo de tabelas hash, um problema comum é a ocorrência de colisões, que ocorrem quando duas chaves diferentes geram o mesmo valor de hash e apontam para a mesma posição na tabela. Para tratar essas colisões, podem ser utilizadas várias técnicas, como o encadeamento separado e o teste linear. O encadeamento separado utiliza uma estrutura de dados adicional, geralmente uma lista encadeada, para armazenar todos os elementos que colidem em uma mesma posição.


Qual das alternativas a seguir descreve corretamente o funcionamento do encadeamento separado em uma tabela hash?

Em uma tabela de dispersão, a eficiência da função de dispersão é fundamental para garantir uma boa performance. Uma função de dispersão eficiente deve cumprir certas condições ideais, cada uma com sua própria descrição. Essas condições incluem minimizar colisões, ser fácil de calcular e garantir que todos os compartimentos da tabela tenham a mesma probabilidade de serem escolhidos. 

Associe corretamente cada condição com a sua descrição correspondente, considerando as características essenciais para o bom funcionamento da tabela de dispersão.

Condições:	Descrições:
1 - Produzir um número baixo de colisões	A. Significa que todos os compartimentos têm a mesma probabilidade de serem escolhidos.
2 - Ser facilmente computável	B. Importante para evitar padrões conhecidos nas chaves.
3 - Ser uniforme	C. Essencial para minimizar o tempo de cálculo em tabelas armazenadas em memória.

Assinale a alternativa correta:

Suponha que existam 𝑛 chaves a serem armazenadas em uma tabela 𝑇, sequencial e de dimensão 𝑚. As posições da tabela se situam no intervalo $[0,m-1]$[0, m-1]. Em um caso simples, onde o número de chaves $n$n n é igual ao número de compartimentos 𝑚, os valores das chaves são 0, 1, ..., $m-1$m-1 Utiliza-se diretamente o valor de cada chave como seu índice na tabela, técnica conhecida como acesso direto. No entanto, para resolver a questão de armazenamento eficiente quando $n<m$n e $m-n$m-n é grande, emprega-se a função de dispersão $h\left(x\right)$h(x), que transforma cada chave  𝑥  em um valor no intervalo $[0,m-1]$[0, m-1]. Se o compartimento $h\left(x\right)$h(x) estiver ocupado, ocorre uma colisão, é um procedimento especial é usado para o armazenamento de 𝑥.

Dada a função de dispersão $h=xmod5$h = x \bmod 5 e as chaves 78 e 13, qual é o compartimento da tabela que causará a colisão?

No contexto de tabelas de dispersão, uma função de dispersão é utilizada para transformar uma chave em um índice da tabela. Este índice determina o compartimento onde a chave será armazenada. Uma técnica simples, porém  eficaz, é utilizar o valor da chave como índice diretamente na tabela. No entanto, para evitar problemas de espaço, utiliza-se uma função de dispersão, que pode causar um fenômeno onde duas ou mais chaves são mapeadas para o mesmo índice. 


Leia o trecho a seguir:


Uma técnica simples de mapeamento de chaves para índices é o [preencher 1], enquanto a função de dispersão ajuda a distribuir chaves entre os compartimentos. O fenômeno onde várias chaves são mapeadas para o mesmo índice é conhecido como [preencher 2], e o método de resolução deste problema é chamado de [preencher 3].


Os termos [preencher 1], [preencher 2] e [preencher 3] são corretamente substituídos por:

Os métodos de dispersão desempenham um papel fundamental na eficiência das tabelas de dispersão. Dois métodos amplamente utilizados são o método da divisão e o método da dobra. Cada método possui características distintas que influenciam sua aplicabilidade e eficiência.


Sobre os métodos de dispersão utilizados em tabelas de dispersão, observe as afirmativas a seguir:

I. No método da divisão, escolher 𝑚 como uma potência de 2 é ideal para garantir uma distribuição uniforme das chaves.
II. No método da dobra, os dígitos da chave são somados sem levar em consideração o "vai um".
III. O método da divisão utiliza o resto da divisão da chave 𝑥 por 𝑚 como endereço-base.
IV. No método da dobra, a operação de "ou exclusivo" (ou ex) entre pedaços da chave pode ser utilizada para melhorar a distribuição das chaves.

Está correto o que se afirma em:

As tabelas hash são estruturas de dados utilizadas para armazenar e buscar informações de maneira eficiente. Um exemplo prático da aplicação de tabelas hash é a organização de registros acadêmicos em uma universidade, onde o registro acadêmico (RA) do aluno é utilizado como chave de busca para encontrar o nome do aluno.


Com base no exemplo da aplicação de tabelas hash em uma universidade para organizar registros acadêmicos, leia as alternativas abaixo e escolha a correta.

Considere a classe Aluno definida em C++ e sua utilização em uma árvore binária de busca. O código a seguir mostra a definição do nó da árvore binária de busca:


struct TreeNode {

    Aluno aluno;

    TreeNode* left;

    TreeNode* right;


    TreeNode(const Aluno& aluno) : aluno(aluno), left(nullptr), right(nullptr) {}

};


Com relação à definição e utilização de um nó do tipo Aluno em uma árvore binária de busca, observe as afirmativas a seguir:

1. O struct TreeNode contém um objeto Aluno e dois ponteiros para outros nós.
2. O construtor do struct TreeNode inicializa o objeto Aluno e define os ponteiros left e right como nullptr.
3. A estrutura TreeNode permite criar uma árvore binária de busca que armazena objetos do tipo Aluno.
4. O método insert na árvore binária de busca deve comparar os atributos nome dos objetos Aluno para inserir um novo nó corretamente.
5. Para buscar um nó na árvore, é necessário comparar o atributo ra dos objetos Aluno.

Está correto o que se afirma em:

Considere a implementação da função destroyTree em uma árvore binária de busca para destruir todos os nós da árvore utilizando o caminhamento pós-ordem. O código a seguir mostra a definição da classe BinarySearchTree com o método destroyTree:


class BinarySearchTree {

private:

    struct TreeNode {

        Aluno aluno;

        TreeNode* left;

        TreeNode* right;

        

        TreeNode(const Aluno& aluno) : aluno(aluno), left(nullptr), right(nullptr) {}

    };


    TreeNode* root;


    void destroyTree(TreeNode* node) {

        if (node == nullptr) {

            return;

        }

        destroyTree(node->left);

        destroyTree(node->right);

        std::cout << "Deletando nó com RA: " << node->aluno.getRA() << std::endl;

        delete node;

    }


public:

    BinarySearchTree() : root(nullptr) {}

    ~BinarySearchTree() {

        destroyTree(root);

    }

};


Com relação ao funcionamento do método destroyTree, observe as afirmativas a seguir:

1. O método destroyTree utiliza o caminhamento pré-ordem para deletar os nós da árvore.
2. O método destroyTree é chamado recursivamente para deletar todos os nós da árvore.
3. O método destroyTree deleta primeiro os nós das subárvores esquerda e direita antes de deletar o nó atual.
4. O método destroyTree é invocado automaticamente pelo destrutor da classe BinarySearchTree.
5. O método destroyTree não imprime nenhuma mensagem durante a destruição dos nós.

Está correto o que se afirma em:

Considere o seguinte trecho de código que define um método destroyTree para destruir uma árvore binária utilizando caminhamento pós-ordem:

void destroyTree(Node* node) {

    if (node == nullptr) {

        return;

    }

    

    destroyTree(node->left);

    destroyTree(node->right);

    

    std::cout << "Deletando nó com valor: " << node->data << std::endl;

    delete node;

}


Com base no código acima, qual das alternativas a seguir apresenta a ordem nas quais os nós são deletados:

Considere as seguintes definições sobre árvores em estruturas de dados: A altura de um nó é o comprimento do caminho mais longo entre o nó até uma [preencher 1]. A profundidade de um nó é a [preencher 2] percorrida da raiz até o nó. Uma árvore binária é aquela em que abaixo de cada nó existem no máximo [preencher 3] subárvores.


Os termos [preencher 1], [preencher 2] e  [preencher 3] são corretamente substituídos por:

Considere a implementação da classe BinarySearchTree em C++ e o método insert utilizado para incluir um novo aluno na árvore binária de busca:

void insert(const Aluno& aluno) {

    root = insert(root, aluno);

}


TreeNode* insert(TreeNode* node, const Aluno& aluno) {

    if (node == nullptr) {

        return new TreeNode(aluno);

    }

    if (aluno.getRA() < node->aluno.getRA()) {

        node->left = insert(node->left, aluno);

    } else if (aluno.getRA() > node->aluno.getRA()) {

        node->right = insert(node->right, aluno);

    }

    return node;
}

I. O método insert insere um novo aluno na árvore binária de busca comparando o RA do aluno a ser inserido com o RA dos nós existentes na árvore.

PORQUE,

II.se o RA do aluno a ser inserido é menor que o RA do nó atual, o método insere o aluno na subárvore direita; caso contrário, insere na subárvore esquerda.

A respeito dessas asserções, assinale a alternativa correta.

Considere a implementação da classe BinarySearchTree em C++ e os métodos para imprimir o conteúdo de uma árvore binária de busca em pré-ordem (pre-order), in-ordem (in-order) e pós-ordem (post-order):



void preOrderPrint() const {

    preOrderPrint(root);

}


void preOrderPrint(TreeNode* node) const {

    if (node == nullptr) {

        return;

    }

    node->aluno.display();

    preOrderPrint(node->left);

    preOrderPrint(node->right);

}


void inOrderPrint() const {

    inOrderPrint(root);

}


void inOrderPrint(TreeNode* node) const {

    if (node == nullptr) {

        return;

    }

    inOrderPrint(node->left);

    node->aluno.display();

    inOrderPrint(node->right);

}


void postOrderPrint() const {

    postOrderPrint(root);

}


void postOrderPrint(TreeNode* node) const {

    if (node == nullptr) {

        return;

    }

    postOrderPrint(node->left);

    postOrderPrint(node->right);

    node->aluno.display();
}


I. O método preOrderPrint percorre a árvore binária de busca imprimindo primeiro o nó raiz, seguido pela subárvore esquerda e, por último, a subárvore direita. 

PORQUE

II. O método postOrderPrint realiza o percurso da árvore binária de busca imprimindo os nós na seguinte ordem: subárvore esquerda, subárvore direita e, finalmente, o nó raiz.

Considere a implementação da classe BinarySearchTree em C++ e os métodos para imprimir o conteúdo de uma árvore binária de busca em pré-ordem (pre-order):


void preOrderPrint() const {

    preOrderPrint(root);

}


void preOrderPrint(TreeNode* node) const {

    if (node == nullptr) {

        return;

    }

    node->aluno.display();

    preOrderPrint(node->left);

    preOrderPrint(node->right);

} 


A partir do código apresentado, analise as seguintes afirmações e determine qual conjunto de instruções sintetiza corretamente o comportamento dos métodos preOrderPrint.

Em estruturas de dados, uma árvore é um conjunto de nós onde existe um nó raiz r que pode conter subárvores ligadas diretamente a este nó. Uma subárvore é também uma árvore. Ressalta-se que não há um sucessor e um predecessor para cada nó de uma árvore e, por isto, estruturas lineares não são adequadas para representar este tipo de hierarquia nos dados.

Assinale a alternativa que identifica corretamente uma das características de uma árvore de estrutura de dados.

Árvores binárias de busca são estruturas fundamentais que podem ser usadas em situações nas quais se pretende organizar os dados. Além disso, quando as inserções e remoções são bastante frequentes, estas são estruturas melhores do que arranjos ordenados.

Com base no texto apresentado, escolha as afirmativas que complementam corretamente as informações já apresentadas:

1. Árvores binárias de busca são úteis para organizar dados utilizando uma chave de busca.
2. Arranjos ordenados são preferíveis às árvores binárias de busca.
3. Árvores binárias de busca são usadas para construir outras estruturas.
4. Árvores binárias de busca são menos eficientes que arranjos ordenados quando a ordenação dos dados é necessária.
5. Árvores binárias de busca são apropriadas para situações em que a organização dos dados é feita por meio de uma chave de busca.

Está correto o que se afirma em:

Supondo que não é permitida a duplicação em uma árvore binária de estrutura de dados, apenas é inserido um novo nó se o elemento não existe. Nesse caso, basta inserir o elemento na posição que ele estaria se fosse buscado. Para a remoção de um nó, três casos principais são considerados:

1. O nó a ser removido é uma folha (não tem filhos).
2. O nó a ser removido tem um único filho.
3. O nó a ser removido tem dois filhos.

Com base nessas informações, indique qual das alternativas abaixo descreve corretamente a ação a ser tomada para remover um nó com dois filhos.

Considere a classe Aluno definida em C++ com a seguinte declaração de atributos e métodos. A informação que se pretende armazenar é o nome do aluno, e cada RA de aluno é um número único.


class Aluno {

private:

    int ra;

    std::string nome;

public:

    Aluno();

    Aluno(int ra, std::string nome);

    void display() const;

    int getRA() const;

    std::string getNome() const;

    void setRA(int ra);

    void setNome(std::string nome);

};


Associe corretamente os métodos com suas explicações. Considere que nem todos os itens das colunas podem possuir associação ou podem possuir mais de uma correlação.

Método	Explicação sobre o método
I. Aluno()	A. Construtor que inicializa ra com -1 e nome com " ".
II. Aluno(int ra, std::string nome)	B. Construtor que inicializa ra e nome com valores fornecidos.
III. display()	C. Método que exibe os valores de ra e nome.
IV. getRA()	D. Método que retorna o valor de ra.
V. getNome()	E. Método que retorna o valor de nome.

Assinale a alternativa que contém a associação correta.

Os algoritmos de grafos são essenciais para solucionar problemas complexos em diversas áreas, incluindo redes de comunicação, transporte e otimização. Um problema clássico nesses contextos é determinar o caminho mais curto entre dois vértices em um grafo ponderado, o que pode otimizar rotas e reduzir custos.   Considere o grafo ponderado abaixo, que representa uma rede de cidades e as distâncias entre elas (em km).

      A

     /|\

  2 / | \ 4

   /  |  \

  B---|---C

  |\  |  /|

  | \ | / |

 6|  \|/  |3

  |   D   |

  |  / \  |

  | /   \ |

  E---5---F

    1

Utilizando o algoritmo de Dijkstra, determine o caminho mais curto e a distância total de A para F e selecione a alternativa correspondente.

As árvores AVL apresentam uma característica fundamental, denominada de fator de balanceamento, que indica a diferença de altura entre as subárvores esquerda e direita de um nó. Para manter uma árvore balanceada, esse fator deve sempre estar entre -1 e 1. Quando essa propriedade é violada após inserções ou remoções, são necessárias rotações para corrigir o balanceamento.

Referente ao fator de balanceamento em árvores AVL, observe as afirmativas a seguir:

1. O fator de balanceamento em uma árvore AVL é calculado subtraindo a altura da subárvore direita da altura da subárvore esquerda.
2. Para que uma árvore AVL esteja balanceada, o fator de balanceamento de cada nó deve ser -1, 0 ou 1.
3. Se o fator de balanceamento de um nó em uma árvore AVL estiver fora do intervalo de -1 a 1, uma rotação deve ser realizada para restaurar o balanceamento.
4. O fator de balanceamento em uma árvore AVL é a soma das alturas das subárvores esquerda e direita de um nó.

Está correto o que se afirma em:

Em uma árvore AVL, um nó pode ficar desbalanceado após uma operação de inserção ou remoção. Quando isso ocorre, é necessário aplicar rotações para reequilibrar a árvore. Suponha que após inserir um novo nó, a árvore tenha ficado desbalanceada. A identificação correta do tipo de rotação a ser aplicada depende da análise do fator de balanceamento dos nós.



Com base nas informações sobre árvore desbalanceada, avalie as afirmativas a seguir:

1. Se a inserção ocorrer na subárvore esquerda da subárvore esquerda de um nó desbalanceado, uma rotação simples à direita é necessária.
2. Se a inserção ocorrer na subárvore direita da subárvore direita de um nó desbalanceado, uma rotação simples à esquerda é necessária.
3. Se a inserção ocorrer na subárvore direita da subárvore esquerda de um nó desbalanceado, uma rotação dupla (esquerda-direita) é necessária.
4. Se a inserção ocorrer na subárvore esquerda da subárvore direita de um nó desbalanceado, uma rotação dupla (direita-esquerda) é necessária.
5. A altura da árvore AVL deve ser sempre recalculada após a aplicação de uma rotação.

É correto o que se afirma em:

Um grafo é uma estrutura matemática composta por vértices e arestas, utilizada para representar relações entre pares de objetos. Diferentes tipos de grafos possuem propriedades específicas que os tornam adequados para diversas aplicações em ciência da computação e teoria dos grafos.

I. Um grafo completo é aquele onde existe uma aresta entre cada par de vértices distintos. PORQUE

II. em um grafo completo com  n vértices, o número total de arestas é dado por n(n−1)/2 

Com base nas informações apresentadas, analise as asserções apresentadas e a relação proposta entre elas.

Uma árvore AVL é uma árvore binária de busca em que a altura das subárvores esquerda e direita de qualquer nó difere em no máximo um. Quando essa condição não é satisfeita, dizemos que a árvore está desbalanceada. 

Considere a árvore AVL abaixo, que ficou desbalanceada após a inserção do nó 13.


  20

     /  \

    10   30

   / \

  5   15

       \

       13

Após a inserção do nó 13, a árvore acima ficou desbalanceada. Para reequilibrar esta árvore AVL, é necessário aplicar rotações. Indique qual deve ser a sequência correta de rotações para balancear essa árvore.

As rotações são operações fundamentais para manter o balanceamento em Árvores AVL após inserções e remoções. Existem quatro tipos principais de rotações que podem ser aplicadas dependendo da situação específica de desbalanceamento: rotação [preencher 1] é aplicada quando a subárvore esquerda de um nó está desbalanceada; rotação [preencher 2] é aplicada quando a subárvore direita de um nó está desbalanceada; rotação [preencher 3] é aplicada quando a subárvore direita do filho esquerdo de um nó está desbalanceada; e rotação  [preencher 4] é aplicada quando a subárvore esquerda do filho direito de um nó está desbalanceada.

Os termos [preencher 1], [preencher 2], [preencher 3] e [preencher 4] são corretamente substituídos por:

Uma árvore AVL é uma árvore binária de busca em que a altura das subárvores esquerda e direita de qualquer nó difere em, no máximo, um. Quando essa condição não é satisfeita, dizemos que a árvore está desbalanceada.  

Considere a árvore AVL abaixo, que está desbalanceada após inserção do nó 7.


10

     /  \

    5    15

   / \

  3   8

 / \

2   4

     \

      7

Determine qual opção apresenta a sequência adequada de rotações para balancear esta árvore e selecione a alternativa adequada.

Um grafo é uma estrutura matemática utilizada para modelar relações entre pares de objetos. Ele é composto por um conjunto de vértices (ou nós) e um conjunto de arestas (ou arcos) que conectam pares de vértices. Os grafos podem ser utilizados para representar diversas situações do mundo real, como redes de computadores, rotas de transporte, relações sociais, entre outras.

Analise o grafo orientado e desbalanceado abaixo, que necessita de balanceamento para otimizar a busca e a manipulação dos dados.


         A

        / \

       B   C

      / \

     D   E

    / \

   F   G

Indique qual é a sequência correta das operações para tornar este grafo balanceado e selecione a alternativa correta.

As árvores AVL são um tipo específico de árvore binária balanceada, garantindo que o balanceamento seja mantido após operações de inserção e deleção de nós neste tipo de árvore e, assim, evitando que a árvore se torne degenerada. Mais especificamente, as árvores AVL garantem que a diferença de altura entre as subárvores esquerda e direita de qualquer nó seja, no máximo, [preencher 1]. Estas árvores podem ser desbalanceadas durante a inserção, mas devem ser re-equilibradas automaticamente através de [preencher 2]. Cada nó em uma árvore AVL possui um fator de [preencher 3], ou seja, é o fator que indica a diferença entre a altura da subárvore esquerda e a altura da subárvore direita.

Os termos [preencher 1], [preencher 2] e [preencher 3] são corretamente substituídos por:

As árvores AVL são amplamente utilizadas em diversas aplicações devido à sua capacidade de manter o balanceamento, o que garante uma eficiência elevada em operações de busca, inserção e remoção. Uma das áreas em que as árvores AVL são frequentemente aplicadas é na implementação de sistemas que requerem operações rápidas e eficientes sobre grandes volumes de dados.

Assinale a alternativa correta que descreve uma aplicação prática das Árvores AVL.

As Árvores AVL são um tipo específico de árvore binária balanceada que garantem que a estrutura da árvore permaneça balanceada, garantindo um desempenho eficiente nas operações de busca, inserção e remoção. O balanceamento é mantido através da verificação do fator de balanceamento, que é a diferença de altura entre as subárvores de um nó.

Sobre a situação apresentada, assinale a alternativa que define precisamente o fator de balanceamento em árvores AVL.

No início do cálculo do PageRank, todas as páginas recebem um valor inicial de PageRank igual. Este valor inicial é fundamental para iniciar o processo de redistribuição de relevância entre as páginas de um grafo. A distribuição inicial igualitária permite que o algoritmo comece sem preconceitos sobre a importância relativa das páginas. Conforme o algoritmo itera, os valores de PageRank são ajustados com base nas ligações entre as páginas.


Selecione a alternativa que identifica corretamente o valor inicial do PageRank atribuído a cada página na primeira iteração do algoritmo PageRank.

A busca em profundidade (DFS) é caracterizada por explorar o máximo possível um caminho antes de retroceder, enquanto a busca em largura (BFS) explora todos os vizinhos de um vértice antes de avançar para os vértices de nível seguinte. Supondo que você está perdido em um labirinto, você lembra das aulas de estrutura de dados em específico a estratégia de busca em profundidade e decide aplicar este conceito.

Assinale a alternativa que descreve corretamente uma característica exclusiva da busca em profundidade (DFS) que você utilizaria para sair do labirinto.

No algoritmo PageRank, a relevância de uma página não é determinada apenas pela quantidade de links recebidos, mas também pela qualidade desses links. Links de páginas com alto PageRank têm mais peso na determinação do PageRank da página que os recebe.

Por que receber links de páginas com PageRank alto é mais benéfico do que receber links de páginas com PageRank baixo?

A análise de algoritmos de busca em grafos, como a busca em profundidade (DFS) e a busca em largura (BFS), envolve entender suas aplicações, vantagens e limitações em diferentes cenários. Esses algoritmos são fundamentais na resolução de problemas complexos em ciência da computação.

Analise as asserções a seguir, sobre os algoritmos de busca em grafos:

I - A busca em profundidade (DFS) é eficiente na detecção de ciclos em um grafo.

PORQUE

II - A DFS explora todos os vizinhos de um vértice antes de avançar para o próximo nível de vértices.

É correto o que se afirma em:

O cálculo do PageRank é um processo complexo que envolve diversas operações que garantem a distribuição adequada dos valores de PageRank entre os vértices de um grafo. As operações incluem inicialização, redistribuição e atualização dos valores de PageRank em cada iteração.

Associe cada operação com sua descrição correta no contexto do cálculo do PageRank. Considere que nem todos os itens das colunas podem possuir associação ou podem possuir mais de uma correlação.

Lista de Operações:	Descrições:
I. Inicialização do vetor pr_previous	A. Divide o valor de PageRank entre os vértices conectados.
II. Cálculo do grau de saída (outputDegree)	B. Define os valores iniciais de PageRank para todos os vértices.
III. Atualização do vetor pr na iteração atual	C. Usa o valor de iterações anteriores para calcular o novo valor.
IV. Redistribuição do valor de PageRank	D. Ajusta os valores de PageRank para refletir a probabilidade de navegação aleatória.
V. Aplicação do fator de amortecimento	E. Conta o número de arestas que saem de cada vértice.

Assinale a alternativa que contém a associação correta.

A implementação do PageRank em C++ envolve a adaptação de um grafo não direcionado para um grafo direcionado, ou seja, um grafo que em suas arestas temos setas indicando as direções de navegação no grafo. Em nossos estudos, vimos como modificar o algoritmo addEdge para trabalhar com grafos direcionados.

Selecione qual das seguintes alternativas compreende corretamente a modificação necessária no método addEdge para adaptar o algoritmo de grafos não direcionados para grafos direcionados.

Em várias aplicações de grafos, diferentes algoritmos de busca são escolhidos com base nas necessidades específicas do problema ou pela complexidade do problema a ser explorado, como encontrar o caminho mais curto, detectar ciclos ou garantir a completude da busca, dentre outras situações que podem ser resolvidas computacionalmente.

Analise as afirmações a seguir sobre os cenários apropriados para o uso da busca em profundidade (DFS) e busca em largura (BFS).

I - DFS é preferível quando é necessário explorar todos os caminhos possíveis até o fim antes de retroceder.
II - BFS é ideal para encontrar o caminho mais curto em termos de número de arestas.
III - DFS é mais eficiente que BFS para encontrar o caminho mais curto em grafos ponderados.
IV - BFS deve ser usada quando todos os vértices precisam ser visitados, garantindo que todos os níveis sejam explorados uniformemente.
V - DFS é eficiente para resolver problemas de labirinto onde todos os caminhos possíveis precisam ser explorados.

É correto o que se afirma em:

O algoritmo PageRank redistribui o valor do PageRank de uma página entre todas as páginas para as quais ela cria links. Isso é feito iterativamente a cada consulta de um nó do grafo, ajustando os valores de PageRank até que os valores de todas as páginas converjam em valores menores.

Selecione a alternativa que analisa corretamente como o algoritmo PageRank redistribui o valor do PageRank de uma página com múltiplos links de saída.

Algoritmos de busca em grafos são essenciais para várias aplicações, incluindo redes de computadores, inteligência artificial e teoria dos grafos. A busca em profundidade (DFS) e a busca em largura (BFS) são duas das abordagens mais comuns. Cada algoritmo tem características e utilizações distintas, que são cruciais para sua aplicação eficaz.

Associe corretamente cada característica com o algoritmo de busca apropriado. Considere que nem todos os itens das colunas podem possuir associação ou podem possuir mais de uma correlação.

Algoritmos:	Características:
A. Busca em profundidade (DFS)	Utiliza uma pilha para gerenciar os vértices.
B. Busca em largura (BFS)	Explora todos os vizinhos de um vértice antes de avançar.
	Pode ser usado para detectar ciclos em um grafo.
	Utiliza uma fila para gerenciar os vértices.
	É ideal para encontrar o caminho mais curto em termos de número de arestas.

A implementação do algoritmo PageRank requer um método específico para calcular os valores do PageRank de todos os vértices em um grafo direcionado. Esse método é responsável por preencher um vetor passado como parâmetro com os valores calculados. Considere o seguinte trecho de código em C++:

void getPageRanks(float* pageRanks) {
    // Cálculo do PageRank para todos os vértices
    for (int i = 0; i < numVertices; ++i) {
      pageRanks[i] = 0; // Inicialização do vetor de PageRanks
      // Cálculo do PageRank para o vértice i
    }
}

Com base no apresentado, assinale a alternativa que apresenta qual é a função do método getPageRanks na implementação do algoritmo PageRank em linguagem C++: