Caderno de Erros Algoritmo e Estrutura de Dados #

Prévia do material em texto

ALGORITMO E ESTRUTURA DE DADOS
Dado o fluxograma: 
Para que a Rotina Principal no fluxograma acima seja executada cinco vezes deve-se: 
I. carregar um como valor inicial, incrementar de um o contador e testar o contador com valor terminal maior que cinco. 
II. carregar seis como valor inicial, decrementar de um o contador e testar o contador com valor terminai menor que um. 
III. carregar zero como valor inicial, incrementar de um o contador e testar o contador com valor terminal maior que cinco. 
IV. carregar cinco como valor inicial, decrementar de um o contador e testar o contador com valor terminai menor que um. 
Está correto o que consta em: 
I e IV, somente. 
A figura a seguir apresenta um fluxograma de uma função que fornece ao usuário o valor do ingresso que deverá ser cobrado para a entrada no cinema.
                     
Os parâmetros de entrada da função são sua IDADE e PROFISSÃO.  
A conversão deste  fluxograma  em  pseudolinguagem  de  programação é
SE (IDADE < 18) OU (PROFISSÃO = ESTUDANTE) OU 
     (PROFISSÃO = PROFESSOR) ENTÃO  
                IMPRIMA (‘VALOR DO INGRESSO IGUAL A 10 REAIS’) 
    SENÃO  
                IMPRIMA (‘VALOR DO INGRESSO IGUAL A 20 REAIS’) 
    FIM SE 
Fluxograma é uma ferramenta para a modelagem de sistemas na qual se representa unicamente uma visão estruturada das funções do sistema, ou seja, o fluxo dos dados.
Errado
Em lógica estruturada, o símbolo de chamada de um procedimento é
                            
Dado o fluxograma acima, se N receber o valor 4 e X o valor 3, a saída na tela será:
93
Considere o seguinte fluxograma para responder às questões de números 48 e 49. Assuma que entradas a, b e c lidas sejam, respectivamente, 12, 5 e 9.
Considerando ainda o fluxograma apresentado, assinale a alternativa que apresenta quantas vezes o teste marcado com (*) na figura é 
Uma das regras básicas para definir novos objetos ou conceitos é que a definição deve conter somente termos que tenham já sido definidos ou que sejam óbvios. Assim, um objeto definido em termos dele próprio é uma violação sérias dessa regra – um círculo vicioso. Por outro lado, existem muitos conceitos de programação que se auto definem. Restrições formais impostas às definições, tais como existência e unicidade, são satisfeitas e não deve ocorrer violação das regras. Tais definições são usadas primordialmente para se definir conjuntos infinitos e são chamadas de: 
Definições recursivas. 
Na lógica matemática e em ciência da computação, uma definição recursiva (oudefinição indutiva) é usada para definir um objeto em termos de si próprio (Aczel 1977). Esta definição é valida porque, para todo n, a recursão sempre vai alcançar o caso base de 0.
As estruturas de controle de fluxo WHILE e DO...WHILE possuem a mesma finalidade e seus respectivos blocos de comandos são executados pelo menos uma vez em cada uma delas.
Parte superior do formulário
Errado
Considere que na Defensoria há uma lista ordenada com o nome de 1000 cidadãos amazonenses. Utilizando o método de pesquisa binária para localizar o nome de um destes cidadãos, serão necessárias, no máximo, 
Parte superior do formulário
10 comparações. 
2^9 = 512
2^10 = 1024
sabemos que o número está na casa do ^9.
 
A fórmula é log n + 1, ou seja, log1000 + 1 --> 9 + 1 = 10
O algoritmo de busca e de ordenação que encontra o menor elemento e o troca com a primeira posição, depois o segundo menor com a segunda posição, e assim sucessivamente (n-1 vezes), usa o método de 
Parte superior do formulário
seleção.
Inserção divide o vetor em 2 (classificado e não classificado).
MergeSort divide para conquistar sucessivamente o vetor, e vai ordenando juntando os vetores.
BubbleSort compara posições adjacentes e vai ordenando o vetor.
Segundo a análise do trecho de algoritmo a seguir, conclui-se que se trata de um algoritmo de ordenação do tipo:
                                 
Insertion sort.
           
A estrutura lógica presente no diagrama apresentado é do tipo
SE ENTÃO SENÃO.
Considerando os conceitos de estruturas de dados, analise as afirmativas abaixo, dê valores Verdadeiro (V) ou Falso (F).
( ) as filas são utilizadas para controlar o acesso de arquivos que concorrem a uma única impressora.
( ) a pilha é uma estrutura de dados baseada no princípio LIFO, na qual os dados que foram inseridos primeiros na pilha serão os últimos a serem removidos.
( ) os nós de uma árvore binária possuem graus zero, um ou dois.
Assinale a alternativa que apresenta a sequência correta de cima para baixo.
V - V - V
Um conjunto ordenado de itens a partir do qual podem ser eliminados itens em uma extremidade e no qual podem ser inseridos itens na outra extremidade é denominado de 
Parte superior do formulário
fila. 
Assinale, das alternativas abaixo, a única que identifica corretamente o comando do pseudocódigo de ordenação Bubble Sortabaixo, que foi extraído na linha pontilhada:
trocar( A[ i ], A[ i + 1 ] )
Na coluna I estão dispostos alguns conceitos relacionados à estrutura de dados. Estabeleça a correta correspondência com suas definições, conforme apresentado na coluna II.
Coluna I
1 Fila
2 Pilha
3 Lista Encadeada
4 Árvore
5 Vetor
Coluna II
( ) coleção de itens de dados.
( ) primeiro a entrar é o primeiro a sair.
( ) bidimensional.
( ) último a entrar é o primeiro a sair.
( ) estrutura de dados estática. 
A sequência correta, de cima para baixo, é: 
3, 1, 4, 2 e 5. 
Qual é o método de ordenação mais eficiente entre os listados a seguir?
Parte superior do formulário
Estruturas de pilhas, filas e árvores binárias são amplamente utilizadas para a construção de algoritmos e programas de computador. Acerca dessas estruturas, julgue o item subsecutivo.
Em uma lista linear, a inserção de um elemento é feita em uma extremidade e a eliminação, na outra. Esse tipo de estrutura também é conhecida como FIFO (first in, first out)
Certo
A Complexidade Computacional é a área da Ciência da Computação que se ocupa, entre outros, do estudo e análise do custo de tempo de execução e espaço ocupado pelos algoritmos. Sobre Complexidade Computacional, marque V para as afirmações Verdadeiras, ou F para as Falsas.
( ) A função de complexidade de tempo de algoritmo indica o tempo necessário para executar o programa que implementa o algoritmo em função do tamanho da entrada.
( ) Se f é uma função de complexidade baseada na análise de pior caso, o custo de aplicar o algoritmo nunca é maior do que f(n).
( ) Na análise do caso médio toma-se a média aritmética do pior caso com o melhor caso.
A sequência correta, de cima para baixo, é: 
Parte superior do formulário
F, V, F. 
Sobre os comandos utilizados na elaboração de programas, considere as afirmativas a seguir.
I. Um comando de seleção permite a escolha de um grupo de comandos a ser executado quando determinada condição é satisfeita ou não.
II. O comando de seleção deve ter uma expressão de condição na qual, em algum momento da execução do programa, ela deve se tornar falso, evitando o loop infinito.
III. Um comando de repetição é utilizado quando é necessário executar um bloco de comandos várias vezes.
Conforme a cartilha de segurança da internet, estão CORRETAS as afirmativas:
I e III, apenas.
Estruturas de dados básicas, como as pilhas e filas, são usadas em uma gama variada de aplicações. As filas, por exemplo, suportam alguns métodos essenciais, como o
Parte superior do formulário
dequeue(), que remove e retorna o elemento do começo da fila; um erro ocorrerá se a fila estiver vazia.
A estrutura de dados 'fila' trabalha como se fosse uma fila na vida real: os primeiros a entrar, serão os primeiros a sair. O último a entrar é o último a sair. Há duas extremidades: início/cabeça da fila; fim/cauda da fila. Sempre que inserir um elemento, ele irá para o final da fila. Sempre que retirar um elemento, será da cabeça da fila.
Aoperação 'deque' retira um elemento da fila.
A operação 'enque' insere um elemento da fila.
Considere um sistema que enfileira tarefas a serem executadas com variadas prioridades. Ao comparar duas formas comuns de implementação de listas de prioridade, uma usando lista ordenada e outra usando heap binária, conclui-se que:
Parte superior do formulário
heap binária é mais indicada, pois apresenta complexidade O(log n) para inserção e remoção e O(1) para consulta;
Falou em lista de prioridade, falou em heap
Assinale EQ ou RP no QUADRO I, se a caraterística descrita é VERDADEIRA para as estruturas de controle indicadas no QUADRO II. 
                         QUADRO I – Característica
 (__) O teste de controle é realizado no fim da estrutura de controle.
 (__) O teste de controle é realizado no início da estrutura de controle.
(__) A condição de saída do loop ocorre quando o teste é FALSO.
(__) A condição de saída do loop ocorre quando o teste é VERDADEIRO.
(__) Se o resultado do teste for FALSO, a execução do programa permanece no loop.
(__) Se o resultado for VERDADEIRO, a execução do programa permanece no loop.
                       QUADRO II - Estrutura de Controle
(EQ) enquanto... faca... fimenquanto
(RP) repita... ate... fimrepita
Tendo por foco o QUADRO I, de cima para baixo a sequência correta é:
RP – EQ – EQ – RP – RP – EQ
Considerando que os ponteiros inicio e fim foram inicializados com NULO, é correto afirmar que a função Fila1
Parte superior do formulário
sempre faz o ponteiro fim apontar para o ponteiro inicio na inserção da 1a informação na fila encadeada.
Um programa pode ser estruturado em módulos denominados funções ou procedimentos. Considerando esse assunto, julgue o próximo item, acerca dos tipos de módulos.
Uma função recursiva pela cauda sempre possui um equivalente iterativo direto.
Certo
As estruturas de repetição são usadas para iterar comandos em laços. Com base nas estruturas de repetição, assinale a alternativa CORRETA: 
Parte superior do formulário
A diferença entre o Enquanto/Faça e o Repita/Até é que no último, os comandos serão executados ao menos uma vez. 
Em operações com datas, deseja-se determinar o número máximo de dias do mês de fevereiro, conforme a regra do ano bissexto. O ano é bissexto se divisível por 4, deixa de ser bissexto se divisível por 100, mas volta a ser bissexto se divisível por 400. Qual dos fluxogramas, a seguir, NÃO apresenta a lógica correta para tal determinação?  
Parte superior do formulário
A tabela a seguir deve ilustrar uma lista duplamente encadeada de cores, estruturada sobre os cinco elementos de um vetor. 
                             
Dado que a ordem correta das cores é Marrom-Verde-Azul-Vermelho-Amarelo, a coluna Cor, na tabela acima, deveria apresentar, de cima para baixo, os seguintes valores:
 
Azul-Vermelho-Amarelo-Verde-Marrom;
A respeito de estruturas de dados, julgue o item seguinte.
A implementação de lista por meio de apontadores permite utilizar posições não contíguas de memória, de modo a se poder inserir e retirar elementos sem que haja necessidade de deslocar os itens seguintes da lista.
Certo
A descrição de uma determinada estrutura de dados deverá ser implementada. Na descrição apresentada, cada item dessa estrutura contém a informação necessária para alcançar o próximo item. Esse tipo de implementação permite utilizar posições não contíguas de memória, sendo possível inserir e retirar elementos, sem haver a necessidade de deslocar itens seguintes dessa estrutura. Trata-se da estrutura:
Listas com estruturas autorreferenciadas.
Em um tipo estruturado arranjo, os itens da lista são armazenados em posições contíguas de memória. 
Em uma estrutura autorreferenciada cada item da lista contém a informação que é necessária para alcançar o próximo item. Ela utiliza posições não contíguas na memória.
Considerando a estrutura de dados do tipo Pilha, assinale a alternativa correta a respeito de operações realizadas sobre esse tipo de estrutura.
Parte superior do formulário
Um elemento a ser removido é o que está há menos tempo na estrutura de dados.
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:
70 e 5.
Considere o fluxograma abaixo. 
                   
Qual a faixa de valores da variável I que será impressa? 
1 a 6. 
Tem-se uma tabela denominada TAB, com 6 posições preenchidas. 
            
Após executar o fluxograma acima, o que vai acontecer com os elementos da tabela?  
O valor lido será colocado na primeira posição, após deslocar os demais elementos para a posição seguinte a que se encontram, sendo descartado o último elemento.
Um sistema de controle distribui os processos para os juízes de um tribunal utilizando critérios de prioridade associados a cada processo, de modo que novos processos podem ser analisados pelos juízes enquanto outros aguardam análise. 
Considerando essas informações, julgue os itens a seguir, acerca dos tipos básicos de estruturas de dados e de operações sobre estruturas de dados.
Caso a implementação seja realizada por meio de max-heap, a operação de remoção de processos de maior prioridade levará um tempo de ordem O(log n).
Certo
Dado o fluxograma: 
Para que a Rotina Principal no fluxograma acima seja executada cinco vezes deve-se: 
I. carregar um como valor inicial, incrementar de um o contador e testar o contador com valor terminal maior que cinco. 
II. carregar seis como valor inicial, decrementar de um o contador e testar o contador com valor terminai menor que um. 
III. carregar zero como valor inicial, incrementar de um o contador e testar o contador com valor terminal maior que cinco. 
IV. carregar cinco como valor inicial, decrementar de um o contador e testar o contador com valor terminai menor que um. 
Está correto o que consta em: 
Parte superior do formulário
I e IV, somente. 
Sobre pilhas e filas, analise as afirmativas a seguir:
I. As operações de push e pop são responsáveis, respectivamente, por inserir e remover itens do início da fila;
II. A fila é um tipo de lista linear conhecida como LIFO (Last In First Out);
III. O método de acesso getTop é responsável por retornar o elemento do topo da pilha;
IV. A pilha é um tipo de dado abstrato em que a inserção de um item sempre se dá em seu topo;
V. Pilhas e filas são tipos abstratos de dados que se distinguem pela forma como se dão a inserção e remoção de itens em suas estruturas.
Estão(está) CORRETA(S) somente as afirmativas 
III, IV e V. 
Seja Lo uma lista ordenada e Lno uma lista não ordenada, ambas com 100 elementos. Os números de comparações, no pior caso, quando aplicando uma busca binária em Lo e uma busca sequencial em Lno são, respectivamente,
Parte superior do formulário
7 e 100.
Lo (ordenada) 
 
Comparações:
1- 100 / 2 = 50
2- 50 / 2 = 25
3- 25 / 2 = 13 (não dividimos em números quebrados)
4- 13 / 2 = 7
5- 7 / 2 = 4
6- 4 / 2 = 2
7- 2 / 2 = 1
 
Lo: 7 comparações
 
Lno (não ordenada): O pior caso será percorrer todos os elementos e, ou o elemento desejado estar na última posição, ou não ser encontrado. Ou seja:
 
Lno: 100 comparações
Considere o seguinte algoritmo, expresso na forma de uma pseudolinguagem:
A complexidade desse algoritmo, no tocante ao seu tempo de execução é:
O(n2 )
A figura a seguir apresenta um fluxograma de uma função que fornece ao usuário o valor do ingresso que deverá ser cobrado para a entrada no cinema.
          
Os parâmetros de entrada da função são sua IDADE e PROFISSÃO.A  conversão  deste  fluxograma  em  pseudolinguagem  de  programação é
Parte superior do formulário
SE (IDADE < 18) OU (PROFISSÃO = ESTUDANTE) OU 
     (PROFISSÃO = PROFESSOR) ENTÃO  
                IMPRIMA (‘VALOR DO INGRESSO IGUAL A 10 REAIS’) 
    SENÃO  
                IMPRIMA (‘VALOR DO INGRESSO IGUAL A 20 REAIS’) 
    FIM SE 
Seja a função recursiva f definida como 
                                   f(a,b) 
                                       se b = 0 ehtão 
                                             retorna a 
                                       senão 
                                               retorna f(b, a MOD b)
onde x MOD y é o resto da divisão de x por y. O valor de f (30, 21)é
A função é recursiva pois fica chamando a si mesma, então devemos repeti - la até o b zerar e cair na primeira condição ,critério de parada, retornando o valor de a.
f (30, 21) é:
retorna f(21, 9(30 mod 21 = 1 resto 9))
f(21, 9)
retorna f(9, 3(21 mod 9 = 2 resto 3))
f(9, 3)
retorna f(3, 0(9 mod 3 = 3 resto 0))
f(3, 0)
Se b = 0 então retorna 3(valor de a)
Resposta 3.
3
Seja a função recursiva f definida como 
              f(a,b) 
                   se b = 0 então 
                         retorna a 
                   senão 
                          retorna f(b, a MOD b)
onde x MOD y é o resto da divisão de x por y. O valor de f (30, 21) é
3
Considerando as estruturas de dados pilhas e filas, é correto afirmar que:
Parte superior do formulário
a pilha (stack) é usada pelo Sistema Operacional para armazenar informações sobre as subrotinas ativas num programa de computador. Quem invoca a subrotina empilha o endereço de retorno; quando termina sua execução, a subrotina invocada desempilha o endereço de retorno.
A implementação de uma fila sequencial precisa de duas variáveis, uma indicando o início da fila (PtrIni) e outra indicando o seu fim (PtrFim). Por convenção, se a fila está vazia, PtrIni = 1 (IndIniFila) e PtrFim = 0 (IndIniFila -1). As inserções são efetuadas sempre no final da fila, ou seja, através de PtrFim. Já as retiradas só podem ser efetuadas no início da fila, através de PtrIni. 
Com base nas informações fornecidas (a variável Info indica o elemento que será inserido na Fila), o algoritmo a seguir é uma representação simbólica da inclusão de uma informação em uma fila sequencial. 
Para completar corretamente o algoritmo, as lacunas I e II são preenchidas correta e, respectivamente, por :
Parte superior do formulário
Overflow - PtrFim ← PtrFim + 1 
Antes de responder precisamos entender os conceitos de Underflow e Overflow em filas.
Diz-se que ocorre uma situação de overflow na fila quando um novo nodo deve ser inserido, mas não há mais nodos disponíveis na mesma. Ocorre uma situação de underflow na fila quando um nodo deve ser retirado da fila, mas a fila está vazia. 
No enunciado diz que o algoritmo a seguir é uma representação simbólica da INCLUSÃO, então vamos trabalhar somente com a variável PtrFim e problemas com Overflow. Quando verificamos que PtrFim chegou ao tamanho IndFimFila o próximo elemento irá causar um Overflow. Seguindo os conceitos da fila, para inserir um novo elemento basta colocar ele no final então incrementamos a última posição que foi inserida PtrFim ← PtrFim + 1.
por seleção, que faz (N2 -N) /2 comparações, sendo N o número de elementos do vetor. 
O selection sort (do inglês, ordenação por seleção) é um algoritmo de ordenação baseado em se passar sempre o menor valor do vetor para a primeira posição (ou o maior dependendo da ordem requerida), depois o de segundo menor valor para a segunda posição, e assim é feito sucessivamente com os (n-1) elementos restantes, até os últimos dois elementos."
Percebe-se que pelo código, que a estrutura de repetição está procurando pelo menor valor e ao final insere na posição em questão.
Vetor desordenado [4 5 1 3 8 7]
1 4 5 3 8 7 
1 3 4 5 8 7
1 3 4 5 8 7
1 3 4 5 8 7
1 3 4 5 7 8 [ Vetor ordenado]
Tanto o algoritmo de ordenação por seleção quanto o de ordenação por inserção tem complexidade assintótica de N2.
Na expressão (N2 -N) /2  tirando a parte menos significativa fica N2
Na expressão N2 log2 (N)  tirando a parte menos significativa fica N log N
Considere o seguinte algoritmo de ordenação de elementos em uma lista: 
1. Escolha um elemento que será chamado o pivot da lista. 
2. Reordene a lista de tal forma que os elementos menores que o pivot venham antes dele e os elementos maiores ou iguais ao pivot venham depois dele. Essa operação é chamada de partição, e cria duas sublistas: 
a. a de menores que o pivot e 
b. a de maiores ou iguais ao pivot. 
3. Aplique recursivamente os passos 1 e 2 às sublistas de menores e maiores que o pivot.
O algoritmo acima corresponde ao
Quicksort, e faz, em média, O(n log n) comparações para ordenar n itens.
Considere o fluxograma a seguir. 
            
A expressão lógica equivalente ao fluxograma que executa a ação A é 
(X < 3) OR (Y = 7) OR (Z > 0) AND (X NOT < 3) OR
(Y NOT = 7) OR (Z > 0) 
Fluxograma é uma ferramenta para a modelagem de sistemas na qual se representa unicamente uma visão estruturada das funções do sistema, ou seja, o fluxo dos dados.
Errado
Analise as afirmativas: 
I. Considere o método de ordenação que implementa o seguinte processo: uma coleção desordenada de n elementos é dividida em duas metades e cada metade é utilizada como argumento para a reaplicação recursiva da subrotina. Os resultados das duas reaplicações são, então, combinados pela intercalação dos elementos de ambas, resultando em uma coleção ordenada. A complexidade do caso médio desse algoritmo é expressa por O(n log2 n). 
II. Existem aplicações para listas lineares nas quais inserções, retiradas e acessos a itens ocorrem sempre em um dos extremos da lista. Nestes casos a estrutura adequada para resolvê-los é a pilha ou stack. 
III. No método Quicksort, o pivô é responsável pelo número de partições em que o vetor é dividido. Como o pivô não pode ser um elemento que esteja repetido no vetor, o Quicksort não funciona quando há elementos repetidos.
Está correto o que se afirma em 
Parte superior do formulário
I e II, apenas.
O conceito de fila circular pode ser implementado, utilizando um vetor. Supondo ser desejado implementar uma fila de dados com um vetor de N posições, poderemos ter no máximo N elementos na fila. Para controle é criado duas variáveis – INICIO e FIM – que armazenam os índices do vetor e marcam o início e fim da fila, respectivamente. 
Considerando que a operação "a%b", retorna o resto da divisão de a por b (operação de Módulo da divisão), a expressão correta para calcular o novo início (INICIO) da fila, após a retirada de um elemento da fila, é 
Parte superior do formulário
INICIO = (INICIO+1)%N
Em lógica estruturada, o símbolo de chamada de um procedimento é
Parte superior do formulário
O gráfico abaixo mostra a relação de dominação assintótica entre funções de complexidade de algoritmos. Os valores de tempo e tamanho do problema são apenas referenciais. Considere apenas os seus valores crescentes. 
     
Com base no gráfico, é correto afirmar que 
f3 e f4, embora sejam exponenciais, apresentam desempenho superior a 2n. 
Um vetor ordenado de inteiros com 2N+1 elementos, com N=0, será usado para criar uma árvore binária de busca da seguinte maneira: o elemento central, de índice N, será usado para criar a raiz; depois, serão inseridos na árvore todos os elementos na seguinte ordem de índices: N-1, N+1, N-2, N+2, ..., 1, 2N-1, 0, 2N. 
Assumindo que a altura de uma folha é zero, qual será a altura resultante dessa árvore?
Parte superior do formulário
N
Dois vetores ordenados, contendo, cada um deles, N números inteiros, precisam ser unidos em outro vetor maior, que conterá os 2N números, que também serão armazenados de forma ordenada. A complexidade de tempo de melhor caso desseprocesso será, então,
Parte superior do formulário
O(N), pois se precisa fazer uma cópia de cada um dos elementos originais, o que implica uma varredura completa de cada vetor de origem.
                             
Dado o fluxograma acima, se N receber o valor 4 e X o valor 3, a saída na tela será:
Parte superior do formulário
93
Uma fila é um tipo de lista linear em que
Parte superior do formulário
as inserções são realizadas em um extremo e as remoções no outro extremo.
Uma lista ordenada de N números é inserida em uma pilha e depois retirada, sendo que, a cada POP, o elemento retirado é inserido em uma árvore de busca binária. Após a completa inserção de todos os elementos nesta árvore, são feitas buscas de números na mesma. O tempo médio de busca de um número nesta árvore é
O(N)
Sobre a estrutura de dados em filas, analise as assertivas e, em seguida, assinale a alternativa que apresenta a(s) correta(s). 
I. Uma fila é uma lista linear em que todas as inserções são realizadas em um extremo da lista, e todas as retiradas no outro extremo. Normalmente, os acessos são realizados no mesmo extremo da lista em que são feitas as retiradas. 
II. Em uma implementação por meio de arranjo (vetores), os itens são armazenados em posições contíguas de memória. Por causa das características da fila, o enfileiramento (inserção na fila) faz a parte de trás da fila expandir-se e o desenfileiramento (remoção) faz a parte da frente da fila contrair-se. Consequentemente, a fila tende a caminhar pela memória do computador, ocupando espaço na parte de trás e descartando espaço na frente da fila. Com poucas inserções e retiradas de itens, a fila vai ao encontro do limite do espaço da memória alocado para ela. 
III. Em uma fila implementada por meio de apontadores, a implementação se dá por meio de células. Cada célula contém um item da fila e um apontador para a outra célula. Também é necessário utilizar apontadores para a frente da fila e para a parte de trás da fila. 
I, II e III. 
Observe o algoritmo em JAVA. 
A complexidade de tempo desse algoritmo, no pior caso, em que n corresponde ao número de elementos do vetor v, é
Parte superior do formulário
O (n2).
Durante a análise de um problema de programação, uma analista montou a seguinte fórmula recursiva para descrever a solução do problema: 
A complexidade da solução encontrada é:
Parte superior do formulário
O(n2).
Parte superior do formulário
Complexidade de Algoritmos
Quando dois elementos estão fora de ordem, há uma inversão, e esses dois elementos são trocados de posição, ficando em ordem correta. Assim, o primeiro elemento é comparado com o segundo. Se uma inversão for encontrada, a troca é feita. Em seguida, independentemente de se houve ou não troca após a primeira comparação, o segundo elemento é comparado com o terceiro, e, caso uma inversão seja encontrada, a troca é feita. O processo continua até que o penúltimo elemento seja comparado com o último. Com esse processo, garante-se que o elemento de maior valor do vetor seja levado para a última posição. A ordenação continua com o posicionamento do segundo maior elemento, do terceiro etc., até que todo o vetor esteja ordenado.
 CELES, W.; CERQUEIRA, R.; RANGEL, J. L. Introdução a Estruturas de Dados. Rio de Janeiro: Elsevier, 2004, com adaptações.
Em relação ao algoritmo descrito, é correto afirmar que a respectiva ordem de complexidade, no pior caso, é
O(n²)
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(n2). 
O(n4log(n)) 
complementando:
para i=0 até n --> O(n)
enquanto j --> O(n)
para k=0 até j --> O(Log n) //Aqui está o pulo do gato. A linha j = j*2 faz com que o laço do enquanto "corra" em velocidade logaritmica/rapida (inverso do exponencial/lenta). Se não houvesse este incremento, aí sim seria de complexidade O(n) como os outros.
execute f --> O(n²) //Ditado pelo enunciado da questão.
De fato: O(n) * O(n) * O(log n) * O(n²) = O(n⁴ log(n))
Considere o algoritmo abaixo.
static int fibonacci(int n) { 
if (n <= 1) { 
return n; 
} 
return fibonacci(n - 2) + fibonacci(n - 1);  
}
A complexidade deste algoritmo, na notação Big O, é  
O(2ⁿ).
Considerando a área de complexidade algoritmos, assinale a opção que apresenta a classe assintótica, na notação O, com o menor tempo de resposta dada a mesma entrada de dados n.
O(log(n))
Os programas 1 e 2 utilizam o mesmo método de pesquisa em um vetor. Nesse método, se for considerado um vetor de n elementos, o consumo de tempo é da ordem de complexidade:
O (log2n). 
A complexidade do algoritmo de busca binária é da ordem de Θ(log2 n), em que n é o tamanho do vetor de busca. 
Para projetar algoritmos eficientes um desenvolvedor deve estar preocupado com a complexidade deste algoritmo, desde sua concepção.
Considere a seguinte função T(n) que mede os recursos (ex. tempo de execução) que um algoritmo necessita no pior caso para processar uma entrada qualquer de tamanho n:
T(n) = O(log(n))
Sabendo que O(log(n)) é a ordem da complexidade de tempo do algoritmo seguindo a notação "big O", é correto afirmar que este algoritmo tem complexidade de ordem: 
sublinear;
O trecho de código escrito em PHP (versão 5.4.4) apresentado a seguir implementa o algoritmo de busca em árvore binária. 
Considere que o método procura() seja aplicado ao nó raiz da árvore binária de busca e que esta seja balanceada. 
Assinale a opção que indica a complexidade desse algoritmo.
O(log n)
No pior caso, uma busca sem sucesso em uma árvore binária perfeita deve visitar uma quantidade de nós internos da ordem de 
O(log n)
Constante - O (1): É único caso onde as instruções dos algoritmos são executadas num tamanho fixo de vezes. Ex: Algoritmo que identifica se um número é par ou ímpar;
Logaritmo - O(log n) : Ocorre tipicamente em algoritmos que dividem problemas em problemas menores. Ex: Algoritmo de busca binária, buscar um elemento em um vetor ordenado;
Linear - O (n): Uma operação básica é executada em cada elemento de entrada do algoritmo. Ex: Busca sequêncial;
O(n log n): Dividem problemas em problemas menores, porém juntando posteriormente a solução dos problemas menores. Ex: Merge Sort;
Quadrática - O(n²): Os itens são processados aos pares, 2 laços aninhados. Ex: Somatório de duas matrizes (2 laços aninhados);
Cúbica - O(n³): Os itens são processados três a três, com 3 laços aninhados. Ex: Multiplicação de matrizes (3 laços aninhados);
Exponencial - O a de n: Algoritmos muitos custosos, possuem pouca aplicação prática. Ex: Algoritmos de força bruta que testam todas as possibilidades;
f(n) = O(1) – Complexidade constante
f(n) = O(log n) – Complexidade sub-linear ou logarítmica
f(n) = O(n) – Complexidade linear
f(n) = O(n log n) – Sub-divisão de problema (Exe.: MergeSort e QuikSort)
f(n) = O(n^2) – Complexidade polinomial
f(n) = O(2^n) – Complexidade exponencial
 f(n) = O(n!) – Complexidade fatorial
Sobre a análise de algoritmos, é CORRETO afirmar que
o algoritmo MERGE-SORT é um algoritmo que recebe como entrada duas listas ordenadas e retorna a junção ordenada delas.
o BUBBLE-SORT e o algoritmo de ordenação por inserção fazem, em média, o mesmo número de comparações.
o algoritmo BUBBLE-SORT é um exemplo de algoritmo de ordenação que utiliza a técnica dividir para conquistar.
tanto o algoritmo QUICKSORT quanto o de ordenação por inserção tem complexidade O(n × log n).
o desempenho na execução do algoritmo QUICK-SORT independe da escolha do pivô.
O(n2 )
A complexidade de execução do algoritmo heapsort, no pior caso é: 
O(n log n).
Considerando-se a análise assintótica (Notação Big O), qual é a complexidade do caso médio do algoritmo de ordenação chamado de Ordenação por Inserção?
O(n²)
Ordenação deAlgoritmos
Um programador construiu uma função para ordenar vetores de inteiros por meio do algoritmo de ordenação por inserção (insertion sort). A versão iterativa desse algoritmo possui dois loops aninhados. Suponha que esse programador tenha inserido, imediatamente antes do incremento da variável de controle do loop mais externo, uma chamada de uma função para percorrer e exibir o conteúdo do vetor que está sendo ordenado. O trecho de código a seguir ilustra como essa chamada é feita.
A Figura abaixo exibe o vetor que foi passado como parâmetro em uma chamada da função de ordenação.
O que será exibido no console quando o valor da variável i for igual a 3? 
1 12 35 78 17 4 43 11 17 1 
Divide o vetor em 2 segmentos: Classificado e Não classificado.
Na 1ª iteração, o vetor CLASSIFICADO possui somente 1 elemento(78 no caso da questão).
Compara o segundo elemento com OS ELEMENTOS DO VETOR CLASSIFICADO e o INSERE na posição correta.
Compara o terceiro elemento com os elementos do vetor classificado e o INSERE na posição correta. E assim sucessivamente...
 
I=0 78 - 12 - 35 - 1 - 17 - 4 - 43 - 11 - 17 - 1
I=1 → 12 é menor que 78, ele é inserido antes:    12 - 78 - 35 - 1 - 17 - 4 - 43 - 11 - 17 - 1
I=2 → 35 é inserido entre 12 e 78:                         12 - 35 - 78 - 1 - 17 - 4 - 43 - 11 - 17 - 1
I=3 → 1 é inserido antes dos outros:                      1 - 12 - 35 - 78 - 17 - 4 - 43 - 11 - 17 - 1
Julgue o item seguinte, quanto aos conceitos da programação estruturada e da programação orientada a objetos e aos métodos de ordenação, pesquisa e hashing.
O método de ordenação conhecido como quick sort utiliza o maior elemento, o qual é sempre colocado ao final do vetor, para garantir que a ordenação seja realizada em ordem decrescente.
Errado
Trata-se do BubbleSort, que percorre o vetor do inicio ao fim, sem interrupção, mantendo o maior no final do vetor.
Parte superior do formulário
Segundo a análise do trecho de algoritmo a seguir, conclui-se que se trata de um algoritmo de ordenação do tipo:
Insertion sort.
Assinale, das alternativas abaixo, a única que identifica corretamente o comando do pseudocódigo de ordenação Bubble Sortabaixo, que foi extraído na linha pontilhada:
trocar( A[ i ], A[ i + 1 ] )
Qual é o método de ordenação mais eficiente entre os listados a seguir?
O(n2 )
A respeito de algoritmos e estruturas de dados, julgue o próximo item.
O algoritmo de ordenamento por inserção tem o menor número de trocas quando o,vetor está ordenado de forma inversa à ordem do procedimento.
Errado
ERRADA. O algoritmo de ordenamento por inserção tem o maior (complexidade O(n²)) número de trocas quando o vetor está ordenado de forma inversa à ordem do procedimento.
Sobre a análise de algoritmos, é CORRETO afirmar que
o BUBBLE-SORT e o algoritmo de ordenação por inserção fazem, em média, o mesmo número de comparações.
Considerando-se a análise assintótica (Notação Big O), qual é a complexidade do caso médio do algoritmo de ordenação chamado de Ordenação por Inserção?
O(n²)
Assinale a opção que contém somente formas de busca em uma árvore binária.
Pré-ordem, ordem-simétrica e pós-ordem.
Em relação às listas de prioridades, qual das seqüências abaixo corresponde a um HEAP?
Parte superior do formulário
190 120 156 078 056 132 140 066
Analise a árvore binária a seguir.
Em relação às árvores binárias de busca, os parâmetros, comprimento de caminho interno e externo, respectivamente I(T) e E(T), constituem um indicativo da qualidade da árvore para o problema da busca. Os valores I(T)/n e E(T)/(n+l) representam os números médios de comparação efetuadas em operações de busca, com e sem sucesso, respectivamente. 
De acordo com essa informações e em relação à arvore bináia acima, assinale a opção que apresenta a quantidade de comparações, em média, que são necessárias, respectivamente, para localizar uma chave e para concluir que uma chave não está presente.
Dados: Rj = Nós externos
       n = Número de Nós internos
2 , 71 e 3,25
Em relação aos Algoritmos de ordenação, assinale a opção correta.
Parte superior do formulário
Ao terminar a primeira interação do método de ordenação bolha (BUBBLE SORT) pode-se garantir que as trocas realizadas posicionam o maior elemento na última posição .
Analise a figura na seguir.
O Autômato Finito Determinista descrito pelo grafo de transição acima é representado por qual das seguintes expressões regulares?
(a | b) *abb
Um time de basquete está selecionando candidatos para compor sua equipe, que deverão informar os seguintes dados: altura, peso e idade. Sabe-se que somente os candidatos que se enquadram nas restrições abaixo serão selecionados.
RESTRIÇÕES: Altura: de 1.70 a 1.85 m 
                           Peso: de 48 a 60 kg 
                           Idade: de 15 a 20 anos
Assinale a opção que apresenta o pedaço do algoritmo, em pseudocódigo, que verifica corretamente se os dados fornecidos pelo candidato se enquadram nas restrições fornecidas:
se (não(altura < 1.70 ou altura > 1.85) e (peso >= 48 e
    peso <= 60) e (idade >= 15 e idade <= 20))
    Então
         Imprima("Candidata aprovada")
   Senão
        Imprima ("Candidata reprovada").
Analise a tabela a seguir.
                          Entrada             Saida
                    A         B         C          S 
                    0          0         0           0 
                    0          0         1           0 
                    0          1         0           0 
                    0          1         1           1 
                    1          0         0           0 
                    1          0         1           1 
                    1          1         0           1 
                    1          1         1           1
Em relação à tabela da verdade acima que entradas A, B e C e a saída S, qual é característica que representa a saída S?
Dado o vetor "VET" de caracteres e o trecho de algoritmo abaixo:
                                                  VET
                                       M   A   H   N   I   R   A   !
                                       1     2    3    4   5   6   7   8 
Para I de 2 até 4 passo 1 faça
                AUX <- VET [I];
                VET [I] <- VET [8-1 + 1] ;
                VET [8- I + 1] <- AUX;
Fim para
AUX <- VET [1];
VET [1] <- VET [8];
VET [8] <- AUX;
Qual é o valor do vetor "VET", após a execução do algoritmo mostrado acima?
!   A    R    I    N    H    A    M 
Analise o seguinte trecho de um algoritmo em pseudocódigo.
Se (Bl) 
Então    {  Comando1 
                  Comando2 
               } 
Senão   {  Se (B2) 
                  Então {   Comando3 
                              } 
                 Senão
                              {  Comando4 
                              } 
            } 
Comando5; 
Analisando-se o trecho acima que apresenta comandos condicionais "se" aninhados com o início e fim delimitados por { }, é correto afirmar que:
se Bl for verdadeiro o Comando5 será executado.
Considerando os percursos apresentados em Szwarcifiter e Markenzon (2010), analise a árvore binária abaixo. 
                                
Assinale a opção que apresenta o percurso nessa árvore em ordem simétrica. 
D G B A H E I C F 
Segundo Szwarcifiter e Markenzon (2010), um aspecto fundamental no estudo das árvores de busca é, naturalmente, o custo de acesso a uma chave desejada. Sendo assim, qual é o tipo de árvore cuja organização visa minimizar o número de comparações efetuadas no pior caso, para uma busca com chaves de probabilidades de ocorrência idênticas? 
Árvore completa. 
Analise  a  árvore  binária  a  seguir.
Assinale  a  opção  que  apresenta  o  percurso  dessa  árvore  binária  em  pré-ordem.
1 2 4 7 3  5 8 9 6
Segundo Szwarcifiter e Markenzon (2010), um aspecto fundamentalno estudo das árvores de busca é, naturalmente, o custo de acesso a uma chave desejada.
Sendo assim, assinale a opção que apresenta o tipo de árvore cuja organização visa a minimizar o número de comparações efetuadas no pior caso para uma busca com chaves de probabilidades de ocorrência idênticas.
Completa.
Analise  a  árvore  binária  a  seguir.
Considerando  os  percursos  apresentados  em  Szwarcifiter  e Markenzon  (2010), assinale  a  opção  que  apresenta  o  percurso da  árvore  binária  acima  em  ordem  simétrica.
Parte superior do formulário
D G B A H E I C F
Observe a execução do trecho do algoritmo a seguir. 
Sabendo-se que o algoritmo acima deveria calcular a soma dos números pares desde 100 até 200, inclusive, assinale a opção que apresenta a instrução que deverá ser substituída para que a saída correta seja fornecida. 
Linha 10  SOMA ← SOMA + PAR
Com relação às estruturas básicas de controle, assinale a opção correta,
Parte superior do formulário
É possível utilizar um comando REPITA no lugar de um comando ENQUANTO, utilizando como para o REPITA a negação da <condição> do ENQUANTO. 
Observe as matrizes MAT1 e MAT2 abaixo. 
Assinale a opção que indica corretamente o número de dimensões e elementos de cada estrutura, representada acima.
MAT1 tem 2 dimensões e 15 elementos; e 
MAT2 tem 3 dimensões e 18 elementos.