4 exercicios estrutura de dados

Prévia do material em texto

18/01/2022 Primeiro Caderno - Evernote
https://www.evernote.com/client/web?login=true#?b=5ac9b6e0-84a0-4170-a6dc-a5efbf353acc&n=45e42d83-8b0a-cd53-9cd9-7d7d4bf35aa8& 1/5
UNIDADE 4 - Estrutura de Dados
UNIDADE 4 - Estrutura de Dados
Questão 1
Um mecanismo utilizado para organizar nossa informação e prover operações convenientes e eficientes 
para acessá-la e manipulá-la é conhecido como estrutura de dados. Diversos tipos de estruturas de dados 
têm sido propostas e o conhecimento das características dessas estruturas é um fator importante para a 
escolha da estrutura que melhor se encaixa na solução de um determinado problema.
 
Neste sentido, o almoxarife de um órgão pediu ao técnico de informática que elaborasse um sistema 
de estoque que, para cada saída de material, considerasse o material que há mais tempo houvera dado 
entrada no almoxarifado.
O técnico deve desenvolver um algoritmo para tratar com uma estrutura de dados de qual tipo? Assinale a 
alternativa correta.
Questão 2
Uma lista simplesmente ligada consiste em uma sequência de elementos, denominados nós. Cada nó 
possui uma informação e um ponteiro para o próximo nó da lista. O último nó da lista aponta para NULL, 
representando que não existe um próximo nó na lista. A lista, propriamente dita, é representada apenas por 
um ponteiro para o primeiro nó dessa lista, chamado de "Início". Uma lista simplesmente ligada tem esse 
nome, pois cada nó da estrutura possui apenas um ponteiro para o próximo nó da lista.
 
Com base no que foi exposto, analise o código da função "func" a seguir:
 
int func(struct Lista* li, int n) {
assert(li != NULL);
struct No* aux = li->inicio;
int x = 0;
while(aux != NULL) {
if (aux->info == n) {
x += 1;
}
Pilha.
Lista simplesmente encadeada.
Lista duplamente encadeada.
Fila.
Pilha dupla.
18/01/2022 Primeiro Caderno - Evernote
https://www.evernote.com/client/web?login=true#?b=5ac9b6e0-84a0-4170-a6dc-a5efbf353acc&n=45e42d83-8b0a-cd53-9cd9-7d7d4bf35aa8& 2/5
aux = aux->proximo;
}
return x;
}
Assinale a alternativa que representa corretamente o objetivo da função "func".
Questão 3
Pilhas e filas são dois tipos fundamentais de estruturas de dados. Dentre as principais operações dessas 
estruturas, estão:
enfileirar(f, item): também conhecida como 
enqueue, enfileira o elemento “item” no final da fila “f”;
desenfileirar(f): também conhecida como dequeue, desenfileira o elemento do início da fila “f” e o retorna;
empilhar(p, item): também conhecida como push, essa função é responsável por empilhar um “item” no 
topo da pilha “p”;
desempilhar(p): também conhecida como pop, essa função é responsável por desempilhar o elemento do 
topo da pilha “p” e retorná-lo.
 
Considere a pilha "p" e a fila "f", tais como:
 
Pilha "p":
M <- topo
N
O
P
 
Fila "f": 
Início -> [A B C D] <- Fim
Calcular e retornar a soma de todos os elementos da lista "li".
Calcular e retornar a soma de todos os elementos iguais a "n" na lista "li".
Calcular e retornar a soma de todos os elementos diferentes de "n" na lista "li".
Calcular e retornar a quantidade de elementos iguais a "n" na lista "li".
Calcular e retornar a quantidade de elementos diferentes de "n" na lista "li".
18/01/2022 Primeiro Caderno - Evernote
https://www.evernote.com/client/web?login=true#?b=5ac9b6e0-84a0-4170-a6dc-a5efbf353acc&n=45e42d83-8b0a-cd53-9cd9-7d7d4bf35aa8& 3/5
Início > [A, B, C, D] < Fim
 
Com base no que foi exposto, analise o código a seguir:
 
for(int i = 0; i < 4; i++) {
empilhar(p, desempilhar(p));
enfileirar(f, desenfileirar(f));
}
Ao final da execução do código apresentado, os estados finais da pilha "p" e da fia "f" serão
Pilha "p":
M <- topo
N
O
P
 
Fila "f": 
Início -> [A, B, C, D] <- Fim
Pilha "p":
P <- topo
O
N
M
 
Fila "f": 
Início -> [D, C, B, A] <- Fim
Pilha "p":
M <- topo
N
O
P
 
Fila "f": 
Início -> [D, C, B, A] <- Fim
Pilha "p":
P <- topo
O
N
M
 
Fila "f": 
Início -> [A, B, C, D] <- Fim
Pilha "p":
M <- topo
N
18/01/2022 Primeiro Caderno - Evernote
https://www.evernote.com/client/web?login=true#?b=5ac9b6e0-84a0-4170-a6dc-a5efbf353acc&n=45e42d83-8b0a-cd53-9cd9-7d7d4bf35aa8& 4/5
Questão 4
Talvez seja necessário saber quais elementos fazem parte de uma lista em determinado momento de um 
sistema. Para tal, é necessário percorrer toda a lista ligada para verificá-los. A lista ligada pode ser impressa 
com todos os seus elementos e é possível utilizar o trecho de código a seguir:
 
void imprimir (Lista* l) {
Lista* p;
printf(“Elementos:\n”);
 
Por ser uma função que percorrerá toda a lista e de impressão em tela, é possível declará-la como VOID, 
uma função que não retornará valor para a função principal.
 
for (p = l; p != NULL; p = p -> prox) {
printf(“ %d -> “, p -> info);
}
}
 
Baseado no trecho de comando FOR, avalie as seguintes asserções e a relação proposta entre elas:
 
I. Neste trecho, uma condição de repetição FOR percorre a lista e envia todos os elementos encontrados 
nela para a memória.
PORQUE
II. Na função principal, declara-se apenas a chamada da função imprimir(), passando como parâmetro a 
lista na qual deseja-se imprimir.
A respeito dessas asserções, assinale a alternativa correta:
Questão 5
O
P
 
Fila "f": 
Início -> [D, B, C, A] <- Fim
As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I.
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa da I.
A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
As asserções I e II são proposições falsas.
18/01/2022 Primeiro Caderno - Evernote
https://www.evernote.com/client/web?login=true#?b=5ac9b6e0-84a0-4170-a6dc-a5efbf353acc&n=45e42d83-8b0a-cd53-9cd9-7d7d4bf35aa8& 5/5
Questão 5
Um dos problemas mais comuns para solucionar com pilhas são os labirintos. Estes são desafios criados 
como problematização de estrutura de dados. As pilhas podem ser aplicadas também no uso de algoritmos 
de Backtracking, que consiste em criar marcações para onde o algoritmo pode retornar. Em um labirinto, 
por exemplo, para encontrar um caminho correto, pode-se andar pelo labirinto até encontrar uma divisão 
nesse caminho. Assim, adiciona-se a posição onde a divisão ocorre, junto ao caminho escolhido na pilha, e 
segue-se por ele. Caso o caminho escolhido não possua uma saída, é removido o ponto anterior da pilha, 
voltando ao último ponto em que o labirinto se dividiu, e recomeça-se por um outro caminho ainda não 
escolhido, adicionando na pilha o novo caminho. O algoritmo de Backtracking pode ser aplicado também 
como operação de desfazer. Baseado no algoritmo de Backtracking, complete as lacunas da asserção a 
seguir:
 
Considerando o contexto apresentado, complete as lacunas a seguir:
Para implementar a operação de Backtracking, as ações são ____________ em ____________ e, caso a 
____________ seja realizada, o estado anterior do sistema pode ser ____________, ou a ação 
____________ pode ser executada.
Assinale a alternativa que completa corretamente as lacunas:
armazenadas / uma pilha / operação de refazer / restaurado / realizada.