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

Considere uma árvore binária de busca (BST) com n (n>3) níveis (o nó raiz está no nível 1), 2ⁿ - 1 nós e todas as chaves diferentes. Suponha, ainda, que algum dos pais de duas folhas seja removido da árvore e, mais tarde, uma chave com o mesmo valor da chave do nó removido seja inserida na árvore.

Quantas são as comparações necessárias para fazer a busca e encontrar o nó cuja chave foi removida e depois reinserida?

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?

Qual é a característica principal desse algoritmo?

Considerando o arranjo X = [5, 2, 4, 6, 1, 3], qual o estado de X após a execução do algoritmo?

Considerando que um algoritmo pode ser entendido como uma ferramenta para resolver um problema computacional bem especificado, analise as afirmações abaixo.
I - Um algoritmo descreve um procedimento computacional específico para obter uma determinada saída que tem um relacionamento com a entrada do algoritmo. II - Pode-se analisar a eficiência de um algoritmo em termos de tempo de execução e de espaço ocupado. III- Quando se analisa o “pior caso” em termos de tempo, tenta-se determinar o limite superior de tempo de execução relacionado com o número de elementos de saída do algoritmo.
Quais estão corretas?

A multiplicação (M) de dois números positivos maiores ou iguais a zero (A e B), realizada através de operações de somas, foi implementado da seguinte forma:
1: M := 0; 2: ENQUANTO (A≠0) FAÇA 3: M := M + A; 4: A := A - 1; 5: FIM-ENQUANTO
O algoritmo, conforme implementado, não realiza a multiplicação. Assinale a alternativa abaixo que melhor identifica o erro de lógica do algoritmo.

Considere a seguinte expressão lógica de um programa, onde X e Y são variáveis numéricas:
X < 7 OR Y = 15 AND X < 7 OR Y = 15 AND NOT (X < 7)
Qual par de valores tornaria FALSA a expressão acima?

Os métodos de ordenação são empregados para rearranjar um conjunto de objetos em uma ordem específica. Considere as seguintes proposições sobre esses métodos:

I. Um método de ordenação é dito estável se a ordem relativa dos itens com chaves iguais mantém-se inalterada pelo processo de ordenação.

II. A estabilidade de um método de ordenação é importante quando o conjunto de dados já está parcialmente ordenado.

III. Na ordenação interna, o número de registros a serem ordenados é pequeno o bastante para que todo o processo se desenvolva na memória interna (principal).

IV. Na ordenação externa, o número de registros a ser ordenado é maior do que o número que cabe na memória interna.

Assinale a alternativa CORRETA:

Analise as proposições abaixo sobre algoritmos e estrutura de dados:

I. Os métodos de ordenação por inserção e bolha possuem complexidade O(n² ) em relação ao número de comparações.

II. Embora O(n² ), o método de ordenação por inserção possui complexidade Ω(n) em relação ao número de comparações.

III. O método de ordenação por inserção, assim como o Quicksort, é estável.

IV. O método de ordenação Quicksort tem complexidade O(n² ) em seu pior caso.

Assinale a alternativa CORRETA:

O método de ordenação Bolha foi usado para ordenar uma tabela em ordem crescente contendo os números [10, 8, 7, 0], serão feitas:

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 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 é

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

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:

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: