Questões de Concurso Comentadas sobre algoritmos e estrutura de dados

Paulo propôs a Rodrigo um jogo, no qual Paulo escolhe um número entre 1 e 32 que Rodrigo deve tentar adivinhar. A cada palpite de Rodrigo, Paulo dá uma pista, dizendo se o palpite é igual, maior ou menor que o número escolhido. Se for igual o jogo é encerrado.

Assinale a opção que indica o número máximo de palpites que Paulo necessitaria até anunciar o número sorteado.

Considere as seguintes operações sobre uma estrutura de dados, inicialmente vazia, organizada na forma de pilhas (ou stack),

PUSH (10)

PUSH (2)

POP ()

POP ()

PUSH (6)

Assinale a opção que apresenta a lista de elementos armazenados na estrutura, após a execução das operações acima.

Considere o pseudo-código abaixo:

F0 = 0

F1 = 1

I = 0

ARA I DE 1 ATÉ 10, FAÇA

T = F1

F1 = F1 + F0

F0 = T

FIM PARA

MOSTRE F1

O valor da variável F1 exibido é

Referente à UML (unified modeling language), analise as seguintes afirmativas e assinale com V as verdadeiras e com F as falsas.
( ) O fator de ramificação de uma árvore pode variar entre pequeno e grande. B-árvores são árvores de busca balanceadas projetadas para funcionar em discos ou outros dispositivos de armazenamento secundário. ( ) Muitos sistemas de banco de dados usam B-árvores ou variantes para armazenar informações. B-árvores generalizam árvores de busca binária de modo natural. ( ) Executar uma busca em uma B-árvore é muito semelhante a executar uma busca em uma árvore de busca binária, exceto que, em vez de tomar uma decisão de ramificação binária ou de “duas vias” em cada nó, toma-se uma decisão de ramificação de várias vias, de acordo com o número de filhos do nó. ( ) Para simplificar, pode ser considerado que, nas árvores de busca binária, qualquer informação-satélite associada a uma chave reside em nós diferentes da chave. Pode-se armazenar com cada chave vários ponteiros para uma outra página de disco que contenha as informações satélites da chave.
Assinale a sequência CORRETA .

O algoritmo Heapsort, quando usado para ordenar uma coleção n elementos distintos, possui, respectivamente, complexidade de melhor caso e de pior caso iguais a

Considere uma Fila Q com os elementos {4, 7, 9, 10, 3, 1}, adicionados da esquerda para a direita, com critério de entrada e saída LIFO (Last In First Out) e com a aplicação das seguintes operações:

Q->remover(), Q->remover(), Q->remover(), Q->adicionar(2), Q->adicionar(3), Q->adicionar(4), Q->remover()

O resultado final da fila Q é

Considere as seguintes afirmativas, sobre estruturas de dados:

I Uma pilha possui as operações básicas de empilhar e desempilhar.

II Uma lista duplamente encadeada não suporta a operação de retirada.

III Uma fila sempre obedece a um critério de entrada e saída.

IV Uma lista sempre obedece a um critério de entrada e saída.

Está correto o que se afirma em

Analise as afirmativas a seguir sobre complexidade de algoritmos:

I. Algoritmos de complexidade O(log n) são chamados de complexidade logarítmica e resolvem um problema quebrando-o em problemas menores.

II. Algoritmos de complexidade O(n) são chamados de complexidade linear, em que um pequeno trabalho é realizado sobre cada elemento de entrada.

III. Algoritmos de complexidade O(1) são chamados de complexidade constante, em que as instruções do algoritmo são executadas um número fixo de vezes.

Estão CORRETAS as afirmativas:

Considere as estruturas de dados com as seguintes propriedades

1) Inserção e remoção acontecem apenas na ‘cabeça’ da estrutura

2) A inserção de um nó no meio da estrutura pode ser realizada com custo computacional constante

3) Respeita a política FIFO: primeiro que entra é o primeiro que sai.

As descrições acima se referem às estruturas, respectivamente,

Assinale a alternativa que contém apenas algoritmos de ordenação de ordem quadrática.

Suponha que ‘vec’ é um array ordenado de 1000 chaves inteiras. Quantas comparações no máximo são necessárias para verificar se um inteiro qualquer ‘r’ pertence a ‘vec’?

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?

Considere o seguinte algoritmo

Inteiro array[10] = {0,1,2,3,4,5,6,7,8,9}

var i = 0

Enquanto i < 10 Faça

Inteiro temp = array[i]

array[i] = array[9-i]

array[9-i] = temp

i = i + 1

Fim enquanto

Qual será o conteúdo do vetor ‘array’ após a execução do programa?

Considere o algoritmo a seguir Inteiro

x1 =2, x2 = -1, x3 = 4

Enquanto (x1 > 0) faça

x2 = x3/3-x2*4

x1 = x3 % x1

Fim enquanto

Imprime(x2)

O que será impresso ao final do programa?

Analise as afirmativas a seguir sobre complexidade de algoritmos:

I. Algoritmos de complexidade O(n log n) resolvem um problema quebrando-o em problemas menores, resolvendo cada um deles independentemente e depois ajuntando as soluções.

II. Algoritmos de complexidade O(1) são chamados de complexidade linear, onde um pequeno trabalho é realizado sobre cada elemento de entrada.

III. Algoritmos de complexidade O(n) são chamados de complexidade constante, onde o tempo de execução cresce na mesma proporção do crescimento da estrutura de dados.

Estão CORRETAS as afirmativas:

Considere as afirmativas, sabendo que N se refere ao número de elementos da estrutura de dados. É correto afirmar:

Sobre as características de índices estruturados na forma de Btrees e Hash tables, analise as afirmativas a seguir.

I. Hash tables aplicam-se somente em buscas que referenciam a chave por inteiro (operador =).

II. B-trees favorecem consultas que buscam chaves num determinado intervalo (operadores >= e <=).

III. B-trees são usualmente mais lentas para buscas pela chave (operador =).

IV. Hash tables favorecem buscas, com o operador ‘LIKE’ do SQL, que não contenham caracteres curingas na primeira posição.

V. B-trees não se aplicam em buscas que se referem a uma substring à esquerda da chave.

Está correto o que se afirma em:

Uma estrutura de dados do tipo LIFO (Last-In, First-Out) é conhecida como

Considere a seguinte expressão lógica, a ser inserida em um programa.

R ← ((A and B) or (C and D)) or E

As variáveis A, B, C, D, E e R são do tipo booleano, podendo assumir valores verdadeiro (1) ou falso (0).

Assinale a alternativa que apresenta valores para A, B, C, D e E que resultem o valor falso (0) em R.

Uma árvore binária completa de busca, isto é, uma árvore em que todos os níveis têm o máximo número de elementos, tem um total de N nós.

O número máximo de comparações necessárias para encontrar um elemento nessa árvore é