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

Um algoritmo de ordenação é executado através dos seguintes passos: (I) escolha de um elemento da lista, denominado pivô; (II) rearranjo da lista, de forma que todos os elementos anteriores ao pivô sejam menores do que ele e que todos os elementos posteriores ao pivô sejam maiores do que ele; e, também, de modo que o pivô, ao fim do processo, esteja em sua posição final, havendo duas sublistas não ordenadas; (III) ordenação recursiva das sublistas dos elementos menores e dos elementos maiores. Que algoritmo é esse?

As linguagens de programação possuem estruturas para que se criem soluções melhores. Marque a alternativa que possui estrutura de repetição representada em pseudocódigo.

Marque a alternativa que apresenta tipos de dados primitivos usados para a criação de programas.

Quando se escreve um algoritmo, ou um programa de computador é quase impossível não se ter uma variável. Uma variável, emprogramação de computadores, é:

Um problema de algoritmo em uma estrutura recursiva demostra que:

Correlacione os algoritmos internos de ordenação de listas da coluna à esquerda com sua descrição, na coluna à direita.

1) Bubblesort. 

2) Ordenação por Seleção 

3) Ordenação por Inserção

4) Shellsort 

5) Quicksort 

( ) Escolhe-se um pivot e particiona-se a lista em duas sublistas: uma com os elementos menores que ele e outra com os maiores, que, ao serem ordenadas e combinadas com o pivot, geram uma lista ordenada. O processo é aplicado às partições para ordená-las. Embora tenha uma complexidade de pior caso de O(n² ), no caso médio é de O(n log n). 

( ) Encontra-se o menor item do vetor. Troca-se com o item da primeira posição do vetor. Repetem-se essas duas operações com os n − 1 itens restantes, depois com os n − 2 itens, até que reste apenas um elemento. 
( ) Método preferido dos jogadores de cartas. A cada momento existem duas partes na lista: uma ordenada (destino) e outra não ordenada (fonte). Inicialmente a lista destino tem apenas o primeiro elemento, e a fonte os demais elementos. Em cada passo a partir de i=2, seleciona-se o i-ésimo item da lista fonte. Deve-se colocá-lo no lugar apropriado na lista destino, de acordo com o critério de ordenação. 

( ) É uma extensão de um outro algoritmo de ordenação conhecido e permite trocas de elementos distantes um do outro, não necessariamente adjacentes. Os itens separados de h posições são rearranjados. Todo h-ésimo item leva a uma lista ordenada. Tal lista é dita estar h-ordenada. 

( ) Varre-se a lista trocando-se de posição os elementos adjacentes fora de ordem. Varre-se a lista até que não haja mais trocas e, neste caso, a lista está ordenada.

A sequência correta, de cima para baixo, é: 

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

O comando condicional se-então-senão (if-then-else) pode-se pode ter seu comportamento simulado com o enquanto-que (while). Dado o trecho de pseudocódigo esquemático abaixo, assinale a alternativa em que se simula o comportamento do se-então-senão (if-thenelse) com o enquanto-que, onde S e T são sequências arbitrárias de comandos e C uma expressão boolena.  se C então faça  S senão faça  T fim-se

Com o comando de repetição repetir-até-que (repeatuntil) pode-se simular o comportamento do enquanto-que (while). Dado o trecho de pseudocódigo esquemático abaixo, assinale a alternativa em que se simula o comportamento do enquanto-que com o repetir-até-que, onde S é uma sequência arbitrária de comandos e C uma expressão boolena que incorpora a condição de parada do laço.
enquanto que C S fim-enquanto

Certas linguagens não possuem o comando de repetição repetir-até-que (repeat-until). Porém, pode-se simular seu comportamento com um enquanto-que (while). Dado o trecho de pseudocódigo esquemático abaixo, assinale a alternativa em que se simula o comportamento do repetir-até-que com o enquanto-que, onde S é uma sequência arbitrária de comandos e C uma expressão boolena que incorpora a condição de parada do laço.
repita S até que C

Considere o algoritmo em pseudocódigo abaixo, que computa, dados dois inteiros, uma sequência de inteiros. Leia(n,a) enquanto n!=1 faça:      imprima n      se (n mod 2)=0 então:          n:=n div 2      senão:          n:=a*n+1 imprima n
Sobre a sequência impressa, dados os valores de n e de a especificados, analise as proposições a seguir. 
1) Para n=6 e a=3, a sequência gerada é: 6 3 10 5 16 8 4 2 1. 2) Para n uma potência de 2, n=2^k para algum k inteiro; para qualquer valor de a, a sequência gerada são as potências de 2 de 2^k até 1. 3) Para n=9 e a=3, a sequência gerada é: 14 7 22 11 33 17 52 26 13 40 20 10 5 16 8 4 2 1. 4) Se n não for uma potência de 2, com a=2 o algoritmo não para, gerando uma sequência infinita. 5) Com a=5, se n=17 o programa fica em laço infinito na sequência 17 86 43 216 108 54 27 136 68 34. Estão corretas, apenas: 

Um usuário necessita encontrar um padrão de informação em um arquivo texto com milhares de tipos de informação diferentes. Para tanto, ele deve utilizar uma expressão regular. A informação procurada possui uma sequência numérica de três dígitos de 0 a 9, um traço, uma sequência de três caracteres de “A” até “Z” maiúsculos ou minúsculos, um ponto - obrigatoriamente - e uma sequência de dois dígitos numéricos de 1 a 5, como neste exemplo “999-AaZ.55”. Assinale a alternativa que apresenta corretamente a expressão regular que localize o padrão dado.

Marque a opção relativa às fases da construção de um algoritmo:

Uma das funções da lógica de programação é definir os passos para se resolver problemas do mundo real através de programas de computador criados nas linguagens de programação. Considere, nesse contexto, a estrutura de passos em pseudolinguagem abaixo.
Se for informado o valor 4000 para a variável salary será exibido o valor

Assinale a alternativa que apresenta as palavras que preenchem, respectivamente, as lacunas do seguinte texto, sobre estruturas de repetição.

O WHILE é uma estrutura de repetição _____, ele repete a execução de um bloco de sentenças enquanto uma condição permanecer verdadeira. Na primeira vez que a condição se tornar falsa, o WHILE _____ a execução do bloco, e a execução continuará com a sentença ou comando que vem logo após _____ WHILE, na sequência do programa. A estrutura de repetição DO ... WHILE tem um comportamento muito semelhante ao WHILE, com uma diferença crucial, a condição é verificada _____ executar o bloco de instruções correspondente.

A preocupação com a complexidade de algoritmos é de extrema importância para o projeto de algoritmos eficientes. Neste contexto, a complexidade de tempo no pior caso para o algoritmo de ordenação QuickSort é

A CASAN precisará desenvolver uma funcionalidade dentro do seu sistema que terá como objetivo ajudar a empresa a diminuir os custos dos trajetos percorridos pelos funcionários de sua equipe de fiscalização. Essa funcionalidade terá que gerar o itinerário de cada funcionário, baseado nos dados de distância, condições das estradas e cidades atendidas pelos funcionários. Qual dos algoritmos a seguir seria uma opção para o desenvolvimento dessa funcionalidade?

Um algoritmo de complexidade exponencial pode ser representado por qual notação?

É importante considerar os diversos tipos de chaves existentes na organização de arquivos, em particular,

Considere o algoritmo abaixo, escrito em linguagem estruturada: 

A = valor inicial

T = 0

Enquanto A < 10 faça

    T = A + T

    A = A + 1

Fim Enquanto

Supondo que A tenha como valores iniciais 5 e 2, os valores finais de T serão, respectivamente,