Prova 2019 estrutura de dados P001-0061

Prévia do material em texto

Gabarito: A,E,A,C
DISCIPLINA
EID001 – Estruturas de Dados
DATA
09 outubro 2019
CÓDIGO DA PROVA
P001
INSTRUÇÕES AO ALUNO
1. É obrigatória a devolução deste caderno de questões ao término da prova.
2. Está autorizada a entrada de alunos até 1 hora depois do início marcado da prova (início 
da prova: 18h).
3. Você só poderá sair depois de transcorridas 1 hora e 15 minutos do início marcado da 
prova.
4. As respostas às questões dissertativas devem demonstrar a linha de raciocínio ou o 
processo de resolução, e não apenas o resultado final.
QUESTÕES OBJETIVAS
Questão 1 (1,5 
pontos)
Assinale a alternativa FALSA em relação à linguagem de programação C:
a) A linguagem C não permite o acesso direto a uma posição de memória, sendo esta 
encapsulada pela linguagem de programação.
b) Para alocar memória na linguagem C, podemos usar a função malloc, que recebe como 
parâmetro o número de bytes que se deseja alocar e retorna o endereço inicial do bloco 
de bytes que foi alocado.
c) A linguagem C faz uma distinção entre um tipo e um ponteiro para um tipo.
d) Na declaração de uma variável, do tipo ponteiro, usamos um * (asterisco) após o 
identificador do tipo para indicar que estamos nos referindo a um endereço para aquele 
tipo.
Questão 2 (1,5 
pontos)
Na implementação de um deque com alocação dinâmica em uma lista ligada e com um nó 
cabeça, foram utilizadas as seguintes estruturas:
typedef int TIPOCHAVE;
typedef struct {
 TIPOCHAVE chave;
} REGISTRO;
typedef struct auxElem {
 REGISTRO reg;
 struct auxElem* ant;
 struct auxElem* prox;
} ELEMENTO;
typedef ELEMENTO* PONT;
1 de 6
CADERNO DE PERGUNTAS
Avaliação
Regular
Gabarito: A,E,A,C
DISCIPLINA
EID001 – Estruturas de Dados
DATA
09 outubro 2019
CÓDIGO DA PROVA
P001
INSTRUÇÕES AO ALUNO
1. É obrigatória a devolução deste caderno de questões ao término da prova.
2. Está autorizada a entrada de alunos até 1 hora depois do início marcado da prova (início 
da prova: 18h).
3. Você só poderá sair depois de transcorridas 1 hora e 15 minutos do início marcado da 
prova.
4. As respostas às questões dissertativas devem demonstrar a linha de raciocínio ou o 
processo de resolução, e não apenas o resultado final.
QUESTÕES OBJETIVAS
typedef struct {
 PONT cabeca;
} DEQUE;
2 de 6
CADERNO DE PERGUNTAS
Avaliação
Regular
Gabarito: A,E,A,C
DISCIPLINA
EID001 – Estruturas de Dados
DATA
09 outubro 2019
CÓDIGO DA PROVA
P001
As funções para excluir os elementos, tanto do início quanto do fim, foram implementadas 
conforme a seguir. Entretanto, algumas partes do código estão faltando. Preencha esses 
pedaços para que o código funcione corretamente.
bool excluirElemDequeInicio(DEQUE* d, REGISTRO* reg){
 if (d->cabeca->prox == d->cabeca) return false; // deque vazio
 PONT apagar = d->cabeca->prox;
 *reg = apagar->reg;
 d->cabeca->prox = __________;
 __________ = d->cabeca;
 free(apagar);
 return true;
}
bool excluirElemDequeFim(DEQUE* d, REGISTRO* reg){
 if (d->cabeca->prox == d->cabeca) return false; // deque vazio
 PONT apagar = d->cabeca->ant;
 *reg = apagar->reg;
 d->cabeca->ant = __________;
 __________ = d->cabeca;
 free(apagar);
 return true;
}
A alternativa que preenche corretamente as lacunas é:
a) apagar->prox, apagar->prox->ant, apagar->ant, apagar->prox->ant
b) apagar->prox, apagar->ant->prox, apagar->ant, apagar->prox->ant
c) apagar->ant, apagar->prox->ant, apagar->prox, apagar->prox->ant
d) apagar->ant, apagar->ant->prox, apagar->prox, apagar->ant->prox
e) apagar->prox, apagar->prox->ant, apagar->ant, apagar->ant->prox
Questão 3 (1,5 
pontos)
A árvore AVL mostrada a seguir foi criada após uma sequência de inserções. 
3 de 6
Gabarito: A,E,A,C
DISCIPLINA
EID001 – Estruturas de Dados
DATA
09 outubro 2019
CÓDIGO DA PROVA
P001
Qual das alternativas mostra uma sequência capaz de gerar a árvore?
a) 0, 9, 1, 15, 12, 8, 7, 6, 3, 57, 35
b) 35, 57, 3, 6, 7, 8, 12, 15, 1, 9, 0
c) 8, 7, 6, 3, 57, 35, 1, 15, 12, 9, 0
d) 57, 3, 6, 7, 8, 12, 15, 1, 9, 0, 35
e) 57, 35, 1, 15, 12, 9, 0, 8, 7, 6, 3
Questão 4 (1,5 
pontos)
Um grafo não direcionado possui 10 vértices rotulados com os seguintes números: {18, 20, 26,
30, 33, 36, 37, 89, 92, 93}. Note que todos os rótulos possuem dois dígitos. Uma aresta liga 
dois vértices se, e somente se, eles possuem dígitos em comum em qualquer posição. Por 
exemplo, uma aresta liga 18 e 89, uma aresta liga 20 e 26, e assim por diante. Assinale a 
alternativa que indica uma possível ordem de visita aos vértices quando executamos uma 
busca em largura começando no vértice 18:
a) 18, 89, 92, 20, 26, 93, 30, 33, 36, 37
b) 18, 89, 92, 93, 30, 33, 36, 37, 20, 26
c) 18, 89, 92, 93, 20, 26, 30, 33, 36, 37
d) 18, 89, 93, 92, 20, 33, 36, 37, 30, 26
e) 18, 89, 93, 92, 20, 26, 30, 33, 36, 37
QUESTÕES DISSERTATIVAS
Questão 5 (2,0 pontos)
Assumindo que temos uma estrutura de dados do tipo pilha implementada com a seguinte 
estrutura:
typedef struct {
 int chave;
} REGISTRO;
typedef struct {
 int topo; // Índice do elemento no topo da pilha.
 int A[MAX];
} PILHA;
4 de 6
Gabarito: A,E,A,C
DISCIPLINA
EID001 – Estruturas de Dados
DATA
09 outubro 2019
CÓDIGO DA PROVA
P001
Crie uma função que recebe uma referência/ponteiro para uma variável do tipo PILHA e reverte
os valores que estão nessa pilha. Nesse caso, o que estava no final da pilha deverá ir para o 
topo e vice-versa.
Questão 6 (2,0 pontos)
Considere o grafo a seguir:
Descreva a ordem de visita dos nós, iniciando no nó “a”, os seguintes percursos:
A) Em largura.
B) Em profundidade.
5 de 6
Gabarito: A,E,A,C
DISCIPLINA
EID001 – Estruturas de Dados
DATA
09 outubro 2019
CÓDIGO DA PROVA
P001
QUESTÕES OBJETIVAS
Questão 1
A resposta correta é: A linguagem C não permite o acesso direto a uma posição de memória, 
sendo esta encapsulada pela linguagem de programação.
Justificativa
A linguagem C permite acesso a uma posição de memória, fazendo distinção entre o que é 
uma posição de memória e o que é um ponteiro para essa região de memória, que seria um 
ponteiro para um determinado tipo. Usamos o * para identificar qual o tipo a que estamos nos 
referenciando. A alocação de memória é feita pelo malloc, que recebe como parâmetro o 
número de bytes que se deseja alocar e retorna o endereço inicial do bloco alocado.
Questão 2
A resposta correta é: apagar->prox, apagar->prox->ant, apagar->ant, apagar->ant->prox
Justificativa
Este é o único preenchimento que fará o código funcionar.
Questão 3
A resposta correta é: 0, 9, 1, 15, 12, 8, 7, 6, 3, 57, 35
Justificativa
Existem várias maneiras de se gerar a configuração pedida, mas dentre as alternativas, apenas
a que foi indicada como resposta correta é capaz de fazer isso.
Questão 4
A resposta correta é: 18, 89, 92, 93, 20, 26, 30, 33, 36, 37
Justificativa
Existem várias maneiras de se percorrer os nós em uma busca em largura. Entretanto, dentre 
as alternativas, apenas aquela indicada como resposta correta é possível em um algoritmo de 
busca em largura.
QUESTÕES DISSERTATIVAS
Questão 5
O aluno deverá substituir as posições A[0] com A[max-1], A[1] com A[max-2], e assim por 
diante.
Rubricas | critérios de correção
1 – Pontuar metade da questão para o aluno que entendeu a lógica pedida.
2 – Pontuar mais 25% para o aluno que estruturou o laço de repetição e as atribuições de 
maneira correta.
3 – Pontuar mais 25% para o aluno que não cometeu nenhum erro de sintaxe.
Questão 6
Várias respostas são possíveis, desde que satisfaçam os percursos pedidos. Um exemplo seria:
Largura: a, c, b, f, i, d, g, h, e, j
Profundidade: a, c, i, j, f, e, d, h, b, g
Rubricas | critérios de correção
Pontuar igualmente para os percursos largura e profundidade. Apenas dar nota para os alunos 
que acertaram integralmente um percurso possível.
6 de 6
GABARITO