Desenvolvimento (Code + Calc) Flashcards
- (FGV – 2021 – IMBEL) Considere um conjunto de 65.536 chaves ordenadas, distintas entre si,
armazenadas num array.
Com relação ao processo de busca binária, assinale a opção que indica o número máximo de acessos ao array necessários para localizar uma determinada chave qualquer.
a) 10
b) 16
c) 64
d) 256
e) 32.768
Para isso, devemos usar a fórmula log2n = 65.536.
Na busca binária, o vetor é dividido ao meio sucessivamente, até achar o valor desejado.
Vamos ver quantas vezes conseguimos dividir por 2 o valor:
65.536/2 = 32768 (1x)
32768/2 = 16384 (2x)
16384/2 = 8192 (3x)
8192/2 = 4096 (4x)
4096/2 = 2048 (5x)
2048/2 = 1024 (6x)
1024/2 = 512 (7x)
512/2 = 256 (8x)
256/2 = 128 (9x)
128/2 = 64 (10x)
64/2 = 32 (11x)
32/2 = 16 (12x)
16/2 = 8 (13x)
8/2 = 4 (14x)
4/2 = 2 (15x)
2/2 = 1 (16x)
Portanto, são, no máximo, 16 vezes.
Gabarito: Letra B
- (FCC – 2013 – MPE-AM) Considere o vetor vet a seguir:
Após a execução dos seguintes comandos de atribuição:
aux ← vet[8]
vet[8] ←vet [1]
vet[4] ← vet[6]
vet[6] ← vet[3]
vet[3] ← vet[1] ← aux
A configuração do vetor (do índice 1 ao 8) será
a) ZONAAMAS
b) AMASZONA
c) SMAZONAS
d) AMASSONA
e) AMAZONAS
Vamos passo a passo:
aux ← vet[8]
É definido o valor de vet[8] para a variável aux. É a oitava posição do vetor, ou seja, A.
Assim, aux = A.
vet[8] ←vet [1]
À posição 8, é atribuído o valor da posição 1. Assim:
SMNAOZAS
vet[4] ← vet[6]
À posição 4, é atribuído o valor da posição 6. Assim:
SMNZOZAS
vet[6] ← vet[3]
À posição 6, é atribuído o valor da posição 3. Assim:
SMNZONAS
vet[3] ← vet[1] ← aux
Às posições 1 e 3, são atribuídos os valores de aux, que é A. Assim:
AMAZONAS
Gabarito: Letra E
- (FCC - 2016 - Copergás - PE - Analista Tecnologia da Informação) Considere o algoritmo a seguir, na forma de pseudocódigo:
Var n, i, j, k, x: inteiro
Var v: vetor[0..7] inteiro
Início
v[0] ← 12
v[1] ← 145
v[2] ← 1
v[3] ← 3
v[4] ← 67
v[5] ← 9
v[6] ← 45
n ← 8
k ← 3
x ← 0
Para j ← n-1 até k passo -1 faça
v[j] ← v[j - 1];
Fim_para
v[k] ← x;
Fim
Este pseudocódigo
a) exclui o valor contido na posição x do vetor v.
b) insere o valor de x entre v[k-1] e v[k] no vetor v.
c) exclui o valor contido na posição k do vetor v.
d) tentará, em algum momento, acessar uma posição que não existe no vetor.
e) insere o valor de k entre v[x] e v[x+1] no vetor v.
O algoritmo, na estrutra de repetição “Para j ← n-1 até k passo -1 faça” percorre o vetor de trás para frente, “empurrando” os valores para o final do vetor.
De fato, a estrutura vai da posição 7 até a 3 no vetor passando os valores da posição anterior para a posterior.
Desse modo v[6] vai para v[7], v[5] para v[6], até que o valor de v[3] fica igual ao valor de v[4].
Na última instrução v[3] recebe outro valor. Ou seja, o algoritmo “afasta” os valores, a partir da posição três, para incluir um novo valor, entre v[2] e v[3] (v[k-1] e v[k]).
Gabarito: Letra B
- (FGV – 2021 – IMBEL) No contexto das estruturas de dados, considere uma pilha (stack) onde as seguintes operações foram executadas.
CLEAR
PUSH (12)
PUSH (14)
POP
PUSH (20)
PUSH (15)
POP
PUSH (19)
Assinale a opção que indica o número de elementos e o valor do elemento localizado no topo da pilha, ao final das operações.
a) 3 / 12
b) 3 / 15
c) 3 / 19
d) 5 / 12
e) 5 / 19
Precisamos definir os comandos.
● CLEAR: limpa a pilha.
● PUSH: inclui um elemento na pilha.
●POP: retira o último elemento incluído da pilha.
Então, vamos seguir linha a linha:
CLEAR
Limpa a pilha.
PUSH (12)
Inclui o número 12 na pilha.
Pilha: (base) [12] (topo)
PUSH (14)
Inclui o número 14 na pilha.
Pilha: (base) [12, 14] (topo)
POP
Remove o número 14 da pilha.
Pilha: (base) [12] (topo)
PUSH (20)
Inclui o número 20 na pilha.
Pilha: (base) [12, 20] (topo)
PUSH (15)
Inclui o número 15 na pilha.
Pilha: (base) [12, 20, 15] (topo)
POP
Remove o número 15 na pilha.
Pilha: (base) [12, 20] (topo)
PUSH (19)
Inclui o número 19 na pilha.
Pilha: (base) [12, 20, 19] (topo)
Portanto, a pilha ficou com 3 elementos, sendo que, em seu topo, está o número 19.
Portanto, 3 / 19.
Gabarito: Letra C
- (FGV – 2018 – MPE-AL) Considere as seguintes operações sobre uma estrutura de dados, inicialmente vazia, organizada na forma de pilhas (ou stack),
PUSH (10)
PUSH (2)
POP ()
POP ()
PUSH (6)
Assinale a opção que apresenta a lista de elementos armazenados na estrutura, após a execução das operações acima.
a) 10, 2, 6
b) 10, 2
c) 2, 6
d) 6
e) 2
Precisamos definir os comandos.
● PUSH: inclui um elemento na pilha.
●POP: retira o último elemento incluído da pilha.
Então, vamos seguir linha a linha:
PUSH (10)
Inclui o número 10 na pilha.
Pilha: (base) [10] (topo)
PUSH (2)
Inclui o número 2 na pilha.
Pilha: (base) [10, 2] (topo)
POP ()
Remove o número 2 na pilha.
Pilha: (base) [10] (topo)
POP ()
Remove o número 10 na pilha.
Pilha: (base) [] (topo)
PUSH (6)
Insere o número 6 na pilha.
Pilha: (base) [6] (topo)
Ao fim, temos apenas o elemento 6.
Gabarito: Letra D
- (CESPE - 2004 – STJ – Analista de Sistemas)
A seguir, está representada corretamente uma operaçãode desempilhamento em uma pilha de nome p.
se p.topo = 0 então
nada {pilha vazia}
senão p.topo 🡨 p.topo-1
Galera, a questão deu uma vaciladinha! O ideal seria dizer p.topo = null, mas vamos subentender que foi isso mesmo que ele quis dizer.
Desse modo, se não tem topo, é porque a pilha está vazia. Se tiver topo, então o topo será o elemento anterior ao topo. O que ocorreu? Eu desempilhei a pilha!
Gabarito: Correto
- (CESPE - 2004 – STJ – Analista de Sistemas) A seguir, está representada corretamente uma operação de retirada em uma fila de nome f.
se f.começo = nil então
erro {fila vazia}
senão j <- f.começo.info
Não, o correto seria:
se f.começo = nil então
erro {fila vazia}
senão f.começo <- f.começo.anterior
Por que, professor? As duas primeiras linhas estão apenas dizendo que se o primeiro elemento da fila for Null (ou Nil), vai dar erro porque a fila está vazia, logo não há como retirar elementos de uma fila vazia.
Agora vejam a última linha: ele atribui a uma variável j o valor f.começo.info. Na verdade, ele simplesmente está colocando em j os dados do primeiro elemento da fila, mas a questão pede o código para retirar um elemento da lista e não para capturar os dados do primeiro elemento.
Na resposta, eu coloco que f.começo, i.e., o primeiro elemento da lista vai ser f.começo.anterior, ou seja, temos um novo primeiro elemento e eu retirei aquele elemento anterior.
Gabarito: Errado
- (FCC - 2016 - Prefeitura de Teresina - PI - Analista Tecnológico - Analista de Suporte Técnico)
Considerando uma estrutura de dados do tipo fila, e a seguinte sequência de comandos sobre essa fila (sendo que o comando Push representa uma inserção de elemento e o comando Pop representa uma exclusão de elemento) e considerando também que a fila estava inicialmente vazia:
Push 3, Push 5, Pop 3, Push 7, Pop 5, Push 9, Push 8
Após a execução dessa sequência de comandos, o conjunto de elementos que resulta na fila é:
a) 3 − 5 − 7 − 9 − 8.
b) 7 − 9 − 8 − 3 − 5.
c) 3 − 3 − 5 − 5 − 7 − 9 − 8.
d) 7 − 9 − 8.
e) 3 − 5 − 3 − 7 − 5 − 9 − 8.
Como a questão nem pediu a ordem, ficou bem fácil. Push inclui e pop retira. Se há dois pop’s, os elementos 3 e 5 são removidos da fila, sobrando 7, 9 e 8.
Gabarito: Letra D
- (IFTM – IFTM– 2023) Dada a árvore de busca binária da imagem a seguir, insira os elementos 23, 12, 64, 93, 71 e 86 (nessa ordem).
Após a inserção, qual é a saída do percurso pós-ordem?
a) 8, 12, 23, 35, 42, 56, 64, 71, 74, 77, 85, 86, 89, 91, 93, 96.
b) 74, 56, 35, 8, 23, 12, 42, 64, 71, 85, 77, 89, 86, 96, 91, 93.
c) 12, 23, 8, 42, 35, 71, 64, 56, 77, 86, 93, 91, 96, 89, 85, 74.
d) 12, 23, 8, 42, 35, 64, 56, 71, 77, 86, 93, 91, 96, 89, 85, 74.
e) Nenhuma das alternativas.
Pré-ordem: Raiz -> Esquerda -> Direita
Em Ordem (Simétrico): Esquerda -> Raiz -> Direita
Pós-ordem: Esquerda -> Direita -> Raiz
Vamos relembrar o conceito de árvore binária? Uma árvore binária é uma estrutura de dados
hierárquica que consiste em nós e arestas. Cada nó possui no máximo dois filhos, chamados de filho esquerdo e filho direito. A raiz da árvore é o nó superior, que não possui pais. As árvores binárias podem ser usadas para representar diversos tipos de dados, como números, strings, objetos, etc. Elas são frequentemente usadas em algoritmos de busca, ordenação e processamento de dados. Em uma árvore binária balanceada, cada nó da árvore tem a mesma altura ou a altura do nó esquerdo é um a menos que a altura do nó direito. Isso garante que a árvore possa ser percorrida de forma eficiente, usando algoritmos como a busca binária. Existem diversos algoritmos de balanceamento para árvores binárias. Um dos algoritmos mais conhecidos é o algoritmo AVL, que usa uma propriedade chamada fator de balanceamento para determinar se um nó está desbalanceado. A inserção pós-ordem é um
tipo de inserção de elementos numa árvore binária. Nessa inserção, os elementos são inseridos na árvore na seguinte ordem:
- Inserir todos os elementos filhos do nó atual. 2. Inserir o próprio nó.
A inserção pós-ordem é frequentemente usada em algoritmos de processamento de dados que precisam visitar todos os elementos da árvore uma única vez.
Vamos juntos, passo a passo para entender como é feita a inserção nesse caso.
Inserção do elemento 23:
1. Comparamos 23 com a raiz, que é 74. Como 23 é menor que 74, seguimos para o lado esquerdo da árvore.
- Comparamos 23 com a raiz do lado esquerdo, que é 56. Como 23 é menor que 56, seguimos para o lado esquerdo da árvore.
- Comparamos 23 com a raiz do lado esquerdo, que é 35. Como 23 é menor que 35, seguimos para o lado esquerdo da árvore.
- Comparamos 23 com a raiz do lado esquerdo, que é 8. Como 23 é maior que 8, inserimos 23 como o novo filho direito de 8.
Inserção do elemento 12:
1. Comparamos 12 com a raiz, que é 74. Como 12 é menor que 74, seguimos para o lado esquerdo da árvore.
- Comparamos 12 com a raiz do lado esquerdo, que é 56. Como 12 é menor que 56, seguimos para o lado esquerdo da árvore.
- Comparamos 12 com a raiz do lado esquerdo, que é 35. Como 12 é menor que 35, inserimos 12 como o novo filho esquerdo de 35.
Inserção do elemento 64:
1. Comparamos 64 com a raiz, que é 74. Como 64 é maior que 74, seguimos para o lado direito da árvore.
- A raiz do lado direito é vazia, então inserimos 64 como a nova raiz do lado direito.
Inserção do elemento 93:
1. Comparamos 93 com a raiz, que é 74. Como 93 é maior que 74, seguimos para o lado direito da árvore.
- Comparamos 93 com a raiz do lado direito, que é 64. Como 93 é maior que 64, inserimos 93
como o novo filho direito de 64.
Inserção do elemento 71:
- Comparamos 71 com a raiz, que é 74. Como 71 é menor que 74, seguimos para o lado esquerdo da árvore.
- A raiz do lado esquerdo é 56. Comparamos 71 com 56. Como 71 é maior que 56, inserimos 71 como o novo filho direito de 56.
Inserção do elemento 86:
1. Comparamos 86 com a raiz, que é 74. Como 86 é menor que 74, seguimos para o lado esquerdo da árvore.
- Comparamos 86 com a raiz do lado esquerdo, que é 56. Como 86 é maior que 56, seguimos para o lado esquerdo da árvore.
- Comparamos 86 com a raiz do lado esquerdo, que é 35. Como 86 é maior que 35, seguimos para o lado esquerdo da árvore.
- Comparamos 86 com a raiz do lado esquerdo, que é 23. Como 86 é maior que 23, inserimos 86 como o novo filho direito de 23
Gabarito: Letra C
A Figura a seguir exibe uma árvore binária.
Suponha que uma função percorra essa árvore em ordem simétrica e exiba os valores de seus nós no console.
Um dos possíveis somatórios do 2º , do 3º e do 4º valores exibidos por essa função é
A 90
B 120
C 130
D 150
E 200
Ordem Simétrica pode ser tanto Esquerda - Raiz - Direita quanto o contrário (Direita - Raiz - Esquerda)
A banca pediu para percorrer a árvore de forma assimétrica, ou seja, em Ordem, que é ERD (Esquerda, Raiz, Direita). No entanto, não é apenas essa forma que pode ser usada, podendo também ser DRE (Direita, Raiz, Esquerda). Essa foi a pegadinha da questão, pois estamos sempre acostumados a percorrer de forma ERD.
Neste sentido, você deve percorrer a árvore pelo lado direito e exibir todos os valores dessa árvore. A sequência seria (40, 30, 20, 70, 100, 60, 10, 80, 50, 90), em que os 2º, 3º e 4º valores, destacados em negrito, somam 120. Portanto, a resposta correta é a letra B.
Fique atento, pois a banca pode fazer a brincadeira de trocar a esquerda e a direita nas ordens de pré-ordem, em ordem e pós-ordem e como não existia nenhuma alternativa que desse a resposta correta se você começasse pela esquerda ERD que daria 140, então era testar pelo lado direito.
Gabarito: B
Os seguintes números serão inseridos, nessa ordem, em uma árvore AVL: 3, 13, 17, 23, 7, 9, 21, 25, 2.
O quinto elemento da árvore a ser visitado, quando é realizada uma busca em pré-ordem, é o número:
A 2;
B 9;
C 13;
D 17;
E 25.
Para resolver a questão e encontrar o quinto elemento a ser visitado em uma busca em pré-ordem (também conhecida como “preorder traversal”) em uma árvore AVL, primeiro precisamos construir a árvore AVL com os números fornecidos, seguindo as regras de balanceamento da árvore AVL.
Os números fornecidos são: 3, 13, 17, 23, 7, 9, 21, 25, 2.
Vamos inserir os números um por um, ajustando a árvore para manter a propriedade AVL (balanceamento de alturas) após cada inserção.
A arvore vai ficar:
3 / \ 2 13 / \ 7 17 \ \ 9 23 / \ 21 25
Busca em pré-ordem ponto À esquerda de cada nó.
Gabarito: B
- (FGV – 2018 – Câmara de Salvador - BA) Gerenciadores de bancos de dados frequentemente empregam índices implementados na forma de árvores B. Nesse tipo de organização, considerando-se uma árvore na qual o número máximo de chaves numa página não folha é 19 (ou seja, d=20), o número máximo de acessos necessários para localizar uma chave, num universo de 10 milhões de chaves distintas, é:
a) 4;
b) 7;
c) 19;
d) 100;
e) 316.
O limite superior da profundidade da árvore é d ≤ 1 + logd/2, sendo que:
● d = a ordem da árvore, ou seja, o número máximo de chaves numa página não folha. Neste caso, d = 20.
● N = a quantidade de registros. Neste caso, N =
10.000.000
Portanto, calculemos:
d ≤ 1 + logd/2
d ≤ 1 + log20/2
d ≤ 1 + log[10]((10.000.001/2)
d ≤ 1 + log10
Para calcularmos na mão este logaritmo, vamos fazer multiplicando 10 por 10 até chegarmos no valor, para termos alguma ideia.
Portanto:
1010 = 100 (2x)
10010 = 1.000 (3x)
1.00010 = 10.000 (4x)
10.00010 = 100.000 (5x)
100.00010 = 1.000.000 (6x)
1.000.00010 = 10.000.000 (7x)
Note do 6 para o 7, o valor ultrapassou 5.000.000,5. Portanto log10 é mais ou menos 6,5, com um arredondamento bem estimado.
Então:
d ≤ 1 + log10
d ≤ 1 + 6,5
d ≤ 7,5
Portanto, a quantidade máxima de acessos é d ≤ 7,5. Como a quantidade máxima de acessos é um número inteiro, então é 7.
Gabarito: Letra B
- (FGV – 2018 – MPE-AL) Em uma árvore B de ordem d, onde cada nó que não o raiz possui entre d e 2d chaves, estão armazenadas 30.000 chaves.
Sabendo-se que d=8, assinale a opção que indica o número máximo de nós visitados para a localização de uma chave.
a) 3
b) 5
c) 7
d) 15
e) 15.000
O limite superior da profundidade da árvore é d ≤ 1 + logm/2, sendo que:
● m = a ordem da árvore, ou seja, o número máximo de chaves numa página não folha. Neste caso, m = 16, porque a quantidade máxima de chaves numa página é 2d = 2*8 = 16.
● N = a quantidade de registros. Neste caso, N =
30.000 Assim:
d ≤ 1 + logm/2
d ≤ 1 + log16/2
d ≤ 1 + log8
d ≤ 1 + log8
Vamos calcular log8 multiplicando 8 por 8 até o valor ultrapassar 15.000,5: 8*8 = 64 (2x)
648 = 512 (3x)
5128 = 4.096 (4x)
4.096*8 = 32.768 (5x)
Note que o valor ultrapassa 15.000 do 4 para o 5. Portanto, log8 está entre 4 e 5. Vamos arredondar e dizer que é 4,5.
d ≤ 1 + 4,5
d ≤ 5,5
Como a quantidade máxima de tentativas é um inteiro, então é 5.
- (FGV – 2021 – IMBEL) Considere uma árvore B+ com as seguintes características.
I. A raiz é uma folha ou um nó que contém, no mínimo, dois filhos.
II. Cada nó diferente do nó raiz e das folhas possui no mínimo d filhos.
III. Cada nó tem no máximo 2d filhos. Cada nó possui entre d-1 e 2d-1 chaves, exceto o raiz que possui entre 1 e 2d-1 chaves.
IV. Somente os nós folhas contêm dados associados às chaves.
Assinale o número máximo de acessos necessários para localizar uma chave, com d=10, num universo de 10 milhões de chaves.
a) 5
b) 7
c) 10
d) 100
e) 1.000
O número máximo de acessos é calculado pela fórmula log d n. Para d = 10 e n = 10.000.000, temos log 10 10000000 = 7.
Gabarito: Letra B
- (FGV – 2021 – TJ-RO) 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>, <id>, <conteúdo>).</conteúdo></id></id></id>
A ordem do conteúdo dos componentes, segundo a instância da lista apresentada, é:
a) Amarelo, Verde, Azul, Vermelho;
b) Azul, Verde, Vermelho, Amarelo;
c) Verde, Vermelho, Amarelo, Azul;
d) Vermelho, Amarelo, Azul, Verde;
e) Vermelho, Azul, Amarelo, Verde.
Considerando que o primeiro número é o ID, temos os seguintes IDs:
ID Cor
1 Verde
2 Azul
3 Amarelo
4 Vermelho
De linha a linha, vamos analisando:
(1, 3, 0, “Verde”)
O verde vem depois do 3 (Amarelo), e antes do 0. Como não existe 0, então sabemos que:
Lista: Amarelo - Verde
(2, 4, 3, “Azul”)
O azul vem depois do 4 (Vermelho), e antes do 3 (Amarelo), então sabemos que:
Lista: Vermelho - Azul – Amarelo – Verde
Apenas com essas duas linhas, já sabemos a ordem que é a letra D, certo? Mas… vamos conferir as demais.
(3, 2, 1, “Amarelo”)
Diz que o Amarelo vem depois do 2 (Azul) e antes do 1 (Verde). Está certo.
(4, 0, 2, “Vermelho”)
Diz que o Vermelho vem depois do 0 (não existe, portanto, é o primeiro), e depois do 2 (Azul). Certo também.
A lista é Vermelho - Azul – Amarelo – Verde.
Gabarito: Letra E
- (CESPE - 2009 - ANAC - Especialista em Regulação - Economia)
Considerando-se uma árvore binária completa até o nível 5, então a quantidade de folhas nesse nível será 24.
Não! A quantidade de folhas em um determinado nível – considerando a raiz como nível 0 –, é dada pela fórmula 2^d, portanto 32.
Gabarito: Errado
- (CESPE - 2009 – ANAC - Analista de Sistemas)
Uma árvore binária completa até o nível 10 tem 2.047 nós.
Se possui 10 níveis, possui [2^(d+1)] -1 : 2047 nós!!
Gabarito: Correto
- (CESGRANRIO – 2010 – PETROBRÁS - Analista de Sistemas) Uma sequência desordenada de números armazenada em um vetor é inserida em uma árvore AVL. Após a inserção nesta árvore, é feito um percurso em ordem simétrica (em ordem) e o valor de cada nó visitado é inserido em uma pilha.
Depois de todos os nós serem visitados, todos os números são retirados da pilha e apresentados na tela. A lista de números apresentada na tela está:
a) ordenada ascendentemente de acordo com os números.
b) ordenada descendentemente de acordo com os números.
c) na mesma ordem do vetor original.
d) na ordem inversa do vetor original.
e) ordenada ascendentemente de acordo com sua altura na árvore.
Essa questão é legal! Olha só…
Eu tenho um vetor com um bocado de valor desordenado. Esses valores são colocados em uma Árvore AVL.
Ora, uma árvore AVL é uma árvore binária de busca, portanto segue suas propriedades. Logo, não importa se estava desordenado. À medida que são inseridos os valores desordenados na árvore, ela vai se balanceando e ordenando os dados.
Após isso, vamos retirar os dados da Árvore AVL. Como? Da esquerda para a direita! E vamos colocá-los em uma pilha.
Se estamos lendo da esquerda para a direita, estamos retirando do menor valor para o maior
valor, logo o maior valor da pilha será o maior valor da Árvore AVL.
Por fim, ao retirar os elementos da pilha,
retiramos do topo (maior) para a base (menor), logo em ordem descendente.
Gabarito: Letra B
- (CESPE – 2010 – PETROBRÁS - Analista de Sistemas) No sistema de dados do Departamento de Recursos Humanos de uma grande empresa multinacional, os registros de funcionários são armazenados em uma estrutura de dados do tipo árvore binária AVL, onde cada registro é identificado por uma chave numérica inteira.
Partindo de uma árvore vazia, os registros cujas chaves são 23, 14, 27, 8, 18, 15, 30, 25 e 32 serão, nessa ordem, adicionados à árvore. Dessa forma, o algoritmo de inserção na árvore AVL deverá realizar a primeira operação de rotação na árvore na ocasião da inserção do elemento:
a) 30
b) 25
c) 18
d) 15
e) 8
Vamos simular! Vamos inserir logo os três primeiros: 23, 14 e 27 (primeira imagem); depois inserimos o número 8 (segunda imagem); e inserimos o número 18 (terceira imagem).
Agora vamos inserir o 15! Esse nó iria para a esquerda de 18 como mostra a primeira imagem abaixo. Nesse caso, o nó 23 ficaria desbalanceado.
O que fazer?
Temos um Caso Esquerda-Direita, portanto temos que fazer uma rotação dupla: primeiro à esquerda no Ramo 14-18 e depois à direita no Ramo 18-23. O resultado é mostrado a imagem abaixo e é na inserção do nó 15 que devemos fazer a primeira rotação.
Gabarito: Letra D
- (CESPE – 2014 – TJ/SE - Analista de Sistemas) Existem dois vetores, chamados A e B, que estão ordenados e contêm N elementos cada, respeitando a propriedade A[N-1]<B[0], onde os índices de ambos os vetores vão de 0 a N-1.
Retiram-se primeiro todos os elementos de A na ordem em que se apresentam e inserem-se esses elementos em uma árvore binária de busca, fazendo o mesmo depois com os elementos de B, que são inseridos na mesma árvore de busca que os de A.
Depois, retiram-se os elementos da árvore em um percurso pós ordem, inserindo-os em uma pilha. Em seguida retiram-se os elementos da pilha, que são inseridos de volta nos vetores, começando pelo elemento 0 do vetor A e aumentando o índice em 1 a cada inserção, até preencher todas as N posições, inserindo, então, os N elementos restantes no vetor B da mesma maneira.
Ao final do processo, tem-se que os vetores:
a) estão ordenados e A[i] < B[i], para todo i=0,. , N-1.
b) estão ordenados e A[i] > B[i], para todo i=0,…., N-1.
c) estão ordenados e não existe mais uma propriedade que relacione A[i] e B[i].
d) não estão ordenados e A[i] < B[i], para todo i=0,…., N-1.
e) não estão ordenados e A[i] > B[i], para todo i=0,…., N-1.
Ele diz que nós temos dois vetores em que A[N-1] < B[0]. Então, vamos imaginá-los aqui:
- Vetor A = [1, 3, 5]
- Vetor B = [7, 9, 11]
Depois ele diz que são retirados todos os elementos de A na ordem que se apresentam e são inseridos em uma árvore binária de busca (lembre-se que uma árvore binária de busca é aquela em que todos os nós da subárvore esquerda possuem um valor numérico menor que o da raiz e os nós da subárvore direita
possuem um valor numérico maior que o da raiz).
Se você desenhar essa árvore, vai perceber que ela vai ficar em ordem toda para a direita - sem nenhum elemento para esquerda. Dito isso, ficou:
- 1, 3, 5, 7, 9, 11.
Depois ele disse que os elementos foram retirados da árvore em pós-ordem, ou seja, subárvore à esquerda, depois subárvore à direita e só depois raiz. Portanto, não tem elemento na esquerda, você retira o
elemento da direita e depois a raiz. E são colocados em uma pilha, logo ficaria:
- 11, 9, 7, 5, 3, 1
Lembrando que numa pilha você insere sempre elementos no topo, logo 1 seria o topo da pilha.
Depois ele diz que você retira os elementos da pilha (também sempre pelo topo) e coloca de volta nos vetores. Logo, ficaria:
- Vetor A = [1, 3, 5]
- Vetor B = [7, 9, 11]
Pronto! Note que fica exatamente a mesma coisa e os vetores ficariam ordenados e A[i] < B[i], para todo i=0,. , N-1. Bacana?
Gabarito: Letra A
- (FCC – 2017 – ARTESP) Considere a estrutura de dados abaixo.
Esta estrutura representa cinco localidades indicadas por 0, 1, 2, 3, 4 com as rotas e as respectivas distâncias entre
elas.
Por exemplo, da localidade 0 há rota para a localidade 1 (distância 10) e para a localidade 2 (distância 5). Um Especialista em Tecnologia da Informação da ARTESP afirma, corretamente, que
a) partindo de qualquer uma das localidades é possível ir para todas as outras e voltar para a localidade de
origem.
b) a distância da rota direta partindo de uma localidade x para uma localidade y não é a mesma da rota de retorno
de y para x.
c) a rota direta mais longa entre duas localidades é 9.
d) a rota mais curta partindo da localidade 3 e chegando na localidade 2 é 9.
e) é possível ir e voltar de todas as localidades adjacentes.
É possível desenhar as rotas da seguinte maneira:
Vamos analisar item a item:
a) partindo de qualquer uma das localidades é possível ir para todas as outras e voltar para a localidade de origem.
É possível ir a qualquer uma das localidades para todas as outras, e voltar para a localidade de origem. A banca definiu este item como errado. Acredito que tenha considerado que é possível, mas não diretamente, e, também, não pelo mesmo caminho. Falso.
b) a distância da rota direta partindo de uma localidade x para uma localidade y não é a mesma da rota de retorno de y para x.
As distâncias são diferentes, de fato.
Por exemplo, de 0 para 1, a distância é 10. Mas, de 1 para 0, é possível fazer o caminho 1-3-4-0, cuja distância é 1+4+7 = 12, ou o caminho 1-2-4-0, cuja distância é 2+2+7 = 11. Verdadeiro.
c) a rota direta mais longa entre duas localidades é 9.
A rota direta mais longa entre duas localidades é entre 0 e 1, cuja distância é 10. Falso.
d) a rota mais curta partindo da localidade 3 e chegando na localidade 2 é 9.
Temos duas rotas possíveis:
* 3-4-0-2: distância 4+7+5 = 16
* 3-4-0-1-2: distância 4+7+10+2 = 23
Falso.
e) é possível ir e voltar de todas as localidades adjacentes.
É possível ir e voltar, porém por caminhos diferentes. Falso.
Gabarito: Letra B
- (FGV - 2015 – TJ-RO – Analista Judiciário - Análise de Sistemas)
Se fosse construído um índice de banco de dados do tipo “bitmap” para essa tabela, tendo o campo Curso como chave, o conteúdo desse índice seria:
a)
6 3
23 3
45 1
57 1
210 3
356 2
1210 1
b)
Física 1001100
Química 0100000
Matemática 0010011
c)
6 001
23 001
45 100
57 100
210 001
356 010
1210 100
d)
0011001100
0100100000
0010010011
e)
00000000110 Matemática
00000010111 Matemática
00000101101 Física
00000111011 Física
00011010010 Matemática
00101100100 Química
10010111010 Química
A questão solicita a criação de um índice usando bitmap da coluna curso.
Lembrando da aula teórica que a tabela bitmap terá como linhas os valores da coluna fonte do índice, ou seja, Física, Química e Matemática. As colunas do bitmap são os números das tuplas
(ROWID) .
O conteúdo do bitmap é o preenchimento de acordo com o valor de cada tupla original relativo à coluna fonte do índice. Construindo o bitmap para curso temos:
A resposta, portanto, é a letra B.
Gabarito: B
- (CEBRASPE/POLC AL/2023)
Julgue o próximo item, no que se refere a estruturas de controle de fluxo.
// codigo 1
i = 1
fim = 7
enquanto i < fim faça
escreva(i)
i = i + 1
fim enquanto
depois = i
// codigo 2
fim = 6
i = 0
enquanto i < fim faça
i = i + 1
escreva(i)
fim enquanto
depois = i
Considerando a estrutura precedente, é correto afirmar que o código 1 e o código 2 apresentam o mesmo resultado.
Temos dois loops Enquanto.
Ambos possuem a mesma estrutura - serão executados enquanto a variável i for menor que a variável fim (i < fim) e, a cada iteração, incrementarão o valor da variável i em 1 unidade.
Vamos analisar a saída de cada código.
Código 1:
Iremos fazer 6 laços (de i = 1 a i = 6), e, a cada laço, iremos:
- Escrever o valor de i
- Incrementá-lo em uma unidade
Então, os laços serão os seguintes:
- Laço 1 - i = 1:
o escreva (i) → 1
o i = i + 1 → i = 2 - Laço 2 - i = 2:
o escreva(i) → 2
o i = i + 1 → i = 3 - Laço 3 - i = 3:
o escreva(i) → 3
o i = i + 1 → i = 4 - Laço 4 - i = 4:
o escreva(i) → 4
o i = i + 1 → i = 5 - Laço 5 - i = 5
o escreva(i) → 5
o i = i + 1 → i = 6 - Laço 6 - i = 6
o escreva(i) → 6
o i = i + 1 → i = 7
No laço 6, quebramos a condição e o bloco Enquanto. As saídas dessa estrutura foram (1, 2, 3, 4, 5, 6).
Código 2:
Iremos também fazer 6 laços, de i = 0 a i = 5. Aqui a ordem da execução da função muda:
- Primeiro somamos 1 ao valor de i
- Depois escrevemos o valor de i
Então, teremos os seguintes laços: - Laço 1 - i = 0
o i = i + 1 → i = 1
o escreva(i) → 1 - Laço 2 - i = 1
o i = i + 1 → i = 2
o escreva(i) → 2 - Laço 3 - i = 2
o i = i + 1 → i = 3
o escreva(i) → 3 - Laço 4 - i = 3
o i = i + 1 → i = 4
o escreva(i) → 4 - Laço 5 - i = 4
o i = i + 1 → i = 5
o escreva(i) → 5 - Laço 6 - i = 5
o i = i + 1 → i = 6
o escreva(i) → 6
A saída aqui será (1, 2, 3, 4, 5, 6).
Veja que temos a mesma saída - isso acontece pois a escrita do
valor da variável acontece antes do incremento no código 1, e depois do incremento no código
2. Sendo assim, correta a afirmativa.
Gabarito: Correto
- (VUNESP/TCM SP/2023)
Analise o algoritmo a seguir, apresentado na forma de uma
pseudolinguagem.
Início
[
Tipo MAT = matriz[1..3,1..3] de inteiros;
MAT: M;
Inteiro: i, j, X, Y;
X ← 0;
Y ← 0;
Para i de 1 até 3 faça
[
Para j de 1 até 3 faça
[
Se i = j
Então M[i,j] ← i + j + 1;
Senão M[i,j] ← i + 2*j + 1;
]
]
Para i de 1 até 3 faça
[
X ← X + M[i,i];
Y ← Y + M[1,i];
]
Imprima (X+Y);
] Fim.
Ao final do algoritmo é impressa a soma (X+Y) que é igual a
a) 29.
b) 30.
c) 31.
d) 32.
e) 33.
Em questões longas como essa, aconselho que analise o código com muita calma e cuidado, para entender a ordem de execução dos comandos.
Nessa questão, estamos executando um loop Para, visando preencher uma matriz 3x3.
Dentro desse loop, executamos outro Para que irá, de fato, preencher a lista. A interação de loops aninhados é a seguinte:
- Começamos a executar o loop externo com i = 1
- Executamos o loop interno de forma completa, com o j indo de 1 a 3
- Passamos para a execução do loop externo com i = 2, repetindo o processo, e para i = 3, repetindo o processo novamente
Então, como já sabemos quais valores começamos a execução do bloco mais interno do código,
vamos começar.
Laço 1 - i = 1; j = 1
Vamos executar um Se, que irá preencher:
- O elemento Mi, j com o valor i + j + 1, se i = j
- O elemento Mi, j com o valor i + 2*j + 1, caso contrário.
Como temos i = j no primeiro laço, caímos no bloco Se, então:
- M1, 1 = i + j + 1;
- M1, 1 = 1 + 1 + 1 = 3
Laço 2 - i = 1; j = 2
Agora, i =~ j, então caímos no bloco do senão. Então:
* M1, 2 = i + 2j + 1
* M1, 2 = 1 + 22 + 1 = 6
Laço 3 - i = 1; j = 3
Novamente, vamos ao bloco senão.
- M1, 3 = i + 2*j + 1
- M1, 3 = 1 + 2*3 + 1 = 8
Com isso encerramos o primeiro laço do loop externo, com i = 1.
Repetiremos esse processo pra
i = 2, e i = 3. Os resultados de cada iteração serão:
- Laço 3: M2, 1 = 5
- Laço 4: M2, 2 = 5
- Laço 5: M2, 3 = 9
- Laço 6: M3, 1 = 6
- Laço 7: M3, 2 = 8
- Laço 8: M3, 3 = 7
Com esses valores, conseguimos construir nossa matriz:
ÍNDICE 1 2 3
1 3 6 8
2 5 5 9
3 6 8 7
Bom, agora que temos a matriz, temos mais um loop para ser executado - e mais um loop Para, que vai de 1 até 3, ou seja, 3 iterações.
Nele, fazemos duas operações:
- Atribuímos incrementalmente o valor de M[i, i] à variável X
- Atribuímos incrementalmente o valor de M[1, i] à variável Y
Vamos resolver esses laços agora.
Laço 1 - i = 1:
* X = M1, 1
* X = 3
* Y = M[1, 1]
* Y = 3
Laço 2 - i = 2:
* X = X + M2, 2
* X = 3 + 5
* X = 8
* Y = Y + M1, 2
* Y = 3 + 6
* Y = 9
Laço 3 - i = 3:
* X = X + M3, 3
* X = 8 + 7
* X = 15
* Y = Y + M1, 3
* Y = 9 + 8
* Y = 17
Então, terminamos com X = 15 e Y = 17.
Por fim, finalmente (ufa), fazemos a soma dos valores
para encontrar a resposta:
X + Y = 15 + 17 = 32
Gabarito: Letra D