Estrutura de Dados Prova Objetiva Nota 100

Prévia do material em texto

Estrutura de Dados PROVA OBJETIVA Nota 100 
 
 
Questão 1/10 - Estrutura de Dados 
No primeiro assunto de nossa disciplina investigamos o que são estruturas de dados e como podemos 
classificá-las em tipos. 
Acerca deste assunto, assinale a alternativa INCORRETA: 
Nota: 10.0 
 
A Um dado que pode ser decomposto em partes mais simples, é considerado um dado estruturado e, portanto, uma estrutura de dados. 
 
B Os tipos de dados manipulados por um algoritmo podem ser classificados em duas categorias distintas: os atômicos, que são dados 
indivisíveis, e os dados compostos, que podem ser divisíveis em mais partes menores. 
 
C Podemos classificar uma estrutura de dados como sendo do tipo homogênea (como registros) ou do tipo heterogênea (como vetores e 
matrizes). 
Você acertou! 
AULA 1 – TEMA 1. Podemos classificar uma estrutura de dados como sendo do tipo heterogênea (como registros) ou do tipo homogênea (como 
vetores e matrizes). 
 
D Uma estrutura homogênea é aquela cujo tipo dos dados nela armazenados são de um único tipo, como inteiro, real, caractere ou lógico 
 
E Uma estrutura contendo dados do tipo caractere e do tipo real pode ser considerada uma estrutura de dados heterogênea. 
 
Questão 2/10 - Estrutura de Dados 
Na AULA 5 estudamos grafos e o algoritmo de caminho mínimo. 
Acerca do algoritmo de caminho mínimo Djikstra, assinale a alternativa CORRETA. 
Nota: 10.0 
 
A Este algoritmo só é capaz de definir um menor caminho caso grafo seja ponderado. 
Podemos usar um grafo ponderado, mas isso não é obrigatório. Caso ele não seja ponderado, significa que todas as arestas terão peso um, e caso a 
métrica seja aditiva, teremos que o menor caminho será o menor número de saltos possíveis. 
 
B O Djikstra só é capaz de definir a melhor rota seguindo uma métrica denominada de aditiva. 
Podemos usar diferentes métricas. A aditiva é a mais comum. 
 
C Quando não existe um caminho entre dois vértices, representamos como se a rota entre eles no vetor de distâncias tem um peso infinito 
(variável de valor extremamente alto). 
Você acertou! 
Correto. AULA 5 – TEMA 4. 
 
D O caminho de um vértice V0 até um vértice V2, passando por um vértice V1, utilizando métrica aditiva, será a soma dos pesos de V0 para 
V1 e V0 para V2. 
Será a soma de V0 para V1 e V2 para V2. 
 
E O vértice de origem sempre terá um caminho infinito para si próprio. 
O vértice de origem para ele mesmo será peso zero do caminho. 
 
 
Questão 3/10 - Estrutura de Dados 
Assuma um vetor de dimensão 10 com dados numéricos e inteiros colocados na seguinte ordem: 
 
| 05 | 07 | 08 | 14 | 24 | 29 | 56 | 77 | 78 | 88 | 
Suponha que você deseja implementar um algoritmo de busca para localizar algum dado neste vetor já 
ordenado de maneira crescente. Você resolve testar a busca sequencial e a busca binária. 
Acerca destes algoritmos e analisando o vetor acima, assinale a alternativa CORRETA: 
Nota: 10.0 
 
A No algoritmo de busca sequencial, o valor 24 seria localizado na 6ª tentativa, se fizermos uma varredura da esquerda para a direita. 
Na 5ª tentativa. 
 
B No algoritmo de busca binária, o valor 24 seria localizado na 3ª tentativa. 
Na 1ª tentativa. 
 
C No algoritmo de busca sequencial, o valor 77 seria localizado mais rapidamente que se comparado com a busca binária. 
Binária se sairia mais rápida. 
 
D No algoritmo de busca sequencial, o valor 07 seria localizado mais rapidamente que se comparado com a busca binária. 
Você acertou! 
CORRETO. Levará menos iterações. 
 
E Em nenhum cenário de busca o algoritmo sequencial irá localizar o valor antes da busca binária. 
É possível que sim, a sequencial ache antes. Dependerá o valor buscado e onde ele se localizado no vetor. 
 
Questão 4/10 - Estrutura de Dados 
Na AULA 5 estudamos conceitos de grafos. Abaixo temos uma imagem de um grafo. 
 
Acerca do grafo acima, assinale a alternativa CORRETA. 
Nota: 10.0 
 
A O grau do vértice V1 é 3. 
O grau é 4. Pois é o número de arestas incidentes. 
 
 
B Todos os vértices deste grafo têm o mesmo grau, caracterizando um grafo trivial. 
Tem o mesmo grau, mas o grafo é chamado de ponderado. 
 
C Este grafo é do tipo completo. 
Você acertou! 
Sim. Todos os vértices estão conectados por uma e somente uma aresta. 
 
D Se removermos qualquer uma das arestas do grafo, estaríamos transformando o grafo em um do tipo completo. 
O grafo já é completo. Se remover uma aresta qualquer, ele deixa de ser completo. 
 
E A aresta que conecta V1 e V3 e V1 E v4 podem ser chamadas de laços. 
Laço é uma aresta com um só vértice. 
 
Questão 5/10 - Estrutura de Dados 
Na AULA 4 estudamos árvores binárias. 
Acerca de árvore binárias e a visualização dos dados em uma árvore construída para funcionar como uma 
Binary Search Tree, e considerando uma árvore binária onde os elementos menores ficam no ramo 
esquerdo e os maiores no ramo direito, assinale a alternativa CORRETA. 
Nota: 10.0 
 
A Como a árvore binária não apresenta sequência/ordem fixas, podemos listar seus dados de diferentes maneiras: pré-ordem, ordem e pós-
ordem. 
Você acertou! 
 
B Uma visualização da árvore em ordem significa lista os elementos em ordem decrescente. 
Ordenação crescente; 
 
C Se fizermos uma listagem iniciando na direita, depois a raiz e depois o ramo esquerdo estaremos listando os elementos de maneira 
crescente. 
Decrescente; 
 
D A impressão de valores em pré-ordem resultará em uma impressão inversa/oposto da em pós-ordem. 
Não existe a relação de oposição entre eles. 
 
E Só é possível visualizar os dados de uma árvore binária caso não exista nenhum nó com grau 0. 
Não existe a relação entre grau e a visualização da árvore. 
 
Questão 6/10 - Estrutura de Dados 
A complexidade de um algoritmo pode ser mensurada matematicamente em termos de uma função de 
custo do algoritmo. 
Acerca da função custo de um algoritmo, assinale a alternativa CORRETA: 
Nota: 10.0 
 
A A ordem de como os dados de entradas estão organizados não tem impacto no desempenho do algoritmo em tempo de execução. 
Tem impacto. Conforme mostrado na AULA 1 – TEMA 2. 
 
 
B O custo matemático de um algoritmo é dado, exclusivamente, pelo custo de tempo de execução de um algoritmo. 
É dado pelo tempo de execução e pelo uso de memória, embora este segundo não esteja sendo investigado em nossa disciplina. 
 
C O custo matemático de tempo de execução de um algoritmo pode ser mensurado através da contagem de instruções em uma linguagem de 
alto nível. 
Você acertou! 
AULA 1 – TEMA 2. CORRETO. 
 
D A função custo é dada em função do tamanho do conjunto de dados de entrada n, ou seja, em função da quantidade de instruções a serem 
executadas. 
n representa a quantidade de dados a serem manipulados, como por exemplo, um vetor de entrada de tamanho n. E não significa as instruções contadas. 
 
E O custo de tempo de execução de um algoritmo corresponde a quantos núcleos paralelos o algoritmo está sendo executado. 
Tempo de execução significa o quão rápido um algoritmo executa para resolver um problema. Não tendo relação com o paralelismo. 
 
Questão 7/10 - Estrutura de Dados 
Uma implementação do algoritmo de ordenação do tipo bubble sort pode ser visto abaixo. As partes que 
envolvem impressão de dados na tela e leitura de dados foram omitidas para um melhor entendimento 
do que é necessário na questão. 
 
X[TAMANHOVETOR], i, j, aux: inteiro 
para i de 1 até TAMANHOVETOR faça 
 para j de 0 até (TAMANHOVETOR - 2) faça 
 se (X[j] > X[j + 1]) então 
 aux <- X[j] 
 X[j] <- X[j + 1] 
 X[j + 1] <- aux 
 fimse 
 fimpara 
fimpara 
Acerca deste algoritmo, assinale a alternativa CORRETA: 
 
Nota: 10.0 
 
A O algoritmo apresentado no exercício realizado a ordenação de dados numéricos, inteiros, em ordem decrescente. 
Ordenação é crescente. 
 
B As linhas de código que correspondem a troca dos valores usando uma variável auxiliar poderiamser também escritas da seguinte 
maneira: 
aux <- X[j+1] 
X[j+1] <- X[j] 
X[j] <- aux 
Você acertou! 
AULA 2 – TEMA 2. CORRETO. 
 
C Se precisarmos ordenar dados não numéricos, como caracteres, precisaremos repensar em toda a lógica do bubble sort, não sendo possível 
adaptar o código facilmente. 
 
Basta adaptarmos a linha da condicional para funcionar com outro tipo de dado. 
 
D Não é possível implementar o bubble sort com laços de repetição do tipo enquanto. 
É possível implementar com qualquer tipo de laço, para, enquanto ou repita. 
 
E A complexidade deste algoritmo, para o pior caso, é O(logn). 
Complexidade O(n²). 
 
Questão 8/10 - Estrutura de Dados 
Uma função que implementa parte do algoritmo merge sort pode ser vista abaixo. Todo o resto do 
algoritmo foi omitido para que analisemos somente este método. O algoritmo completo pode ser visto no 
material PDF da Aula 2. 
No código, inicio e fim são variáveis inteiras que correspondem a posições no vetor de dados, parteinteira 
significa truncar em zero casas decimais o respectivo cálculo da linha 6 e intercala refere-se a uma função 
que realiza a ordenação neste método. 
 
1. Função mergesort(X, inicio, fim) 
2. Var 
3. Meio: inteiro 
4. Inicio 
5. Se (inicio < fim) então 
6. Meio <- parteinteira((inicio + fim) / 2) 
7. mergesort(X, inicio, meio) 
8. mergesort(X, meio + 1, fim) 
9. Intercala(X, inicio, fim, meio) 
10. Fimse 
11. funfunção 
 
A assumindo que a dimensão do vetor de dados X é 10, e que a primeira chamada da função mergesort foi 
realizada com os seguintes parâmetros: Função mergesort(X, 0, 9). 
Acerca deste algoritmo, assinale a alternativa INCORRETA: 
Nota: 10.0 
 
A Na segunda instância aberta da função mergesort na memória do programa, a variável inicio vale zero e a variável meio vale 2. 
 
B Na primeira instância aberta da função mergesort na memória do programa, a variável meio corresponde ao valor 4. 
 
C Na segunda instância aberta da função mergesort na memória do programa, a variável inicio vale zero e a variável fim vale 2. 
Você acertou! 
Fim vale 4. 
 
D Na terceira instância aberta da função mergesort na memória do programa, a variável inicio vale zero e a variável fim vale 2. 
 
E Na primeira instância aberta da função mergesort na memória do programa, a variável inicio vale zero e a variável fim vale 9. 
 
Questão 9/10 - Estrutura de Dados 
 
Na AULA 5 estudamos a árvore binária balanceada AVL. Observe um exemplo de árvore AVL abaixo: 
 
Suponha que você quer remover o nó folha de valor 99. Acerca do balanceamento e rotação desta árvore 
sem o 99. Assinale a alternativa CORRETA: 
Nota: 10.0 
 
A A árvore ficará balanceada e não precisará de rotação nenhuma. 
 
B A árvore ficará com um desbalanceamento de valor 2 na raiz. 
 
C O nó filho de valor 80 está com balanceamento 0, resultando em uma rotação simples para a direta. 
Você acertou! 
Raiz -> Desbalanceada = -2. 
Filho da esquerda -> Balanceado = 0 
Rotação simples para a direita 
 
D A árvore está com um desbalanceamento de valor -2 na raiz, resultando em uma rotação simples para a esquerda. 
 
E O nó filho de valor 80 está com balanceamento 1, resultando em uma dupla com filho para a esquerda e pai para a direita. 
 
Questão 10/10 - Estrutura de Dados 
Na AULA 5 estudamos conceitos de grafos. Abaixo temos uma imagem de um grafo. 
 
Acerca do grafo acima, assinale a alternativa CORRETA. 
Nota: 10.0 
 
A O grafo contém arestas múltiplas, pois temos mais de um caminho para sair de V1 e chegar em V9, por exemplo. 
 
Arestas múltiplas são para arestas com os mesmos vértices de origem e destino. 
 
B O grau do vértice V9 é 3. 
O grau é 4. Pois é o número de arestas incidentes. 
 
C Todos os vértices deste grafo têm o mesmo grau. 
Temos graus diferentes: 2, 3 e 4. 
 
D Este grafo é do tipo completo. 
No grafo completo, todos os vértices precisam estar conectados entre si por somente uma aresta. Neste grafo faltam diversas conexões. 
 
E O grau do vértice V4 é 3. 
Você acertou! 
Correto. Pois é o número de arestas incidentes.