Apol 03 - Estrutura de Dados - 2019

Prévia do material em texto

Questão 1/5 - Estrutura de Dados 
Filas apresentam características de inserção e 
remoção na estrutura de dados seguindo a regra do 
primeiro que entra é o primeiro que sai. Observe o 
código da fila abaixo construída utilizando listas 
encadeadas. O código realiza a inserção de um novo 
elemento nesta fila. 
 
1. NovoElemento->dado = numero 
2. se (Head == NULO) então 
3. Head = NovoElemento 
4. Senão 
5. ElementoVarredura = Head 
6. enquanto (ElementoVarredura->prox <> NULO) 
7. ElementoVarredura = ElementoVarredura-
>prox 
8. Fimenquanto 
9. ElementoVarredura->prox = NovoElemento 
10. NovoElemento->prox = NULO 
11. Fimse 
Considerando que NovoElemento é um novo elemento 
que será inserido nesta fila, ElementoVarredura é uma 
variável que servirá para localizar o local de inserção, 
Head é o elemento que está no início da fila, assinale a 
alternativa CORRETA acerca de filas implementadas 
com listas encadeadas: 
Nota: 20.0 
 A O último elemento da lista encadeada deverá conter um ponteiro nulo, 
conforme indicado na linha 9. 
Na linha 10. 
 B As linhas 6, 7 e 8 indicam nos dizem que, para realizar a inserção, 
precisamos varrer até localizarmos o último elemento, o qual não poderá 
conter um ponteiro nulo. 
O último conterá um ponteiro nulo. 
 C Se o head estiver nulo, significa que podemos inserir um elemento após o 
head, mesmo que ele esteja nulo 
Head nulo significa inserir no local do próprio 
head. 
 D A varredura pela posição de inserção inicia no primeiro elemento da 
lista, conforme indicado na linha 5. 
Você acertou! 
Correto. 
 E Não seria possível substituir o laço de repetição enquanto por uma para-
faça devido a condição de parada aplicada. 
É sempre possível substituir um laço de repetição 
por outro, basta fazer as devidas adaptações. 
 
Questão 2/5 - Estrutura de Dados 
Na AULA 4 estudamos árvores binárias. 
Acerca de árvore binárias e a inserção dos dados em 
uma árvore construída para funcionar como uma Binary 
Search Tree, assinale a alternativa CORRETA. 
Nota: 20.0 
 A Em uma BST trabalhando com dados numéricos inteiros, cada elemento 
de valor maior que seu nó pai é inserido no ramo esquerdo. 
Valores menores ficam no ramo esquerdo; 
 B Em uma BST, podemos inserir elemento em qualquer posição da árvore 
binária. 
Inserção somente no nó-folha; 
 C Em uma BST trabalhando com dados numéricos inteiros, cada elemento 
de valor menor que seu nó pai é inserido no ramo direito. 
Valores maiores ficam no ramo esquerdo; 
 D Se tivermos uma árvore com somente uma raiz e com o valor 1, e 
inserirmos, na sequência, o valor 2, seguido pelo 3, 4 e 5. Isso resultará 
em uma árvore binária se comportando como se fosse uma lista 
encadeada simples, pendendo para o ramo esquerdo. 
Penderá para o ramo direito; 
 E Caso já exista um elemento inserido, tanto no ramo esquerdo quanto 
no ramo direito de um nó, deve-se avançar para o próximo nó para 
tentar a inserção, pois não será possível inserir neste. 
Você acertou! 
Correto. Como ambos ponteiro já estão ocupados, 
pulamos par ao próximo e verificamos; 
 
Questão 3/5 - Estrutura de Dados 
Pilhas apresentam características de inserção e 
remoção na estrutura de dados seguindo a regra do 
primeiro que entra é o último que sai. Observe o código 
da pilha abaixo construída utilizando listas encadeadas. 
O código realiza a inserção de um novo elemento nesta 
pilha. 
 
1. NovoElemento->dado = numero 
2. se (Top == NULO) então 
3. NovoElemento->prox = NULO 
4. Senão 
5. NovoElemento->prox = Top 
6. fimse 
7. Top = NovoElemento 
Considerando que NovoElemento é um novo elemento 
que será inserido nesta pilha e top é o elemento que 
está no topo da pilha, assinale a alternativa CORRETA 
acerca de pilhas implementadas com listas 
encadeadas: 
Nota: 0.0 
 A A linha 2 verifica se o topo da pilha está vazio. Caso esteja vazio, significa 
que não é possível inserir um novo elemento na pilha. 
É possível inserir, e a inserção se dá no próprio 
topo. 
 B Se tivermos um só elemento na pilha, significa que a lista não terá um 
topo. 
Terá um topo e será o próprio único elemento. 
 C Caso o topo não esteja vazio, fazemos o elemento do topo apontar para o 
novo elemento. 
O novo elemento apontará para o topo. Linha 5. 
 D Na linha 7, o topo da pilha vira o novo elemento inserida, fazendo com que 
o antigo topo seja apagado. 
O antigo topo não é apagado, pois na linha 5 
fazemos o novo elemento apontar para ele. 
 E O topo da pilha é o único elemento que fica armazenado em uma 
variável conhecida pelo programa. Todos os outros elementos são 
acessados a partir dos ponteiros de referencia de cada elemento. 
Correto. Como este código está implementado 
com listas encadeadas, armazenamos somente o 
primeiro elemento. 
 
Questão 4/5 - Estrutura de Dados 
No terceiro assunto da disciplina estudamos a estrutura 
de dados do tipo lista encadeada. O código abaixo 
representa cada elemento de uma lista duplamente 
encadeada. 
 
1. registro ElementoDaLista_Dupla 
2. dado: inteiro 
3. prox: ElementoDaLista[->) 
4. ant: ElementoDaLista[->) 
5. fimregistro 
Acerca de lista encadeadas duplas, assinale a 
alternativa INCORRETA: 
Nota: 0.0 
 A O código de criação da estrutura de uma lista encadeada dupla, conforme 
apresentado acima, é igual para uma circular e uma não circular. 
 B O código acima representa uma lista não circular, pois uma lista 
dupla e circular deveria conter um ponteiro para o próximo elemento 
da lista, outro ponteiro para o elemento anterior da lista e também um 
ponteiro para o primeiro elemento da lista. 
Não existe o ponteiro para o primeiro elemento. 
Somente o ultimo elemento aponta de volta para o 
primeiro. 
 C O código acima pode representar uma lista encadeada dupla não circular, 
pois conterá um ponteiro para o próximo elemento da lista e um para o 
elemento anterior da lista. 
 D Se removermos a linha 4, transformamos a lista encadeada dupla em uma 
simples. 
 E Um inserção no final da lista encadeada e circular, significaria fazer com o 
que o novo elemento inserido no final tivesse seu ponteiro para o próximo 
elemento apontando de volta para o início da lista encadeada. 
 
Questão 5/5 - Estrutura de Dados 
Na AULA 4 estudamos árvores binárias. 
Acerca de árvore binárias e a busca dos dados em uma 
árvore construída para funcionar como uma Binary 
Search Tree, assinale a alternativa INCORRETA. 
Nota: 20.0 
 A A busca em uma árvore apresentará um desempenho inferior ao em 
uma lista encadeada devido a sua organização não linear. 
Você acertou! 
O desempenho é superior. O(logn), enquanto que 
a lista é O(n) para a busca. 
 B A varredura em uma árvore do tipo BST é eficiente devido ao fato dos 
elementos estarem já organizados, com valores menores para um lado e 
maiores para o outro lado. 
 C A busca em uma BST delimita a área de busca sempre pela metade, 
reduzindo um problema de dimensão n, em dois problemas n/2. 
 D A complexidade assintótica para a busca na árvore pode ser considerada 
O(logn). 
 E Ao chegar no final de um ramo, ou seja, ambos ponteiros do nó forem 
nulos, significa que o valor buscado não existe na árvore binária.