Handbook de TI - Estruturas de Dados para concursos - Questões comentadas

Prévia do material em texto

Questões comentadas
Estruturas de Dados
para concursos
Handbook de Questões de TI Comentadas para Concursos Volume questões de TI
Prefácio
A eficiência de um algoritmo está associada à forma com que seus dados estão organizados.
As diferentes formas de organização de dados para atender os diferentes requisitos dos algorit-
mos, no ramo da Ciência da Computação, são chamadas de Estruturas de Dados.
Atualmente, as soluções de software demandam por algoritmos cada vez mais complexos. Para
desenvolver algoritmos complexos e eficientes, o desenvolvedor precisa dominar os conceitos das
diversas estruturas de dados: vetores, listas, filas, pilhas, árvores, grafos e hashs; bem como as
diversas técnicas de busca e ordenação de dados.
É por este motivo que diversos concursos na área de Tecnologia de Informação têm cobrado
este tema, como forma de examinar o conhecimento e a capacidade dos candidatos em prover
algoritmos complexos e eficientes, utilizando diferentes formas de estrutura de dados.
Este volume foi preparado pelo Grupo Handbook de TI justamente para suprir esta lacuna,
fornecendo uma série que questões de estrutura de dados comentadas em detalhes para você.
Bons estudos,
Grupo Handbook de TI
Página 1 de 28
www.handbookdeti.com.br
Handbook de Questões de TI Comentadas para Concursos Volume questões de TI
Direitos Autorais
Este material é registrado no Escritório de Direitos Autorais (EDA) da Fundação Biblioteca
Nacional. Todos os direitos autorais referentes a esta obra são reservados exclusivamente aos
seus autores.
Os autores deste material não proíbem seu compartilhamento entre amigos e colegas próxi-
mos de estudo. Contudo, a reprodução, parcial ou integral, e a disseminação deste material de
forma indiscriminada através de qualquer meio, inclusive na Internet, extrapolam os limites da
colaboração. Essa prática desincentiva o lançamento de novos produtos e enfraquece a comuni-
dade concurseira Handbook de TI.
A série Handbook de Questões de TI Comentadas para Concursos � Além do Gabarito é uma
produção independente e contamos com você para mantê-la sempre viva.
Grupo Handbook de TI
Página 2 de 28
www.handbookdeti.com.br
Handbook de Questões de TI Comentadas para Concursos Volume questões de TI
Canais de Comunicação
O Grupo Handbook de TI disponibiliza diversos canais de comunicação para os concurseiros
de TI.
Loja Handbook de TI
Acesse a nossa loja virtual em http://www.handbookdeti.com.br
Serviço de Atendimento
Comunique-se diretamente conosco através do e-mail faleconosco@handbookdeti.com.br
Twitter do Handbook de TI
Acompanhe de perto promoções e lançamentos de produtos pelo nosso Twitter http://twitter.
com/handbookdeti
Página 3 de 28
www.handbookdeti.com.br
Handbook de Questões de TI Comentadas para Concursos Volume questões de TI
1. Assuntos relacionados: Métodos de Busca, Pesquisa Binária, Árvore B,
Banca: CESGRANRIO
Instituição: BNDES
Cargo: Analista de Suporte
Ano: 2008
Questão: 50
Os dados de uma agenda contendo nome, telefone e endereço de pessoas estão organizados
em um arquivo de dados com acesso somente de leitura. Um dispositivo eletromecânico D,
que possibilita acesso direto, contém, aproximadamente, 90 milhões de registros ordenados
por nome. Assumindo que o tamanho do campo endereço é variável e que D pode ter
arquivos (pré-existentes) de índices que se referenciam ao arquivo de dados, e supondo que
não possui cache, qual é a estratégia que realizará, em média, menos operações de I/O para
consultar todos os registros cujo nome começa por uma determinada letra?
(a). Pesquisa binária diretamente sobre o arquivo de dados, uma vez que já existe
ordenação por nome.
(b). Pesquisa sobre o arquivo de índices indexados pelo nome, implementando um
algoritmo de busca em uma árvore B-Tree balanceada.
(c). Pesquisa seqüencial sobre um arquivo de índices indexado pelas letras do alfabeto e
posterior leitura sequencial sobre o arquivo de dados, nos quais cada índice aponta
para o endereço do início da respectiva letra na agenda.
(d). Pesquisa binária sobre um arquivo de índices indexado pelo nome, para posterior
acesso ao arquivo de dados.
(e). Leitura seqüencial diretamente sobre o arquivo de dados, sem a utilização de ar-
quivos auxiliares de índice.
Solução:
(A) ERRADA
Para que fosse possível pesquisa binária diretamente sobre arquivo de dados, como seus
registros tem tamanhos variáveis, seria necessário incluir informações que serviriam de �pon-
teiros� em cada registro. O que não é possível, já que o arquivo de dados permite apenas
leitura. Portanto, a alternativa A não é possível.
(B) ERRADA
De maneira geral, a abordagem por B-Tree é uma boa opção. Entretanto, é importante
observar que para recuperar cada registro é necessária uma consulta à B-Tree e posteri-
ormente ao arquivo de dados. Tal implementação utilizaria um número de operações da
ordem (n/26)/*log(n), onde n é o número total de registros. Analisaremos as outras opções
adiante. Note que a opção nem explicitou como seria o acesso ao arquivo de dados.
(C) CORRETA
Essa é uma opção bem eficiente para o caso, já que será necessário apenas encontrar a
letra do alfabeto correspondente (mesmo que de maneira sequencial) no arquivo de índices
e depois percorrer sequencialmente o arquivo de dados. A ordem neste caso é 13+n/26. Ou
seja, mais rápido que o caso descrito na alternativa B.
Página 4 de 28
www.handbookdeti.com.br
Handbook de Questões de TI Comentadas para Concursos Volume questões de TI
(D) ERRADA
O caso e o custo são muito parecidos com aqueles explicitados na alternativa B e, como
consequência, o seu resultado não supera o desempenho descrito na alternativa C.
(E) ERRADA
Neste caso, a ordem seria percorrer o arquivo de dados até encontrar o primeiro registro
cujo nome começa com a letra especificada e depois percorrer todos os elementos que aten-
dam a condição. O custo seria da ordem n/2+n/26.
Concluímos que a alternativa mais eficiente é a alternativa C.
Página 5 de 28
www.handbookdeti.com.br
Handbook de Questões de TI Comentadas para Concursos Volume questões de TI
2. Assuntos relacionados: Estruturas de Dados, Árvore B,
Banca: CESGRANRIO
Instituição: Petrobras
Cargo: Analista de Sistemas - Eng. de Software
Ano: 2008
Questão: 59
Considere uma árvore B de grau mínimo igual a 2 (o que significa que cada nó pode ter, no
máximo, 3 chaves) inicialmente vazia, na qual são inseridas as chaves N, D, T, B, Z, K, R,
F, G, nesta ordem, as quais são comparadas com base na ordem do alfabeto. Considerando
o algoritmo de inserção em uma única passagem, conclui-se que
(a). a altura da árvore resultante será 3.
(b). B estará em um nó interno.
(c). o nó raiz conterá a chave K.
(d). haverá 4 nós folhas.
(e). F e G pertencerão à mesma folha.
Solução:
Árvores B são árvores de busca balanceadas projetadas para trabalhar com discos magnéti-
cos ou outros dispositivos de armazenamento secundário.
Antes de solucionarmos a presente questão, é de enorme importância que vejamos algu-
mas características da árvore B. São elas:
• para um dado nó x, n[x] representa o atual número de chaves armazenadas em x;
• as n[x] chaves são armazenadas em ordem não-decrescente (chave1[x] ≤ chave2[x] ≤ ...
≤ chaveN[x]);
• folha[x] é um valor booleano verdadeiro se x é folha e falso se x é um nó interno;
• se x é um nó interno, então ele contém n[x] + 1 ponteiros para os seus filhos. Nesse
caso, note que os nós folhas, os quais estão localizados nos extremos da árvore, não
têm filhos;
• as chaves existentes em um nó x separam as faixas de chaves armazenadas em cada
sub-árvore. Por exemplo, considere um nó x que contém apenas uma chave de valor V
(oque significa, como já vimos, que ele poderá possuir até dois nós filhos: sub-árvore
esquerda e sub-árvore direita). Nesse cenário, qualquer chave com valor menor que V
encontrar-se-á na sub-árvore esquerda. Por outro lado, chaves com valor maior que V
estarão localizadas na sub-árvore direita;
• em uma árvore B, todas as folhas se encontram na mesma profundidade, a qual é
representada pela altura da árvore. Por convenção, o nó raiz da árvore B encontra-se
na altura 0 (zero);
• existem limites máximos e mínimos no número de chaves que um nó pode conter. Esse
limite é expressado em termos do grau mínimo da árvore B (considerado, aqui, como
um parâmetro t). Assim, cada nó diferente da raiz deve ter, pelo menos, t - 1 chaves,
isto é, no mínimo t filhos (se a árvore é não-vazia, o nó raiz deve ter pelo menos uma
chave). No que se refere ao limite máximo, cada nó pode conter até 2t - 1 chaves, ou
seja, 2t filhos;
Página 6 de 28
www.handbookdeti.com.br
Handbook de Questões de TI Comentadas para Concursos Volume questões de TI
• quando da tentativa de inserção de uma chave em um nó x cheio (contendo 2t - 1 cha-
ves), uma operação fundamental, denominada split, é efetuada. Tal operação consiste
em: dividir o nó x em dois nós filhos, cada um contendo t - 1 chaves; mover a chave
mediana de x para o nó pai de x. Se x não possuir nó pai, então a árvore cresce em
altura por um;
• antes da inserção de uma chave em um nó x cheio, devemos assegurar que o nó pai de
x também não esteja cheio antes do split de x, evitando, dessa forma, que splits sejam
realizados recursivamente;
• após a ocorrência de um split, a nova chave será inserida no nó folha existente em uma
das sub-árvores criadas.
Agora estamos aptos a resolver a presente questão. O primeiro passo da criação de uma
árvore B consiste em alocar um nó raiz vazio, o qual não possui chaves e, logicamente, nem
nós filhos. Em seguida, nós iremos inserir as chaves, uma a uma, respeitando os limites que
os nós possuem. No caso da árvore em questão, com t igual a 2, um nó terá no mínimo uma
chave e no máximo 3 chaves. A Figura 1, apresenta, passo a passo, a inserção de cada chave
(nós que são modificados pelo processo de inserção estão sombreados).
Ao observarmos a Figura 1, podemos notar que:
• 1) representa o estado inicial da nossa árvore, a qual contém apenas um nó (raiz) vazio;
• 2), 3) e 4) são os resultados das inserções das respectivas chaves, N, D e T, o que nada
mais é que uma simples inserção no nó raiz;
• 5) é o resultado da inserção da chave B na árvore prévia. O nó raiz DNT, que está
cheio, é dividido em dois nós contendo D e T, a chave N é movida para o novo nó raiz,
e a árvore B cresce em altura por um;
• 6) é o resultado da inserção da chave Z na árvore prévia, a qual é uma simples inserção
na folha;
• O mesmo ocorre em 7) e 8) para as chaves K e R, respectivamente;
• 9) é o resultado da inserção da chave F. O nó folha BDK é divido antes de F ser inserida
no nó mais a direita das duas folhas (nó K);
• 10) é o resultado da inserção da chave G na folha FK.
Portanto, a resposta correta é a alternativa E.
Página 7 de 28
www.handbookdeti.com.br
Handbook de Questões de TI Comentadas para Concursos Volume questões de TI
Figura 1: inserção de chaves em uma árvore B.
Página 8 de 28
www.handbookdeti.com.br
Handbook de Questões de TI Comentadas para Concursos Volume questões de TI
3. Assuntos relacionados: Estruturas de Dados, Pilha,
Banca: CESGRANRIO
Instituição: BNDES
Cargo: Analista de Suporte
Ano: 2008
Questão: 69
Seja P uma pilha que, inicialmente vazia, sofre, sequencialmente, as seguintes operações:
PUSH(P,3)
PUSH(P,5)
POP(P)
PUSH(P,7)
PUSH(P,9)
PUSH(P,6)
PUSH(P,2)
POP(P)
POP(P)
PUSH(P,8)
PUSH(P,1)
POP(P)
POP(P)
POP(P)
Qual a soma dos valores dos elementos restantes de P?
(a). 10
(b). 9
(c). 16
(d). 19
(e). 35
Solução:
Pilha é uma estrutura de dados que implementa uma fila do tipo LIFO (Last In, First
Out). As duas operações básicas para manipulação de pilhas são: PUSH e POP. O PUSH é
utilizado para adicionar um novo dado ao topo da pilha, enquanto o POP é utilizado para
remover o último elemento inserido. A Figura 2 mostra os estados da pilha P após serem
aplicadas cada uma das operações da sequência em questão.
Figura 2: sequência de estados da pilha P.
Portanto, após a sequência de operações, a soma dos elementos restantes é 7 + 3 = 10.
Página 9 de 28
www.handbookdeti.com.br
Handbook de Questões de TI Comentadas para Concursos Volume questões de TI
As pilhas são largamente utilizadas em vários níveis dos sistemas computacionais moder-
nos, sendo tipicamente úteis para manipulação de interrupções, tanto de hardware quanto
de software. Nesses casos, são armazenados nas pilhas os endereços das instruções a serem
executadas pelo computador.
São estruturas de dados do tipo pilha que permitem que o fluxo de execução dos programas
seja desviado por meio da chamada de funções. Os leitores que tiverem alguma experiência
com programação recursiva, em especial em C, já devem ter se deparado com o erro Control
Stack Overflow. Isso acontece quando, por um erro de definição da condição de parada da
recursão, novas chamadas da função recursiva vão sendo feitas até que o espaço alocado para
a pilha de execução se esgote, abortando a execução do programa.
Página 10 de 28
www.handbookdeti.com.br
Handbook de Questões de TI Comentadas para Concursos Volume questões de TI
4. Assuntos relacionados: Estruturas de Dados, Fila, Árvore, Lista Encadeada, Pilha,
Banca: ESAF
Instituição: Secretaria do Tesouro Nacional (STN)
Cargo: Analista de Finanças e Controle - Tecnologia da Informação / Desenvolvimento de
Sistemas de Informação
Ano: 2008
Questão: 18
Navegadores Web armazenam as URLs (Uniform Resource Locators) visitadas recentemente
em uma determinada estrutura de dados. Com isso, permite que o usuário visite o último
site visitado, ao recuperar a URL na estrutura, usando uma operação de retorno (back). A
estrutura de dados apropriada para implementar este recurso é a
(a). fila.
(b). árvore.
(c). lista encadeada simples.
(d). lista encadeada dupla.
(e). pilha.
Solução:
O problema acima, dos Navegadores Web, descrevem uma forma de armazenamento de
URL que possui como característica a funcionalidade de recuperar a última URL acessada.
A seguir iremos fazer uma breve descrição sobre as estrutura de dados mais conhecidas,
respectivamente, fila, árvore, lista, e pilha.
(A) ERRADA
Uma fila é simplesmente uma lista de informações que é acessada na ordem primeira a
entrar, primeiro a sair, sendo chamada de FIFO (First Int, First Out). Isto é, o primeiro
elemento colocado na fila é o primeiro a ser retirado, o segundo elemento colocado é o
segundo a ser recuperado e assim sucessivamente. Essa é a única forma de armazenar e
recuperar em uma fila, não é permitido acesso a nenhum item específico.
(B) ERRADA
Uma árvore é uma estrutura de dados que organiza seus elementos de forma hierárquica.
Cada elemento em uma árvore consiste de informação juntamente com um ponteiro para o
membro esquerdo e um ponteiro para o membro direito. A raiz é o primeiro elemento em
uma árvore. Cada elemento de dado é chamado de nó da árvore e qualquer parte da árvore
é chamada de uma subárvore. Um nó que não tem subárvore ligadas a ele é chamado de nó
terminal.
(C) ERRADA
Um lista encadeada é uma estrutura de dados onde cada elemento possui um ligação com
um/dois elementos. Cada elemento possui um dado e um/dois ponteiros para o(s) ele-
mento(s) subsequentes.
Uma lista encadeada pode acessar seu armazenamento de forma randômica, porque cada
Página 11 de 28
www.handbookdeti.com.br
Handbookde Questões de TI Comentadas para Concursos Volume questões de TI
porção de informação carrega consigo um ponteiro ao próximo elemento de dados na lista.
Uma lista simplesmente encadeada requer que cada elemento de informação contenha um
ponteiro com o próximo elemento da lista. Cada elemento de dado geralmente consiste em
uma estrutura que inclui campos de informação e ponteiro de ligação com o próximo ele-
mento.
(D) ERRADA
Uma lista duplamente encadeada consiste em dados e ponteiros para o próximo elemento e
para o item anterior. O fato de ter dois ponteiros em lugar de um tem a vantagem da lista
poder ser lida em ambas as direções.
(E) CORRETA
Uma pilha é o inverso de uma fila porque usa o acesso no formato de último a entrar,
primeiro a sair, o que algumas vezes é chamado de LIFO (Last In, First Out). Para visua-
lizar uma pinha imagine uma pinha de pratos. O primeiro prato na mesa é o último a ser
usado e o último prato colocado na pilha é o primeiro a ser usado. Pilhas são usadas em
grande quantidade em software de sistema. As duas operações básicas da pilha são:
• push: coloca um elemento no topo da pilha;
• pop: remove (recupera) um elemento do topo da pinha, ou seja, o último elemento da
lista.
Portanto, a única estrutura de dados que possui uma funcionalidade de recuperar o último
elemento inserido é a estrutura pilha, desta forma, a letra correta é a E.
Página 12 de 28
www.handbookdeti.com.br
Handbook de Questões de TI Comentadas para Concursos Volume questões de TI
5. Assuntos relacionados: Estruturas de Dados, Árvores Binárias, Árvores AVL,
Banca: FCC
Instituição: TRT 18a Região
Cargo: Analista Judiciário - Tecnologia da Informação
Ano: 2008
Questão: 24
Árvore AVL balanceada em altura significa que, para cada nó da árvore, a diferença entre
as alturas das suas sub-árvores (direita e esquerda) sempre será
(a). menor ou igual a 2.
(b). igual a 0 ou -1.
(c). maior que 1.
(d). igual a 1.
(e). igual a -1, 0 ou 1.
Solução:
As árvores binárias de pesquisa são projetadas para um acesso rápido à informação. Ide-
almente a árvore deve ser razoavelmente equilibrada e a sua altura será dada (no caso de
estar completa). Contudo, com alguns dados, a árvore binária de pesquisa pode degenerar,
tendo no pior caso altura n-1, tornado-se o acesso muito mais lento, O(n). É o que acontece
no caso em que a construção da árvore é feita por inserções sucessivas e os valores são dados
com chaves ordenadas (crescentes ou decrescentes).
Adelson-Velskii e Landis, em 1962, apresentaram uma árvore de busca binária que é ba-
lanceada com respeito a altura das sub-árvores. Uma característica importante deste tipo
de árvore é que uma busca é realizada em O(log(n)) se a árvore possui n nós. Em uma árvore
AVL, cada nó está equilibrado em altura, significando isto que, em cada nó, a diferença de
alturas entre as subárvores esquerda e direita é no máximo 1. Uma outra definição para
árvores AVL será aquela em que para qualquer nó P se verifica que o módulo do fator de
equilíbrio é sempre menor ou igual a um. Entende-se por fator de equilíbrio de um nó P a
diferença da altura da subárvore esquerda de P e altura da subárvore direita de P. Dado o
exposto, a alternativa correta da questão é a letra E.
Uma árvore AVL terá uma estrutura semelhante a uma árvore binária de pesquisa com
a condição de que a árvore de pesquisa mantém-se equilibrada em altura depois de cada
operação de inserção e eliminação.
Também há um tipo de árvore binária que garante a busca em O(log(n)) conhecida como
árvore rubro-negra. Entretanto, ela não tem a mesma propriedade em relação ao fator de
equilíbrio. Uma propriedade garantida da árvore rubro-negra é que, caso ela possua n nós,
ela terá altura menor ou igual à 2log(n+1).
Página 13 de 28
www.handbookdeti.com.br
Handbook de Questões de TI Comentadas para Concursos Volume questões de TI
6. Assuntos relacionados: Estruturas de Dados, Árvores Binárias, Árvore Binária de Busca,
Banca: Cesgranrio
Instituição: Petrobras
Cargo: Analista de Sistemas Pleno - Processos
Ano: 2006
Questão: 50
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.
Solução:
Classicamente, uma árvore binária é definida como uma estrutura de dados com as seguintes
características:
• não ter elemento algum (uma árvore vazia);
• ter um elemento distinto (nó raiz da árvore), com dois ponteiros para estruturas dis-
tintas, denominadas sub-árvore esquerda e sub-árvore direita.
Cada um dos dois nós sub-sequentes a um nó raiz (nó da esquerda e nó da direita) são
chamados filhos do nó raiz.
Uma árvore binária de busca (ou árvore de busca binária ou árvore de pesquisa binária)
é organizada em uma árvore binária, sendo uma estrutura onde todos os nós possuem cha-
ves que são valores e, por padrão, os nós à esquerda formam uma sub-árvore com valores
inferiores ao do nó raiz e os nós à direita formam uma sub-árvore com valores superiores ao
do nó da raiz. Assim, as chaves em uma árvore binária de busca são sempre armazenadas
satisfazendo à propriedade de árvore de pesquisa binária:
Seja x um nó em uma árvore binária de busca. Se y é um nó na sub-árvore esquerda
de x, então chave[y] <= chave[x]. Se y é um nó na sub-árvore direita de x, então chave[x]
<= chave[y].
Página 14 de 28
www.handbookdeti.com.br
Handbook de Questões de TI Comentadas para Concursos Volume questões de TI
Essa propriedade orienta tanto a busca por valores na árvore quanto a inserção de novos nós,
que são operações recorrentes nessa estrutura de dados. Uma outra operação interessante,
que permite a impressão de todos os valores armazenados em uma árvore binária de busca,
é chamada de percurso e pode-se dar, de acordo com a literatura comumente encontrada, de
três formas distintas: percurso de árvore em ordem (ou em ordem simétrica), percurso de ár-
vore de pré-ordem (ou em pré-ordem) e percurso de árvore de pós-ordem (ou em pós-ordem).
Há, ainda, autores que registram um quarto tipo de percurso conhecido como percurso em
largura (ou percurso em nível).
No percurso de árvore em ordem simétrica, a chave da raiz de uma sub-árvore é impressa
entre os valores de sua sub-árvore esquerda e aqueles de sua sub-árvore direita. Semelhan-
temente, o percurso de árvore de pré-ordem imprime a raiz antes dos valores em uma ou
outra sub-árvore, e o percurso de árvore de pós-ordem imprime a raiz depois dos valores
contidos em suas sub-árvores. Esses três tipos de percurso, definidos recursivamente, são
considerados percursos em profundidade.
O percurso em nível (percurso em largura), mais bem compreendido de forma não-recursiva,
visita os nós na ordem em que aparecem nos níveis da árvore: primeiramente, são visitados
todos os nós do nível 0; em seguida, visitam-se os nós do próximo nível; e assim por diante.
Em geral, os nós são visitados da esquerda para a direita em cada um dos níveis.
Dadas as informações apresentadas na questão, tem-se a seguinte árvore binária de busca:
Figura 3: exemplo defigura.
Como �Lina� é o primeiro valor apresentado à árvore binária de busca que está inicialmente
vazia, ele é considerado a raiz da árvore principal. O valor seguinte, �Ana�, é considerado me-
nor do que o anterior (critério: ordem alfabética) e, portanto, deverá ser inserido à esquerda
do nó raiz. O valor seguinte, �Lia�, também é inferior ao valor da raiz e, consequentemente,
será inserido à esquerda do mesmo. Como é superior ao valor �Ana� já presente, situar-se-á
à direita do mesmo. E assim por diante.
Um percurso em pré-ordem (isto é, um percurso no qual a raiz é visitada antes de seus
filhos) é Lina, Ana, Ada, Lia, Cris, Bia, Lua, Sol, Rita, Mel, Rosa, Val. Observa-se que a
raiz de cada (sub-)árvore é visita antes de seus filhos (�Lina� vem antes de �Ana� e �Lua�,
�Ana� vem antes de �Ada� e �Lia�, e assim sucessivamente) e na sequência visitam-se pri-
meiramente os filhos da esquerda e, em seguida, os filhos da direita. A outra opção para um
percurso em pré-ordem, agora visitando os filhos da direita antes dos filhos da esquerda, é
Lina, Lua, Sol, Val, Rita, Rosa, Mel, Ana, Lia, Cris, Bia, Ana.
Página 15 de 28
www.handbookdeti.com.br
Handbook de Questões de TI Comentadas para Concursos Volume questões de TI
Um percurso em ordem simétrica (isto é, um percurso no qual a raiz aparece entre seus
filhos) é Ada, Ana, Bia, Cris, Lia, Lina, Lua, Mel, Rita, Rosa, Sol, Val. Considerou-se a
visita aos filhos da esquerda antes dos filhos da direita. A ordem inversa, ou seja, filhos
da direita antes dos filhos da esquerda, também é possível: Val, Sol, Rosa, Rita, Mel, Lua,
Lina, Lia, Cris, Bia, Ana, Ada.
Para a árvore dada, um percurso em pós-ordem (isto é, a raiz é visita após seus filhos),
visitando primeiramente os filhos da esquerda, é Ada, Bia, Cris, Lia, Ana, Mel, Rosa, Rita,
Val, Sol, Lua, Lina. Visitando os filhos da direita antes dos filhos da esquerda, o outro
percurso em pós-ordem é Val, Rosa, Mel, Rita, Sol, Lua, Bia, Cris, Lia, Ada, Ana, Lia.
Para o percurso em nível, tem-se Lina, Ana, Lua, Ada, Lia, Sol, Cris, Rita, Val, Bia,
Mel, Rosa como um percurso que realiza uma visita aos filhos da esquerda antes dos filhos
da direita. Inversamente, visitando os filhos da direita primeiramente, obtêm-se Lina, Lua,
Ana, Sol, Lia, Ada, Val, Rita, Cris, Rosa, Mel, Bia.
Apenas as assertivas II e III condizem com a teoria exposta. As demais, buscam confundir
o candidado, �embaralhando� resultados possíveis (a assertiva I é um percurso em nível e a
assertiva IV apresenta um percurso em pré-ordem). Desta forma, a resposta da questão é a
letra (B).
Página 16 de 28
www.handbookdeti.com.br
Handbook de Questões de TI Comentadas para Concursos Volume questões de TI
7. Assuntos relacionados: Programação, Estruturas de Dados, Tabela Hash,
Banca: FCC
Instituição: TRT 15a Região
Cargo: Analista Judiciário - Tecnologia da Informação
Ano: 2009
Questão: 22
Uma estrutura de dados especial de armazenamento de informações, cuja ideia central é
utilizar uma função que, quando aplicada sobre uma chave de pesquisa, retorna o índice
onde a informação deve ser armazenada denomina-se
(a). vetor de dispersão.
(b). matriz de dispersão.
(c). tabela hash.
(d). árvore binária.
(e). lista encadeada
Solução:
A resposta da questão é a alternativa C, tabela hash, que também é conhecida como tabela
de espalhamento ou de dispersão.
A implementação de uma tabela hash se baseia na escolha de uma função, chamada função
hash, que associe uma chave de pesquisa a um índice em uma estrutura de dados. O requisito
mais importante de uma função hash é o de distribuir uniformemente as chaves pelos vários
índices, de forma eliminar ou minimizar a chance de que mais de uma chave seja mapeada
para o mesmo índice, problema conhecido como colisão.
Por mapearem uma chave de pesquisa a um determinado índice de forma direta, as ta-
belas hash proporcionam um tempo médio de busca constante, ou seja, O(1). Em virtude
de seu alto desempenho, as tabelas hash são tipicamente utilizadas na indexação de gran-
des volumes de informações em bancos de dados e na criação de esquemas associativos de
acesso às memória cache. A Figura 4 mostra, de forma básica, como se dá o esquema de
mapeamento de chaves em índices usando uma tabela hash.
Figura 4: Tabela Hash.
No entanto, a definição de uma boa função hash nem sempre é uma tarefa simples, sendo
um trabalho trabalho profundamente relacionado à estatística. Portanto, para otimizar a
Página 17 de 28
www.handbookdeti.com.br
Handbook de Questões de TI Comentadas para Concursos Volume questões de TI
função hash, é necessário conhecer a natureza da chave a ser utilizada e como os valores que
a chave pode assumir se distribuem ao longo do domínio. Os métodos de implementação de
funções hash mais comuns são o método da divisão, o método da dobra, e o método da
multiplicação.
Com relação às limitações das tabelas hash, valem as seguintes observações. As tabelas
hash são estruturas de dados que não permite armazenar elementos repetidos, recuperar
elementos sequencialmente, nem recuperar antecessores ou sucessores de um determinado
elemento já encontrado. Caso essas operações tenham muita importância no sistema, vale a
pena considerar a utilização de estruturas de dados como listas encadeadas, árvores, entre
outras.
Página 18 de 28
www.handbookdeti.com.br
Handbook de Questões de TI Comentadas para Concursos Volume questões de TI
8. Assuntos relacionados: Programação, Estruturas de Dados,
Banca: ESAF
Instituição: Receita Federal (RF)
Cargo: Técnico da Receita Federal - Tecnologia da Informação
Ano: 2006
Questão: 21
Analise as seguintes afirmações relacionadas a Noções de Programação:
I. Quando uma função é chamada e os parâmetros formais da função copiam os valores
dos parâmetros que são passados para ela, sem que ocorra alteração dos valores que os
parâmetros têm fora da função, este tipo de chamada de função é denominado chamada
com passagem de parâmetros por valor. Isso ocorre porque são passados para a função
apenas os valores dos parâmetros e não os próprios parâmetros.
II. Uma função que pode chamar a si própria é chamada função recursiva. Um critério
de parada vai determinar quando a função deverá parar de chamar a si mesma. Isso
impede que a função entre em loop.
III. Uma fila é uma lista de informações com operações especiais de acesso. O acesso aos
elementos da fila é feito pela extremidade oposta à da inserção, ou seja, o elemento
disponível estará sempre na extremidade oposta à da inserção. Esta regra é também
conhecida como LIFO (Last In First Out).
IV. No desenvolvimento estruturado, uma boa prática de modularização é proporcionar
um alto acoplamento entre os módulos, mantendo a dependência lógica e liberdade de
comunicação entre eles.
Indique a opção que contenha todas as afirmações verdadeiras.
(a). II e III
(b). I e II
(c). III e IV
(d). I e III
(e). II e IV
Solução:
Vamos analisar as afirmativas separadamente, pois termos diferentes são utilizados em cada
uma.
I. CORRETA. Na passagem de parâmetros por valor, a função recebe uma cópia dos
argumentos quando é invocada. Ou seja, as alterações de valor nas variáveis que repre-
sentam os argumentos não é propagado fora do escopo da função. Já na passagem de
parâmetros por referência, são enviadas internamente para a função, as referências dos
argumentos que foram passados, e não uma simples cópia. Os valores alterados, neste
caso, irão ser efetivados fora do escopo da função.
II. CORRETA. Uma função recursiva é uma função que pode invocar a si própria. Em
toda função recursiva existem dois passos importantes: o passo básico e o passo re-
cursivo. O passo básico é o passo em que o resultado é imediatamenteconhecido, já
o passo recursivo é o passo em que se tenta resolver um sub-problema do problema
inicial. O passo básico é, em si, o critério de parada, pois uma vez que o conjunto de
entrada �bate� com o caso básico, a função recursiva não é mais chamada.
Página 19 de 28
www.handbookdeti.com.br
Handbook de Questões de TI Comentadas para Concursos Volume questões de TI
III. ERRADA. As filas são estruturas baseadas no princípio FIFO (first in, first out), ou
seja, os elementos que foram inseridos no início são os primeiros a serem removidos. É
verdadeiro dizer que, neste caso, o acesso ao elemento da fila é feito pela extremidade
oposta ao da inserção. O erro está em dizer que a regra utilizada é a LIFO (Last In
First Out). A regra LIFO, a qual se refere a afirmativa, é a regra básica da estrutura
de dados conhecida como pilha. Na pilha, os dados que foram inseridos por último,
serão os primeiros a serem removidos, ou seja, a extremidade de inserção e de deleção
é a mesma.
IV. ERRADA. Dizemos que o acoplamento é baixo quando uma mudança em um módulo
não requererá a mudança em outro módulo. Acoplamento baixo é sinal de um sistema
bem estruturado e isso se consegue através de uma modularização bem pensada. O
acoplamento baixo pode reduzir o desempenho em relação a um sistema com alto
acoplamento. Entretanto, o acoplamento baixo é requerido na maioria dos casos, pois
oferece uma manutenabilitadade mais simplificada. Além disso, o acoplamento baixo
facilita a coesão elevada. Módulos com alta coesão possuem responsabilidades bem
definidas e é bem difícil dividi-las em duas ou mais classes.
Dado o exposto, as afirmativas corretas são somente a (I) e (II), logo, a alternativa correta
é a letra (B).
Página 20 de 28
www.handbookdeti.com.br
Handbook de Questões de TI Comentadas para Concursos Volume questões de TI
9. Assuntos relacionados: Algoritmos de Ordenação, Heapsort, Ordenação por Árvore de
Decisão, Ordenação por Comparação, Quicksort, Ordenação por Inserção, Ordenação por
Intercalação,
Banca: CESGRANRIO
Instituição: Petrobras
Cargo: Analista de Sistemas - Eng. de Software
Ano: 2008
Questão: 56
Sobre o algoritmo de ordenação heapsort, assinale a afirmação correta.
(a). Utiliza ordenação por árvore de decisão, ao invés de ordenação por comparação.
(b). A estrutura de dados que utiliza, chamada heap, pode ser interpretada como uma
árvore binária.
(c). Seu desempenho de pior caso é pior do que o do algoritmo quicksort.
(d). Seu desempenho de pior caso é o mesmo da ordenação por inserção.
(e). Seu desempenho de pior caso é menor do que o da ordenação por intercalação.
Solução:
O Heapsort utiliza uma estrutura de dados chamada heap binário (árvore binária mantida na
forma de vetor) para ordenar os elementos a medida que os insere na estrutura. Dessa forma,
ao final das inserções, os elementos podem ser sucessivamente removidos da raiz da heap,
na ordem desejada. Para uma ordenação crescente, deve ser construída uma heap máxima
(o maior elemento fica na raiz). Já para uma ordenação decrescente, deve ser construída
uma heap mínima (o menor elemento fica na raiz). Em resumo, as principais características
desse algoritmo são:
• ordenação por seleção;
• heap gerada e mantida no próprio vetor a ser ordenado (utilização eficiente da memó-
ria);
• complexidade (em qualquer caso: pior, médio ou melhor): O(n log n);
• consumo de memória ao construir a árvore;
• não é indicado para vetores pequenos por conta do tempo de construção da árvore.
(A) ERRADA
Algoritmos que se baseiam apenas em comparações entre os elementos de entrada para
efetuarem ordenações são denominados algoritmos de ordenação por comparação. Os algo-
ritmos Heapsort, Quicksort e Ordenação por Intercalação (Mergesort) são alguns exemplos
desse tipo de algoritmo.
Uma árvore de decisão representa, de modo abstrato, as comparações executadas por um
algoritmo de ordenação. Suas principais propriedades são: é uma árvore binária; possui no
mínimo n! folhas (para n igual ao número de elementos a serem ordenados); cada folha
contém uma permutação dos dados de entrada. O caminho mais longo da árvore representa
o pior caso de execução do algoritmo.
É sempre possível construir uma árvore de decisão para algoritmos de ordenação por com-
paração. Essa construção é realizada da seguinte forma:
Página 21 de 28
www.handbookdeti.com.br
Handbook de Questões de TI Comentadas para Concursos Volume questões de TI
• fixe o n;
• verifique qual é a primeira comparação do algoritmo, que pode resultar em �sim� ou
�não�. Nesse passo, é necessário saber quais são os índices que estão sendo comparados;
• a primeira comparação é colocada na raiz da árvore de decisão, incluindo os arcos �sim�
e �não�;
• repita os passos anteriores para cada nó da árvore. Em cada comparação, é necessário
saber quais são os índices que estão sendo comparados. Observe que sempre se deve
analisar os índices originais, ou seja, não devem ser consideradas as trocas de índices
ocorridas durante a execução do algoritmo.
Tendo em vista os conceitos apresentados, conclui-se que o algoritmo Heapsort pode ser
representado por uma árvore de decisão, já que é um dos algoritmos que realiza ordenação
por comparação. Portanto, essa alternativa está errada.
(B) CORRETA
Considerando a explicação apresentada acima, se torna fácil concluir que é essa a alter-
nativa correta.
(C) ERRADA
Seu desempenho no pior caso (igual ao do melhor ou médio caso) é O(n log n). Esse é
o melhor resultado dentre os algoritmos baseados em comparações. Esse conhecimento já
bastaria para concluir que essa alternativa está incorreta. As complexidades do algoritmo
Quicksort são O(nlogn) para o melhor caso e O(n2) para o pior caso. É sempre importante
ter em mente que quanto mais eficiente for a escolha do pivot, mais eficiente será o desem-
penho da ordenação do algoritmo Quicksort.
(D) ERRADA
No pior caso, a ordenação por inserção apresenta complexidade igual a O(n2), pois nesse
caso são necessárias n(n− 1)/2 ≈ (n2)/2 comparações. Esse cenário sempre ocorre quando
a sequência de entrada está ordenada na ordem inversa à desejada.
(E) ERRADA
Também chamado de Mergesort, o algoritmo de ordenação por intercalação, um algoritmo
recursivo, se utiliza da técnica �dividir para conquistar�. Sua idéia básica é que é mais fácil
criar uma sequência ordenada a partir de duas outras também ordenadas. Para isso, ele
divide a sequência original em pares de dados, as ordena, depois as agrupa em sequências
de quatro elementos, e assim por diante, até ter toda a sequência dividida em apenas duas
partes. Sua complexidade tanto para o pior quanto para o melhor caso é O(n log n). Seu
ponto fraco é a �baixa� eficiência na utilização de memória, complexidade espacial O(n).
Contudo, existe uma variante desse algoritmo que realiza a ordenação no próprio vetor de
entrada, ou seja, complexidade espacial O(1), mas a sua implementação é extremamente
complicada.
Página 22 de 28
www.handbookdeti.com.br
Handbook de Questões de TI Comentadas para Concursos Volume questões de TI
10. Assuntos relacionados: Estruturas de Dados, Lista Encadeada, Tabela Hash,
Banca: CESGRANRIO
Instituição: Petrobras
Cargo: Analista de Sistemas - Eng. de Software
Ano: 2008
Questão: 57
Informações comuns às questões de números 57 e 58.
Considere uma tabela hash H, onde H[i] denota uma posição da tabela. H é implemen-
tada usando uma função h(k) para determinar a posição i de armazenamento, k sendo a
chave do elemento de dados x a ser armazenado em H, e denotada por k = chave[x]. H é
um hash com encadeamento, ou seja, cada H[i] é uma lista encadeada que armazenará os
elementos de dados que, de outra forma, colidiriam para a posição. Nesta implementação,as listas são duplamente encadeadas, ou seja, cada elemento e da lista armazena também os
ponteiros proximo[e] e anterior[e]. Cada lista L possui ainda o valor inicio[L], que aponta
para o primeiro elemento da lista. NIL representa um ponteiro vazio.
← denota o operador de atribuição.
O pseudocódigo a seguir mostra uma operação nesta estrutura, porém apresenta erro em
uma de suas linhas. As linhas estão numeradas apenas para facilitar a correspondência com
as alternativas.
01 proximo[chave[x]] ← inicio[H[h(chave[chave[x]])]]
02 se inicio[H[h(chave[chave[x]])]] 6= NIL
03 então inicio[anterior[inicio[H[h(chave[chave[x]])]]]] ← chave[x]
04 inicio[H[h(chave[chave[x]])]] ← chave[x]
05 anterior[chave[x]] ← NIL
O erro citado é corrigido por
(a). 01 chave[x] ← inicio[H[h(chave[x])]]
(b). 02 se proximo[H[h(chave[chave[x]])]] 6= NIL
(c). 03 então anterior[inicio[H[h(chave[chave[x]])]]] ← chave[x]
(d). 04 proximo[inicio[H[h(chave[chave[x]])]]] ← proximo[chave[x]]
(e). 05 anterior[chave[x]] ← inicio[H[h(chave[chave[x]])]]
Solução:
Antes de partirmos para a resolução da questão, relembremos as estruturas de dados citadas
(Tabela Hash e Lista Encadeada).
As Tabelas Hash são utilizadas geralmente em cenários em que o número real de chaves
armazenadas é menor que o número de chaves possíveis. Nessas condições, Tabelas Hash
tornam-se uma alternativa efetiva ao endereçamento direto de uma matriz, visto que usam
matrizes de tamanho proporcional ao número de chaves realmente armazenadas.
Em uma Tabela Hash, a função hash (na questão, h(k)) é utilizada para calcular em qual
entrada da tabela o elemento de chave k será armazenado. Se a tabela possuir tamanho m,
isto é, m entradas, então o espaço de saída da função h(k) será: 0, 1, . . . , m-1. O propósito
Página 23 de 28
www.handbookdeti.com.br
Handbook de Questões de TI Comentadas para Concursos Volume questões de TI
da função hash é reduzir a faixa de índices da matriz que precisam ser tratados. Essa redu-
ção, contudo, possui um preço, o de que duas chaves distintas podem mapear para a mesma
entrada na tabela.
As Listas Encadeadas são estruturas de dados nas quais os objetos estão arranjados em
uma ordem linear, fornecendo uma simples e flexível representação para conjuntos dinâmi-
cos.
Na lista L em questão, cada elemento é um objeto com um campo chave e dois outros
campos ponteiros: próximo e anterior. Dado um elemento �e� na lista, proximo[e] aponta
para o seu sucessor na lista encadeada, e anterior[e] aponta para o seu predecessor. Se ante-
rior[e] = NIL, o elemento �e� não possui predecessor e ele é o primeiro elemento, ou cabeça,
da lista (lembre-se que essa lista é apenas duplamente encadeada, e não circular). Pelo lado
oposto, se proximo[e] = NIL, o elemento �e� não possui sucessor, sendo, então, o último
elemento, ou rabo, da lista.
Pelo enunciado, podemos notar que a referida lista (L) também possui um atributo ini-
cio, que aponta para o primeiro elemento da lista. Se inicio[L] = NIL, então a lista é vazia.
Assim sendo, partiremos para a resolução da questão.
Ao analisar o pseudocódigo, podemos notar que a função hash h(k) é alimentada pela chave
da chave do elemento x e não apenas pela chave de x (chave[x]) como o enunciado apresenta,
o que poderia nos confundir.
Nesse pseudocódigo, todas as linhas estão corretas com exceção da linha 03. Vejamos,
passo a passo, o porquê:
1. chave[x]: determina a chave do elemento x;
2. chave[chave[x]]: determina a chave da chave do elemento x;
3. h(chave[chave[x]]): calcula a entrada da Tabela H que será indexada;
4. H[h(chave[chave[x]])]: representa uma lista duplamente encadeada que está localizada
na entrada h(chave[chave[x]]) da Tabela H;
5. inicio[H[h(chave[chave[x]])]]: recupera o primeiro elemento (cabeça) da lista
H[h(chave[chave[x]])]. Além disso, como o código da linha 03 é executado apenas se a
condição da linha 02 é satisfeita, temos, obviamente, que inicio[H[h(chave[chave[x]])]]
é uma referência de memória válida (6= NIL);
6. anterior[inicio[H[h(chave[chave[x]])]]]: esta sequência de indexações recupera o ponteiro
para o nó que precede o nó da cabeça. Como estamos tratando com uma lista dupla-
mente encadeada e não circular, fica evidente que tal ponteiro possui valor NIL;
7. inicio[anterior[inicio[H[h(chave[chave[x]])]]]]: é neste nível de indexação que chegamos
ao erro. Ao substituirmos a parte interna do colchete mais externo por NIL, como
vimos no item anterior, obteremos inicio[NIL], o que representa uma violação de acesso
à memória. Portanto, a resposta correta é a alternativa C.
Página 24 de 28
www.handbookdeti.com.br
Handbook de Questões de TI Comentadas para Concursos Volume questões de TI
11. Assuntos relacionados: Estruturas de Dados, Lista Encadeada, Tabela Hash,
Banca: CESGRANRIO
Instituição: Petrobras
Cargo: Analista de Sistemas - Eng. de Software
Ano: 2008
Questão: 58
Corrigindo-se o erro citado, o pseudocódigo corresponderia a uma operação de
(a). inserção de x em H.
(b). inserção da chave de x em H.
(c). inserção da chave da chave de x em H.
(d). remoção da chave de x de H.
(e). remoção de x de H.
Solução:
Após a correção do erro existente no pseudocódigo, teremos:
01 proximo[chave[x]] ← inicio[H[h(chave[chave[x]])]]
02 se inicio[H[h(chave[chave[x]])]] 6= NIL
03 então anterior[inicio[H[h(chave[chave[x]])]]] ← chave[x]
04 inicio[H[h(chave[chave[x]])]] ← chave[x]
05 anterior[chave[x]] ← NIL
A partir da análise do pseudocódigo acima, constamos que estamos diante de uma inserção,
pois:
• a atribuição existente na linha 01 faz com que o campo ponteiro próximo do nó chave[x]
passe apontar para a atual cabeça da lista. Para fins meramente ilustrativos, veja
abaixo a Figura 5 que apresenta dois cenários iniciais possíveis da lista. O primeiro em
que ela é vazia e o segundo em que há apenas um nó;
• na linha 03, ao ponteiro anterior da atual cabeça da lista (inicio[H[h(chave[chave[x]])]]),
é atribuído o endereço do nó que contém a chave de x (chave[x]). Lembre-se que antes
dessa atribuição, anterior[inicio[H[h(chave[chave[x]])]]] apontava para NIL, por se tratar
do primeiro nó da lista. A Figura 6 ilustra esse cenário, o qual nós chamaremos de 2.1,
pois advém do cenário 2 que foi apresentado no item anterior;
• na linha 04, ao atributo inicio da lista H[h(chave[chave[x]])] é atribuído o nó que contém
a chave x. Em outras palavras, o nó x passa a ser o nó cabeça da lista. A Figura 7
ilustra dois possíveis casos, um na lista vazia (1.1) e o outro em uma lista contendo um
nó (2.2);
• na linha 05, ao ponteiro anterior do nó contendo a chave x, e atual cabeça da lista,
é atribuído o valor NIL, uma vez que ele não possui predecessor. Novamente, para
ilustrar essa atribuição, nós recorreremos a Figura 8, a qual apresenta o cenário 1.2,
proveniente de uma lista inicialmente vazia, e o cenário 2.3, proveniente de uma lista
não-vazia.
Página 25 de 28
www.handbookdeti.com.br
Handbook de Questões de TI Comentadas para Concursos Volume questões de TI
Figura 5: ilustração da linha 01 do pseudocódigo.
Figura 6: ilustração da linha 03 do pseudocódigo.
Página 26 de 28
www.handbookdeti.com.br
Handbook de Questões de TI Comentadas para Concursos Volume questões de TI
Figura 7: ilustração da linha 04 do pseudocódigo.
Figura 8: ilustração da linha 05 do pseudocódigo.
Página 27 de 28
www.handbookdeti.com.br
Handbook de Questões de TI Comentadas para Concursos Volume questões de TI
Questão Resposta
1 C
2 E
3 A
4 E
5 E
6 B
7 C
8 B
9 B
10 C
11 B
Página 28 de 28 Handbook de TI Além do Gabarito
Índice Remissivo
Árvore, 11
Árvore B, 4, 6
Árvore Binária de Busca, 14
Árvores AVL, 13
Árvores Binárias, 13, 14
Algoritmosde Ordenação, 21
Estruturas de Dados, 6, 9, 11, 13, 14, 17, 19,
23, 25
Fila, 11
Heapsort, 21
Lista Encadeada, 11, 23, 25
Métodos de Busca, 4
Ordenação por Árvore de Decisão, 21
Ordenação por Comparação, 21
Ordenação por Inserção, 21
Ordenação por Intercalação, 21
Pesquisa Binária, 4
Pilha, 9, 11
Programação, 17, 19
Quicksort, 21
Tabela Hash, 17, 23, 25
29