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

Certa cadeia de caracteres (string) não vazia tem comprimento X e contém uma frase em português constituída apenas por letras (acentuadas ou não), dígitos e os sinais comuns de pontuação. Se codificada segundo o padrão ISO-8859-1 (Latin-1), esta cadeia requer X bytes para sua representação; se codificada em UTF-8, são necessários X+1 bytes, ou seja, um byte a mais em relação à representação ISO-8859-1. É correto afirmar que o byte adicional:

Em relação ao tema “estruturas de dados”, analise as afirmativas a seguir e marque a opção correta:

I - Nas árvores B todas as folhas sempre estarão no mesmo nível.

II - Nas listas duplamente encadeadas, todos os nós apontam para os nós sucessores e antecessores.

III - Nas árvores binárias cada nó pode ter no máximo duas subárvores.

Um arquivo é organizado logicamente como uma sequência de registros, cada um deles representando um objeto ou uma entidade. Com base no conhecimento sobre as diferentes maneiras de organizar registros em arquivos, considere as seguintes afirmativas.   
I. Uma organização de arquivo hash (também chamada de acesso direto) fornece um acesso muito rápido aos registros, quando a condição de pesquisa é de igualdade em um único campo; neste caso, o campo é chamado campo de hash. A ideia do hashing é forncecer uma função h, chamada função hash, que, aplicada ao valor do campo hash de um registro, gere o endereço do bloco do disco no qual o registro será armazenado.
II. Em uma organização de arquivo heap, os registros são armazenados fisicamente em ordem sequencial a partir dos valores de um de seus campos, chamado campo de classificação. Na organização de arquivo heap, a inclusão e a exclusão de registros são operações dispendiosas porque os registros deverão permanecer ordenados fisicamente.
III. Em uma organização de arquivo sequencial, os registros estão posicionados no arquivo segundo a ordem pela qual foram incluídos, de forma que os novos registros são acrescentados ao final do arquivo ou onde haja espaço disponível. Na organização sequencial, para ler todos os registros pela ordem dos valores de algum campo, é preciso criar uma cópia do arquivo e ordená-la através de técnicas especiais de classificação externa.
IV. As operações em arquivos são geralmente divididas em operações de recuperação e operações de atualização. As operações de recuperação não alteram nenhum valor no arquivo, apenas localizam certos registros, de forma que seus valores de campo possam ser examinados e processados. As operações de atualização mudam o arquivo por meio da inclusão ou da exclusão de registros ou pela modificação de valores dos campos.   
Assinale a alternativa CORRETA.

No processo de criação de um banco de dados relacional, primeiro foram criadas as tabelas onde seriam guardados os dados; depois, foi feita a inserção dos dados nessas tabelas. Nenhuma outra estrutura auxiliar foi criada no banco para melhorar o desempenho além das chaves primárias. Após realizar uma simulação de carga, com dados e aplicativos reais, o responsável percebeu que uma busca importante tentava encontrar uma pessoa pelo número do seu título de eleitor, no campo TITELE, que não era uma chave primária planejada. Essa busca demorava muito, pois o SGBD precisava procurar em todos os registros até encontrar aquele com o número desejado.

Supondo-se que o SGBD suporta visões, índices árvore-B e de tabela de espalhamento (hashs), joins e procedimentos armazenados, a maneira de acelerar essa busca ao máximo é criar um(a)

 Considere  o  seguinte  pseudocódigo,  no  qual  uma  rotina  com  complexidade O(n) é aplicada em um laço duplo. 
PARA i ←1 ATÉ n FAÇA                  INÍCIO                                  PARA j ←1 ATÉ i FAÇA                                                 INÍCIO  rotina com complexidade Ο(n);                                          FIM;                         FIM PARA;             FIM;  FIM PARA; 

Em uma estrutura de dados em árvore binária, necessariamente,

Considere duas estruturas de dados, I e II, com as seguintes características típicas:

I. O PRIMEIRO elemento a ser inserido é o PRIMEIRO a ser retirado.
II. O PRIMEIRO elemento a ser inserido é o ÚLTIMO a ser retirado.

As estruturas I e II são, respectivamente, dos tipos

Qual árvore a seguir NÃO é binária?

Um programador recebeu a tarefa de elaborar um algoritmo para criar uma única lista encadeada, não necessariamente ordenada, a partir de duas listas encadeadas ordenadas já existentes.

Cada uma das listas originais possui ponteiros para o primeiro e para o último elementos. Qual é a complexidade do algoritmo mais eficiente que esse programador pode produzir?

Ao entrevistar um conjunto de usuários, uma analista de sistemas coletou os seguintes requisitos:

Os atendentes podem cadastrar, atualizar e excluir pedidos. Todos os pedidos são cadastrados com o status “aberto”. O status de um pedido é único e corresponde à situação em que ele se encontra a cada momento. Após ter suas informações completamente fornecidas, um pedido é passado para o departamento de ativação, que muda seu status para “ativando” e muda, posteriormente, para “atendido” quando o atendimento se encerra. Uma vez que um pedido não está mais em aberto, ele não pode ser modificado para atender a solicitações externas. Sobre um mesmo pedido, considere as seguintes proposições e seu significado pretendido:

P: o pedido está em aberto.
Q: o pedido está ativando.
R: o pedido está atendido.
M: o pedido pode ser modificado.

Para os requisitos descritos, vale a seguinte fórmula da lógica proposicional:

Um vetor ordenado de inteiros com 2N+1 elementos, com N=0, será usado para criar uma árvore binária de busca da seguinte maneira: o elemento central, de índice N, será usado para criar a raiz; depois, serão inseridos na árvore todos os elementos na seguinte ordem de índices: N-1, N+1, N-2, N+2, ..., 1, 2N-1, 0, 2N.

Assumindo que a altura de uma folha é zero, qual será a altura resultante dessa árvore?

Considere o pseudocódigo abaixo.

Função teste(inteiro a, inteiro b): inteiro
var x: inteiro
Início

x ← a
a ← b
b ← x

retorna (b * (x + a) / 2)

Fim.

Algoritmo Principal
var a, b: inteiro Início
Leia (a, b)
imprima (teste(a,b))

Fim

Considerando que a e b receberam, respectivamente, os valores 4 e 3, conclui-se que será impresso o valor

Os métodos de ordenação correspondem ao processo de rearranjar um conjunto de objetos em ordem ascendente ou descendente. O objetivo da ordenação é facilitar a recuperação posterior dos itens do conjunto ordenado. Um algoritmo de ordenação que pode ser usado em uma ampla variedade de situações é denominado de

Assinale a alternativa que preenche corretamente as lacunas do enunciado abaixo, na ordem em que aparecem.

Comandos do-while (“faça-enquanto”), while-do (“enquanto-faça”) e for (“para-condição-atualização”), em linguagens de programação, permitem a execução de laços e são necessários em muitos algoritmos.

No comando do-while, a expressão lógica associada ao ________ é avaliada ________ execução do bloco de comandos; no ________, a expressão lógica de controle é avaliada ________.

Por sua política de acesso FIFO (First In, FIrst Out), que trata dos elementos na ordem de sua chegada, a estrutura de dados que é tipicamente utilizada em simulações ou tratamento de eventos em interfaces gráficas é denominada

Uma estrutura de dados que contém um grupo de itens homogêneos (todos do mesmo tipo) e que sejam diretamente identificados e acessíveis através do uso de índices inteiros é denominada