Questões de Concurso Sobre algoritmos e estrutura de dados

O analista José precisa escolher entre dois algoritmos, Abusca e Cbusca. José sabe que, sendo N o tamanho da entrada do algoritmo, Abusca requer 2^N + log₂(N) operações para ser executado. Já o Cbusca requer N⁴ + N operações para ser executado. José determinou, na notação O-grande, a complexidade de tempo no pior caso para cada algoritmo e, por fim, deve escolher o algoritmo que apresenta a menor ordem de complexidade no pior caso.

José deve escolher o algoritmo:

O analista Joaquim precisou ordenar um array com N elementos. Para economizar tempo, Joaquim optou por usar um algoritmo já disponível na biblioteca de ordenação. A biblioteca contém as implementações originais dos algoritmos Quicksort, Selection Sort, Insertion Sort, Merge Sort e Heap Sort. O analista escolheu o algoritmo que, no pior caso, apresenta uma relação quadrática entre a quantidade de operações necessárias para a ordenação e o número de elementos do array. No caso médio, a quantidade de operações necessárias se aproxima de N multiplicado por um logaritmo de N.

Joaquim escolheu o algoritmo de ordenação:

Uma certa organização busca melhorar a qualidade e agilidade do seu atendimento eletrônico. Para isso um projeto foi criado para agrupar os e-mails recebidos de acordo com o tipo de problema a ser resolvido e assim repassá-los para o setor mais apropriado.

A equipe responsável pela implementação do projeto resolveu utilizar um modelo de linguagem recente para representar o máximo possível de informação contida num e-mail em um vetor de dimensão 768. Entretanto, depararam-se com o seguinte problema: as distâncias entre os vetores se mostraram muito pequenas, tornando o agrupamento por diversos algoritmos muito pouco significativo.

Com esse último problema em mente, a sequência mais apropriada de algoritmos a ser aplicada sobre os vetores, de forma a obter um agrupamento significativo dos e-mails, é:

O cientista de dados Pedro trabalha em um projeto que envolve a previsão dos movimentos de um braço robótico em um ambiente complexo. Pedro tem um fluxograma de um algoritmo de aprendizado por reforço que é capaz de se adaptar dinamicamente ao ambiente e ajustar suas ações com base nos resultados de ações anteriores.

O algoritmo representado pelo referido fluxograma que deve ser empregado para a realização da tarefa de Pedro é o:

As estruturas de dados utilizadas em programação determinam como as informações serão armazenadas, organizadas e acessadas, sendo uma parte importante no projeto de software, com impacto no seu desempenho e eficiência.

Sobre estruturas de dados lineares, analise as afirmativas a seguir.

I. Para realizar uma busca por um elemento em uma lista simplesmente encadeada pode-se começar a busca pelo início ou fim da lista.

II. Listas duplamente encadeadas não permitem a exclusão de elementos que não sejam o último ou o primeiro elemento da lista.

III. Uma lista circular pode ser simplesmente encadeada ou duplamente encadeada.

Está correto o que se afirma em 

A Notação Polonesa Reversa (RPN, do inglês Reverse Polish Notation) foi desenvolvida como uma forma de escrever expressões lógicas e aritméticas sem usar parênteses. Essa notação ganhou popularidade ao ser implementada em calculadoras científicas, onde permite reduzir a quantidade de acionamento de teclas no cálculo de expressões.

Quando uma calculadora opera no modo RPN, os operandos são inseridos previamente em uma estrutura de dados e, ao utilizar-se um operador (soma, subtração, ...), a quantidade de operandos necessários são retirados da estrutura na ordem inversa da inserção e, após o cálculo da operação, o resultado é inserido na estrutura de dados. Assim, por exemplo, caso se deseje calcular a expressão A + (B – C)*D em uma calculadora operando no modo RPN, pode-se seguir o seguinte procedimento: 

• Insere A

• Insere B

• Insere C

• Realiza a operação de subtração

• Insere D

• Realiza a operação de multiplicação

• Realiza a operação de soma

De acordo com a descrição acima, assinale a opção que indica a estrutura de dados que melhor caracteriza a utilizada pelo modo RPN para armazenar os operandos e resultados.

Com relação à formulação de algoritmos e suas formas de representação, analise as afirmativas a seguir e assinale (V) para a verdadeira e (F) para a falsa.

( ) O refinamento passo a passo de cima para baixo é um processo para refinar o pseudocódigo, mantendo uma representação completa do programa durante cada refinamento.

( ) A técnica conhecida como “repetição controlada por contador” é muitas vezes denominada como “repetição definida”, porque o número de repetições é conhecido antes do laço começar a ser executado.

( ) O fluxograma é uma representação gráfica de um algoritmo. É desenhado com alguns símbolos especiais, como retângulos, elipses, círculos e losangos, conectados por setas.

As afirmativas são, respectivamente,

Um sistema de banco de dados normalmente possui estruturas de dados auxiliares, chamadas de índices ou estruturas de indexação, que são utilizadas para agilizar a recuperação de registros em resposta a certas condições de pesquisa. Existem diversos métodos de indexação, tanto para dados convencionais, baseados em tipos numéricos e textuais, quanto para dados espaciais representados por pontos, linhas e polígonos.
Nesse contexto, analise as afirmativas a seguir e assinale (V) para a verdadeira e (F) para a falsa.
( ) Tanto as Árvores-B+ quanto as Árvores-R são árvores balanceadas. ( ) Em uma Árvore-B+, uma busca por um valor de chave iniciada pelo nó raiz percorre apenas um único caminho até um nó folha (ou terminal). ( ) Em uma Árvore-R, uma busca iniciada pelo nó raiz pode exigir a verificação de mais de uma sub-árvore desse nó raiz para selecionar os itens que satisfazem o critério de busca. ( ) Uma quad-tree sempre é uma árvore balanceada. ( ) Uma das desvantagens de um Árvore-k-d (k-d-tree) é que ela é uma estrutura sensível à ordem nos quais os pontos são inseridos.
As afirmativas são, respectivamente,

Deseja-se implementar em um sistema de comunicações uma técnica de codificação de informação que consiste no envio de uma palavra código de 5 bits que representa 2 bits de mensagem, conforme tabela abaixo. 

Se uma palavra código é recebida com erros de transmissão, escolhe-se, durante o processo de decodificação, a palavra código com a menor distância Hamming da palavra código recebida.

Durante a comunicação de um octeto, o receptor recebeu o seguinte trem de bits 11001001110111011010.

O valor transmitido, em decimal, foi igual a 

Ao realizar a soma dos números binários 00011010₍₂₎ e 00100111₍₂₎, obtém-se como resposta o número binário

Qual é a finalidade principal da análise de algoritmos?

Os algoritmos de roteamento usam algum padrão de medida, chamado de métrica, a fim de determinar a melhor rota para um dado destino. Para ajudar no processo de determinação de rotas, os algoritmos de roteamento inicializam e mantêm tabelas de roteamento, que contém informações de rotas. Sendo assim, analise a figura a seguir.
  

De acordo com a imagem, é correto afirmar: 

Considere as assertivas abaixo sobre criptografia e funções do tipo hash:

I. O MD5 não é propriamente um modelo criptográfico, existindo limitações até mesmo de segurança. Seu hash é constituído por uma estrutura hexadecimal de 32 caracteres.
II. O AES (Advanced Encryption Standard) é um algoritmo de criptografia, porém é unidirecional, não permitindo a descriptografia.
III. O RSA (Rivest-Shamir-Adleman) é um algoritmo de criptografia assimétrica bidirecional.

Conforme as assertivas, responda a alternativa verdadeira:

Julgue as sentenças abaixo como VERDADEIRAS ou FALSAS.

1. (__) Vetores (arrays bidimensionais) e matrizes (arrays unidimensionais) são estruturas de dados que permitem armazenar e manipular coleções de dados de forma eficiente.
2. (__) Fluxogramas são representações gráficas de algoritmos, utilizando símbolos padronizados para denotar diferentes tipos de instruções ou operações (como processos, decisões, entrada/saída de dados, entre outros).
3. (__) Ao utilizar uma sintaxe simplificada e próxima da língua nativa do aprendiz, o Portugol permite uma compreensão mais intuitiva dos conceitos fundamentais de programação, como variáveis, estruturas de controle e lógica de programação.

A sequência CORRETA é:

Qual das seguintes opções melhor descreve o conceito de uma estrutura de sequência em programação?

Um analista de sistemas está projetando um sistema que requer a implementação de uma estrutura de dados para representar um conjunto de elementos, onde a busca por um elemento específico deve ser realizada de forma eficiente. Qual estrutura de dados é mais apropriada para essa situação?

Considere as seguintes características, encontradas em alguns algoritmos de ordenação:

I - É estável, ou seja, não altera a ordem relativa dos elementos que possuem o mesmo valor de chave de ordenação.
II - Percorre repetidamente a lista a ser ordenada, comparando o elemento corrente com o seguinte e, se necessário, trocando os seus valores.
III - Divide a lista a ser ordenada em duas partes: uma sublista ordenada de elementos, que é construída da esquerda para a direita (ordem crescente), à frente de uma sublista referente aos elementos não ordenados, sendo que, inicialmente, a primeira lista é vazia, enquanto a segunda contém todos os elementos a serem ordenados.

Essas características se aplicam, respectivamente, aos seguintes métodos de ordenação:

A Figura a seguir exibe uma árvore binária.

Suponha que uma função percorra essa árvore em ordem simétrica e exiba os valores de seus nós no console.

Um dos possíveis somatórios do 2º , do 3º e do 4º valores exibidos por essa função é

Marcos, um analista do TJ contratado para otimizar o desempenho de um servidor de alta capacidade, enfrenta desafios com lentidão durante períodos de alta demanda. Uma investigação minuciosa revelou que a raiz do problema reside na gestão ineficaz da memória cache. Para abordar isso, Marcos sugere a adoção de um algoritmo de substituição de cache mais eficiente.

Considerando os algoritmos de substituição de cache mais comuns, Marcos resolverá o problema de desempenho do servidor com o algoritmo:

Bárbara implementa um algoritmo de ordenação estável cuja complexidade temporal média O_T pertence a O(n.logn) e cuja complexidade espacial O_E pertence a O(n), sendo n o tamanho do vetor a ser ordenado.

O algoritmo implementado é o: