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

Considere uma árvore B de ordem 2 inicialmente vazia.
Os números abaixo são inseridos na seguinte ordem:

10, 15, 8, 3, 4, 12, 20, 9.

Que número(s) compõe(m) o nó raiz?

Analise as seguintes afirmações relacionadas a conceitos básicos de estruturas de dados.

I. Em uma árvore genérica, não binária, cada nó pode ter qualquer quantidade de nós filhos.

II. Em uma árvore binária de pesquisa, a busca é feita de tal forma que se o dado procurado está na raiz a pesquisa será encerrada. Caso contrário, a busca continua e deve ser feita em apenas uma das duas sub-árvores.

III. Uma árvore binária é considerada balanceada quando, para cada nó, a altura das duas sub-árvores diferem, no máximo, da somatória da quantidade de nós existentes nos níveis pares, dividido pela quantidade de níveis considerados.

IV. Um circuito em um grafo é um caminho único que tem origem no primeiro nó e se encerra no último nó.

Indique a opção que contenha todas as afirmações verdadeiras.

Analise as seguintes afirmações relativas a estruturas de dados:

I. Uma árvore binária qualquer de altura 3 tem no máximo 8 folhas.

II. Ao se transformar uma árvore genérica, formada apenas pela raiz e seus quatro filhos, em uma árvore binária, a árvore resultante terá apenas uma folha.

III. A única condição para uma árvore binária de pesquisa ser considerada balanceada é que, para cada nó, a altura da sub-árvore da esquerda seja igual à altura da sub-árvore da direita.

IV. Uma árvore binária de pesquisa balanceada deve ter o número de folhas igual ao número de nós.

Estão corretos os itens:

Dadas as variáveis numéricas A e B, contendo os valores 2 e 6, respectivamente; a variável L, contendo o literal FALSO; e a variável lógica V, contendo o valor lógico verdadeiro, assinale a expressão lógica cujo resultado possui valor lógico falso.

A respeito de funções e algoritmos, assinale a afirmativa correta.

Uma _________ B+ é uma estrutura de dados muito utilizada em banco de dados e sistemas de arquivos. Que palavra completa a frase corretamente?

Um analista especificou os dados que devem constar de um pedido de cliente. Um item de pedido (P) deve conter o nome do cliente (N), seu CGC (opcional), a data do pedido e uma lista de itens, contendo pelo menos um item. Cada item da lista deve conter obrigatoriamente o código do produto (CP) ,sua quantidade (Q) e seu preço unitário (PU).

A descrição formal de um pedido é:

Considere uma árvore binária de busca com n elementos e altura mínima. O tempo de acesso a qualquer elemento desta árvore é da ordem de:

Considere os seguintes algoritmos, todos com complexidade assintótica O(n):

Algoritmo 1: executa uma iteração simples sobre uma lista de tamanho n.

Algoritmo 2: executa duas iterações simples sobre uma lista de tamanho n, uma após a outra.

Algoritmo 3: executa uma iteração simples sobre uma lista de tamanho n, mas a iteração interna realiza uma operação constante que leva t_C tempo.

Algoritmo 4: executa uma iteração sobre uma lista de tamanho n e, dentro dessa iteração, realiza uma operação constante k vezes, em que o tempo total das operações é k * t_D e(k * t_D > t_C).

Algoritmo 5: executa uma iteração simples sobre uma lista de tamanho n, mas a iteração interna realiza uma operação com complexidade O(1).

Qual dos algoritmos é menos eficiente em termos de tempo de execução, embora todos tenham a mesma complexidade assintótica O(n)?

Considere o algoritmo a seguir, escrito em pseudocódigo, para inserir um novo valor z em uma árvore de busca binária A com n nós e altura h. 

1             y = NULL 2             x = A.raiz 3             ENQUANTO x ≠ NULL FAÇA: 4              y = x 5             SE z.chave < x.chave: x = x.esquerda 6             SE NÃO: x = x.direita 7             z.p = y 8            SE y = NULL: A.raiz = z 9            SE NÃO: 10               SE z.chave < y.chave: y.esquerda = z 11          SE NÃO: y.direita = z

O algoritmo acima é executado no tempo

Métodos de ordenação são algoritmos que ordenam os elementos de uma estrutura de dados. Considere os principais algoritmos de ordenação, marque V para as afirmativas verdadeiras e F para as falsas.


( ) Bubble Sort é eficiente para grandes conjuntos de dados.
( ) Merge Sort é mais eficiente em termos de espaço do que o Quick Sort.
( ) Insert Sort é baseado na estratégia de dividir para conquistar.


A sequência está correta em