Prova Eletrônica Estrutura de Dados 1

Prévia do material em texto

Prova Eletrônica - Estrutura de Dados 
 
Pergunta 1 
3 / 3 pts 
Uma fila duplamente terminada, isto é, uma estrutura linear que permite inserir 
e remover de ambos os extremos é chamada. 
 
 Autômato. 
 
 
 Uma árvore AVL. 
 
 
 Deque 
 
 
 Shift-and. 
 
 
 Árvore. 
 
 
IncorretaPergunta 2 
0 / 3 pts 
O estudo das estruturas de dados envolve um objetivo teórico, que procura 
identificar e desenvolver modelos matemáticos, determinando que classes de 
problemas podem ser resolvidos com o seu uso, e um objetivo prático, que 
busca criar representações concretas dos objetos e desenvolver rotinas 
capazes de atuar sobre estas representações, de acordo com o modelo 
considerado. Considere as definições das estruturas de dados: 
 
 I. São conhecidas como listas LIFO − Last In First 
Out. Uma máquina puxando vagões de trens é um exemplo de funcionamento 
de uma estrutura deste tipo. 
 II. O armazenamento de dados em Memória 
Secundária (MS) ou externa, se dá através da sua utilização. Os algoritmos e 
as estruturas de dados para processamento de dados em MS têm que 
considerar que o custo para se acessar um registro é algumas ordens de 
grandeza maior do que o custo de processamento na Memória Primária (MP) 
ou interna. 
 III. É uma forma especial de se agrupar dados, em 
que cada item possui uma referência para o próximo item, como se fosse uma 
corrente, com cada item sendo um dos elos. Costuma-se chamar esses itens 
de nós ou nodos. 
 IV. São conhecidas como listas FIFO − First In First 
Out. Pessoas organizadas para entrar em um trem metropolitano é um exemplo 
de funcionamento desta estrutura. 
 V. É utilizada para pesquisa em MS, quando os 
arquivos contêm mais registros do que a MP pode armazenar. É uma estrutura 
de dados utilizada para manutenção e organização de arquivos, podendo ser 
utilizada para armazenar e recuperar informações que estão em grandes 
repositórios de dados. 
As estruturas definidas nos itens de I a V são, respectivamente: 
 
 Pilhas − Diretórios − Heap − Filas − Tabelas Hashing. 
 
 Stacks − Heaps 
− Lista Encadeada Circular − Queues − Tabelas Hashing. 
 
 Pilhas − Arquivos − Lista Encadeada − Filas – Árvore B. 
 
 
 Queues − Heaps − Árvore Binária de Busca − Pilhas − Árvore AVL. 
 
 Queues − Arquivos − Lista Duplamente Encadeada − Stacks − Heap. 
 
Pergunta 3 
3 / 3 pts 
Segundo a teoria das listas de prioridades - Heaps. Determine entre as duas 
imagens abaixo quais tipos de heap elas representam 
Lista de Prioridade – Heap (a) Lista de Prioridade – Heap (b) 
 
 Heap (a) é um heap máximo. 
 
 
 Os heaps (a) e (b) são de mínimo. 
 
 
 Heap (b) é um heap máximo. 
 
 
 Os heaps (a) e (b) são de máximo. 
 
 
 Heap (a) é um heap mínimo. 
 
 
Pergunta 4 
3 / 3 pts 
Segundo a imagem abaixo e a teoria sobre árvores AVL. Se o próximo número 
a ser inserido nesta árvore for o número 7, qual seria o comportamento do 
algoritmo de balanceamento desta árvore? 
 
 
 O número 7 seria inserido como filho direito de 15. Assim, a árvore continua 
balanceada. 
 
 
 O número 7 seria inserido como filho direito de 11. Assim, a árvore continua 
balanceada. 
 
 
 O número 7 seria inserido como filho esquerdo de 11. Com isso a árvore 
ficaria desbalanceada nos nós 15 e 28, bastando apenas um tratamento no nó 
15 com uma rotação simples a direita. Ao final da rotação, o nó 11 ficaria como 
filho a esquerda do nó 28 e os nós 7 e 15 seriam seus filhos da esquerda e 
direita, respectivamente. 
 
 
 O número 7 seria inserido como filho direito de 11. Com isso a árvore ficaria 
desbalanceada nos nós 15 e 28, bastando apenas um tratamento no nó 15 
com uma rotação simples a direita. Ao final da rotação, o nó 11 ficaria como 
filho a esquerda do nó 28 e os nós 7 e 15 seriam seus filhos da esquerda e 
direita, respectivamente. 
 
 
 O número 7 seria inserido como filho direito de 11. Com isso a árvore ficaria 
desbalanceada nos nós 15 e 28, bastando apenas um tratamento no nó 15 
com uma rotação simples a direita. Ao final da rotação, o nó 15 ficaria como 
filho a esquerda do nó 28 e os nós 7 e 11 seriam seus filhos da esquerda e 
direita, respectivamente. 
 
 
IncorretaPergunta 5 
0 / 3 pts 
Segundo a imagem abaixo e a teoria sobre árvores binárias. É correto afirmar 
que: 
 
 
 que o nó 4 é um nó folha da árvore. 
 
 
 que os nós 2, 8, 1, 4 e 3 são descendentes do nó 6. 
 
 
 que os nós 4 e 3 são descendentes do nó 1. 
 
 
 que o nó 8 e 3 são raízes da árvore. 
 
 
 que a árvore tem altura igual a 4. 
 
 
Pergunta 6 
3 / 3 pts 
A tabela abaixo mostra as operações para a manipulação de uma pilha. 
 
 
 
Utilizando as definições acima, a sequência de instruções a seguir foi 
implementada para avaliar o resultado de uma expressão, sendo A, B, C, D e E 
os operandos desta expressão. O resultado da avaliação é acumulado em F. 
 
OPERAÇÕES: 
 1ª - PUSH(A) 
 2ª - PUSH(B) 
 3ª - SUB( ) 
 4ª - PUSH(C) 
 5ª - PUSH(D) 
 6ª - PUSH(E) 
 7ª - MPY( ) 
 8ª - ADD( ) 
 9ª - DEC( ) 
 10ª - DIV( ) 
 11ª - POP( ) 
 
Com base no que foi exposto acima, se A, B, C, D e E apresentarem, 
respectivamente, os valores 9, 3, 2, 1 e 1, qual o valor armazenado na pilha ao 
final da execução das operações? 
 
2 
 
 
5 
 
 
6 
 
 
4 
 
 
3 
 
 
Pergunta 7 
3 / 3 pts 
O desenho de um possível grafo com graus de vértice 5, 2, 2, 2, 2, 1 é? 
 
 
 
 
 
Correto! 
 
 
 
 
 
Pergunta 8 
3 / 3 pts 
Em uma estrutura de dados do tipo fila, a política de acesso aos dados é do 
tipo. 
 
 First In, Last Out. 
 
 First In, Never Out. 
 
 Last In, First Out. 
 
 First In, First Out. 
 
 Last In, Never Out. 
 
IncorretaPergunta 9 
0 / 3 pts 
Segundo a imagem abaixo e a teoria sobre árvores binárias. É incorreto afirmar 
que: 
 
 
 os nós folhas são: 1, 3, 4 e 8. 
 
 
 os nós folhas são 3 e 5. 
 
 
 o número de nós desta árvore estritamente binária é , onde é o 
número de folhas. 
 
 que existem 4 nós folhas. 
 
 
 a quantidade máxima de nós no 3º nível desta árvore é , onde é o número 
de níveis da árvore. 
 
Pergunta 10 
3 / 3 pts 
Maria precisa utilizar uma estrutura de dados para gerenciar trabalhos de 
impressão em uma impressora compartilhada por vários computadores em 
uma rede. As regras dessa estrutura devem permitir que os trabalhos sejam 
impressos na ordem em que forem enviados, ou seja, o primeiro a enviar um 
pedido de impressão deve ser o primeiro a ter sua solicitação atendida. Não 
deve ser permitido inserir pedidos de impressão no meio dos pedidos já 
realizados. 
A estrutura de dados mais adequada para Ana utilizar é: 
 
 árvore binária. 
 
 
 fila. 
 
 
 lista encadeada ordenada. 
 
 
 pilha. 
 
 
 tabela hash.