AV - Complexidade de Algoritmos

Prévia do material em texto

Disciplina: COMPLEXIDADE DE ALGORITMOS AVS 
 
 
Avaliação: 
10,0 
Nota Partic.: Av. Parcial.: 
2,0 
Nota SIA: 
10,0 pts 
 
 
 
 
 
ENSINEME: ALGORITMOS DE ORDENAÇÃO AVANÇADOS 
 
 
 1. Ref.: 4059323 Pontos: 1,00 / 1,00 
 
O algoritmo de ordenação mais eficiente para um conjunto grande de elementos randomicamente 
inseridos é: 
 
 Selection sort 
 Shell sort 
 Quick sort 
 Bubble sort 
 Insert sort 
 
 
 2. Ref.: 4053481 Pontos: 1,00 / 1,00 
 
Correlacione os algoritmos internos de ordenação de listas com sua descrição: 
 
I. Bubble sort 
II. Ordenação por seleção 
III. Ordenação por inserção 
IV. Shell sort 
V. Quick sort 
 
( ) Escolhe-se um pivô e particiona-se a lista em duas sublistas - uma com os elementos menores que 
ele e outra com os maiores, que, ao serem ordenadas e combinadas com o pivô, geram uma lista 
ordenada. O processo é aplicado às partições para ordená-las. Embora tenha uma complexidade de pior 
caso de O(n2 ), no caso médio, é de O(n log n). 
 
( ) Encontra-se o menor item do vetor. Troca-se com o item da primeira posição do vetor. Repetem-se 
essas duas operações com os n − 1 itens restantes; depois, com os n − 2 itens; até que reste apenas 
um elemento. 
 
( ) Método preferido dos jogadores de cartas. A cada momento, existem duas partes na lista ¿ uma 
ordenada (destino) e outra não ordenada (fonte). Inicialmente, a lista destino tem apenas o primeiro 
elemento, e a fonte, os demais elementos. Em cada passo, a partir de i=2, seleciona-se o i-ésimo item 
da lista fonte. Deve-se colocá-lo no lugar apropriado na lista destino, de acordo com o critério de 
ordenação. 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%204059323.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%204053481.');
 
( ) É uma extensão de outro algoritmo de ordenação conhecido e permite trocas de elementos distantes 
um do outro, não necessariamente adjacentes. Os itens separados de h posições são rearranjados. Todo 
h-ésimo item leva a uma lista ordenada. Tal lista é dita estar h-ordenada. 
 
( ) Varre-se a lista, trocando de posição os elementos adjacentes fora de ordem. Varre-se a lista até que 
não haja mais trocas. Neste caso, a lista está ordenada. 
 
A sequência correta, de cima para baixo, é: 
 
 I, IV, V, III, II 
 I, II, III, IV, V 
 V, II, III, IV, I 
 I, III, II, IV, V 
 V, IV, II, III, I 
 
 
 
 
ENSINEME: ALGORITMOS EM ÁRVORES BINÁRIA E ÁRVORE AVL 
 
 
 3. Ref.: 3990639 Pontos: 1,00 / 1,00 
 
Após a inserção de um nó, é necessário verificar cada um dos nós ancestrais desse nó inserido, 
relativamente à consistência com as regras estruturais de uma árvore AVL. 
 PORQUE 
O fator de balanceamento de cada nó, em uma árvore AVL, deve pertencer ao conjunto formado por 
{−2, −1, 0, +1, +2}. 
 
Analisando-se as afirmações acima, conclui-se que: 
 
 as duas afirmações são verdadeiras, e a segunda não justifica a primeira. 
 a primeira afirmação é verdadeira, e a segunda é falsa. 
 as duas afirmações são falsas. 
 a primeira afirmação é falsa, e a segunda é verdadeira. 
 as duas afirmações são verdadeiras, e a segunda justifica a primeira. 
 
 
 4. Ref.: 3990638 Pontos: 1,00 / 1,00 
 
Árvore AVL é uma árvore de busca autobalanceada. Isso significa que: 
 
 as alturas das duas subárvores a partir de cada nó diferem no máximo em uma unidade. 
 cada nó da árvore possui até três descendentes. 
 as alturas das duas subárvores a partir de cada nó diferem no máximo em duas unidades. 
 as alturas das duas subárvores a partir de cada nó são exatamente iguais. 
 pode possuir até duas raízes. 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%203990639.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%203990638.');
 
 
 
 
ENSINEME: ALGORITMOS EM GRAFOS 
 
 
 5. Ref.: 3992624 Pontos: 1,00 / 1,00 
 
(Adaptado de: DPE-RJ - Técnico Superior Especializado - Tecnologia da Informação - 2019) 
Para que um sistema seja testado adequadamente, é preciso realizar uma quantidade mínima de testes. Para apoiar essa 
definição, foi criada a Complexidade Ciclomática de McCabe, com fundamentação na teoria dos grafos. Essa técnica define uma 
métrica de software que fornece uma medida quantitativa da complexidade lógica de um programa, apresentando um limite 
superior para a quantidade de casos de testes de software que devem ser conduzidos. 
 
A Complexidade Ciclomática pode ser calculada tanto pelo número de regiões quanto pelo número de arestas e nós. 
 
Complexidade é calculada pela fórmula CC = arestas - nós + 2 
 
Com base no grafo de fluxo anterior, correspondente a um trecho de código a ser testado, a quantidade mínima de testes que 
devem ser realizados para garantir que cada caminho do código tenha sido percorrido em ao menos um teste é: 
 
 3 (três) 
 5 (cinco) 
 4 (quatro) 
 6 (seis) 
 11 (onze) 
 
 
 6. Ref.: 3992630 Pontos: 1,00 / 1,00 
 
(IBGE - Analista Censitário - Análise de Sistemas - Desenvolvimento de Aplicações - Web Mobile - 2017) 
Observe a figura a seguir que ilustra relações entre colegas e seus interesses: 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%203992624.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%203992630.');
 
O tipo de Banco de Dados NoSQL, não relacional, que armazena tais informações, utilizando estruturas de vértices e arestas, com 
propriedades associadas, é o: 
 
 
Tabular 
 
Documento 
 Grafo 
 
Chave-valor 
 
Colunar 
 
 
 
 
ENSINEME: ANÁLISE DE ALGORITMO 
 
 
 7. Ref.: 3990621 Pontos: 1,00 / 1,00 
 
No algoritmo abaixo, os parâmetros da função valor são recebidos e são impressos na própria função. 
Assim sendo, o valor da variável u exibido na última linha da função é: 
Algoritmo questao_prova; 
var 
x,y: inteiro; 
inicio 
x<- 4; 
y<- 2; 
valor(x,y); 
fim. 
 
sub-rotina valor(inteiro: u, v) 
inicio 
u <- u * 2; 
v <- v + u; 
u <- u - 1; 
escreva(u); 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%203990621.');
fim sub-rotina; 
 
Marque a opção que mostra o valor correto exibido da variável u. 
 
 4 
 8 
 10 
 7 
 5 
 
 
 8. Ref.: 3990628 Pontos: 1,00 / 1,00 
 
Analise o custo computacional dos algoritmos a seguir, que calculam o valor de polinomio de grau n da 
forma onde os coeficientes são números de ponto flutuante armazenados no vetor [a..n], e o valor de n é 
maior que zero. Todos os coeficientes podem assumir qualquer valor, exceto o coeficiente anan que é 
diferente de zero. 
 
Com base nos algoritmos 1 e 2, avalie as asserções a seguir e a relação proposta entre elas. 
1. Os algoritmos possuem a mesma complexida assintótica 
 PORQUE 
1. Para o melhor caso, ambos possuem a complexidade O(n) 
 
A respeito dessas asserções, assinale a opção correta: 
 
 a primeira asserção é uma proposição verdadeira e a segunda uma proposição falsa. 
 as duas asserções são proposições verdadeiras e a segunda não é a justificativa correta da 
primeira. 
 a primeira asserção é uma proposição falsa e a segunda uma proposição verdadeira. 
 as duas asserções são proposições verdadeiras, mas a segunda é uma justificativa correta da 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%203990628.');
primeira. 
 tanto a primeira quanto a segunda asserções são proposições falsas. 
 
 
 
 
ENSINEME: RECURSIVIDADE 
 
 
 9. Ref.: 3992587 Pontos: 1,00 / 1,00 
 
Ano: 2017 Banca: CONSULPLAN Órgão: TRE-RJ Prova: CONSULPLAN - 2017 - TRE-RJ - Técnico Judiciário - Programação de 
Sistemas 
Analise as afirmativas a seguir a respeito de algoritmos recursivos. 
I. Diz-se que uma rotina é recursiva se a sua definição envolver uma chamada a ela mesma. Neste sentido, o termo recursão é 
equivalente ao termo indução utilizado por matemáticos. 
II. Cada algoritmo recursivopossui um algoritmo iterativo equivalente e vice-versa, mas que pode ter mais ou menos 
complexidade em sua construção. 
III. Uma função recursiva possui duas partes: caso base e caso recursivo. 
IV. Um algoritmo pode ser chamado de iterativo quando ele requer a repetição implícita de um processo até que determinada 
condição seja satisfeita. 
V. A recursividade possibilita a escrita de um código mais enxuto, com maior legibilidade e simplicidade. 
Assinale a alternativa que possui alguma afirmação INCORRETA. 
 
 
II e III 
 
I e II 
 
I e IV 
 
I e V 
 III e IV 
 
 
 10. Ref.: 3992618 Pontos: 1,00 / 1,00 
 
O código abaixo é uma implementação: 
 
public class Misterio { 
public static long Misterio(long x) { 
if (x == 1) 
return 1; 
else 
return x * Misterio(x-1); 
} 
} 
 
 Recursiva do fatorial 
 
Iterativa da exponenciação 
 
Recursiva da série de Fibonacci 
 
Recursiva da exponenciação 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%203992587.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%203992618.');
 
Iterativa da série de Fibonacci