Prova Eletrônica Estrutura de Dados 1

Prévia do material em texto

3 / 3 ptsPergunta 1
O desenho de um possível grafo com graus de vértice 5, 2, 2, 2, 2, 1
é?
 
 
 
 
 
3 / 3 ptsPergunta 2
Uma estrutura de dados com vocação de FIFO de duplo fim e que
admite a rápida inserção e remoção em ambos os extremos é.
 uma lista linear. 
 um deque.
 Uma pilha. 
 uma árvore AVL. 
 uma splay tree.
3 / 3 ptsPergunta 3
Observe as figuras I e II, que representam duas estruturas de dados.
 fila e pilha. 
 vetor e lista. 
 fila e lista. 
 fila e vetor. 
 vetor e pilha. 
0 / 3 ptsPergunta 4IncorretaIncorreta
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:
 
 Stacks − Heaps
− Lista Encadeada Circular − Queues − Tabelas Hashing.
 
 Queues − Arquivos − Lista Duplamente Encadeada − Stacks − Heap.
 Queues − Heaps − Árvore Binária de Busca − Pilhas − Árvore AVL.
 Pilhas − Diretórios − Heap − Filas − Tabelas Hashing.
 Pilhas − Arquivos − Lista Encadeada − Filas – Árvore B. 
0 / 3 ptsPergunta 5IncorretaIncorreta
Segundo a imagem abaixo e a teoria sobre árvores binárias. É
incorreto afirmar que:
 os nós folhas são 3 e 5. 
 que existem 4 nós folhas. 
 os nós folhas são: 1, 3, 4 e 8. 
 
 a quantidade máxima de nós no 3º nível desta árvore é , onde é o
número de níveis da árvore.
 
 o número de nós desta árvore estritamente binária é , onde é
o número de folhas.
3 / 3 ptsPergunta 6
A estrutura de dados que consiste no armazenamento de cada
elemento em um endereço calculado a partir da aplicação de uma
função sobre a chave de busca denomina-se.
 Árvore binária balanceada. 
 Tabela hashing. 
 Lista. 
 Fila. 
 Deque. 
3 / 3 ptsPergunta 7
Segundo a imagem abaixo e a teoria sobre árvores binárias. Qual seria
os elementos em um percurso “Pré-ordem”?
 6, 2, 1, 4, 3, 5, 8, 7, 12, 10. 
 1, 3, 5, 4, 2, 7, 10, 12, 8, 6. 
 2, 1, 3, 4, 5, 6, 7, 8, 10, 12. 
 1, 2, 3, 4, 5, 6, 7, 8, 10, 12. 
 2, 1, 3, 5, 4, 7, 10, 12, 8, 6. 
3 / 3 ptsPergunta 8
Editores de texto fornecem um mecanismo de reversão de operações
(“undo”) que cancela operações recentes e reverte um documento ao
estado anterior à operação. Esse mecanismo de “desfazer” é
implementado mantendo as alterações do texto em uma estrutura de
dados do tipo.
 Deque. 
 Heap. 
 Hash. 
 Pilha. 
 Fila. 
3 / 3 ptsPergunta 9
Considere uma estrutura de fila (disciplina FIFO) de números inteiros
com duas operações: INSERE(n) e RETIRA( ). Considere, também,
que a representação do estado da fila em um instante qualquer é
realizada listando os elementos, de forma que o primeiro elemento, da
esquerda para a direita, é o mais antigo presente na fila.
INSERE(2)
INSERE(3)
RETIRA
INSERE(1)
RETIRA
INSERE(4)
INSERE(5)
RETIRA
RETIRA
 1 2 3 4 5 
 4 5 
 5 
 2 3 1 4 5 
 3 1 4 
3 / 3 ptsPergunta 10
Sobre as Tabelas Hash é incorreto afirmar que:
 
 A ideia central do Hash é utilizar uma função, aplicada sobre parte da
informação (chave), para retornar o índice onde a informação deve ou
deveria estar armazenada.
 Cada posição na tabela representa um endereço. 
 Uma tabela hashing é uma generalização de uma árvore com m nós
 
 Os elementos a serem armazenados nela possuem um valor-chave
que é utilizado para calcular o endereço na tabela onde serão
alocados.
 
 Uma tabela hashing é uma generalização de um vetor com mposições.