GUIA DE ESTUDO - Algoritmos e Complexidade

Prévia do material em texto

Algoritmos e Complexidade 
 
1- O algoritmo de ordenação mais eficiente para um conjunto grande de 
elementos randomicamente inseridos é: 
A- Selection sort 
B- Insert sort 
C- Shell sort 
D- Quick sort 
E- Bubble sort 
 
Resposta: D. 
2- Acerca dos algoritmos de ordenação, assinale a afirmativa correta: 
A- O algoritmo insertion sort é mais eficiente do que o quick sort para grandes 
entradas de dados. 
B- A complexidade do algoritmo bubble sort é de ordem logarítmica. 
C- O shell sort é um algoritmo de ordenação estável e instável. 
D- O algoritmo merge sort é implementado por meio de divisão e conquista. 
E- O algoritmo de ordenação heap sort utiliza uma árvore ternária de busca. 
 
Resposta: D. 
3- Observe a árvore binária a seguir: 
 
O caminhamento central (infixado) sobre essa árvore produz a sequência 
de visitação: 
A- A - B - C - D - E - F - G - H - I - J - K 
B- D - H - J - K - I - E - B - F - G - C - A 
C- D - B - H - E - J - I - K - A - F - C - G 
D- J - K - I - H - E - D - B - F - G - C - A 
E- A - B - D - E - H - I - J - K - C - F - G 
 
Resposta: C. 
4- Árvore de pesquisa é uma estrutura de dados eficiente para armazenar 
informação, sendo particularmente adequada quando existe a 
necessidade de considerar todos ou alguma combinação de registros. 
Assinale uma combinação correta desses registros: 
A- As operações de inserir, retirar e pesquisar são definidas. 
B- Não é necessário indexar os registros. 
C- Utilização de estruturas de dados como lista, pilha e fila. 
D- Acesso direto e sequencial eficientes, facilidade de inserção e retirada de 
registro, boa taxa de utilização de memória, utilização de memória primária 
e secundária. 
E- Utilização de algoritmos de ordenação eficientes. 
 
 
Resposta: D. 
5- (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 detestes que devem ser 
realizados para garantir que cada caminho do código tenha sido 
percorrido em ao menos um teste é: 
A- 4 (quatro) 
B- 5 (cinco) 
C- (seis) 
D- 11 (onze) 
E- 3 (três) 
 
Resposta: A. 
6- (FCC - ARTESP - Agente de Fiscalização à Regulação de Transporte 
- Tecnologia de Informação - 2017)Considere a estrutura abaixo que 
representa um problema de rotas em pequena escala: 
 
Considere, por hipótese, que se solicitou a um Agente de Fiscalização à 
Regulação de Transporte da ARTESP utilizar alguma estratégia lógica 
para, partindo do ponto 1, chegar ao ponto 6 usando a menor rota. De um 
mesmo ponto pode haver mais de uma rota, com distâncias diferentes. A 
lógica correta utilizada pelo Agente, em função dos pontos a serem 
percorridos, foi: 
A- {1} {2,3} {2,4} {5,6} {6}, caminho mais curto 1-2-5-6. 
B- {6} {5,4} {3,1} {1}, caminho mais curto 6-4-3-1, que é igual a 1-3-4-6. 
C- {6} {4} {5,3} {2,1} {1}, caminho mais curto 6-4-3-5-2-1, que é igual a 1-2-5-3-
4-6. 
D- {1} {3,2} {4,5} {6}, caminho mais curto 1-3-4-6. 
E- {1} {2} {4} {6}, caminho mais curto 1-2-4-6. 
 
 
Resposta: D. 
7- 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. 
 
A- V, V, V 
B- V, F, V 
C- F, V, F 
D- F, F, V 
E- V, F, F 
 
Resposta: A. 
8- Analise o custo computacional dos algoritmos a seguir, que calculam o 
valor 
de polinômio 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 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 complexidade 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- tanto a primeira quanto a segunda asserção são proposições falsas. 
B- as duas asserções são proposições verdadeiras e a segunda não é a 
justificativa correta da primeira. 
C- a primeira asserção é uma proposição falsa e a segunda uma proposição 
verdadeira. 
D- as duas asserções são proposições verdadeiras, mas a segunda é uma 
justificativa correta da primeira. 
F- a primeira asserção é uma proposição verdadeira e a segunda uma 
proposição falsa. 
 
 
 
Resposta: C. 
9- . 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);} 
} 
A- Recursiva da série de Fibonacci 
B- Recursiva da exponenciação 
C- Iterativa da série de Fibonacci 
D- Iterativa da exponenciação 
E- Recursiva do fatorial 
 
Resposta: E. 
10- Analise o seguinte código: 
public static double recursive (double d) { 
if (d <= 1) { 
return 1; 
} else { 
return d * recursive(d - 1);} 
} 
Assinale o conteúdo que será exibido na saída do programa quando a 
função for chamada com o parâmetro 6: 
A- 360 
B- 240 
C- 1440 
D- 720 
E- 120 
 
 
Resposta: D. 6 * (6 - 1) * (5 - 1) * (4 - 1) * (3 - 1) * (2 - 1) * (1) , que é igual a 720. 
11- Analise as seguintes afirmações relacionadas a conceitos básicos sobre 
Programação: 
I. Um procedimento é um conjunto de comandos para uma tarefa 
específica referenciada por um nome no algoritmo principal, 
retornando um determinado valor no seu próprio nome. 
II. Podem-se inserir módulos em um algoritmo. Para isso, pode-se 
utilizar "Procedimentos" ou "Funções". As ações das "Funções" e 
dos "Procedimentos" são hierarquicamente subordinadas a um 
módulo principal. 
III. Cada "Função" ou "Procedimento" pode utilizar constantes ou 
variáveis do módulo principal ou definir suas próprias constantes 
ou variáveis. 
IV. Uma variável global indica o endereço onde um valor é 
armazenado na memória do computador, enquanto um ponteiro 
representa um valor numérico real. 
Indique a opção que contenha todas as afirmações verdadeiras. 
A- I e III. 
B- II e IV. 
C- II e III. 
D- III e IV. 
E- I e II. 
 
Resposta: C. 
12- Considere o algoritmo em pseudocódigo, descrito a seguir. 
 
Calcule a complexidade do algoritmo, sabendo que a função f tem 
complexidade igual a O(n22): 
A- O(n²2log22(n)) 
B- O(n³3) 
C- O(n³3log(n)) 
D- O(n55) 
E- O(n44log(n)) 
 
Resposta: E. 
13- Sobre o conceito de Algoritmos Recursivos, analise as afirmações abaixo 
e, a seguir, assinale a alternativa correta. 
I. Um programa tem um número limitado de procedimentos recursivos. 
II. Recursividade é utilizada exclusivamente quando não se sabe 
solucionar um problema de maneira imediata, então é realizada a 
divisão em problemas menores para alcançar o resultado desejado. 
III. Todos os problemascomputacionais resolvidos de maneira iterativa 
gastam mais memória que se resolvidos de forma recursiva. 
 
A- Nenhuma das afirmações está correta. 
B- Somente a afirmação II está correta. 
C- Somente a afirmação I está correta. 
D- Somente a afirmação III está correta. 
E- As afirmações I e II estão corretas. 
 
Resposta: A. 
14- A ordenação de elementos em um vetor pode ser executada a partir de 
diversos algoritmos conhecidos que são adequados para situações 
específicas. Sobre algoritmos de ordenação, analise as seguintes 
afirmativas: 
I. O algoritmo bubble sort é eficiente para ordenar poucos 
elementos, mas é lento para ordenar muitos itens. 
II. O algoritmo selection sort para ordenação crescente consiste em 
mover o menor valor do vetor para a primeira posição; depois, o 
segundo menor para a segunda posição; e assim sucessivamente, 
até os dois últimos valores. 
III. O algoritmo quick sort ordena os valores de um vetor por meio de 
sucessivas seleções do elemento correto a ser posicionado em um 
segmento ordenado. 
Está(ão) correta(s) a(s) afirmativa(s): 
A- II apenas 
B- I, II e III 
C- I e III 
D- I e II 
E- I apenas 
Resposta: D. 
15- Considere que os percentuais foram inseridos no vetor vet de 5 posições, 
a partir da posição 1, na seguinte sequência: 25.33, 27.72, 27.10, 26.90 e 
27.31, ou seja, com os dados de 2008 até 2012. Um técnico em 
processamento de dados do TCE-RS utilizou um método para ordenar os 
dados de vet. O método realizou os seguintes passos no processo de 
ordenação: 
• Passo 1 - 25.33 27.72 27.10 26.90 27.31; 
• Passo 2 - 25.33 27.10 27.72 26.90 27.31; 
• Passo 3 - 25.33 26.90 27.10 27.72 27.31; 
• Passo 4 - 25.33 26.90 27.10 27.31 27.72. 
Trata-se do método de ordenação: 
A- Bubble sort 
B- Fast sort 
C- Insertion sort 
D- Quick sort 
E- Selection sort 
 
 
Resposta: C. 
16- A estrutura abaixo representa uma célula de uma árvore em linguagem 
C; 
typedef struct _no { 
int chave; 
struct _no *esq, *dir; 
} 
 
Assinale a alternativa correta sobre qual sequência será impressa ao executar 
um caminhamento na árvore abaixo, conforme o código escrito em linguagem 
C a seguir: 
 void ordem (no *arvore) { 
if (arvore != NULL) { 
printf ( "%d", arvore -> chave); 
ordem ( arvore -> esq ); 
ordem ( arvore -> dir ); 
} 
} 
A- ABCDEXY 
B- ABDCEYX 
C- YXEABBC 
D- AEXYBCD 
E- CBDAXEY 
 
Resposta: A. 
17- Analise a seguinte árvore binária e assinale a alternativa correta. 
 
A- "B" e "C" são caules da árvore. 
B- Com exceção do nó "A", que é raiz, os demais nós são conhecido 
como folhas. 
C- TA é a subárvore enraizada em "A", portanto toda a árvore. 
D- "B" tem grau de saída 3 e "C" grau 2. 
E- "A" é filho de todos. 
 
Resposta: C. 
18- (FCM - IFN-MG - Ciências da Computação: Teoria da Computação - 2018) 
Considere o grafo abaixo assim como sua representação por lista de 
adjacência: 
 
A Árvore em Largura e a Árvore em Profundidade, respectivamente, 
tendo como raiz o vértice 1, são: 
 
 
 
 
Resposta: D. 
19- (COMPERVE - UFRN - Engenheiro - Engenharia da Computação - 2019) 
O código abaixo pode ser utilizado para atravessar um grafo: 
Entrada: um gráfico G e um vértice v de G 
Saída: todos os vértices alcançáveis de v marcados 
função DFS(G,v): 
marque v 
para todas as arestas adjacentes a v, faça 
 se vértice w não estiver marcado, então 
 Chame recursivamente DFS(G,w) 
 fim se 
fim para 
fim função 
 
Entre os diversos tipos de algoritmos utilizados para atravessar grafos, esse 
código implementa o algoritmo: 
A- Busca em profundidade ou depth first search. 
B- Busca em largura ou breadth first search. 
C- Busca melhor-primeiro ou best first search. 
D- Busca exaustiva ou brute force search. 
E- Busca pelo caminho mínimo (shortest path). 
 
 
Resposta: A. 
20- 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 deforma 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: 
A- As afirmativas I, II e III estão erradas. 
B- As afirmativas I, II e III estão certas. 
C- A afirmativa I está errada, e as afirmativas II e III estão certas. 
D- A afirmativa III está errada, e as afirmativas I e II estão certas. 
E- A afirmativa II está errada, e as afirmativas I e III estão certas. 
 
Resposta: B. 
21- 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): 
A- Bubble sort. 
B- Quick sort e insertion sort. 
C- Merge sort e bubble sort. 
D- Quick sort e merge sort. 
E- Insertion sort. 
 
Resposta: D. 
22- 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. 
 
A- 40 - 15 - 45 - 30 - 50. 
B- 42 - 60 - 20 - 30 - 50. 
C- 40 - 10 - 45 - 30 – 50 
D- 42 - 60 - 20 - 48 - 50. 
E- 40 - 60 - 45 - 48 – 50 
Resposta: E. 
23- (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 é: 
A- 16 
B- 14 
C- 17 
D- 15 
E- 13 
 
Resposta: B. 
 
 
 
 
 
 
 
 
 
 
 
 
 
24- (CESGRANRIO - Banco da Amazônia - Técnico Científico - Banco de 
Dados - 014) 
 
 
 
Resposta: B. 
25- Considere a função recursiva `função definida por: 
func(1) = 1 
func(n) = (n - 1) * func(n - 1) 
Quais são os valores de func(4) e func(5), respectivamente? 
A- 24 e 120 
B- 6 e 24 
C- 12 e 24 
D- 2 e 6 
E- 1 e 2 
 
Resposta: B. 
26- 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: 
A- Recursividade direta 
B- Lista linear simples 
C- Lista circular 
D- Recursividade indireta 
E- Recursividade simples 
 
 
Resposta: D. 
27- 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) 
fim sub-rotina; 
Marque a opção que mostra o valor correto exibido da variável u: 
A- 10 
B- 8 
C- 4 
D- 7 
E- 5 
 
 
Resposta: D. 
28- Ano: 2010 Banca: FCC Órgão: TRT - 20ª REGIÃO (SE) Prova: FCC - 2010 
- TRT - 20ª REGIÃO (SE) – Técnico Judiciário - Tecnologia da Informação 
Objeto que se constitui parcialmente ou é definido em termos de si 
próprio. Nesse contexto, um tipo especial de procedimento (algoritmo) 
será utilizado, algumas vezes, para a solução de alguns problemas. Esse 
procedimento é denominado: 
A- Recursividade 
B- Condicionalidade 
C- Repetição 
D- Rotatividade 
E- Interligação 
 
Resposta: A. 
29- Correlacione os algoritmos internos de ordenação de listas com suadescriçã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. 
( ) É 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, é: 
A- I, II, III, IV, V 
B- V, II, III, IV, I 
C- I, III, II, IV, V 
D- I, IV, V, III, II 
E- V, IV, II, III, I 
Resposta: B. 
30- Árvore de pesquisa é uma estrutura de dados eficiente para armazenar 
informação, sendo particularmente adequada quando existe a 
necessidade de considerar todos ou alguma combinação de registros. 
Assinale uma combinação correta desses registros. 
A- Utilização de estruturas de dados como lista, pilha e fila. 
B- As operações de inserir, retirar e pesquisar são definidas. 
C- Acesso direto e sequencial eficientes, facilidade de inserção e retirada de 
registro, boa taxa de utilização de memória, utilização de memória primária 
e secundária. 
D- Utilização de algoritmos de ordenação eficientes. 
E- Não é necessário indexar os registros. 
 
 
Resposta: C. 
31- (CESGRANRIO - Transpetro - Analista de Sistemas Júnior - Processos 
de Negócio - 2018). Uma das medidas de qualidade do código de um 
software é a Complexidade, que pode ser medida por meio da 
complexidade ciclomática. Considere um grafo de fluxo que possui 5 nós 
e 12 arcos. 
Qual a complexidade ciclomática desse grafo? 
A- 15 
B- 9 
C- 17 
D- 19 
E- 11 
 
Resposta: B. V(G) = E - N + 2. V(G) = 12 - 5 + 2 = 9 
32- Árvore AVL é uma árvore de busca auto balanceada. Isso significa que: 
A- cada nó da árvore possui até três descendentes. 
B- as alturas das duas sub árvores a partir de cada nó diferem no máximo em 
uma unidade. 
C- as alturas das duas sub árvores a partir de cada nó diferem no máximo em 
duas unidades. 
D- as alturas das duas sub árvores a partir de cada nó são exatamente iguais. 
E- pode possuir até duas raízes. 
 
Resposta: D. 
33- Sobre o conceito de Algoritmos Recursivos, analise as afirmações 
abaixo e, a seguir, assinale a alternativa correta. 
I. Um programa tem um número limitado de procedimentos 
recursivos. 
II. Recursividade é utilizada exclusivamente quando não se sabe 
solucionar um problema de maneira imediata, então é realizada a 
divisão em problemas menores para alcançar o resultado 
desejado. 
III. Todos os problemas computacionais resolvidos de maneira 
iterativa gastam mais memória que se resolvidos de forma 
recursiva. 
 
A- Somente a afirmação II está correta 
B- As afirmações I e II estão corretas 
C- Somente a afirmação III está correta 
D- Somente a afirmação I está correta 
E- Nenhuma das afirmações está correta 
 
Resposta: E. 
34- Em relação aos algoritmos de ordenação, avalie se as afirmativas a 
seguir são verdadeiras (V) ou falsas (F): 
I. O algoritmo quick sort é muito eficiente quando há uma quantidade 
pequena de elementos a ordenar. 
II. O algoritmo shell sort utiliza intensamente a inserção direta. 
III. No algoritmo bubble sort, o número de variáveis envolvidas é 
pequeno. 
As afirmativas I, II e III são, respectivamente: 
A- F, V e V 
B- V, F e V 
C- V, F e F 
D- F, F e V 
E- V, V e V 
Resposta: A. 
35- (CS-UFG - Fundação Unirg - Analista de Sistemas - 2017)Seja S o grafo 
de fluxo de controle de um programa P. Se o teste que aplica um conjunto 
de dados de teste satisfaz o critério todos os ramos de S, então pode-se 
concluir que esse conjunto também irá satisfazer o critério: 
A- Todos os comandos de P. 
B- Todos os predicados de P. 
C- Todos os caminhos de P. 
D- Todas as classes de P. 
E- Todas as respostas de P. 
 
Resposta: A. 
36- Leia as afirmativas a seguir considerando que f(n) e g(n) são funções 
positivas. 
I- Se g(n) é O(f(n)), um algoritmo de função de complexidade de 
tempo f(n) possui Ordem de complexidade g(n). 
II- Se g(n) é O(f(n)), f(n) é um limite superior para g(n). 
III- Se a função g(n) = 7.log(n) +6 , então a função g(n) é O(log(n)). 
IV- Se g(n) = n2 e f(n) = (n+1)2 temos que g(n) é O(f(n)) e f(n) é O(g(n)). 
V- Se g(n) = 2n+1 e f(n) = 2n temos que g(n) = O(f(n)). 
Assinale a alternativa que apresenta somente as afirmativas: 
A- II, III, V. 
B- I, II, IV, V. 
C- II, III, IV, V. 
D- II, III, IV. 
E- I, III, IV, V. 
Resposta: C. 
37- O algoritmo bubble sort é popular, mesmo que ineficiente. Usando esse 
algoritmo para ordenar um vetor em ordem crescente, contendo os 
números [ 5, 4, 1, 3, 2 ], serão feitas: 
A- 10 Comparações e 9 Trocas. 
B- 10 Comparações e 10 Trocas 
C- 16 Comparações e 9 Trocas 
D- 6 Comparações e 10 Trocas 
E- 10 Comparações e 8 Trocas 
 
Resposta: E. 
38- Ano: 2014 Banca: FUNCAB Órgão: MDA Prova: FUNCAB - 2014 - MDA - 
Analista de Negócios. Observe o algoritmo a seguir, que utiliza o conceito 
de função recursiva. 
algoritmo "MDA" 
var 
X, W, N : inteiro 
funcao FF(Y:inteiro):inteiro 
inicio 
N <- N + 1| 
se Y < 2 entao 
 retorne 1 
senao 
retorne Y * FF(Y-1) 
 fimse 
fimfuncao 
inicio 
X <-5 
 N <-0 
W <- FF(X) 
W <-W-50 
escreval(W,N) 
fimalgoritmo 
Após a execução, o algoritmo, os valores de W e N serão, respectivamente: 
A- 70 e 0 
B- 120 e 5 
C- 70 e 1 
D- 70 e 5 
E- 120 e 1 
 
Resposta: D. 
39- Em relação aos algoritmos de ordenação, avalie se as afirmativas a 
seguir são verdadeiras (V) ou falsas (F): 
I. O algoritmo quick sort é muito eficiente quando há uma quantidade 
pequena de elementos a ordenar. 
II. O algoritmo shell sort utiliza intensamente a inserção direta. 
III. No algoritmo bubble sort, o número de variáveis envolvidas é 
pequeno. 
 
As afirmativas I, II e III são, respectivamente: 
 
A- V, F e V 
B- V, F e F 
C- F, V e V 
D- F, F e V 
E- V, V e V 
 
Resposta: C. 
40- Acerca das estruturas de dados Árvores, analise as afirmativas a seguir. 
I. A árvore AVL é uma árvore binária com uma condição de balanço, 
porém não completamente balanceada. 
II. Árvores admitem tratamento computacional eficiente quando 
comparadas às estruturas mais genéricas como os grafos. 
III. Em uma Árvore Binária de Busca, todas as chaves da subárvore 
esquerda são maiores que a chave da raiz. 
Assinale: 
A- Se todas as afirmativas estiverem corretas. 
B- se somente as afirmativas II e III estiverem corretas. 
C- se somente a afirmativa I estiver correta. 
D- se somente as afirmativas I e III estiverem corretas. 
E- se somente as afirmativasI e II estiverem corretas. 
 
Resposta: E. 
41- 
 
 
 
Resposta: B. 
42- 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 deum número neste elemento é: 
A- O(N) 
B- O(1) 
C- O(log N) 
D- O(Nlog N) 
E- O(N ) 
 
Resposta: A. 
43- Registros são exemplos de tipos de dados heterogêneos. Assim, sobre 
tipos de dados elementares e estruturados, é correto afirmar que os 
elementos de um registro são de tamanhos potencialmente diferentes e 
residem em posições de memória: 
A- flexíveis 
B- aleatórias 
C- procedimentais 
D- espalhadas 
E- adjacentes 
 
Resposta: E. 
44- Considere os algoritmos a seguir e as suas correspondentes 
complexidades indicadas: 
 
 
A- I, II e IV. 
B- II, III, IV e V. 
C- II, III e V. 
D- I, III, IV e V. 
E- I, II e III. 
 
Resposta: E. 
45- 
 
 
 
Resposta: E. 
46- 
 
 
Resposta: E. 
 
47- 
 
 
Resposta: B. 
48- Ano: 2020 Banca: FAPEC Órgão: UFMS Prova: FAPEC - 2020 - UFMS - 
Técnico de Tecnologia da Informação. 
Considere a seguinte função recursiva: funcao recursiva(x : inteiro): 
inteiro início 
se x = 1 então 
retorne -x 
 senão 
retorne -5 * recursiva(x - 1) + x 
fim se 
fim funcao 
Qual é o valor retornado pela função se ela for chamada com x = 4? 
 
A- 143 
B- 56 
C- 143 
D- 164 
E- 56 
 
Resposta: D.