Questões de Algoritmos e Estrutura de Dados do ano 2022

Seja uma função que realiza uma busca binária sobre um array de números inteiros ordenados. Não se sabe, em princípio, se os números estão ordenados ascendente ou descendentemente. O cabeçalho dessa função é o seguinte:
int busca (int [ ] vet, int elem)
Isto é, a função busca recebe um array de números inteiros (vet) e um número inteiro (elem) como parâmetros, e retorna um número inteiro. Caso exista em vet um inteiro igual a elem, a função retornará o índice desse inteiro no array; caso contrário, a função retornará -1.
O algoritmo de busca binária produz um índice (ind) a cada iteração sobre o array, tendo em vista comparar o elemento que se deseja procurar (elem) com o elemento vet [ ind ]. Isto é:
if ( vet [ ind ] == elem )              return ind;
No comando acima, diz-se que houve uma visita ao elemento vet [ ind ].
Admita que a função busca foi chamada por meio do comando a seguir:
int resp = busca (vet, 50);
Sabendo-se que os elementos visitados foram 54, 17, 33 e 50, nesta ordem, qual array foi passado como parâmetro para a função busca? 

Considere o pseudocódigo do método de ordenação Insertion Sort, o qual ordena em ordem crescente os números naturais armazenados em um vetor (array) v de tamanho t indexado a partir de zero (ou seja, índices do vetor variam de 0 a t-1).
Assinale a alternativa que completa corretamente o espaço pontilhado entre chaves do pseudocódigo abaixo.

função Ordena(v, t) {      i ? 1      enquanto i < t faça      {            j ? i           enquanto j > 0 e v[j-1] > v[j] faça           {                .....................           }           i ? i + 1      } }

Analise as afirmativas abaixo sobre lógica de programação e assinale a alternativa correta.

I. Na passagem de parâmetros por valor é feita uma cópia do parâmetro fornecido a uma função para uma variável interna à própria função.
II. Funções recursivas não podem conter laços de repetição.
III. A resposta da operação lógica x1 XOR x2 será verdadeira (true) se os valores das variáveis x1 e x2 forem diferentes entre si.
IV. A resposta da operação lógica x1 NAND x2 será sempre falsa (false) se x1 e x2 forem iguais.
V. Um programa estruturado é composto por um conjunto de funções.

Considere as funções F e G escritas em pseudocódigo mostradas a seguir.

função F(n) {      se n = 0 então         retorne 1      senão         retorne n * F(n - 1) } função G(m) {      x ? 1     para i ? 2 até m faça         x ? x * i     retorne x }

Analise as afirmativas abaixo e assinale a alternativa correta.
I. As funções F e G são equivalentes.
II. A função G retorna o valor 120 quando invocada da seguinte forma: G(5).
III. A função F não possui uma estrutura de repetição.
IV. F é uma função recursiva e G é uma função iterativa.

Considere o problema de ordenar em ordem crescente o vetor (array) de números inteiros [7, 30, 2, 45, 66, 13, 17, 23, 1, 15] utilizando o algoritmo de ordenação Bubble Sort em sua versão não recursiva. Analise as afirmativas abaixo e assinale a alternativa correta.

I. São feitas 23 trocas de elementos do vetor até que ele esteja totalmente ordenado.
II. A ordem dos elementos do vetor será [2, 7, 30, 13, 17, 23, 1, 15, 45, 66] após 10 trocas de elementos.
III. O número de trocas de elementos diminui à medida que a execução do algoritmo de ordenação avança.