EngComp2016 EID001EstruturasdeDados P26 GABARITO

Prévia do material em texto

AVALIAÇÃO PRESENCIAL 
CADERNO DE PERGUNTAS 
curso: Engenharia de Computação bimestre: 9º bimestre ano: 2018 | 2sem 
CÓDIGO DA PROVA 
P26 
 Preencha atentamente o cabeçalho de TODAS AS FOLHAS DE RESPOSTA que você utilizar. 
 Ao término da prova, entregue apenas a folha de resposta ao aplicador. Leve este caderno de perguntas consigo. 
Boa prova! 
disciplina: EID001 – Estrutura de Dados 
 
1 
1. P1 é uma pilha com 5 posições - v(1) a v(5) -, na qual v(5) é o topo. De v(1) até v(5), a pilha P1 está 
preenchida, respectivamente, com os símbolos Q5, Q3, Q1, Q4, Q2. Há ainda mais duas pilhas, inicialmente 
vazias, P2 e P3, com o mesmo tamanho. Qual é a quantidade mínima de movimentos entre as três pilhas 
para que a pilha P1, originalmente cheia, esteja preenchida de v(5) até v(1), respectivamente, com os 
símbolos Q1, Q2, Q3, Q4, Q5? 
A) 7. 
B) 11. 
C) 10. 
D) 9. 
E) 8. 
___________________________________________________ 
2 
2. Considere a árvore AVL apresentada na figura a seguir. Com base nesta árvore, foram realizadas as seguintes 
operações: 
 
I - Inserção das chaves: 70, 30, 60, 55, 40, 38. 
II - Remoção das chaves: 40, 50, 70, 55. 
 
 
 
Considere a estrutura de dados a seguir: 
 
 
 
Assinale a alternativa que apresenta os valores impressos pela função imprime. 
AVALIAÇÃO PRESENCIAL 
CADERNO DE PERGUNTAS 
curso: Engenharia de Computação bimestre: 9º bimestre ano: 2018 | 2sem 
CÓDIGO DA PROVA 
P26 
 Preencha atentamente o cabeçalho de TODAS AS FOLHAS DE RESPOSTA que você utilizar. 
 Ao término da prova, entregue apenas a folha de resposta ao aplicador. Leve este caderno de perguntas consigo. 
Boa prova! 
disciplina: EID001 – Estrutura de Dados 
 
A) 21, 30, 33, 38, 45, 60, 98. 
B) 33, 21, 45, 38, 60, 98, 30. 
C) 98, 60, 45, 38, 33, 30, 21. 
D) 30, 21, 38, 45, 98, 60, 33. 
E) 33, 21, 30, 60, 45, 38, 98. 
___________________________________________________ 
3 
3. Considere a implementação de uma lista encadeada para armazenar reais, dada pelo tipo a seguir: 
 
 
 
Assuma que os elementos de uma lista ligada estão em ordem crescente. Escreva uma função recursiva que 
insere um elemento com valor $v$ nesta lista, mantendo a ordenação. Caso um elemento com o mesmo valor 
já esteja presente na lista, a inserção não deve ser feita e uma mensagem de erro deve ser emitida. Essa 
função deve obedecer ao seguinte protótipo: 
void insere_elemento (Lista* L, int v) 
AVALIAÇÃO PRESENCIAL 
CADERNO DE PERGUNTAS 
curso: Engenharia de Computação bimestre: 9º bimestre ano: 2018 | 2sem 
CÓDIGO DA PROVA 
P26 
 Preencha atentamente o cabeçalho de TODAS AS FOLHAS DE RESPOSTA que você utilizar. 
 Ao término da prova, entregue apenas a folha de resposta ao aplicador. Leve este caderno de perguntas consigo. 
Boa prova! 
disciplina: EID001 – Estrutura de Dados 
 
 
___________________________________________________ 
4 
4. Considere uma Árvore Binária, cuja estrutura de dados é dada por: 
 
 
AVALIAÇÃO PRESENCIAL 
CADERNO DE PERGUNTAS 
curso: Engenharia de Computação bimestre: 9º bimestre ano: 2018 | 2sem 
CÓDIGO DA PROVA 
P26 
 Preencha atentamente o cabeçalho de TODAS AS FOLHAS DE RESPOSTA que você utilizar. 
 Ao término da prova, entregue apenas a folha de resposta ao aplicador. Leve este caderno de perguntas consigo. 
Boa prova! 
disciplina: EID001 – Estrutura de Dados 
 
 
a) Escreva uma função que calcula a altura de uma árvore AVL. Essa função deve obedecer ao seguinte 
protótipo: 
int altura (NoArv *r) 
 
b) Escreva uma função que realiza a cópia de uma árvore. Essa função deve obedecer ao seguinte protótipo: 
NoArv *copia(NoArv *raiz) 
___________________________________________________