Questões

Considere a definição da seguinte struct escrita em linguagem de programação C.

struct endereço {
char logradouro [50];
int numero;
char cidade[30];
char estado[2];
} end1;

A alternativa que manipula corretamente a struct acima definida é:

Dentre os fundamentos matemáticos da ciência da computação, existe um importante conceito que se revela na definição de um conjunto não vazio de nós (vértices) e um conjunto de arcos (arestas), dispostos de tal forma que cada arco necessariamente conecte dois nós. Assinale a alternativa que corresponde à descrição correta do conceito em questão:

Correlacione os algoritmos internos de ordenação de listas com sua descrição:

1. Escolhe-se um pivô 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 pivô, geram uma lista ordenada. O processo é aplicado às partições para ordená-las. Embora tenha uma complexidade de pior caso de O(n2 ), no caso médio, é de O(n log n).
2. 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.
3. 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.
4. É uma extensão de 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.
5. Varre-se a lista, trocando de posição os elementos adjacentes fora de ordem. Varre-se a lista até que não haja mais trocas. Neste caso, a lista está ordenada.

Qual é o nome do algoritmo de ordenação que mantém uma parte da lista ordenada, inserindo elementos na posição correta?

Considerando o trecho de código abaixo, qual é o resultado da busca binária para o elemento 18?

São corretas as afirmações:

I. O algoritmo de Dijkstra é um algoritmo guloso que encontra o caminho mínimo em um grafo ponderado com pesos não negativos.

II. O algoritmo de Dijkstra funciona mantendo um conjunto de vértices não visitados e um conjunto de vértices visitados, e calculando as distâncias mínimas a partir do vértice de origem para todos os vértices não visitados. O algoritmo utiliza uma fila de prioridade para selecionar o vértice com a menor distância entre os vértices não visitados a cada iteração.

III. O algoritmo de Bellman-Ford é outro algoritmo que pode ser usado para encontrar o caminho mínimo de fonte única em grafos ponderados, inclusive em grafos com pesos negativos.

O que é inclusão digital?

Qual é o caso mais desfavorável para o algoritmo de busca linear?

A pesquisa em memória primária tem a capacidade de encontrar a informação (que é dividida em registros contendo uma chave) desejada em um grande volume de dados. A busca por essa informação requer a escolha de um método de busca que considere a quantidade de dados envolvidos e a periodicidade das operações de inserção e remoção. Considerando a pesquisa em memória primária, avalie as afirmações a seguir em relação aos métodos de pesquisa e as relacione adequadamente aos termos a que se referem.

1. Pesquisa sequencial.
2. Pesquisa binária.
3. Transformação de chave (hashing).

I. Os registros armazenados em uma tabela são diretamente endereçados a partir de uma transformação aritmética sobre a chave de busca.

II. Percorre-se uma lista comparando a chave de busca com o valor de cada posição. Se o valor da chave for igual para alguma posição, então devolva esta posição. Caso a lista toda tenha sido percorrida então devolva -1, indicando que a chave não foi encontrada.

III. Adota o paradigma dividir para conquistar, fazendo com que o tempo de busca seja reduzido, pois, a cada iteração do algoritmo, o tamanho do vetor é dividido ao meio.

Assinale a alternativa que relaciona adequadamente os dois grupos de informações.