Algoritmos e Estrutura de Dados: 2/2

Saudações, concurseiros !

Continuamos aqui com nossos estudos sobre Algoritmos e Estrutura de Dados, desse vez concluindo, aprofundando o tópico de Estrutura de Dados. Ressalto, mais uma vez, que esse é um assunto bastante cobrado por qualquer organizadora. É difícil ver uma prova de Analista de Sistemas (Desenvolvimento) que não tenha uma ou outra questão sobre ele.

Ao final do artigo, vamos apresentar uma questão que ilustra bem como as organizadoras cobram o assunto, retirada da mais recente prova que comentei (TRF 5a região – FCC 2008 – disponível em breve na loja).

Sem mais delongas, vamos  começar pelos Arrays

Estrutura de dados: Array

· Estrutura de dados linear, homogênea (contém elementos do mesmo tipo) e armazenada contiguamente

· Elementos são acessados diretamente (acesso aleatório) através de um índice. Acesso rápido

· Têm tamanho fixo , não podem ser incrementados ou diminuídos sem implicar complexos processos de cópia

Estrutura de dados: Stack (Pilha)

· Estrutura do tipo Last in , First Out (LIFO)

· Uma pilha é uma lista linear na qual o primeiro elemento a entrar é o último elemento a sair. Ela possui apenas uma entrada, chamada de topo, a partir da qual os dados entram e saem dela

· É muito usada em compiladores para parsing e como estrutura para armazenar variáveis locais a um bloco de função

· Operações: push (empilhar) , pop (desempilhar) e peek (olhar o conteúdo do topo)

· Os itens em uma pilha podem ser empilhados e desempilhados em tempo constante de O(1), sendo desnecessário qualquer tipo de comparação

Estrutura de dados: Queue (Fila)

· Estrutura do tipo First in , First Out (FIFO)

· Semelhante à pilha, só que neste caso só são permitidas inserções no final da fila e remoções no começo.

· Esse tipo específico de estrutura é muito usado em aplicações que requerem que os itens sejam acessados na ordem em que foram adicionados à lista

· Outros tipos de filas:

o Deque (double-ended queue): permite remover/inserir elementos em qualquer lado

o Priority Queue: mantém os elementos ordenados de acordo com algum critério de prioridade

Estrutura de dados: Linked List (Lista Ligada)

· Estrutura de dados do tipo linear e dinâmica

· É composta por células que apontam para o próximo elemento da lista

· Uma lista ligada deve guardar as referências para o seu primeiro e último elementos (este, por sua vez, tem seu apontador voltado para uma referência nula)

· Vantagem: A inserção de um elemento no meio da lista não implica mover todos os elementos

· Desvantagem: o acesso sequencial, para eliminação ou inserção de um elemento no meio da lista

· Variação: lista duplamente encadeada

o Cada nó tem referência para ambos o anterior e o próximo elemento

o Melhora o desempenho de algumas operações sobre a lista, como remover um elemento do final ou mostrar os elementos na ordem inversa

Estrutura de dados: Binary Trees (Árvores Binárias)

· Uma árvore binária é uma estrutura caracterizada por:

o Ou não tem elemento algum (árvore vazia)

o Ou tem um elemento distinto, denominado raiz, com dois apontadores para duas estruturas diferentes, denominadas sub-árvore esquerda e sub-árvore direita

· Cada elemento pode ter até, no máximo, dois filhos

· Em uma árvore binária de busca, todos os nós que são descendentes à esquerda de um nó A têm valores menores que A. Todos os nós que são descendentes à direita de A têm valores maiores que A

· Árvores binárias fazem buscas, inserções e deleções em O(log n)

· Percorrer uma árvore significa visitar todos os seus nós em uma determinada ordem.

· Pode-se percorrer de 3 formas:

o Pré ordem

§ Visite a raiz

§ Percorra a sub-árvore à esquerda

§ Percorra a sub-árvore à direita

o Em ordem

§ Percorra a sub-árvore à esquerda

§ Visite a raiz

§ Percorra a sub-árvore à direita

o Pós ordem

§ Percorra a sub-árvore à esquerda

§ Percorra a sub-árvore à direita

§ Visite a raiz

· Uma árvore binária balanceada é aquela em que a diferença de profundidade (nível) entre todas as folhas (elementos sem filhos) é de, no máximo, 1.

· O número máximo de folhas por nível é dado por 2i, onde i = nível

Estrutura de dados: Hashtable (Tabela hash)

· É uma estrutura de dados especial, que associa chaves de pesquisa (hash) a valores

· Seu objetivo é, a partir de uma chave simples, fazer uma busca rápida e obter o valor desejado

· É baseada em arrays

· Função de espalhamento: responsável por gerar um índice a partir de uma determinada chave. Idealmente, este índice deve ser único para evitar colisões

· Para resolver colisões pode-se usar:

o Algoritmo de rehash, que calcula um novo hash baseado em uma determinada função, caso haja colisão

o Encadeamento, onde encontra-se uma posição disponível na tabela e indicamos que está posição é a que deve ser buscada em seguida

Com isso terminamos nossos estudos sobre Algoritmos e Estrutura de Dados. Tivemos como objetivo apenas uma visão introdutória ao assunto, isto é, uma revisão,  requerendo, claro, um estudo mais aprofundado caso o candidato não tenha familiaridade com ele. Recomendo o livro Estrutura de Dados e Algoritmos em Java, que tem uma visão bem sintética e acessível do assunto. Você pode encontrá-lo em http://www.submarino.com.br/produto/1/1939597/estrutura+de+dados+e+algoritmos+em+java

Para finalizar, vamos olhar uma questão do Tribunal Regional Federal da Quinta região (2008):

51. Vetores associativos, caches e sets

(A) especificam a profundidade de um nó nas árvores binárias (distância de um nó até a raiz).

(B) são tipicamente implementados por tabelas hash, usadas na indexação de grandes volumes  de dados.

(C) especificam as ordens de grandeza em uma estrutura DEQUE.

(D) são elementos especificados no modelo conceitual de dados.

(E) devem ser especificados pelos usuários de bancos de dados durante o projeto lógico.

Comentário:

Tipos de estruturas que têm como objetivo fazer uma busca rápida e retornar o valor desejado são, tipicamente, implementados através de uma estrutura de dados especial chamada Hashtable. Tal estrutura é baseada em arrays e associa chaves de pesquisa (hash) a valores armazenados. Um dos problemas encontrados na implementação de tabelas hash é a chamada colisão. Ela ocorre quando duas chaves de busca são mapeadas para o mesmo valor na tablela. É um problema inevitável, pois não existe uma função hash ideal, isto é, na prática sempre haverá colisões,  pois o universo de chaves é finito. Um requisito básico, que toda função hash deve ter para amenizar este problema, é que ela possua uma distribuição uniforme, de forma que as chaves sejam “espalhadas” o máximo possível, para evitar colisões.

Quando uma colisão ocorre, pode-se usar, dentre outras, as seguintes soluções:

Algoritmo de rehash, que calcula um novo hash baseado em uma determinada função, caso haja colisão

Encadeamento, onde encontra-se uma posição disponível na tabela e indica-se que esta posição é a que deve ser buscada em seguida

Vetores associativos, caches (imagine a memória cache de um computador), e sets (conjuntos) são, todos, estruturas de dados que recebem uma chave de busca para retornar um valor e, por consequência, “nos bastidores” usam uma tabela hash para efetuar este mecanismo.

Referência:

Michael T. Goodrich. Estrutura de Dados e Algoritmos em Java. Editora: Bookman. Ano: 2007. Edição: 4.

Bons estudos!

»crosslinked«

nandopedrosa

Analista de Finanças e Controle - Ministério da Fazenda/Coordenação de Sistemas Graduação: Universidade Federal de Pernambuco Certificações: ITIL Foundation Certified Java Programmer Certified Java Associate Certified Aprovações: Concurso Ano Cargo Posição Organizadora PBGÁS 2007 Analista de Sistemas 1 FCC SERPRO 2008 Administração de TI 1 CESPE COPERGÁS 2008 Analista de Sistemas 1 UPENET INMETRO 2007 Analista de Sistemas 2 CESPE STN 2008 AFC-TI 2 ESAF STJ 2008 Analista Judiciário 3 CESPE TRF-5 2008 Analista Judiciário 5 FCC TRF-5 2008 Técnico Judiciário 5 FCC TCU 2008 ACE-TI 7 CESPE TJ-PE 2007 Analista Judiciário 11 FCC BNDES 2008 Analista de Sistemas 27 CESGRANRIO

Você pode gostar...

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *