2ALGORITMOS E PROGRAMAÇÃO II quiz 2

Prévia do material em texto

• Pergunta 1 
1 em 1 pontos 
 
Existe um algoritmo de ordenação que parece com o jeito de organizar as cartas de baralho na mão de 
um jogador de pôquer. Qual é o nome desse algoritmo? 
 
 
Resposta Selecionada: 
Insertion sort. 
Respostas: 
Insertion sort. 
 
Selection sort. 
 
Bubble sort. 
 
QuickSort. 
 
MergeSort. 
Comentário da 
resposta: 
Insertion sort. Esse algoritmo abre espaço no vetor para incluir os elementos 
menores primeiro que os maiores, como um jogador de pôquer organizando as 
cartas em sua mão. 
 
 
• Pergunta 2 
1 em 1 pontos 
 
Qual a função do caso básico em um algoritmo recursivo? 
Resposta Selecionada: e. 
Servir como critério de parada. 
Respostas: a. 
Deixar mais rápido. 
 b. 
Deixar a programação dinâmica. 
 c. 
Servir como um template. 
 d. 
Não existe caso básico em algoritmo recursivos. 
 e. 
Servir como critério de parada. 
Comentário da 
resposta: 
O caso básico dá ao algoritmo recursivo uma resposta imediata, isso significa que 
aquele é o menor valor de resposta que pode ser obtido no processo. Sendo assim, 
ele funciona como um critério de parada. 
 
 
• Pergunta 3 
0 em 1 pontos 
 
As estruturas de dados pilha e fila são essenciais em muitos aspectos dos sistemas computacionais. 
Sobre estas duas estruturas de dados, analise as seguintes afirmativas. 
I. A pilha é ocasionalmente chamada de FIFO (First-in, First-out – o primeiro a entrar é o primeiro a 
sair). 
II. A fila é uma lista LIFO (Last-in, First-out – o último a entrar é o primeiro a sair). 
III. O resultado de uma tentativa inválida de remover um elemento de uma fila vazia é chamado de 
underflow. 
IV. O resultado de uma tentativa inválida de desempilhar ou acessar um item de uma pilha vazia é 
chamado de underflow. 
Assinale a alternativa CORRETA. 
 
Resposta Selecionada: e. 
Todas as afirmativas estão corretas. 
Respostas: a. 
Apenas as afirmativas I e II estão corretas. 
 b. 
Apenas as afirmativas III e IV estão corretas. 
 
c. 
Apenas as afirmativas I e III estão corretas. 
 d. 
Apenas as afirmativas II e IV estão corretas. 
 e. 
Todas as afirmativas estão corretas. 
Comentário da 
resposta: 
Underflow é o termo utilizado em programação para erro ao tentar 
remover um item de um vetor. 
 
 
• Pergunta 4 
1 em 1 pontos 
 
Qual algoritmo de busca deve ser utilizado quando não se tem a certeza de que o conjunto de dados 
está ordenado? 
 
Resposta Selecionada: d. 
Busca sequencial. 
Respostas: a. 
Busca binária. 
 b. 
Busca em largura. 
 
c. 
Busca em profundidade. 
 
 d. 
Busca sequencial. 
 e. 
Busca ligada. 
Comentário da 
resposta: 
A busca sequencial é o método mais simples e mais utilizado para encontrar 
elementos em conjuntos de dados não ordenados. 
 
• Pergunta 5 
0 em 1 pontos 
 
Ao inserir um nó dentro de uma estrutura heap, deve ser realizado um processo para manter a ordem. 
Qual o nome desse processo? 
 
Resposta Selecionada: a. 
Heapsort. 
Respostas: a. 
Heapsort. 
 b. 
Bubble sort. 
 c. 
Sift-up. 
 
d. 
Max-heap. 
 e. 
Min-heap. 
Comentário da 
resposta: 
O processo que leva o nó inserido da folha da árvore em direção a raiz 
até que o nó esteja na posição correta é chamado de sift-up. É como se 
o nó fosse peneirado até seu lugar. 
 
 
• Pergunta 6 
1 em 1 pontos 
 
Qual estrutura de dados serve como base para o Heap? 
Resposta Selecionada: a. 
Árvore binária. 
Respostas: a. 
Árvore binária. 
 b. 
Pilha. 
 c. 
Fila. 
 d. 
 
Vetor. 
 e. 
Lista ligada. 
Comentário da 
resposta: 
Para manter as operações em tempo logarítmico, o Heap se baseia em uma 
árvore binária. 
 
• Pergunta 7 
0 em 1 pontos 
 
A estrutura de dados ______ é uma lista linear em que todas as inserções são realizadas em um 
extremo da estrutura e todas as retiradas e acessos são realizados no outro extremo da estrutura. Uma 
implementação por meio de arranjos é circular, delimitada pelos apontadores “Frente” e “Trás”. Para 
inserir um item, basta mover o apontador “Trás” uma posição no sentido horário; para retirar um item, 
basta mover o apontador ”Frente” uma posição no sentido horário. 
Assinale a alternativa que completa corretamente a lacuna do texto acima. 
 
Resposta Selecionada: c. 
Pilha. 
Respostas: a. 
Tabela hash. 
 b. 
Árvores binárias. 
 c. 
Pilha. 
 d. 
Árvore binária de pesquisa. 
 e. 
Fila. 
Comentário da 
resposta: 
A fila opera com a regra FIFO, onde o último elemento que entrou deve ser 
o último a sair. Sendo assim, as extremidades de entrada e saída dos 
dados são opostas. 
 
 
• Pergunta 8 
0 em 1 pontos 
 
Considerando o conceito de Complexidade de Algoritmos, representado por O(função), assinale a 
alternativa que apresenta, de forma crescente, as complexidades de algoritmos. 
 
Resposta Selecionada: b. 
O(n2); O(n3); O(2n); O(log n); O(n log n). 
Respostas: a. 
O(2n); O(n3); O(n2); O(log n); O(n log n). 
 b. 
 
O(n2); O(n3); O(2n); O(log n); O(n log n). 
 c. 
O(n3); O(n2); O(2n); O(n log n); O(log n). 
 d. 
O(log n); O(n log n); O(n2); O(n3); O(2n). 
 
e. 
O(n log n); O(log n); O(2n); O(n3); O(n2). 
Comentário da 
resposta: 
As funções são crescentes a partir da seguinte regra: constante, 
logarítmicas, lineares, polinomiais e exponenciais. 
 
• Pergunta 9 
0 em 1 pontos 
 
O algoritmo de ordenação baseado em várias iterações sobre o array, realizando, quando necessárias, 
trocas, sempre posicionando o menor elemento nas primeiras posições, denomina-se método: 
 
Resposta Selecionada: b. 
da inserção (insertion sort) 
Respostas: a. 
das trocas (exchange sort) 
 b. 
da inserção (insertion sort) 
 c. 
da bolha (bubble sort) 
 d. 
da seleção (selection sort) 
 e. 
da permuta (permutation sort) 
Comentário da 
resposta: 
O selection sort procura pelo menor elemento em um vetor e o posiciona 
sempre na primeira posição livre do vetor, garantindo assim sua 
ordenação. 
 
 
• Pergunta 10 
0 em 1 pontos 
 
Dado os conjuntos de dados abaixo: 
I. [10, 29, 31, 15, 12]. 
II. [10, 15, 16, 18, 19, 20]. 
III. [1, 2, 3, 5, 4, 6, 7, 8] 
Qual(is) representa(m) o pior caso do algoritmo QuickSort? 
 
 
Resposta Selecionada: c. 
Apenas I e III. 
Respostas: a. 
Apenas I e II. 
 b. 
Apenas II e III. 
 c. 
Apenas I e III. 
 d. 
Apenas II. 
 e. 
Apenas III. 
Comentário da 
resposta: 
No pior caso do QuickSort, o vetor deve estar totalmente 
ordenado. 
 
 
 
 
PERGUNTA 1 
1. Considere os seguintes algoritmos e suas complexidades na notação Big O: - Algoritmo A: 
O(log n); - Algoritmo B: O(n2); - Algoritmo C: O(n . log n). Considerando-se o pior caso de 
execução destes algoritmos, é correto afirmar que o algoritmo: 
 
a. A é o menos eficiente. 
 
b. C é o menos eficiente. 
 
c. A não é o mais eficiente nem o menos eficiente. 
 
d. B é o menos eficiente. 
 
e. C é o mais eficiente. 
1 pontos 
PERGUNTA 2 
1. Existe um algoritmo de ordenação que parece com o jeito de organizar as cartas de baralho 
na mão de um jogador de pôquer. Qual é o nome desse algoritmo? 
 
 
 
Insertion sort. 
 
 
Selection sort. 
 
 
Bubble sort. 
 
 
QuickSort. 
 
 
MergeSort. 
1 pontos 
PERGUNTA 3 
1. Considere as estruturas de dados com as seguintes propriedades: 
I) Inserção e remoção acontecem apenas na ‘cabeça’ da estrutura. 
II) A inserção de um nó no meio da estrutura pode ser realizada com custo computacional 
constante. 
III) Respeita a política FIFO: primeiro que entra é o primeiro que sai. 
As descrições acima se referem às estruturas, respectivamente, 
 
a. Fila, Pilha, Lista. 
 
b. Lista, Pilha, Fila. 
 
c. Pilha, Fila, Lista. 
 
d. Pilha, Lista, Fila. 
 
e. Lista, Fila, Pilha. 
1 pontos 
PERGUNTA 4 
1. Assinale a opção que apresenta o algoritmo de ordenação com o pior desempenho, 
considerando-se um vetor com valores ordenados em ordem inversa.a. Insertion sort. 
 
b. QuickSort. 
 
c. MergeSort 
 
d. Selection sort. 
 
e. Bubble sort. 
1 pontos 
PERGUNTA 5 
1. No contexto de estrutura de dados, uma pilha é: 
 
a. uma lista do tipo LILO. 
 
b. uma lista do tipo FIFO. 
 
c. 
um tipo de lista linear em que as operac ̧ões de inserc ̧ão e remoção são realizadas na 
extremidade denominada topo. 
 
d. 
um tipo de lista linear em que as operac ̧ões de inserc ̧ão e remoção são realizadas 
aleatoriamente. 
 
e. 
um tipo de lista linear em que as operac ̧ões de inserc ̧ão são realizadas em uma 
extremidade e as operac ̧ões de remoc ̧ão são realizadas em outra extremidade. 
1 pontos 
PERGUNTA 6 
1. Qual estrutura de dados serve como base para o Heap? 
 
a. Árvore binária. 
 
b. Pilha. 
 
c. Fila. 
 
d. Vetor. 
 
e. Lista ligada. 
1 pontos 
PERGUNTA 7 
1. O elemento do pivô que auxilia o processo de particionar um vetor é característica de qual 
algoritmo? 
 
a. Bubble sort. 
 
b. Insertion Sort. 
 
c. Selection sort. 
 
d. QuickSort. 
 
e. MergeSort. 
1 pontos 
PERGUNTA 8 
1. Ao usar o método Bubble sort para ordenar uma tabela em ordem crescente contendo os 
números 10, 8, 7 e 0, serão feitas: 
 
a. 6 comparações e 4 trocas. 
 
 
b. 8 comparações e 6 trocas. 
 
c. 6 comparações e 6 trocas. 
 
d. 8 comparações e 8 trocas. 
 
e. 8 comparações e 4 trocas. 
1 pontos 
PERGUNTA 9 
1. Assinale a opção correta: 
 
a. 
Uma fila é um tipo de lista linear em que todas as categorias são inseridas em um 
extremo, ficando as classes restritas ao outro extremo. 
 
b. 
Uma pilha é um tipo de lista linear em que todas as operações de inserção e remoção 
são realizadas numa mesma extremidade. 
 
c. 
Uma fila é um tipo de lista colinear em que inserções parametrizadas são realizadas no 
mesmo extremo que as remoções. 
 
d. 
Uma pilha é um tipo de lista encadeada em que todas as operações de inserção e 
retrieve são realizadas na extremidade mais próxima. 
 
e. 
Uma pilha é um fila linear em que todas as operações de carry e stand são realizadas 
numa mesma extremidade. 
1 pontos 
PERGUNTA 10 
1. Qual a função do caso básico em um algoritmo recursivo? 
 
a. Deixar mais rápido. 
 
b. Deixar a programação dinâmica. 
 
c. Servir como um template. 
 
d. Não existe caso básico em algoritmo recursivos. 
 
e. Servir como critério de parada.