Estruturas de Dados - apostilando.yolasite.comapostilando.yolasite.com/.../handbook_questoes_estruturas_de_dados.pdf · diversas estruturas de dados: vetores, listas, las, pilhas,

Questões comentadas

Estruturas de Dadospara concursos

Handbook de Questões de TI Comentadas para Concursos Volume questões de TI

Prefácio

A e�ciê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. Paradesenvolver algoritmos complexos e e�cientes, o desenvolvedor precisa dominar os conceitos dasdiversas estruturas de dados: vetores, listas, �las, pilhas, árvores, grafos e hashs; bem como asdiversas técnicas de busca e ordenação de dados.

É por este motivo que diversos concursos na área de Tecnologia de Informação têm cobradoeste tema, como forma de examinar o conhecimento e a capacidade dos candidatos em proveralgoritmos complexos e e�cientes, 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 28www.handbookdeti.com.br

www.handbookdeti.com.br


Direitos Autorais

Este material é registrado no Escritório de Direitos Autorais (EDA) da Fundação BibliotecaNacional. Todos os direitos autorais referentes a esta obra são reservados exclusivamente aosseus 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 deforma indiscriminada através de qualquer meio, inclusive na Internet, extrapolam os limites dacolaboraçã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 é umaprodução independente e contamos com você para mantê-la sempre viva.

Grupo Handbook de TI




Canais de Comunicação

O Grupo Handbook de TI disponibiliza diversos canais de comunicação para os concurseirosde 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 [email protected]

Twitter do Handbook de TI

Acompanhe de perto promoções e lançamentos de produtos pelo nosso Twitter http://twitter.com/handbookdeti


http://www.handbookdeti.com.br

[email protected]

http://twitter.com/handbookdeti

http://twitter.com/handbookdeti



1. Assuntos relacionados: Métodos de Busca, Pesquisa Binária, Árvore B,Banca: CESGRANRIOInstituição: BNDESCargo: Analista de SuporteAno: 2008Questão: 50

Os dados de uma agenda contendo nome, telefone e endereço de pessoas estão organizadosem 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 ordenadospor nome. Assumindo que o tamanho do campo endereço é variável e que D pode terarquivos (pré-existentes) de índices que se referenciam ao arquivo de dados, e supondo quenão possui cache, qual é a estratégia que realizará, em média, menos operações de I/O paraconsultar 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á existeordenação por nome.

(b). Pesquisa sobre o arquivo de índices indexados pelo nome, implementando umalgoritmo de busca em uma árvore B-Tree balanceada.

(c). Pesquisa seqüencial sobre um arquivo de índices indexado pelas letras do alfabeto eposterior leitura sequencial sobre o arquivo de dados, nos quais cada índice apontapara o endereço do início da respectiva letra na agenda.

(d). Pesquisa binária sobre um arquivo de índices indexado pelo nome, para posterioracesso 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 seusregistros 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 apenasleitura. Portanto, a alternativa A não é possível.

(B) ERRADA

De maneira geral, a abordagem por B-Tree é uma boa opção. Entretanto, é importanteobservar 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 daordem (n/26)/*log(n), onde n é o número total de registros. Analisaremos as outras opçõesadiante. Note que a opção nem explicitou como seria o acesso ao arquivo de dados.

(C) CORRETA

Essa é uma opção bem e�ciente para o caso, já que será necessário apenas encontrar aletra do alfabeto correspondente (mesmo que de maneira sequencial) no arquivo de índicese depois percorrer sequencialmente o arquivo de dados. A ordem neste caso é 13+n/26. Ouseja, mais rápido que o caso descrito na alternativa B.




(D) ERRADA

O caso e o custo são muito parecidos com aqueles explicitados na alternativa B e, comoconsequê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 registrocujo nome começa com a letra especi�cada 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 e�ciente é a alternativa C.




2. Assuntos relacionados: Estruturas de Dados, Árvore B,Banca: CESGRANRIOInstituição: PetrobrasCargo: Analista de Sistemas - Eng. de SoftwareAno: 2008Questão: 59

Considere uma árvore B de grau mínimo igual a 2 (o que signi�ca que cada nó pode ter, nomá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. Considerandoo 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 �lhos. Nessecaso, note que os nós folhas, os quais estão localizados nos extremos da árvore, nãotêm �lhos;

• as chaves existentes em um nó x separam as faixas de chaves armazenadas em cadasub-árvore. Por exemplo, considere um nó x que contém apenas uma chave de valor V(o que signi�ca, como já vimos, que ele poderá possuir até dois nós �lhos: sub-árvoreesquerda e sub-árvore direita). Nesse cenário, qualquer chave com valor menor que Vencontrar-se-á na sub-árvore esquerda. Por outro lado, chaves com valor maior que Vestarã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-sena altura 0 (zero);

• existem limites máximos e mínimos no número de chaves que um nó pode conter. Esselimite é expressado em termos do grau mínimo da árvore B (considerado, aqui, comoum parâmetro t). Assim, cada nó diferente da raiz deve ter, pelo menos, t - 1 chaves,isto é, no mínimo t �lhos (se a árvore é não-vazia, o nó raiz deve ter pelo menos umachave). No que se refere ao limite máximo, cada nó pode conter até 2t - 1 chaves, ouseja, 2t �lhos;




• 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 consisteem: dividir o nó x em dois nós �lhos, cada um contendo t - 1 chaves; mover a chavemediana de x para o nó pai de x. Se x não possuir nó pai, então a árvore cresce emaltura por um;

• antes da inserção de uma chave em um nó x cheio, devemos assegurar que o nó pai dex também não esteja cheio antes do split de x, evitando, dessa forma, que splits sejamrealizados recursivamente;

• após a ocorrência de um split, a nova chave será inserida no nó folha existente em umadas 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, nemnós �lhos. Em seguida, nós iremos inserir as chaves, uma a uma, respeitando os limites queos nós possuem. No caso da árvore em questão, com t igual a 2, um nó terá no mínimo umachave e no máximo 3 chaves. A Figura 1, apresenta, passo a passo, a inserção de cada chave(nós que são modi�cados 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 nadamais é 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çãona 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 inseridano 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.




Figura 1: inserção de chaves em uma árvore B.




3. Assuntos relacionados: Estruturas de Dados, Pilha,Banca: CESGRANRIOInstituição: BNDESCargo: Analista de SuporteAno: 2008Questã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 �la do tipo LIFO (Last In, FirstOut). 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 pararemover o último elemento inserido. A Figura 2 mostra os estados da pilha P após seremaplicadas 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.




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 quantode software. Nesses casos, são armazenados nas pilhas os endereços das instruções a seremexecutadas pelo computador.

São estruturas de dados do tipo pilha que permitem que o �uxo de execução dos programasseja desviado por meio da chamada de funções. Os leitores que tiverem alguma experiênciacom programação recursiva, em especial em C, já devem ter se deparado com o erro ControlStack Over�ow. Isso acontece quando, por um erro de de�nição da condição de parada darecursão, novas chamadas da função recursiva vão sendo feitas até que o espaço alocado paraa pilha de execução se esgote, abortando a execução do programa.




4. Assuntos relacionados: Estruturas de Dados, Fila, Árvore, Lista Encadeada, Pilha,Banca: ESAFInstituição: Secretaria do Tesouro Nacional (STN)Cargo: Analista de Finanças e Controle - Tecnologia da Informação / Desenvolvimento deSistemas de InformaçãoAno: 2008Questão: 18

Navegadores Web armazenam as URLs (Uniform Resource Locators) visitadas recentementeem uma determinada estrutura de dados. Com isso, permite que o usuário visite o últimosite visitado, ao recuperar a URL na estrutura, usando uma operação de retorno (back). Aestrutura de dados apropriada para implementar este recurso é a

(a). �la.

(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 deURL 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, �la, árvore, lista, e pilha.

(A) ERRADA

Uma �la é simplesmente uma lista de informações que é acessada na ordem primeira aentrar, primeiro a sair, sendo chamada de FIFO (First Int, First Out). Isto é, o primeiroelemento colocado na �la é o primeiro a ser retirado, o segundo elemento colocado é osegundo a ser recuperado e assim sucessivamente. Essa é a única forma de armazenar erecuperar em uma �la, não é permitido acesso a nenhum item especí�co.

(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 omembro esquerdo e um ponteiro para o membro direito. A raiz é o primeiro elemento emuma á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 comum/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




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 umponteiro com o próximo elemento da lista. Cada elemento de dado geralmente consiste emuma 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 epara o item anterior. O fato de ter dois ponteiros em lugar de um tem a vantagem da listapoder ser lida em ambas as direções.

(E) CORRETA

Uma pilha é o inverso de uma �la 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 serusado e o último prato colocado na pilha é o primeiro a ser usado. Pilhas são usadas emgrande 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 dalista.

Portanto, a única estrutura de dados que possui uma funcionalidade de recuperar o últimoelemento inserido é a estrutura pilha, desta forma, a letra correta é a E.




5. Assuntos relacionados: Estruturas de Dados, Árvores Binárias, Árvores AVL,Banca: FCCInstituição: TRT 18a RegiãoCargo: Analista Judiciário - Tecnologia da InformaçãoAno: 2008Questão: 24

Árvore AVL balanceada em altura signi�ca que, para cada nó da árvore, a diferença entreas 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 deestar 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 aconteceno caso em que a construção da árvore é feita por inserções sucessivas e os valores são dadoscom 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 tipode árvore é que uma busca é realizada em O(log(n)) se a árvore possui n nós. Em uma árvoreAVL, cada nó está equilibrado em altura, signi�cando isto que, em cada nó, a diferença dealturas entre as subárvores esquerda e direita é no máximo 1. Uma outra de�nição paraárvores AVL será aquela em que para qualquer nó P se veri�ca que o módulo do fator deequilíbrio é sempre menor ou igual a um. Entende-se por fator de equilíbrio de um nó P adiferença da altura da subárvore esquerda de P e altura da subárvore direita de P. Dado oexposto, a alternativa correta da questão é a letra E.

Uma árvore AVL terá uma estrutura semelhante a uma árvore binária de pesquisa coma condição de que a árvore de pesquisa mantém-se equilibrada em altura depois de cadaoperaçã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 deequilíbrio. Uma propriedade garantida da árvore rubro-negra é que, caso ela possua n nós,ela terá altura menor ou igual à 2log(n+1).




6. Assuntos relacionados: Estruturas de Dados, Árvores Binárias, Árvore Binária de Busca,

Banca: CesgranrioInstituição: PetrobrasCargo: Analista de Sistemas Pleno - ProcessosAno: 2006Questã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, aexecuçã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 é de�nida como uma estrutura de dados com as seguintescaracterí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ãochamados �lhos 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 valoresinferiores ao do nó raiz e os nós à direita formam uma sub-árvore com valores superiores aodo nó da raiz. Assim, as chaves em uma árvore binária de busca são sempre armazenadassatisfazendo à 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 esquerdade x, então chave[y] <= chave[x]. Se y é um nó na sub-árvore direita de x, então chave[x]<= chave[y].




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, detrê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 emlargura (ou percurso em nível).

No percurso de árvore em ordem simétrica, a chave da raiz de uma sub-árvore é impressaentre 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 ououtra sub-árvore, e o percurso de árvore de pós-ordem imprime a raiz depois dos valorescontidos em suas sub-árvores. Esses três tipos de percurso, de�nidos recursivamente, sãoconsiderados 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 visitadostodos 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 de �gura.

Como �Lina� é o primeiro valor apresentado à árvore binária de busca que está inicialmentevazia, 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 à esquerdado 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�lhos) é Lina, Ana, Ada, Lia, Cris, Bia, Lua, Sol, Rita, Mel, Rosa, Val. Observa-se que araiz de cada (sub-)árvore é visita antes de seus �lhos (�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 �lhos da esquerda e, em seguida, os �lhos da direita. A outra opção para umpercurso em pré-ordem, agora visitando os �lhos da direita antes dos �lhos da esquerda, éLina, Lua, Sol, Val, Rita, Rosa, Mel, Ana, Lia, Cris, Bia, Ana.




Um percurso em ordem simétrica (isto é, um percurso no qual a raiz aparece entre seus�lhos) é Ada, Ana, Bia, Cris, Lia, Lina, Lua, Mel, Rita, Rosa, Sol, Val. Considerou-se avisita aos �lhos da esquerda antes dos �lhos da direita. A ordem inversa, ou seja, �lhosda direita antes dos �lhos 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 �lhos),visitando primeiramente os �lhos da esquerda, é Ada, Bia, Cris, Lia, Ana, Mel, Rosa, Rita,Val, Sol, Lua, Lina. Visitando os �lhos da direita antes dos �lhos da esquerda, o outropercurso 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 �lhos da esquerda antes dos �lhosda direita. Inversamente, visitando os �lhos 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 confundiro candidado, �embaralhando� resultados possíveis (a assertiva I é um percurso em nível e aassertiva IV apresenta um percurso em pré-ordem). Desta forma, a resposta da questão é aletra (B).




7. Assuntos relacionados: Programação, Estruturas de Dados, Tabela Hash,Banca: FCCInstituição: TRT 15a RegiãoCargo: Analista Judiciário - Tecnologia da InformaçãoAno: 2009Questã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 índiceonde 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 tabelade espalhamento ou de dispersão.

A implementação de uma tabela hash se baseia na escolha de uma função, chamada funçãohash, que associe uma chave de pesquisa a um índice em uma estrutura de dados. O requisitomais 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 mapeadapara 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 virtudede 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 deacesso às memória cache. A Figura 4 mostra, de forma básica, como se dá o esquema demapeamento de chaves em índices usando uma tabela hash.

Figura 4: Tabela Hash.

No entanto, a de�nição de uma boa função hash nem sempre é uma tarefa simples, sendoum trabalho trabalho profundamente relacionado à estatística. Portanto, para otimizar a




função hash, é necessário conhecer a natureza da chave a ser utilizada e como os valores quea chave pode assumir se distribuem ao longo do domínio. Os métodos de implementação defunções hash mais comuns são o método da divisão, o método da dobra, e o método damultiplicação.

Com relação às limitações das tabelas hash, valem as seguintes observações. As tabelashash são estruturas de dados que não permite armazenar elementos repetidos, recuperarelementos sequencialmente, nem recuperar antecessores ou sucessores de um determinadoelemento já encontrado. Caso essas operações tenham muita importância no sistema, vale apena considerar a utilização de estruturas de dados como listas encadeadas, árvores, entreoutras.




8. Assuntos relacionados: Programação, Estruturas de Dados,Banca: ESAFInstituição: Receita Federal (RF)Cargo: Técnico da Receita Federal - Tecnologia da InformaçãoAno: 2006Questão: 21

Analise as seguintes a�rmações relacionadas a Noções de Programação:

I. Quando uma função é chamada e os parâmetros formais da função copiam os valoresdos parâmetros que são passados para ela, sem que ocorra alteração dos valores que osparâmetros têm fora da função, este tipo de chamada de função é denominado chamadacom passagem de parâmetros por valor. Isso ocorre porque são passados para a funçãoapenas 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ériode parada vai determinar quando a função deverá parar de chamar a si mesma. Issoimpede que a função entre em loop.

III. Uma �la é uma lista de informações com operações especiais de acesso. O acesso aoselementos da �la é feito pela extremidade oposta à da inserção, ou seja, o elementodisponível estará sempre na extremidade oposta à da inserção. Esta regra é tambémconhecida como LIFO (Last In First Out).

IV. No desenvolvimento estruturado, uma boa prática de modularização é proporcionarum alto acoplamento entre os módulos, mantendo a dependência lógica e liberdade decomunicação entre eles.

Indique a opção que contenha todas as a�rmaçõ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 a�rmativas separadamente, pois termos diferentes são utilizados em cadauma.

I. CORRETA. Na passagem de parâmetros por valor, a função recebe uma cópia dosargumentos 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 deparâmetros por referência, são enviadas internamente para a função, as referências dosargumentos que foram passados, e não uma simples cópia. Os valores alterados, nestecaso, 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. Emtoda 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 é imediatamente conhecido, jáo passo recursivo é o passo em que se tenta resolver um sub-problema do problemainicial. O passo básico é, em si, o critério de parada, pois uma vez que o conjunto deentrada �bate� com o caso básico, a função recursiva não é mais chamada.




III. ERRADA. As �las são estruturas baseadas no princípio FIFO (�rst in, �rst out), ouseja, 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 �la é feito pela extremidadeoposta ao da inserção. O erro está em dizer que a regra utilizada é a LIFO (Last InFirst Out). A regra LIFO, a qual se refere a a�rmativa, é a regra básica da estruturade 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ódulonão requererá a mudança em outro módulo. Acoplamento baixo é sinal de um sistemabem estruturado e isso se consegue através de uma modularização bem pensada. Oacoplamento baixo pode reduzir o desempenho em relação a um sistema com altoacoplamento. Entretanto, o acoplamento baixo é requerido na maioria dos casos, poisoferece uma manutenabilitadade mais simpli�cada. Além disso, o acoplamento baixofacilita a coesão elevada. Módulos com alta coesão possuem responsabilidades bemde�nidas e é bem difícil dividi-las em duas ou mais classes.

Dado o exposto, as a�rmativas corretas são somente a (I) e (II), logo, a alternativa corretaé a letra (B).




9. Assuntos relacionados: Algoritmos de Ordenação, Heapsort, Ordenação por Árvore deDecisão, Ordenação por Comparação, Quicksort, Ordenação por Inserção, Ordenação porIntercalação,Banca: CESGRANRIOInstituição: PetrobrasCargo: Analista de Sistemas - Eng. de SoftwareAno: 2008Questão: 56

Sobre o algoritmo de ordenação heapsort, assinale a a�rmaçã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 naforma de vetor) para ordenar os elementos a medida que os insere na estrutura. Dessa forma,ao �nal 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 �ca na raiz). Já para uma ordenação decrescente, deve ser construídauma heap mínima (o menor elemento �ca na raiz). Em resumo, as principais característicasdesse algoritmo são:

• ordenação por seleção;

• heap gerada e mantida no próprio vetor a ser ordenado (utilização e�ciente 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 paraefetuarem 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 exemplosdesse tipo de algoritmo.

Uma árvore de decisão representa, de modo abstrato, as comparações executadas por umalgoritmo de ordenação. Suas principais propriedades são: é uma árvore binária; possui nomínimo n! folhas (para n igual ao número de elementos a serem ordenados); cada folhacontém uma permutação dos dados de entrada. O caminho mais longo da árvore representao 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:




• �xe o n;

• veri�que 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áriosaber quais são os índices que estão sendo comparados. Observe que sempre se deveanalisar os índices originais, ou seja, não devem ser consideradas as trocas de índicesocorridas durante a execução do algoritmo.

Tendo em vista os conceitos apresentados, conclui-se que o algoritmo Heapsort pode serrepresentado por uma árvore de decisão, já que é um dos algoritmos que realiza ordenaçãopor 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 algoritmoQuicksort são O(nlogn) para o melhor caso e O(n2) para o pior caso. É sempre importanteter em mente que quanto mais e�ciente for a escolha do pivot, mais e�ciente 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 nessecaso são necessárias n(n− 1)/2 ≈ (n2)/2 comparações. Esse cenário sempre ocorre quandoa 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 algoritmorecursivo, se utiliza da técnica �dividir para conquistar�. Sua idéia básica é que é mais fácilcriar uma sequência ordenada a partir de duas outras também ordenadas. Para isso, eledivide a sequência original em pares de dados, as ordena, depois as agrupa em sequênciasde quatro elementos, e assim por diante, até ter toda a sequência dividida em apenas duaspartes. Sua complexidade tanto para o pior quanto para o melhor caso é O(n log n). Seuponto fraco é a �baixa� e�ciê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 deentrada, ou seja, complexidade espacial O(1), mas a sua implementação é extremamentecomplicada.




10. Assuntos relacionados: Estruturas de Dados, Lista Encadeada, Tabela Hash,Banca: CESGRANRIOInstituição: PetrobrasCargo: Analista de Sistemas - Eng. de SoftwareAno: 2008Questã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 achave 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á oselementos 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 osponteiros proximo[e] e anterior[e]. Cada lista L possui ainda o valor inicio[L], que apontapara 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 emuma de suas linhas. As linhas estão numeradas apenas para facilitar a correspondência comas alternativas.

01 proximo[chave[x]] ← inicio[H[h(chave[chave[x]])]]02 se inicio[H[h(chave[chave[x]])]] 6= NIL03 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 chavesarmazenadas é menor que o número de chaves possíveis. Nessas condições, Tabelas Hashtornam-se uma alternativa efetiva ao endereçamento direto de uma matriz, visto que usammatrizes 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 qualentrada 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




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 mesmaentrada na tabela.

As Listas Encadeadas são estruturas de dados nas quais os objetos estão arranjados emuma ordem linear, fornecendo uma simples e �exível representação para conjuntos dinâmi-cos.

Na lista L em questão, cada elemento é um objeto com um campo chave e dois outroscampos ponteiros: próximo e anterior. Dado um elemento �e� na lista, proximo[e] apontapara 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 ladooposto, se proximo[e] = NIL, o elemento �e� não possui sucessor, sendo, então, o últimoelemento, 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 chaveda 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á localizadana entrada h(chave[chave[x]]) da Tabela H;

5. inicio[H[h(chave[chave[x]])]]: recupera o primeiro elemento (cabeça) da listaH[h(chave[chave[x]])]. Além disso, como o código da linha 03 é executado apenas se acondiçã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 ponteiropara o nó que precede o nó da cabeça. Como estamos tratando com uma lista dupla-mente encadeada e não circular, �ca evidente que tal ponteiro possui valor NIL;

7. inicio[anterior[inicio[H[h(chave[chave[x]])]]]]: é neste nível de indexação que chegamosao erro. Ao substituirmos a parte interna do colchete mais externo por NIL, comovimos no item anterior, obteremos inicio[NIL], o que representa uma violação de acessoà memória. Portanto, a resposta correta é a alternativa C.




11. Assuntos relacionados: Estruturas de Dados, Lista Encadeada, Tabela Hash,Banca: CESGRANRIOInstituição: PetrobrasCargo: Analista de Sistemas - Eng. de SoftwareAno: 2008Questã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= NIL03 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 �ns meramente ilustrativos, vejaabaixo a Figura 5 que apresenta dois cenários iniciais possíveis da lista. O primeiro emque 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 antesdessa atribuição, anterior[inicio[H[h(chave[chave[x]])]]] apontava para NIL, por se tratardo 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éma chave x. Em outras palavras, o nó x passa a ser o nó cabeça da lista. A Figura 7ilustra dois possíveis casos, um na lista vazia (1.1) e o outro em uma lista contendo umnó (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, parailustrar 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 listanão-vazia.




Figura 5: ilustração da linha 01 do pseudocódigo.










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

Algoritmos de 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, 21Ordenação por Comparação, 21Ordenação por Inserção, 21Ordenação por Intercalação, 21

Pesquisa Binária, 4Pilha, 9, 11Programação, 17, 19

Quicksort, 21

Tabela Hash, 17, 23, 25

29

Documents

Estruturas de Dados - apostilando.yolasite.comapostilando.yolasite.com/.../handbook_questoes_estruturas_de_dados.pdf · diversas estruturas de dados: vetores, listas, las, pilhas,