CCT0608-ALGORITMOS-AVANCADOS-AV2

Prévia do material em texto

CCT0608 – ALGORIMOS AVANÇADOS 
AV2 – 25/11/2020 
 
 
ALUNO: Pedro da Graça Meirelles 
 
1) Construa uma árvore binária tendo como base uma lista composta pelos 8 últimos 
números de sua matrícula na Estácio. 
 
03196309 
 
R: ??? 
 
 
 
2) Faça a representação por expressão sem parênteses dos elementos da árvore binária 
da questão número 1. 
 
R: ??? 
 
3) Marque a opção que contém ERRO sobre árvore binária. 
 
( ) Um valor menor do que o nó pai deverá ser inserido à esquerda 
( ) Um valor maior do que o nó pai deverá ser inserido à direita 
( ) Valores iguais deverão ser inseridos uma vez. As outras vezes serão representados 
por * 
( ) Ao deletar um nó que tiver apenas um filho, o nó será deletado e o filho entrará no 
lugar do pai 
( x ) Um nó pai não poderá conter valor menor do que um nó filho 
 
 
4) Qual das opções abaixo representa um exemplo de algoritmo de ordenação por 
comparação? 
 
( ) Ordenação por divisão 
( ) Ordenação por multiplicação 
( ) Ordenação por subtração 
( ) Ordenação por variação 
( x ) Ordenação por mistura 
 
 
5) Marque a opção CORRETA sobre uma busca sequencial em um vetor. 
 
( ) A verificação deverá ser feita nos elementos do vetor que tiverem valores menores 
do que o procurado 
( x ) A verificação deverá ser feita em cada elemento do vetor 
( ) A verificação deverá ser feita nos elementos do vetor que tiverem valores maiores 
do que o procurado 
( ) A verificação deverá ser feita a partir do último elemento do vetor 
( ) A verificação deverá ser feita até a metade do vetor 
 
6) Observe o trecho de algoritmo abaixo composto por 12 linhas: 
 
Algoritmo teste 
Declaração de variáveis 
 A, soma: inteiro 
Início 
 A <- 10 
 soma <- 0 
 Enquanto A < 100 faça 
 Soma <- soma + A 
 A<- A+1 
 Fimenquanto 
 Escreva(“Soma =”,soma) 
Fimalgoritmo 
 
Quantas unidades de tempo é consumida por cada linha deste algoritmo? 
 
Não tomam tempo nenhum: Resposta: 1, 2, 3, 4 e 12 
Uma unidade de tempo: Resposta: 5, 6 e 11. 
Quatro unidades de tempo: Resposta: 7. 
Está embutido na linha 7: Resposta: 8. 
 
 
7) Com relação à complexidade de um algoritmo quanto ao comportamento pode-se 
afirmar que: 
 
( ) O pior caso é quando o algoritmo representa o menor tempo de execução sobre 
todas as entradas de tamanho n 
( ) A medida que N aumenta o fator que estiver sendo analisado aumenta 
exponencialmente. Nesse caso é polinomial 
( ) O melhor caso é quando a medida que N aumenta o fator que estiver sendo 
analisado (tempo ou espaço) aumenta linearmente 
( x ) Algoritmo com complexidade exponencial, não é executável para valores de N 
muito grandes 
( ) A média dos tempos de execução de todas as entradas de tamanho n é o melhor 
caso 
 
 
 
 
8) A técnica dividir para conquistar está relacionada à que tipo de algoritmo? 
 
( x ) Ordenação por intercalação 
( ) Ordenação por mistura 
( ) Combinação 
( ) Intercalação simples 
( ) Divisão simples 
 
 
 
9) A função que está relacionada a classificação de forma recursiva é: 
 
( ) Insertionsort 
( ) Quicksort 
( x ) Mergesort 
( ) Include 
( ) Exclude 
 
 
 
10) A técnica divisão e conquista para pesquisa em um vetor ordenado é conhecida 
como? 
 
( ) Pesquisa sequencial 
( ) Pesquisa aleatória 
( ) Pesquisa ordenada 
( x ) Pesquisa binária 
( ) Pesquisa paralela