Complexidade de Algoritimos - AV Estácio

Prévia do material em texto

1 - Analise as seguintes afirmativas sobre os métodos de ordenação: 
 I. Quick sort divide um conjunto de itens em conjuntos menores, que são ordenados de forma independente, e, depois, os resultados são combinados para produzir a solução de ordenação do conjunto maior. 
II. Seleção é um método que consiste em selecionar o menor item de um vetor e substituí-lo pelo item que estiver na primeira posição. Essas duas operações são repetidas com os itens restantes até o último elemento. 
III. Shell sort é uma extensão do algoritmo de ordenação por inserção, contornando o problema que ocorre quando o menor item de um vetor está na posição mais à direita. 
Assinale a alternativa correta:
R: As afirmativas I, II e III estão certas.  
2 - Se f é uma função de complexidade para um algoritmo F, então, O(f) é considerada a complexidade assintótica ou o comportamento assintótico do algoritmo F. Assinale a alternativa que apresenta somente algoritmos com complexidade assintótica, quando f(n) = O(n log n):  
R: Quick sort e merge sort.  
3 - Observe a árvore binária a seguir: 
O caminhamento central (infixado) sobre essa árvore produz a sequência de visitação:
R: D - B - H - E - J - I - K - A - F - C - G 
4 - Imagine que temos números de 1 a 100 em uma árvore de pesquisa binária (ABP). Agora queremos procurar o número 50. Assinale a alternativa que apresenta a possível sequência de elementos da árvore consultada.
R: 40 - 60 - 45 - 48 - 50.  
5 - (CESPE/CEBRASPE - TRT - 8ª Região (PA e AP) - Analista Judiciário - Tecnologia da Informação - 2016)
A quantidade de grau total do grafo na figura é:
R: 14 
6 - 
	(CESGRANRIO - Banco da Amazônia - Técnico Científico - Banco de Dados - 2014)
O grafo anterior pode ser representado pela seguinte matriz:
	
	
R:
 
7 - Uma lista ordenada de N números é inserida em uma pilha e depois retirada, sendo que, a cada POP, o elemento retirado é inserido em um vetor de elementos. Após a completa inserção de todos os elementos neste vetor, são feitas buscas de números na mesma. O tempo médio de busca de um número neste elemento é:
R: O(N) 
8 - Classifique cada uma das seguintes afirmações em "V" (se verdadeira) ou "F" (se falsa) e escolha a alternativa que corresponde à sequência correta de indicações. 
I- Um registro reúne uma coleção de informações, facilitando a sua organização e o seu uso. 
II- Cada informação distinta de um registro é considerada um atributo ou campo. 
III- O atributo pode ser definido como qualquer tipo de dado que a linguagem utiliza ou como outra estrutura de dados: vetor, matriz ou mesmo outro registro.
R: V V V
9 - Considere a função recursiva `func¿ definida por
func(1) = 1
func(n) = (n - 1) * func(n - 1)
Quais são os valores de func(4) e func(5), respectivamente?
R: 6 e 24 
10 - Ano: 2019 Banca: Quadrix Órgão: Prefeitura de Jataí - GO Prova: Quadrix - 2019 - Prefeitura de Jataí - GO - Analista de Tecnologia da Informação
A situação em que dois subprogramas fazem chamadas recíprocas, como, por exemplo, um subprograma P faz uma chamada a um subprograma J, que, por sua vez, faz uma chamada a P, é caracterizada como uma
R: Recursividade indireta