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
- (CESGRANRIO/Petrobras/2014) Sejam quatro processos criados no instante de tempo 0 (P1 , P2 , P3 e P4 ) e que possuam as características descritas na Tabela a seguir.
Considerando-se um tempo de troca de contexto igual a 4 u.t., qual é o tempo de turnaround de cada processo caso a política de execução de processos seja a SJF?
A) P1-11/ P2- 40/P3 -56/P4-68
B) P1-19/ P2-56/P3 -31/P4-8
C) P1-23/ P2-68 / P3-39/ P4-8
D) P1-27/ P2 -68/P3 - 43/P4-12
E) P1-40/ P2 - 25/P3-35/ P4-52
O tempo de turnaround é o tempo de existência de um processo, ou seja, o tempo desde a sua criação até seu término.
As políticas de escalonamento buscam minimizar o tempo de turnaround.
A política SJF (Shortest Job First) executa todo o processo menor, depois o segundo menor e assim por diante.
Pegadinha!!! A prioridade não importa para a política SJF, então aquela coluna na tabela só serve pra atrapalhar!!! Sabendo que o tempo de troca de contexto é de 4 u.t.
(unidades de tempo), temos:
● P4 (8 u.t.): terminou a execução em 8 u.t.;
● troca de contexto (4 u.t.);
● P1 (11 u.t.): terminou a execução em 23 u.t.
(8 + 4 + 11);
● troca de contexto (4 u.t.);
● P3 (12 u.t.): terminou a execução em 39 u.t. (8 + 4 + 11 + 4 + 12);
● troca de contexto (4 u.t.);
● P2 (25 u.t.): terminou a execução em 68 u.t.
(8 + 4 + 11 + 4 + 12 + 4 + 25).
Gabarito: C
- (CESGRANRIO/IBGE/2016) Seja um sistema operacional que implementa multiprogramação e mantém cinco processos simultaneamente na memória. Considere-se ainda que os processos são independentes, com tempo de overhead desprezível (igual a zero).
Sabe-se que todos os processos demandam exatos 40% do tempo aguardando a conclusão de operação de entrada e saída.
Nesse caso, qual é o percentual de utilização do processador?
A) 1,02%
B) 6,25%
C) 60,00%
D) 93,75%
E) 98,98%
Questão de probabilidade e não de sistemas operacionais!!! 🙂
Mas vamos lá… pense no seguinte: são 5 processos e mesmo que 4 estejam bloqueados (aguardando a conclusão de uma operação de entrada e saída), 1 estaria usando o processador.
Então a única situação em que o processador fica ocioso é quando os 5 processos estiverem aguardando a conclusão de uma operação de entrada e saída.
Cada processo demanda 40% do tempo aguardando a conclusão de uma operação de entrada e saída, como está no enunciado.
Lembrando que a multiplicação significa “E”, então a probabilidade de P1 E P2 E P3 E P4 E P5 estarem aguardando E/S é 0,4 x 0,4 x 0,4 x 0,4 x 0,4 = 0,01024 (ou 1,024%).
Logo, 100% - 1,024% = 98,976% de probabilidade do processador estar em uso. Arredondando, fica 98,98%.
Gabarito: E
- (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
- (FCC – 2017 – ARTESP) Nas rodovias paulistas os veículos pagam pedágio em função do número de eixos e da sua categoria. Há 15 categorias de veículos. Para realizar o cálculo do pedágio, existe uma tarifa mínima que é multiplicada por um valor relativo ao número de eixos.
Considere a estrutura abaixo que indica a categoria do veículo pelo número da coluna; na primeira linha armazena a quantidade de eixos; na segunda linha armazena o valor pelo qual a tarifa mínima deve ser multiplicada.
Exemplos: o veículo 0 é motocicleta / motoneta / bicicleta a motor que tem 2 eixos, mas é isento; o veículo 2 é caminhonete / furgão que tem 2 eixos e paga 1 tarifa; o veículo 13 é um caminhonete/automóvel com reboque que
tem 4 eixos e paga 2 tarifas.
Considerando que n é a categoria do veículo, que tm é a tarifa mínima e que a estrutura é denominada mpedagio, o trecho em pseudocódigo que calcula vp, o valor pedágio, corretamente, é:
a) vp ← mpedagio[n,0] * mpedagio[n,1] * tm
b) vp ← mpedagio[1,n] * tm
c) vp ← vp + (mpedagio[0,n] + mpedagio[1,n]) * tm
d) vp ← (mpedagio[n,0]/ mpedagio[n,1]) * tm
e) se (n = 0) então vp ← 0 senão vp ← (mpedagio[0,n]/ 2) * tm fim se
A primeira linha do mpedagio armazena a quantidade de eixos do veículo;
já a segunda, armazena o valor pelo qual a
tarifa deve ser multiplicada.
Então, o valor do pedágio será justamente o valor na linha 1, na coluna n (mpedagio[1,n]), multiplicado por tm. Ou seja, vp ← mpedagio[1,n] * tm.
As demais alternativas estão incorretas.
Gabarito: Letra B
