Questões de Algoritmos e Estrutura de Dados

Questão 1891

• Banca: NCE-UFRJ
• Órgão: BNDES
• Ano: 2005
• Provas: NCE-UFRJ - 2005 - BNDES - Profissional Básico - Análise de Sistemas - Desenvolvimento
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Algoritmos de Ordenação

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:

• A. O(n)
• B. O(n²)
• C. O(log₂ n)
• D. O(log₁₀ n)
• E. O(nⁿ)

Gabarito: C

Comentários

• Está questão deveria ser anulada, pois todas as alternativas estão corretas.
  A notação O significa o seguinte:
  Dadas duas funções positivas quaisquer, f e g
  f(n) = O(g(n)) se e somente se
  Existe um número real K e um número real n0 tal que f(n) <= K . g(n) para todo n > n0.
  Em palavras: para n suficientemente grande a função g multiplicada por uma constante sempre será um limite superior de f.
  Como já foi explicado acima, o tempo de acesso no caso do exercício é da ordem O(log n).
  O problema é que a função:
  1: f(n) = n é um limite superior de g(n) = log n, pois para n grande n > log n, logo log n = O(n) e a letra A é correta.
  2: f(n) = n2 é um limite superior de g(n) = log n, pois para n grande n2 > log n, logo log n = O(n2) e a letra B é correta.
  3: log n = O(log2 n) e a letra C é correta.
  4: log10 n = log2n/log210 (propriedade de logaritmos) como 1/log210 é uma constante log10 n = K log2n, log10n = O(log2n) logo a letra D é correta. Isso é importante para perceber que não importa a base do logaritmo nas notações Omega, Theta e O.
  5: f(n) = nn é um limite superior de g(n) = log n, pois para n grande nn > log n, logo log n = O(nn) e a letra E é correta.

• A questão deveria ser anulada porque não define o que é altura mínima. Caso a árvore fosse uma AVL ou Vermelho e Preto a resposta estaria correta. No entanto, poderia ser por exemplo esta árvore [1] -> [2] -> [3] -> [4] -> [5] - > [6] e assim por diante. Neste caso o tempo seria O(n).

• c-

  In a binary search tree, the left child of a node has a lesser value than the parent whereas the right child has a greater value than the parent. If there are n nodes in a binary search tree, the maximum height is n-1 and minimum height is ceil(log2n).

  https://www.geeksforgeeks.org/relationship-number-nodes-height-binary-tree/

Questão 2287

• Banca: NCE-UFRJ
• Órgão: TRE-RJ
• Ano: 2001
• Provas: NCE-UFRJ - 2001 - TRE-RJ - Analista Judiciário - Tecnologia da Informação
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Lógicas de Programação

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 é:

• A. P = N + (CGC) + 1{CP+Q+PU}
• B. P = N + {CGC} +1(CP+Q+PU)
• C. P = N + CGC + *{CP+Q+PU}
• D. P = {N+ CGC + (CP+Q+PU)}
• E. P = {CGC} + N{CP+Q+PU}

Gabarito: A

Comentários

• Tente lembrar de "expressão regular" para resolver a questão.N = sempre vai aparecer.() = torna o valor opcional.{} = valor que vai aparecer.1 = define que vai aparecer pelo menos uma vez.+ = concatena

Questão 5092

• Banca: CESGRANRIO
• Órgão: EPE
• Ano: 2007
• Provas: CESGRANRIO - 2007 - EPE - Analista de Gestão Corporativa Júnior - Área Tecnologia da Informação
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Conceitos Básicos de Estrutura de Dados; Estrutura de Dados

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

• A. Pilha.
• B. Árvore.
• C. Lista.
• D. Matriz.
• E. Fila.

Gabarito: B

Comentários

• Em ciência da computação, uma Árvore B+ é um tipo de árvore. Representa a ordenação de dados de uma maneira que permita uma inserção e remoção eficiente de elementos. É um índice dinâmico de multi-níveis com ligações máximas e mínimas no número de chaves em cada nodo. Os sistemas de ficheiros NTFS para o Microsoft Windows, o sistema de ficheiros ReiserFS para Unix, o XFS para IRIX e Linux, e o JFS2 para AIX, OS/2 e Linux, usam este tipo de árvore.Uma árvore B+ é uma variação da árvore B. Numa árvore-B+, contrastando com uma árvore-B, todos dos dados são gravados nas folhas. Os nodos internos contêm apenas chaves e apontadores da árvore. Todas as folhas estão no mesmo nível mais baixo. Os nodos das folhas também estão ligados entre si como uma lista de ligações para efectuar consultas facilmente.Fonte: Wikipedia

• Uma Árvore B+ é um tipo de árvore que representa a ordenação de dados de uma maneira que permita uma inserção e remoção eficiente de elementos. É um índice dinâmico de multi-níveis com ligações máximas e mínimas no número de chaves em cada nodo.

  Resposta: B

Questão 5434

• Banca: CESGRANRIO
• Órgão: Petrobras
• Ano: 2006
• Provas: CESGRANRIO - 2006 - Petrobrás - Analista de Sistemas Pleno - Engenharia de Software
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Complexidade de Algoritmos; Conceitos Básicos e Algoritmos

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

• A. O limite inferior de um algoritmo ( ) é utilizado para a análise do pior caso de sua execução.
• B. Uma função f(n) domina assintoticamente g(n), se existem duas constantes positivas c e n₀, tais que, para
• C. A função f(5log₂ N) é O²(N).
• D. A função f(5N³ + 2N²) é O(N²).
• E. Se duas funções f( ) e g( ) têm limite superior justo, então f( ) é O( g( ) ) e g( ) é O( f( ) ).

Gabarito: E

Questão 5437

• Banca: CESGRANRIO
• Órgão: Petrobras
• Ano: 2006
• Provas: CESGRANRIO - 2006 - Petrobrás - Analista de Sistemas Pleno - Engenharia de Software; CESGRANRIO - 2006 - Petrobrás - Analista de Sistemas Pleno - Processos
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Árvores; Estrutura de Dados

Insira as chaves {Lina, Ana, Lia, Ada, Lua, Sol, Cris, Bia, Rita, Mel, Rosa, Val} em uma árvore binária de busca (considere que a árvore está inicialmente vazia). Considere agora, a execução dos seguintes percursos sobre a estrutura após a inserção das chaves.

I - Um percurso em pré-ordem seria: { Ada, Bia, Cris, Lia, Ana, Mel, Rosa, Rita, Val, Sol, Lua, Lina}

II - Um percurso em ordem simétrica seria: {Val, Sol, Rosa, Rita, Mel, Lua, Lina, Lia, Cris, Bia, Ana, Ada}

III - Um percurso em nível seria: {Lina, Ana, Lua, Ada, Lia, Sol, Cris, Rita, Val, Bia, Mel, Rosa}

IV - Um percurso em pós-ordem seria: {Lina, Ana, Ada, Lia, Cris, Bia, Lua, Sol, Rita, Mel, Rosa, Val}

Estão corretos apenas os percursos indicados em:

• A. I e II.
• B. II e III.
• C. I, II e III.
• D. I, II e IV.
• E. II, III e IV.

Gabarito: B

Comentários

• Pré-order: root, then left sub-tree, then right sub-tree
  Post-order: then left sub-tree, then right sub-tree, root
  symetric order: left sub-three, root, then right sub-tree
• Os percursos em pré-ordem e pós-ordem estão invertidos (I é um percurso em pós-ordem e IV é um percurso em pré-ordem). Os outros dois estão corretos.
• 1º) Ordenar alfabeticamente os nomes.2º) Substituir os nomes ordenados por números (1,2,3,4,5,6,7,8,9,10,11,12).3º) Substituir pelos números os nomes da lista original, ficando assim (6,2,5,1,7,11,4,3,9,8,10,12) onde 6 é Lia, 2 é Ana, 5 é Lia e assim por diante.4º) Distribuir na árvore binária lembrando que, se um número é menor que raiz ele fica a esquerda se é maior fica a direita e assim o número vai descendo os níveis tomando a direita ou esquerda do nó seguinte até se tornar folha (nó sem filho)IMAGEM DA ÁRVORE: http://img405.imageshack.us/img405/4049/screenhunter002.gifCom isso temos:I) ERRADO: na Pré Ordem comecaria pelo raiz (6) LinaII) CERTO: Se considerarmos que este percurso simetrico comecou pela esquerdaIII) CERTO: De cima para baixo da esquerda para a direitaIV) ERRADO: na Pós ordem o primeiro item seria (1) Ada.
• O percurso simétrico (in ordem): E - D - V sempre retorna as chaves em ordem crescente.... Portanto o item 2 estaria errado. Na minha opnião esta questão deveria ter sido anulada.
• também não concordo que o item II esteja correto. Ele está mostrando os elementos em ordem decrescente, o que nãocaracteriza a ordem simétrica.
• Árvore Resultante:
  
  
  Pré-Ordem:     LINA ANA ADA LIA CRIS BIA LUA SOL RITA MEL ROSA VAL
  IN-Ordem:       ADA ANA BIA CRIS LIA LINA LUA MEL RITA ROSA SOL VAL
  POS-ORDEM: ADA ANA BIA CRIS LIA MEL ROSA RITA VAL SOL LUA LINA
  
  Simétrico: Já respondido no Ítem 2 (Segue a lógica: Da direita para a esquerda, visitando o PAI. Se filho esquerdo tem filho, visita o filho mais a direita, depois o seu Pai, e assim por diante.) Olhem a ilustração para facilitar o entendimento:
  
  Nível: Respondido item 3(Basta pegar de cima para baixo olhando a árvore resultante.
  
  
• A questão deveria ser anulada pois o item II não está em ordem,(está invertido) . Quanto ao percurso em nível eu nunca ouvi falar , mas pela explicação do colega Leonardo eu tive uma idéia do que seja. A propósito na minha resolução em pós ordem ANA vem depois de LIA . Como não pude identificar nenhuma que estivesse correta, eu marcaria a b , pois apesar de invertida a ordem do item II bate, e eu não sei o percurso em nível mais sei que os outros itens estão incorretos.
• Questãozinha complicada de se desenhar numa prova! A sugestão do amigo Ricardo de transformar em números é ótima! Depois de aplicar essa sugestão e de ver o link dele do desenho da árvore consegui matar a questão.
  O percurso em-ordem é sub-árvore esquerda, raiz e sub-árvore direita, mas na questão tem que ser usado o invertido (em-ordem simétrica). Por isso o item II está correto.
  A questão é muito boa para reforçar os conhecimentos sobre árvore de busca binária!

• O comentário dessa questão está detalhadamente no link abaixo , página 13:

  https://issuu.com/liberbooksbr/docs/quest__es_comentadas_de_ti_para_con_9e2cd361f37179

• A maneira mais fácil que eu encontrei pra fazer essa questão sem ter que montar toda a arvore em tabela alfabética é a seguinte:

  1 - Toda arvore binária criada do zero começa com o primeiro termo inserido

  ( com isso, sabemos que Lina é a raiz da árvore)

  2-Todo percurso Pré-Ordem começa com a Raiz da árvore, que seria Lina

  ( Isso já descarta a I , logo ACD estão erradas )

  Entre B e D, a única alternativa distinta entre ela é a IV

  3- Analisando IV:

  Sabe-se que percurso Pós-Ordem não começa com a raiz da árvore

  ( logo a IV está falsa pq sabemos que Lina é a Raiz da Arvore )

  Gabarito: B

  Assista esse vídeo que vc NUNCA MAIS vai esquecer como é feito os percursos(Pré-Ordem, In Ordem, Pós-Ordem)

  https://www.youtube.com/watch?v=OvMuKaG4Qhk&ab_channel=NetupProvedor

• Questão errada, a única alternativa correta é a alternativa 3, que fala da busca em nível. Quanto a ordem simétrica, é a mesma coisa que o percurso in-order: E,R,D, a qual retornaria as chaves em ordem.