atv4 ED1 thiago

Prévia do material em texto

19/07/2021 Unicesumar - Ensino a Distância
1/9
ATIVIDADE 4 - ENG SOFT - ESTRUTURA DE DADOS I - 52/2021
Período:05/07/2021 08:00 a 19/07/2021 23:59 (Horário de Brasília)
Status:ABERTO
Nota máxima:1,00
Gabarito:Gabarito será liberado no dia 20/07/2021 00:00 (Horário de Brasília)
Nota obtida:
1ª QUESTÃO
Cada nó da lista duplamente encadeada possui pelo menos três campos: um de dados e dois de endereço.
Um dos endereços é usado para apontar ao nó anterior e o segundo aponta para o próximo nó. 
Oliveira, P. M.;  Pereira, R. de L. Estrutura de Dados I. Maringá-Pr.: Unicesumar, 2019. 
Considere uma lista duplamente encadeada contendo 20 registros, onde cada nó é composto por três
campos: 
- next: um ponteiro para o próximo elemento da lista; 
- value: informação armazenada pelo elemento; 
- prev: um ponteiro para o elemento anterior da lista. 
O décimo elemento desta lista é representado por “C”, e "A" e "B" são dois outros elementos que não
pertencem à lista, com seus respectivos ponteiros "pA", "pB" e "pC".  
Compreendido isso, analise o trecho de (pseudo)código abaixo. 
pB.next <- pA; 
pA.prev <- pB; 
pA.next <- pC.next; 
pC.next.prev <- pA; 
pC.next <- pB; 
pB.prev <- pC; 
Esse trecho de (pseudo)código é utilizado para inserir os novos elementos na lista. 
Assinale a alternativa correta após a execução completa desse trecho.  
ALTERNATIVAS
B, antes do C, e A, antes do B.
B, antes do C, e A, logo após o C.
A, antes do C, e B, logo após o C.
B, logo após o C, e A, logo após o B.
A, logo após o C, e B, logo após o A.
2ª QUESTÃO
19/07/2021 Unicesumar - Ensino a Distância
2/9
Existe uma forma de alocar variáveis dinamicamente, criando mais e mais espaços de acordo com a
necessidade do programador, sem haver necessidade de prevê-las durante o desenvolvimento do
programa.
 
OLIVEIRA, P. M.; PEREIRA, R. L. Estrutura de Dados I. Maringá-Pr.: Unicesumar, 2019.
 
Assinale a alternativa correta referente a alocação dinâmica de memória, utilizando funções em linguagem
C:
ALTERNATIVAS
A função free é, geralmente, usada com o operador sizeof.
As funções calloc e realloc são usadas para liberar vetores.
A função clear é usada para limpar o conteúdo de um ponteiro.
A função malloc usa o número de blocos de memória que serão alocados na memória.
As funções malloc e free e o operador sizeof, são essenciais para a alocação dinâmica de memória.
3ª QUESTÃO
Suponha a estrutura de dados E, cujo algoritmo de inserção de um novo valor é representado pelo
pseudocódigo abaixo,
 
se t ≠ M então
   t := t +1
   E(t) := novo-valor
senão
   overflow
 
onde M é o número de posições disponíveis em memória e o termo overflow representa que algo
transbordou.
 
Assinale a alternativa que indica o tipo da estrutura de dados é representado por E.
ALTERNATIVAS
fila
pilha
grafo
lista circular
lista simplesmente encadeada
Atenção! Questão anulada.
19/07/2021 Unicesumar - Ensino a Distância
3/9
ALTERNATIVAS
void le_matriz(){
 int origem, origem;
 scanf("%d",&origem);
 scanf("%d",&destino);
 ma
origem
destino
=1;
 ma
destino
origem
=1;
}
void le_matriz(){
 int origem, origem;
 scanf("%d",&origem);
 scanf("%d",&destino);
 if (origem > n-1 || destino > n-1 || origem < 0 || destino < 0){
 ma
origem
destino
=1;
 ma
destino
origem
=1;
 }
}
void le_matriz(){
 int origem, origem;
 scanf("%d",&origem);
 scanf("%d",&destino);
 if (origem <= n && destino <= n && origem >= 0 && destino >= 0){
 ma
origem
destino
=1;
 ma
destino
origem
=1;
 }
}
19/07/2021 Unicesumar - Ensino a Distância
4/9
void le_matriz(){
 int origem, origem;
 scanf("%d",&origem);
 scanf("%d",&destino);
 if (origem < n-1 && destino < n-1 && origem > 0 && destino > 0){
 ma
origem
destino
=1;
 ma
destino
origem
=1;
 }
}
void le_matriz(){
 int origem, origem;
 scanf("%d",&origem);
 scanf("%d",&destino);
 if (origem <= n-1 && destino <= n-1 && origem >= 0 && destino >= 0){
 ma
origem
destino
=1;
 ma
destino
origem
=1;
 }
}
5ª QUESTÃO
19/07/2021 Unicesumar - Ensino a Distância
5/9
O algoritmo de Dijkstra assemelha-se ao algoritmo de busca em largura. O algoritmo de Dijkstra leva em
consideração uma matriz de custos. Cada entrada na matriz tem armazenado o custo (peso) da aresta entre
dois vértices. Durante a visita aos vértices adjacentes, o programa inclui na fila apenas os vértices de menor
custo. O algoritmo de Dijkstra é muito utilizado em situações em que é preciso minimizar custos ou otimizar
recursos. 
Oliveira, P. M.;  Pereira, R. de L. Estrutura de Dados I. Maringá-Pr.: Unicesumar, 2019. 
A tabela a seguir apresenta alguns aeroportos internacionais localizados na região sul do Brasil. Você pode
verificar o resultado da aplicação do algoritmo de Dijkstra para a obtenção do caminho mínimo para o custo
(em milhares) entre alguns desses aeroportos que compõem o conglomerado aeroviário da região.
Considere que o algoritmo pega como entrada um grafo orientado ponderado e um vértice de origem,
passando a construir progressivamente um grafo no qual os diferentes vértices são classificados por ordem
crescente de sua distância mínima em relação ao nó inicial. Considere o grafo não orientado, ou seja, é
possível fazer o caminho de ida e volta entre os caminhos dos aeroportos .
Analisando os dados da tabela e a explicação apresentada, assinale a conclusão correta:
ALTERNATIVAS
O menor custo entre os aeroportos Afonso Pena e de Pelotas é de R$ 91.000.
O menor custo entre os aeroportos Afonso Pena e Salgado Filho é de R$ 99.000.
Para alcançar o menor custo operacional entre os aeroportos de Foz do Iguaçu e de Florianópolis, terá que investir
R$ 31.000.
Para obter o menor custo operacional entre os aeroportos Afonso Pena e Salgado Filho, obrigatoriamente deverá
fazer uma conexão no aeroporto de Navegantes.
Para chegar ao menor custo partindo do aeroporto Afonso Pena e pousando no aeroporto Salgado Filho, deverá fazer
as seguintes conexões: Afonso Pena - Foz do Iguaçu - Florianópolis - Salgado Filho.
6ª QUESTÃO
19/07/2021 Unicesumar - Ensino a Distância
6/9
A estrutura de ponteiros é muito importante, porque graças a ela é possível fazer alocação dinâmica na
memória, navegar nela para frente e para trás a partir de uma variável ou de qualquer endereço. Um
ponteiro permite ainda que você monitore endereços na memória, atribua e recupere valores de variáveis
sem ao menos tocá-las. 
Oliveira, P. M.;  Pereira, R. de L. Estrutura de Dados I. Maringá-Pr.: Unicesumar, 2019. 
A partir do excerto acima, você já deve ter observado que a maioria das aplicações computacionais possui
os comandos Anular   e Refazer  .
O comando Anular desfaz a última operação realizada na aplicação, enquanto que, o outro refaz uma
operação que havia sido desfeita. São comandos bem intuitivos. 
Para desenvolver esses comandos em uma aplicação computacional, o desenvolvedor pode utilizar duas
estruturas de dados que armazenam as sucessivas operações de desfeitas e refeitas, de modo
que ao usuário escolher o comando Refazer, o sistema recupere a última operação desfeita. 
Nesse contexto assinale o tipo de estrutura de dados que pode ser utilizadas por esses comandos. 
ALTERNATIVAS
Fila.
Lista.
Pilha.
Grafo.
Matriz.
7ª QUESTÃO
19/07/2021 Unicesumar - Ensino a Distância
7/9
Pense no vetor como uma matriz de uma única linha e quantidade de colunas equivalente ao seu tamanho.
O vetor é uma estrutura homogênea, por isso só pode armazenar um único tipo de dado. As matrizes,
diferentemente, possuem pelo menos duas dimensões. A declaração é parecida com a de vetores,
precisando indicar também a quantidade de linhas além da quantidade de colunas. 
Oliveira, P. M.;  Pereira, R. de L. Estrutura de Dados I. Maringá-Pr.: Unicesumar, 2019. 
Você foi contratado(a) para desenvolver um sistema de vendas de ingressos para uma casa de
espetáculos, cuja disposição dos lugares considera N fileiras,cada uma das fileiras contendo
M assentos. A matriz com os assentos é armazenada em um vetor, segundo sua sequência de linhas, da
primeira para a última, e, em cada linha, da primeira coluna para a última. Sendo a primeira posição no vetor
a de índice 0 (zero).  
Para compreender a regra, considere três variáveis, a, f e c, onde a indica a posição do assento na casa de
espetáculos, f é a fileira na qual o assento está localizado e c é o número da coluna.  
Assinale como deve ser calculado essa localização. 
ALTERNATIVAS
a = M x f + c
a = M x (f + c)
a = M x (5 +2)
a = M x (f - 1) + (c - 1) 
a = M x (6 - 1) + (3 - 1)
8ª QUESTÃO
O algoritmo de Dijkstra assemelha-se ao algoritmo de busca em largura. O algoritmo de Dijkstra leva em
consideração uma matriz de custos. Cada entrada na matriz tem armazenado o custo (peso) da aresta entre
dois vértices. Durante a visita aos vértices adjacentes, o programa inclui na fila apenas os vértices de menor
custo. O algoritmo de Dijkstra é muito utilizado em situações em que é preciso minimizar custos ou otimizar
recursos. 
Oliveira, P. M.;  Pereira, R. de L. Estrutura de Dados I. Maringá-Pr.: Unicesumar, 2019. 
A tabela a seguir apresenta o resultado da aplicação do algoritmo de Dijkstra para a obtenção do caminho
mínimo para o deslocamento entre diversas cidades.
Considere que o algoritmo pega como entrada um grafo orientado ponderado e um vértice de origem,
passando a construir progressivamente um grafo no qual os diferentes vértices são classificados por ordem
crescente de sua distância mínima em relação ao nó inicial. 
Analisando os dados da tabela e a explicação apresentada, assinale a conclusão correta: 
 
19/07/2021 Unicesumar - Ensino a Distância
8/9
ALTERNATIVAS
O menor caminho entre as cidades A e D é de 2 km.
A menor distância entre as cidades A e F é de 15 km.
Para percorrer o menor caminho entre a cidade B e a cidade E, terá que se deslocar 5 km.
Para percorrer o menor caminho entre as cidades A e F, obrigatoriamente deverá passar na cidade C.
Para percorrer o menor caminho entre as cidades A e F, deverá se deslocar na sequência A - B - E - F.
9ª QUESTÃO
Observe a ilustração a seguir: 
 
Considere que a ilustração representa a estrutura de um banco de dados NoSQL, ou seja, não relacional, que
associa professores e disciplinas. Os professores colaboram entre si e são responsáveis pelas disciplinas, ora
mediando e ora lecionando a disciplina. 
Nesse contexto, ao analisar a estrutura de dados representada, podemos afirmar que se trata de um banco
de dados baseado em __________.  
Assinale a alternativa que completa corretamente a afirmação acima. 
ALTERNATIVAS
lista
pilha
grafo
tabela
árvore
10ª QUESTÃO
19/07/2021 Unicesumar - Ensino a Distância
9/9
A técnica de busca em profundidade faz com que todo um segmento de um grafo seja visitado até o final,
antes que uma nova porção seja investigada. A partir de um primeiro nó, o algoritmo coloca todos os
vértices adjacentes em uma pilha e marca o nó atual como visitado. Em seguida, o programa pega o nó do
topo, desempilhando-o, e repete o processo. A busca segue até que o alvo seja encontrado ou que a pilha
esteja vazia. 
Oliveira, P. M.;  Pereira, R. de L. Estrutura de Dados I. Maringá-Pr.: Unicesumar, 2019. 
Considere o grafo a seguir 
 
Ao simular a execução do algoritmo de busca em profundidade a partir do vértice ‘1’ do grafo, assinale a
sequência que corresponde a ordem de visitação dos nós. 
ALTERNATIVAS
1 - 2 - 3 - 4 - 5 - 6 - 7 - 8
1 - 2 - 4 - 5 - 8 - 3 - 6 - 7
1 - 3 - 7 - 6 - 2 - 5 - 8 - 4
4 - 2 - 8 - 5 - 1 - 6 - 3 - 7
4 - 8 - 5 - 2 - 6 - 7 - 3 - 1