Algoritmos e complexidade

Question 1

O que são sub-rotinas?

Answer 1

São blocos (de funções) que realizam tarefas específicas

Question 2

Para o que sub-rotinas são utilizadas?

Answer 2

Principalmente para a redução de complexidade de um algoritmo

Question 3

Quais as partes obrigatórias de uma sub-rotina?

Answer 3

Nome, tipo de retorno e corpo da função

Question 4

Qual a diferença entre função e procedimento?

Answer 4

Funções retornam valores, enquanto procedimentos não retornam nada

Question 5

Cite algumas vantagens de sub-rotinas:

Answer 5

• Torna o algoritmo mais legível
• Podem ser testadas individualmente
• São independentes
• Podem ser reutilizadas
• Facilitam a manutenção do algoritmo

Question 6

O que são vetores?

Answer 6

Uma lista de variáveis com mesmo tipo primitivo armazenada na memória de maneira sequencial

Question 7

O que são registros?

Answer 7

Uma lista de variáveis que podem ter diferentes tipos primitivos, armazenada na memória de maneira sequencial

Question 8

O que são ponteiros?

Answer 8

Variáveis que armazenam o endereço na memória de outras variáveis

Question 9

Qual a principal justificativa para o uso de ponteiros?

Answer 9

Gerenciar o armazenamento de endereços na memória

Question 10

Quais pontos a análise de algoritmos leva em consideração?

Answer 10

A exatidão do algoritmo, o tempo de execução e o espaço que ocupa em memória

Question 11

O que é análise assintótica?

Answer 11

Uma análise que descreve a complexidade de um algoritmo quando a entrada de dados se torna muito grande.

Question 12

O que é definição recursiva?

Answer 12

Quando um item é definido, e aparece como parte da própria definição.

Question 13

Como também é chamada a definição recursiva?

Answer 13

Definição Indutiva

Question 14

Quais as partes de uma definição recursiva?

Answer 14

1 - Uma base, que determina um caso simples de item definido

2 - Um passo recursivo, onde os outros casos do item vão ser definidos com base nos casos anteriores

Question 15

Onde a definição recursiva pode ser utilizada?

Answer 15

1 - Sequência de objetos

2 - Funções

3 - Conjuntos

Question 16

O que é uma sequência de objetos?

Answer 16

Uma lista de objetos enumerados.

Question 17

O que ocorre com uma sequência de objetos quando é recursiva?

Answer 17

Explicita o primeiro valor e define os próximos valores com base no inicial

Question 18

Qual a definição recursiva de uma função?

Answer 18

Um domínio de inteiros não negativos com dois passos.

Question 19

O que é o problema de Fibonacci?

Answer 19

Uma sequência infinita de números naturais, aonde a partir do terceiro o valor é obtido pela soma dos dois números anteriores.

Question 20

Qual a fórmula do algoritmo de Fibonacci?

Answer 20

F(n) = F(n-1) + F(n-2)

Question 21

O que é um conjunto?

Answer 21

Um conjunto de valores finitos e desordenados.

Question 22

Quais as 3 leis da recursividade?

Answer 22

1 - Deve ter um caso básico

2 - Deve mudar seu estado e se aproximar do caso básico

3 - Deve chamar a si mesmo

Question 23

Quais os tipos de recursividade?

Answer 23

1 - Em cauda

2 - Indireta

3 - Aninhada

Question 24

O que é a recursividade em cauda?

Answer 24

Quando a função chama ela mesmo no final da sua execução

Question 25

O que é a recursividade indireta?

Answer 25

Quando uma função A chama a função B, e a função B chama a função A novamente.

Question 26

O que é recursividade aninhada?

Answer 26

Quando uma função recursiva chama outra função recursiva dentro de si.

Question 27

Qual a principal vantagem da recursividade?

Answer 27

Simplicidade, podendo resolver um problema com poucas linhas

Question 28

Qual a principal desvantagem de recursividade?

Answer 28

A chamada em loop e o empilhamento de ações

Question 29

O que é ordenação?

Answer 29

É o método de organizar um conjunto de objetos em ordem ascendente ou descendente

Question 30

Qual o objetivo da ordenação?

Answer 30

Facilitar a recuperação dos itens de um conjunto

Question 31

Com base em que a ordenação é feita? E quais as mais comuns?

Answer 31

É feita com base em uma chave de ordenação. E, as chaves de ordenação mais comuns são:

• Ordem numérica
• Ordem alfabetica (lexicográfica)

Question 32

Quais os tipos de ordenação?

Answer 32

1 - Interna (IN-PLACE)
2 - Externa

Question 33

Quando uma ordenação é interna?

Answer 33

O conjunto de dados é pequeno e cabe na memória principal. O processo de ordenar é realizado na memória principal.

Question 34

Quando a ordenação é externa?

Answer 34

Quando o conjunto de dados não cabe todo na memória principal.

Podendo estar em um disco externo em formato de registro que serão acessados sequencialmente

Question 35

Como funciona o bubble sort?

Answer 35

Comparando o elemento da vez ao próximo. Se não estiver na ordem correta, são trocados. Isso é repetido até que todas as trocam sejam feitas

Question 36

Qual complexidade do algoritmo bubble sort?

Answer 36

O(n²)

Question 37

Como funciona o insertion sort?

Answer 37

Verificando cada item por vez, e inserindo ele em seu devido lugar na lista.

Question 38

Qual a complexidade do algoritmo insertion sort?

Answer 38

O(n²)

Question 39

Como funciona o selection sort?

Answer 39

Selecionando o melhor elemento para ocupar uma posição no array a cada execução.

Question 40

Qual a complexidade do selection sort?

Answer 40

O(n²)

Question 41

Qual o tipo dos algortimos merge sort e quick sort?

Answer 41

Dividir para conquistar

Question 42

Como funciona o merge sort?

Answer 42

Nele, o vetor é divido em vetores com a metade do tamanho original. Isso acontece até que o vetor tenha somente um item, e esteja ordenado e intercalado

Question 43

Qual a complexidade do merge sort?

Answer 43

O(N log2 N)

Question 44

Como funciona o quick sort?

Answer 44

Divide o vetor em duas partes, e faz isso até que o vetor tenha apenas um item, enquanto os outros ficam ordenados.

Question 45

Qual a complexidade do quick sort?

Answer 45

No pior caso: O(n²),

No melhor caso: O(N log N)

Question 46

De qual algoritmo o shell sort é derivado e como ele funciona?

Answer 46

É derivado do insertion sort e funciona com base na diminuição de incrementos

Question 47

Qual a complexidade do shell sort?

Answer 47

O(n^1.25)

Question 48

Pois quais elementos uma árvore binária T é composta?

Answer 48

Por um objeto N chamado de nó raiz, e por galhos Te e Td