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

Considere que em uma tabela de dispersão (ou tabela hash) de módulo 9, inicialmente vazia, que usa endereçamento aberto, técnica de tentativa linear para resolver colisões e função de dispersão h(k) = k mod m, onde k é a chave a ser inserida, foram inseridas as seguintes chaves: 3, 14, 15, 81, 65, 19, 35, 40 e 50 (nesta ordem). O número de colisões para a inserção desses dados é:  

As Estruturas de Dados definem a forma como os dados serão armazenados na memória do computador. Duas das estruturas de dados mais utilizadas na computação são a Pilha e a Fila. Considere as afirmativas abaixo que comparam as estruturas de Pilha e Fila:

I - A estrutura chamada Pilha é descrita como uma estratégia LIFO - last in, first out (o último que entra é o primeiro que sai), isto é, os elementos da pilha só podem ser retirados na ordem inversa à ordem que foram introduzidos.

II - A estrutura chamada Fila é descrita como uma estratégia FIFO - first in, first out (o primeiro que entra é o primeiro que sai), isto é, os elementos da pilha só podem ser retirados na mesma ordem em que foram inseridos.

III - Uma estrutura que recebe dos dados 10, 20, 30, 40 e 50 nessa ordem e só permite a sua retirada na ordem 50, 40, 30, 20 e 10 é um exemplo de uma Pilha.

IV - Uma estrutura que recebe dos dados 10, 20, 30, 40 e 50 nessa ordem e só permite a sua retirada na ordem 50, 40, 30, 20 e 10 é um exemplo de uma Fila.

V - Um programa que usa apenas estruturas de Pilha recebe os dados 1, 2, 3, 4 e 5 nessa ordem e imprime os dados na ordem 1, 2, 3, 4 e 5 pode ter sido implementado com duas estruturas de Pilha consecutivas.

As afirmativas CORRETAS são: 

Assinale as operações características de uma estrutura de dados do tipo pilha (stack).

A complexidade do algoritmo de busca binária numa lista ordenada, com N elementos, é

Considere a lista duplamente encadeada exibida a seguir.

(1, 3, 0, “Verde”)

(2, 4, 3, “Azul”)

(3, 2, 1, “Amarelo”)

(4, 0, 2, “Vermelho”)

Cada elemento pertencente à lista é representado por uma quádrupla, com o seguinte formato:

(<id>, <id do anterior>, <id do seguinte>, <conteúdo>).

A ordem do conteúdo dos componentes, segundo a instância da lista apresentada, é:

João precisa codificar uma função f(A), onde A é um array unidimensional de números inteiros, que deve retornar o maior valor armazenado em A.

A complexidade de um algoritmo eficiente para a função f, para um array com n (n ≥ 1) elementos, deveria ser:

Em um sistema operacional, a estrutura de dados utilizada para organizar chamadas de funções recursivas por meio da inserção ou remoção de elementos via operações como push e pop é denominada

Em um problema de classificação é entregue ao cientista de dados um par de covariáveis, (x₁ , x₂ ), para cada uma das quatro observações a seguir: (6,4), (2,8), (10,6) e (5,2). A variável resposta observada nessa amostra foi “Sim”, “Não”, “Sim”, “Não”, respectivamente.
A partição que apresenta o menor erro de classificação quando feita na raiz (primeiro nível) de uma árvore de decisão é: 

Qual é a afirmativa correta sobre estruturas de dados?

função a ( n)

{

    se    (n = 4)    então

         retorne n ;

    senão

         retorne    (4*a(n+1) ) ; 

    fim se ;

}

escreva ( a (2) ) ;

Para o algoritmo anterior, o resultado apresentado é igual a

O algoritmo de ordenação que requer uma quantidade constante de O(1) espaço de memória adicional é o algoritmo de

Na classificação de algoritmos por meio de seu método de design, aquele que reduz a complexidade exponencial para a complexidade polinomial para muitos problemas e mantém uma tabela para subproblemas já resolvidos é denominado