UNIVESP - 2020 - GABARITO - PROVA - Estruturas de Dados

Prévia do material em texto

GABARITO 
DISCIPLINA 
EID001 - Estruturas de Dados 
APLICAÇÃO 
30/09/2020 
CÓDIGO 
DA PROVA P007/P008 
 
QUESTÕES OBJETIVAS 
Questão 1.1 
O objetivo da lista ligada (dinâmica) é: 
 
I. Armazenar elementos em uma sequência. 
II. Permitir a inserção e a remoção de elementos em qualquer posição. 
III. Permitir a inserção de elementos apenas no início e a remoção apenas no final. 
IV. Usar posições de memória sequenciais fisicamente. 
V. Utilizar apenas área de memória efetivamente necessária. 
 
Estão corretas as afirmações: 
a) I, III e V. 
b) I, II e V. 
c) III, IV e V. 
d) I, II, IV e V. 
e) II, IV e V. 
 
RESOLUÇÃO 
A resposta correta é: I, II e V. 
 
Justificativa 
Uma lista ligada (dinâmica) consiste em uma sequência de itens que não estão necessariamente em 
posições físicas consecutivas na memória, pois usa ponteiros para ligar seus elementos. Por ser uma 
estrutura de dados dinâmica, é possível utilizar apenas a memória realmente necessária, sem 
desperdício. A lista tem como característica a possibilidade de inserção e remoção de elementos em 
quaisquer posições. 
 
 
Questão 1.2 
Um deque é uma estrutura de dados dinâmica que permite a inserção e a remoção de elementos em 
qualquer extremidade (início ou final). Para isso, deve ser possível o percorrimento da estrutura nos 
dois sentidos. Portanto, qual seria a melhor definição para um elemento de um deque? 
 
a) 
 typedef struct tempRegistro{ 
 REGISTRO reg; 
 struct tempRegistro* prox; 
} ELEMENTO; 
 
 
b) 
 typedef struct auxElem { 
 REGISTRO reg; 
 struct auxElem* ant; 
 struct auxElem* prox; 
} ELEMENTO; 
 
c) 
 typedef struct aux { 
 REGISTRO reg; 
 struct aux* prox; 
} ELEMENTO; 
 
d) 
 typedef struct aux { 
 TIPOCHAVE chave; 
 struct aux *esq; 
} ELEMENTO; 
 
e) 
 typedef int[TAM] ELEMENTO; 
 
RESOLUÇÃO 
A resposta correta é: 
 typedef struct auxElem { 
 REGISTRO reg; 
 struct auxElem* ant; 
 struct auxElem* prox; 
} ELEMENTO; 
 
Justificativa 
Para permitir o percorrimento nos dois sentidos, normalmente o deque é implementado como uma 
lista duplamente ligada e por isso são necessários dois ponteiros para cada elemento - um para seu 
antecessor (ant) e outro para seu sucessor (prox). As outras alternativas apresentam apenas um 
ponteiro ou nenhum. 
 
 
Questão 1.3 
Uma matriz é considerada esparsa quando possui: 
a) todo o conteúdo nulo ou com valores insignificantes. 
b) o número de linhas igual ao número de colunas. 
c) a maioria de seu conteúdo nulo ou insignificante. 
d) sua diagonal principal nula. 
e) sua diagonal principal com conteúdo igual a 1. 
 
 
RESOLUÇÃO 
A resposta correta é: a maioria de seu conteúdo nulo ou insignificante. 
 
Justificativa 
Uma matriz esparsa é uma matriz na qual a grande maioria dos elementos possui um valor padrão 
(por exemplo, zero) ou são nulos ou faltantes. Isso gera um desperdício de memória, uma vez que 
apenas uma pequena parcela de elementos tem valor diferente de zero. Não tem sentido para 
aplicações uma matriz com todo o conteúdo nulo - alternativa (a). Uma matriz é quadrada quando o 
número de linhas é igual ao número de colunas - alternativa (b). A matriz com diagonal principal nula - 
alternativa (d) - ou igual a 1 - alternativa (e) - não tem relação com matriz esparsa. 
 
 
Questão 1.4 
Preencha as lacunas escolhendo a alternativa correta. 
A estrutura de dados pilha dupla que usa a definição abaixo 
 
typedef struct { 
 REGISTRO A[MAX]; 
 int topo1; 
 int topo2; 
} PILHADUPLA; 
 
apresenta uma estrutura __________, que economiza espaço porque possui em um __________ único, 
duas pilhas implementadas. O espaço é compartilhado pelas pilhas, quando uma usa muito espaço, a 
outra usa pouco, de tal forma que a __________ dos tamanhos das pilhas não muda. 
 
a) dinâmica, arranjo, diferença 
b) estática, arranjo, diferença 
c) dinâmica, deque, soma 
d) estática, arranjo, soma 
e) estática, ponteiro, soma 
 
RESOLUÇÃO 
A resposta correta é: estática, arranjo, soma 
 
Justificativa 
A pilha dupla compartilha espaço em um único arranjo (vetor) estático. A vantagem é que a soma dos 
tamanhos das duas pilhas não muda, mas uma pode crescer mais em detrimento da outra. Observe 
que a definição contém dois topos, que representam os topos das pilhas, ocupando, cada uma, um 
extremo do arranjo. 
 
 
QUESTÕES DISSERTATIVAS 
 
Questão 2 
Seja o seguinte grafo G1: 
 
1. Mostre um percurso em profundidade a partir do nó 1 em G1. 
2. Idem, a partir do nó 4. 
3. Mostre um percurso em largura a partir do nó 1 em G1. 
4. Idem, a partir do nó 4. 
5. Dê exemplos de ciclos a partir do nó 1 em G1. 
 
RESOLUÇÃO 
1. Na busca em profundidade, procura-se o mais fundo no grafo sempre que possível. As arestas são 
exploradas a partir do vértice v mais recentemente descoberto que ainda tem arestas não exploradas 
saindo dele e, quando todas as arestas de v são exploradas, a busca em profundidade volta ao vértice 
anterior a v (backtracking) para seguir arestas ainda não exploradas. Um percurso em profundidade a 
partir do nó 1 em G1: 1-2-3-5-4. 
2. Um percurso em profundidade a partir do nó 4 em G1: 4-1-2-3-5. 
3. A busca em largura primeiro visita todos os adjacentes de um nó para, então, visitar os adjacentes 
dos adjacentes e assim por diante. É um tipo de busca em camadas, que inicia em um vértice inicial e 
percorre a primeira camada, depois a segunda etc. Um percurso em largura a partir do nó 1 em G1: 1-
2-4-3-5. 
4. Um percurso em largura a partir do nó 4 em G1: 4-1-2-5-3. 
5. Um ciclo em um grafo acontece quando, a partir de um determinado vértice, pudermos percorrer 
algum caminho que nos leve a esse mesmo vértice. Exemplos de ciclos a partir do nó 1 em G1: 1-2-4-1, 
1-2-3-5-4-1. 
 
Rubricas | critérios de correção 
20% cada item 
 
 
Questão 3 
Considere o grafo ponderado da figura abaixo. Através do algoritmo de Dijkstra, obtenha as menores 
distâncias entre os nós: 
 
1. de A até G 
2. de A até F 
3. de A até C 
4. de B até G 
5. de B até F 
6. de C até F 
7. de D até E 
8. de E até A 
9. de G até A 
10. de G até D 
 
RESOLUÇÃO 
Matriz de pesos (assume-se 1000 como peso infinito quando não há aresta entre os nós): 
 
Menores distâncias, com o caminho (nós precedentes): 
 
Rubricas | critérios de correção 
O importante aqui é mencionar os caminhos mínimos obtidos pelo algoritmo de Dijkstra (coluna 
“menor distância” na tabela acima), o que vale 75% da questão. Outros itens, como nós precedentes 
(última coluna), valem 25%.