Considere o seguinte trecho de código em Linguagem C, que visa manipular uma lista encadeada simples, e analise o comportamento da função mistério a seguir:

Qual é o resultado da execução dessa função sobre uma lista não vazia e qual é a sua complexidade de tempo?

Um algoritmo de busca sequencial em um vetor de n elementos possui uma complexidade de tempo, no pior caso, de O(n). Se um algoritmo de ordenação por seleção (Selection Sort) for aplicado a esse mesmo vetor, qual será a sua complexidade de tempo no pior caso?

Para que a Busca Binária seja aplicada com sucesso em um vetor, qual pré-requisito é obrigatório e qual é a sua complexidade de tempo no pior caso?

Sobre algoritmos de ordenação, assinale a alternativa que apresenta, respectivamente, a definição do conceito de “estabilidade” e o algoritmo que NÃO é estável em sua implementação padrão.

Considere o seguinte vetor de inteiros:

V = {8, 3, 7, 4, 9, 2}.

Suponha que o algoritmo Quicksort seja aplicado a esse vetor utilizando a seguinte estratégia:

• o pivô é sempre o primeiro elemento do subvetor;

• a partição organiza os elementos de forma que valores menores que o pivô fiquem à esquerda e valores maiores fiquem à direita.

Após a primeira operação de partição, qual será a posição final do pivô no vetor? Considere o algoritmo de partição de Lomuto, onde o pivô é o primeiro elemento e, ao final da partição, o pivô é posicionado entre os elementos menores e maiores.

[3, 8, 12, 15, 19, 27, 31].
Aplicando busca binária para localizar o valor 19, quantas comparações serão realizadas até encontrar o elemento, considerando a estratégia padrão de busca binária que compara inicialmente com o elemento central? Considere a implementação clássica da busca binária que retorna o índice do elemento ou -1 se não encontrado. As comparações consideram apenas as verificações do elemento central.

Considere o algoritmo:

Qual é a complexidade assintótica?

Analise o seguinte pseudocódigo:

Qual será o valor retornado por f(7)?

Analise o trecho de pseudocódigo abaixo:

Qual é o valor impresso pelo algoritmo?

 Analise a função recursiva abaixo escrita em pseudocódigo:

Qual é o valor retornado pela chamada calcular(6)?

Considerando a notação Big-O e o comportamento dos principais algoritmos de busca e ordenação, assinale a alternativa que apresenta, correta e respectivamente, a descrição da complexidade e das características do algoritmo Merge Sort.

Um professor solicita a um estudante que desenvolva um algoritmo em Portugol para calcular a média aritmética de um conjunto de notas inseridas pelo usuário, encerrando a entrada de dados quando o usuário digitar o valor –1. O estudante apresenta o seguinte algoritmo:

Considerando os fundamentos de algoritmos e lógica de programação, assinale a alternativa correta.

Pilhas e filas são estruturas de dados lineares fundamentais, com políticas de acesso distintas que determinam sua adequação a diferentes classes de problemas. Assinale a alternativa correta. 

 Sobre análise de complexidade e algoritmos de ordenação, analise as assertivas a seguir:

I. A notação O (big-O) define um limite superior assintótico: f(n) = O(g(n)) se, e somente se, existem constantes c > 0 e n₀ ≥ 1 tais que 0 ≤ f(n) ≤ c·g(n) para todo n ≥ n₀.

II. O Merge Sort apresenta complexidade Θ(n log n) no pior, no melhor e no caso médio, mantendo esse desempenho independentemente da distribuição de entrada.

III. O algoritmo Quick Sort com estratégia de pivô aleatório (randomized quicksort) possui complexidade Θ(n log n) no pior caso, eliminando completamente a possibilidade de comportamento quadrático.

IV. Se um algoritmo tem complexidade O(n²), então ele também tem complexidade O(n³), pois toda função limitada superiormente por c·n² também é limitada superiormente por c·n³ para n suficientemente grande.

Quais estão corretas?

Sobre divisão e conquista, memoização e programação dinâmica, assinale a alternativa correta.

Durante a manutenção de um pequeno sistema interno utilizado para registrar solicitações de suporte técnico em uma escola, um técnico em manutenção e suporte de informática recebeu a tarefa de revisar um algoritmo responsável por organizar a fila de atendimentos e calcular automaticamente o tempo médio de resolução. Ao analisar a documentação do sistema, ele verificou que o algoritmo original foi descrito inicialmente por meio de um fluxograma e posteriormente convertido para pseudocódigo. Considerando conceitos fundamentais de lógica de programação, analise as afirmativas a seguir:

I.Um algoritmo pode ser entendido como uma sequência organizada de passos destinada a resolver um problema ou executar uma tarefa computacional, podendo ser descrito por diferentes representações, como linguagem natural estruturada, pseudocódigo ou fluxogramas.
II.Fluxogramas utilizam símbolos gráficos padronizados para representar operações, decisões e fluxos de controle, permitindo visualizar a lógica de execução de um processo antes ou durante sua implementação em código.
III.O processo de depuração envolve a análise do comportamento de um programa ou algoritmo com o objetivo de localizar e corrigir falhas lógicas ou erros de implementação que afetam o resultado esperado.
IV.Em algoritmos estruturados, estruturas de decisão e repetição são utilizadas para controlar o fluxo de execução, permitindo que determinadas instruções sejam executadas de acordo com condições previamente avaliadas.
V.A etapa de depuração consiste apenas na tradução direta do algoritmo para uma linguagem de programação específica, sem envolver análise do comportamento do programa durante sua execução.

Com base nas afirmativas apresentadas, assinale a alternativa CORRETA:

Considere os algoritmos clássicos de ordenação: Bubble Sort, Selection Sort, Insertion Sort, Merge Sort e Quick Sort.
Analise as afirmativas a seguir com base em suas propriedades formais de complexidade, estabilidade e uso de memória na implementação tradicional apresentada na literatura clássica.
I. O Insertion Sort possui complexidade de tempo O(n²) no pior caso e pode apresentar complexidade O(n) no melhor caso, quando o vetor já se encontra ordenado.
II. O Merge Sort apresenta complexidade O(n log n) nos casos melhor, médio e pior, é estável e, em sua implementação tradicional, requer espaço adicional proporcional a O(n).
III. O Quick Sort apresenta complexidade média O(n log n) e pior caso O(n²), podendo este ocorrer quando o pivô escolhido produz partições altamente desbalanceadas.
IV. O Selection Sort possui complexidade O(n²) nos casos melhor, médio e pior e, em sua implementação tradicional, não é considerado um algoritmo estável.
Assinale a alternativa CORRETA:

Considere um algoritmo destinado a verificar se uma matriz quadrada “M”, de ordem “n”, é simétrica. Para isso, ele percorre apenas os elementos acima da diagonal principal e compara cada “M[i][j]” com “M[j][i]”, interrompendo a execução ao encontrar a primeira divergência. De acordo com o enunciado, o número de comparações realizadas entre pares de posições no pior caso, ou seja, quando a matriz efetivamente é simétrica e de ordem “n”, é:

Com relação a ferramentas para o desenvolvimento de algoritmos, qual afirmativa abaixo está incorreta? 

Assinale a alternativa que representa graficamente um Terminal conforme a norma ISO 5807:1985 (E).