Estrutura de Dados

Uma estrutura de dados é um meio para armazenar e organizar dados com o objetivo de facilitar o acesso e as modificações. Nenhuma estrutura de dados única funciona bem para todos os propósitos, e assim é importante conhecer os pontos fortes e as limitações de várias delas.

Estrutura de Dados Elementares (Tipos Estruturados)

A maioria das linguagens de programação trabalha com tipos de dados elementares e tipos estruturados.

• São considerados tipos de dados elementares: Boolean, Inteiro, Real.

• Vector (Vetor), Queue (Pilha), List (Lista), Tree (Árvore), Vector (Vetor) e Stack (Pilha) são estrutura de dados, também conhecidos como tipos estruturados.

Examinaremos a representação de conjuntos dinâmicos por estruturas de dados simples que usam ponteiros. Embora muitas estruturas de dados complexas possam ser modeladas com a utilização de ponteiros, apresentaremos apenas as estruturas rudimentares: pilhas, filas, listas ligadas e árvores enraizadas. Também discutiremos um método pelo qual objetos e ponteiros podem ser sintetizados a partir de arranjos.

Arranjo (Array)

Em programação de computadores, um Array (Arranjo), também conhecido como vetor (para arrays uni-dimensionais) ou matriz (para arrays bi-dimensionais), é uma das mais simples estruturas de dados. Os arranjos mantêm uma série de elementos de dados, geralmente do mesmo tamanho e tipo de dados armazenados de forma linear. Elementos individuais são acessados por sua posição no arranjo. A posição é dada por um índice, também chamado de Subscrição. O índice geralmente utiliza uma sequência de números inteiros, (ao contrário de um array associativo) mas o índex pode ter qualquer valor ordinal. Alguns arrays são multi-dimensionais, significando que eles são indexados por um número fixo de números inteiros, por exemplo, por um sequência (ou sucessão) finita de quatro números inteiros. Geralmente, arranjos uni e bidimensionais são os mais comuns.

O vetor e a matriz, como arrays, são estruturas de dados linear e estática, composta por um número finito de elementos de um determinado tipo de dados.

Os arrays podem ser considerados como as estruturas de dados mais simples. Têm a vantagem de que os seus elementos são acessíveis de forma rápida, mas têm uma notável limitação: são de tamanho fixo (Estático), mas podem ser incrementados ou diminuídos com determinados algoritmos, geralmente envolvendo a cópia de elementos de um array para outro e reiniciar o original com a nova dimensão. Os vetores podem ser implementados desta forma.

Estas estruturas de dados são ajeitadas nas situações em que o acesso aos dados seja realizado de forma aleatória e imprevisível (Acesso aleatório). Porém, se os elementos podem estar ordenados e vai-se empregar um acesso sequencial, seria mais recomendada uma lista.

A forma de acesso aos elementos de um array é direta, ao contrário das listas. Isto quer dizer que o elemento desejado é obtido a partir do seu índice e não é preciso procurá-lo elemento por elemento. No caso das listas, por exemplo, para alcançar o terceiro elemento ter-se-á de acessar primeiro os dois anteriores (ou bem de guardar um ponteiro que permita aceder de maneira rápida a esse elemento em particular).

Como cada item de um vetor está associado a um índice, a inserção e remoção podem ser feitas em qualquer elemento (indexada).

Uma estrutura de dados array pode ser do tipo lista, vetor ou matriz.

Os componentes de um vetor são caracteristicamente homogêneos e de acesso aleatório por intermédio de índices. Significa dizer que o tipo dos dados de um vetor é sempre igual, ou seja, se é criado um vetor de caracteres com 10 posições, significa que o tipo de dados dos 10 elementos inseridos será caractere. Acesso aleatório significa que posso acessar qualquer elemento do vetor através do índice, ou seja, quero o elemento da posição 4 então digo vet[4], não preciso passar pela posição 1,2 e 3 para chegar à posição 4, posso acessar diretamente a posição 4 através do nome do vetor e do índice da posição desejada, vet[4] por exemplo.

Não há possibilidade de que o arranjo seja de elementos heterogêneos. Não confunda um arranjo onde os elementos são registros (onde os componentes do registro podem ser de tipos diferentes) com a ideia de arranjo heterogêneo. Quando o arranjo é um agregado de registros, todos os elementos do arranjo possuem a mesma forma (definida pelo registro), ou seja, o arranjo é homogêneo. Outro cuidado é não confundir o tipo de dado do arranjo (homogêneo = tipos iguais) com o conteúdo de cada elemento do arranjo (valores diferentes).

Vetores associativos, caches e sets são tipicamente implementados por tabelas hash, usadas na indexação de grandes volumes de dados.

Matriz

É uma estrutura de dados (um tipo de arranjo) dividida em linhas e colunas. Desta forma, é possível armazenar diversos valores dentro dela. Para obter um valor é necessário identificá-lo por meio do número da linha e da coluna onde está armazenado.

Basicamente são estáticas, mas é possível através de algoritmos de cópia simular matrizes dinâmicas, sendo assim, estes são os tipos possíveis de matrizes:

Matriz Estática:

• As faixas de subscrito estão estaticamente vinculadas e a alocação de armazenamento é estática (feita antes da execução);

• Vantagem: eficiência (em relação à alocação dinâmica).

Matriz Fixa Dinâmica na Pilha (Matriz Fixa):

• Faixas de subscrito estão estaticamente vinculadas, mas a alocação é feita no momento da declaração durante a execução;

• Vantagem: eficiência de espaço.

Matriz Dinâmica na Pilha:

• Faixas de subscritos estão dinamicamente vinculadas e a alocação de armazenamento é dinâmica (feita durante a execução)

• Vantagem: flexibilidade (o tamanho de uma matriz não precisa ser conhecido antes da sua utilização)

Matriz Dinâmica no Monte:

• A vinculação das faixas dos índices e a alocação são dinâmicas e podem mudar várias vezes

• Vantagem: flexibilidade (matrizes podem crescer ou encolher durante a execução do programa)

Registro

Registro é uma estrutura básica que permite guardar coleções de dados de diferentes tipos, sendo normalmente utilizado quando um objeto tem diferentes atributos, isto é, contém campos de diferentes tipos.

Lista

Lista linear é uma estrutura de dados dinâmica na qual seus elementos estão organizados de maneira sequencial. Os tipos mais comuns de listas lineares são as pilhas, as filas e os deques.

Lista pode conter um número qualquer de elementos, expandindo-se ou contraindo-se conforme o elementos são inseridos ou retirados, por isso dizemos que ela não é estática, mas dinâmica. Nesse tipo de estrutura, os acessos só podem ser feitos sequencialmente.

É linear e dinâmica quando encadeada; apresenta um campo para conter o dado a ser armazenado e outro campo para apontar para o próximo elemento. Filas não podem ser encadeadas.

Lista circular: É uma lista onde de qualquer elemento da estrutura é possível acessar qualquer outro.

Lista linear: É uma estrutura de dados dinâmica na qual seus elementos estão organizados de maneira sequencial. Os tipos mais comuns de listas lineares são as pilhas, as filas e os deques.

Uma lista não-linear é uma estrutura de dados na qual os elementos estão organizados de maneira diversa à sequencial. O tipo mais comum de listas não-lineares é a árvore, que é uma estrutura de dados não-linear organizada sob uma forma recursiva, isto é, os elementos da árvores também são árvores.

Lista Simples (Lista Simplesmente Encadeada)

Na área de ciência da computação, uma lista ligada (ou lista simplesmente encadeada) é uma vantajosa alternativa na implantação de arranjos. Arranjos implicam que o tamanho de N elementos devem ser fixados a priori.

Uma alternativa para esta desvantagem é o uso de lista encadeadas, que permite a criação de arrays sem um número de N elementos fixo.

Uma lista é formada por nós. Nó é um objeto composto que armazena uma referência para um elemento ou objeto qualquer e uma referência next (próximo) que permite fazer a ligação com o próximo nó da lista até que o último aponte para uma região de memória nula (null).

O primeiro e o último nós de uma lista são chamados respectivamente de cabeça (referência head) e cauda (referência tail) da lista.

Exemplo de Lista Simplesmente Encadeada:

Numa lista singularmente encadeada, para acessar o último nodo é necessário partir do primeiro e ir seguindo os campos de ligação até chegar ao final da lista. Por isso dizemos que o acesso é sequencial.

Lista Duplamente Encadeada

Na área de ciência da computação, uma lista duplamente ligada (ou lista duplamente encadeada) é uma extensão da lista simplesmente ligada (ou lista simplesmente encadeada).

Numa lista cada elemento, ou nó, é composto normalmente por uma variável que guarda a informação (Objeto, inteiro, cadeia de caracteres, etc.) e dois ponteiros (referências a endereços de memória) que permitem a ligação entre os vários nós desta lista. Este tipo de lista é conhecido por “Duplamente ligada” ou “Duplamente encadeada” exatamente pelo fato de possuir duas variáveis de controle (ponteiros) ao contrário da lista simplesmente ligada que possui somente um, o qual aponta para o próximo elemento da lista.

A função destas variáveis é guardar o endereço de memória do nó anterior e do nó posterior, identificados normalmente como “previous” e “next”. Com estas estruturas podemos realizar diversas tarefas que seriam impossíveis ou muito dispendiosas com uma lista simplesmente encadeada.

No modelo mais simples deste tipo de lista, ao criar a lista o primeiro nó tem seu ponteiro “previous” apontando sempre para nulo e o último nó com seu “next” apontando para nulo. Este modelo não é muito confiável, já que não há um controle efetivo para saber quem é o primeiro e quem é o ultimo elemento, já que a única maneira de extrair tal informação é verificar quem possui o “prev” ou o “next” nulo.

Existem várias ramificações da lista duplamente encadeada, e muitas delas servem também para a lista simplesmente encadeada. Aqui temos alguns exemplos:

Lista duplamente encadeada com sentinelas: Neste modelo de lista possuímos dois Nós estáticos a cabeça da lista (head) e o fim da lista (tail). O elemento prev (anterior) do nó head aponta sempre para nulo enquanto no nó tail quem aponta para nulo é o next (próximo).

• Vantagens: Maior facilidade de controle da lista, maior confiabilidade e menor risco de perda acidental da lista.

• Desvantagens: Maior gasto de espaço em disco (2 nós a mais).

Lista duplamente encadeada circular: Neste modelo de lista possuímos apenas um sentinela. Esta lista é conhecida como circular pois o sentinela aponta para o primeiro elemento da lista e o último elemento da lista aponta para o sentinela, formando assim um círculo lógico.

• Vantagens: Economia de espaço em disco (1 nó a menos que a lista duplamente encadeada com sentinelas), maior confiabilidade em relação ao modelo comum.

• Desvantagens: Maior complexidade nos algoritmos.

Pilha e Fila

As pilhas e filas são conjuntos dinâmicos nos quais o elemento removido do conjunto pela operação DELETE é especificado previamente. Em uma pilha, o elemento eliminado do conjunto é o mais recentemente inserido: a pilha implementa uma norma de último a entrar, primeiro a sair, ou LIFO (last-in, first-out). De modo semelhante, em uma fila, o elemento eliminado é sempre o que esteve no conjunto pelo tempo mais longo: a fila implementa uma norma de primeiro a entrar, primeiro a sair, ou FIFO (first-in, first-out). Existem vários modos eficientes de implementar pilhas e filas em um computador. É possível implementar usando um arranjo simples essas duas estruturas.

Pilha

Pilha é uma estrutura de dados dinâmica (não estática) e linear com acesso restrito aos seus elementos, uma vez que eles são colocados e retirados por um único lado e são ordenados pelo princípio LIFO (Last In First Out – Último a entrar é o primeiro a sair) e pelo princípio FILO (Primeiro a entrar é o último a sair). Assim, sempre que um elemento é adicionado ou retirado seu topo é alterado. Porém, por apenas ser possível retirar o elemento do topo pode-se dizer que a pilha é uma estrutura de dados com acesso restrito aos seus elementos, uma vez que eles são colocados e retirados por um único lado e são ordenados pelo princípio LIFO (last in first out). Assim, sempre que um elemento é adicionado ou retirado seu topo é alterado.

O conceito de pilha é amplamente utilizado na informática, como, por exemplo, durante a execução de um programa, para o armazenamento de valores de variável local a um bloco e também para conter o endereço de retorno do trecho de programa que chamou a função ou procedimento atualmente em execução. Pilha é o tipo de estrutura usada, por exemplo, na avaliação de expressões numéricas, na recursividade e pelos compiladores, na passagem de parâmetros para as funções. Na execução de um programa, uma estrutura pode ser usada na chamada de procedimentos para armazenar o endereço de retorno (e os parâmetros reais). À medida que procedimentos chamam outros procedimentos, mais e mais endereços de retorno devem ser montados em determinada ordem para, posteriormente, serem recuperados corretamente à medida que os procedimentos chegam ao seu fim. Esta estrutura é adequadamente representada por uma pilha.

Por não ser estática, a implementação dinâmica de pilhas possui as mesmas vantagens que as listas dinâmicas, ou seja, não é necessário saber a quantidade máxima de elementos que serão armazenados.

Lista, pilha, fila e array são casos típicos de estruturas lineares, enquanto árvore, grafo e heap são casos típicos de estruturas não lineares.

A operação INSERT sobre uma pilha é chamada com frequência PUSH, e a operação DELETE, que não toma um argumento de elemento, é frequentemente chamada POP. Esses nomes são alusões a pilhas físicas, como as pilhas de pratos usados em restaurantes. A ordem em que os pratos são retirados da pilha é o oposto da ordem em que eles são colocados sobre a pilha e, como consequência, apenas o prato do topo está acessível.

Como mostra a figura abaixo, podemos implementar uma pilha de no máximo n elementos com um arranjos[ 1 .. N ]. O arranjo tem um atributo topo [S] que realiza a indexação do elemento inserido mais recentemente. A pilha consiste nos elementos S[1 .. Topo[S]], onde S[1] é o elemento na parte inferior da pilha e S[topo[S]] é o elemento na parte superior (ou no topo).

Quando topo[S] = O, a pilha não contém nenhum elemento e está vazia. É possível testar se a pilha está vazia, através da operação de consulta STACK-EMPTY. Se uma pilha vazia sofre uma operação de extração, dizemos que a pilha tem um estouro negativo, que é normalmente um erro. Se topo[S] excede n, a pilha tem um estouro positivo. (Em nossa implementação de pseudocódigo, não nos preocuparemos com o estouro de pilhas).

A figura acima é uma implementação de arranjo de uma pilha S. Os elementos da pilha só aparecem nas posições levemente sombreadas. (a) A pilhas tem 4 elementos. O elemento do topo é 9. (b) A pilhas após as chamadas PUSH(S, 17) e PUSH(S, 3). (c) A pilhas após a chamada POP(S) retomou o elemento 3, que é o elemento mais recentemente inserido na pilha. Embora o elemento 3 ainda apareça no arranjo, ele não está mais na pilha; o elemento do topo é o elemento 17.

Cada uma das operações sobre pilhas pode ser implementada com algumas linhas de código.

STACK-EMPTY(S)

1 if topo[S] =O

2 then return TRUE

3 else return FALSE

PUSH(S,x)

1 topo[S] = topo[S] + 1

2 S[topo[S]] = x

POP(5)

1 if STACK-EMP1Y(S)

2 then error “underflow”

3 else topo[S] = topo[S] – 1

4 return S[ topo [ S] + 1]

Atenção: a pilha aceita 2 operações básicas, entretanto em algumas questões a FCC considera que estas são 3, incluindo a operação: CHECK que verifica o elemento topo da pilha sem removê-lo.

Fila (Queue)

Filas e Listas são dinâmicas e lineares; Fila, assim como a pilha , é uma versão especial de lista.

As Filas podem sim ser implementadas através do encadeamento, vide o exemplo das “Filas com Lista Encadeada”.

Uma fila é uma estrutura de dados que admite inserção de novos elementos e remoção de elementos antigos. Mais especificamente, uma fila (= queue) é uma estrutura sujeita à seguinte regra de operação: sempre que houver uma remoção, o elemento removido é o que está na estrutura há mais tempo. Em outras palavras, o primeiro objeto inserido na fila é também o primeiro a ser removido. Essa política é conhecida pela sigla FIFO (= First-In-First-Out).

Portanto a fila segue:

• LILO significa Last In Last Out –> Último a entrar é o último a sair.

• FIFO significa First In First Out –> Primeiro a entrar é o primeiro a sair.

Chamamos a operação INSERT sobre uma fila de ENQUEUE (ENFILEIRAR), e também a operação DELETE de DEQUEUE (DESINFILEIRAR); como a operação POP sobre pilhas a operação DEQUEUE não tem nenhum argumento de elemento.

Em uma fila, cada operação ENQUEUE e DEQUEUE o tempo 0(1).

Lista, pilha, fila e array são casos típicos de estruturas lineares, enquanto árvore, grafo e heap são casos típicos de estruturas não lineares.

Pela definição de fila, se os elementos são inseridos por um extremo da lista linear, eles só podem ser removidos pelo outro.

A implementação de uma fila dupla normalmente é mais eficiente com uma lista duplamente encadeada que com uma encadeada simples.

Uma fila duplamente terminada, isto é, uma estrutura linear que permite inserir e remover de ambos os extremos é chamada Deque

Na fila de prioridade cada elemento tem associado a ele uma prioridade absoluta ou relativa. Novos elementos passam na frente os elementos com prioridade menor do que ele. A fila de prioridade ainda é uma fila e portanto Linear. Além disso, não se pode afirmar que é FIFO pois as filas de prioridades tem 3 operações que quebram o FIFO. InsertWithPriority que adiciona elemento com prioridade, GetNext que recupera o elemento com maior prioridade e o PeekAtNext que faz um busca na fila em busca do elemento de maior prioridade sem removê-lo.

Fila dupla (Deque)

O nome Deque vem da abreviação de Double-Ended Queue (fila com dois fins).

Numa fila dupla, os elementos podem ser inseridos e removidos de qualquer um dos extremos da fila.

Deque: São filas duplamente ligadas, isto é, filas com algum tipo de prioridade. Por exemplo, sistemas distribuídos sempre necessitam que algum tipo de processamento seja mais rápido, por ser mais prioritário naquele momento, deixando outro tipos mais lentos ou em fila de espera, por não requererem tanta pressa.

A implementação de uma fila dupla normalmente é mais eficiente com uma lista duplamente encadeada que com uma encadeada simples.

Uma fila dupla (Deque) é uma lista linear na qual os elementos podem ser inseridos ou removidos de qualquer extremo.

Hash ou Função de Espalhamento

A função de espalhamento ou função de dispersão é a responsável por gerar um índice a partir de determinada chave. Caso a função seja mal escolhida, toda a tabela terá um mau desempenho.

O ideal para a função de espalhamento é que sejam sempre fornecidos índices únicos para as chaves de entrada. A função perfeita seria a que, para quaisquer entradas A e B, sendo A diferente de B, fornecesse saídas diferentes. Quando as entradas A e B são diferentes e, passando pela função de espalhamento, geram a mesma saída, acontece o que chamamos de colisão.

Na prática, funções de espalhamento perfeitas ou quase perfeitas são encontradas apenas onde a colisão é intolerável (por exemplo, nas funções de dispersão da criptografia), ou quando conhecemos previamente o conteúdo da tabela armazenada. Nas tabelas de dispersão comuns a colisão é apenas indesejável, diminuindo o desempenho do sistema. Muitos programas funcionam sem que seu responsável suspeite que a função de espalhamento seja ruim e esteja atrapalhando o desempenho.

Por causa das colisões, muitas tabelas de dispersão são aliadas com alguma outra estrutura de dados, tal como uma lista encadeada ou até mesmo com árvores balanceadas. Em outras oportunidades a colisão é solucionada dentro da própria tabela.

Um bom método de resolução de colisões é essencial, não importando a qualidade da função de espalhamento. Considere um exemplo derivado do paradoxo do aniversário: mesmo que considerarmos que a função selecionará índices aleatórios uniformemente em um vetor de um milhão de posições, há uma chance de 95% de haver uma colisão antes de inserirmos 2500 registros.

Os mecanismos mais comuns para tratamento de colisões são: endereçamento aberto e encadeamento.

Tabela Hash ou Tabela de Dispersão

É um tipo de estrutura de dados em que a função de dispersão é a responsável por gerar um índice a partir de determinada chave; por causa das colisões, muitas tabelas de dispersão são aliadas com alguma outra estrutura de dados.

A tabela Hash é uma estrutura de dados que associa chaves de pesquisa a valores. Seu objetivo é, a partir de uma chave simples, fazer uma busca rápida e obter o valor desejado. Ela pode ser representada por um vetor onde cada posição deste é chamada de encaixe e armazena uma uma classe de partição.

Tabelas de dispersão são tipicamente utilizadas para implementar vetores associativos, conjuntos e caches. São tipicamente usadas para indexação de grandes volumes de informação (como bases de dados), uso em banco de dados, implementações das tabelas de símbolos dos compiladores, na programação de jogos para acessar rapidamente a posição para qual o personagem irá se mover e na implementação de um dicionário. A implementação típica busca uma função de dispersão que seja de complexidade O(1), não importando o número de registros na tabela (desconsiderando colisões). O ganho com relação a outras estruturas associativas (como um vetor simples) passa a ser maior conforme a quantidade de dados aumenta. Outros exemplos de uso das tabelas de dispersão são as tabelas de transposição em jogos de xadrez para computador até mesmo em serviços de DHCP.

Conjunto

Os conjuntos são tão fundamentais para a ciência da computação quanto o são para a matemática. Enquanto os conjuntos matemáticos são invariáveis, os conjuntos manipulados por algoritmos podem crescer, encolher ou sofrer outras mudanças ao longo do tempo. Chamamos tais conjuntos de conjuntos dinâmicos.

Os algoritmos podem exigir vários tipos diferentes de operações a serem executadas sobre conjuntos. Por exemplo, muitos algoritmos precisam apenas da capacidade de inserir, eliminar, e testar a pertinência de elementos a um conjunto. Um conjunto dinâmico que admite essas operações é chamado dicionário. Outros algoritmos exigem operações mais complicadas. Por exemplo, filas de prioridade mínima, que foram introduzidas no contexto da estrutura de dados do tipo heap (monte), admitem as operações de inserção de um elemento e de extração do menor elemento de um conjunto. A melhor maneira de implementar um conjunto dinâmico depende das operações que devem ser admitidas.

Os elementos de um conjunto dinâmico

Em uma implementação típica de um conjunto dinâmico, cada elemento é representado por um objeto cujos campos podem ser examinados e manipulados se tivermos um ponteiro para o objeto. Alguns tipos de conjuntos dinâmicos pressupõem que um dos campos do objeto é um campo de chave de identificação. Se as chaves são todas diferentes, podemos imaginar o conjunto dinâmico como um conjunto de valores de chaves. O objeto pode conter dados satélite, que são transportados em campos de outro objeto, mas não são utilizados de outro modo pela implementação do conjunto. Ele também pode ter campos que são manipulados pelas operações de conjuntos; esses campos podem conter dados ou ponteiros para outros objetos no conjunto.

Alguns conjuntos dinâmicos pressupõem que as chaves são extraídas de um conjunto totalmente ordenado, como o dos números reais, ou ainda o conjunto de todas as palavras que seguem a ordenação alfabética usual. (um conjunto totalmente ordenado satisfaz à propriedade de tricotomia) Uma ordenação total nos permite definir o elemento mínimo do conjunto, por exemplo, ou falar do próximo elemento maior que um dado elemento em um conjunto.

Operações sobre conjuntos dinâmicos

As operações sobre um conjunto dinâmico podem ser agrupadas em duas categorias: consultas, que simplesmente retornam informações sobre o conjunto, e operações de modificação, que alteram o conjunto. Aqui está uma lista de operações típicas. Qualquer aplicação específica normalmente exigirá que apenas algumas dessas operações sejam implementadas.

Search (S, k): Uma consulta que, dado um conjunto S e um valor de chave k, retorna um ponteiro x para um elemento em S tal que chave[x] = k, ou NIL se nenhum elemento desse tipo pertencer a S.

Insert (S, x): Uma operação de modificação que aumenta o conjunto S com o elemento apontado por x. Normalmente, supomos que quaisquer campos no elemento x necessários para a implementação do conjunto já tenham sido inicializados.

Delete (S, x): Uma operação de modificação que, dado um ponteiro x para um elemento no conjunto S, remove x de S. (Observe que essa operação utiliza um ponteiro para um elemento x, não um valor de chave.)

Minimun (S): Uma consulta sobre um conjunto totalmente ordenado S que retorna um ponteiro para o elemento de S com a menor chave.

Maximun (S): Uma consulta sobre um conjunto totalmente ordenado S que retorna um ponteiro para o elemento de S com a maior chave.

Successor (S, x): Uma consulta que, dado um elemento x cuja chave é de um conjunto totalmente ordenado S, retorna um ponteiro para o maior elemento seguinte em S, ou NIL se x é o elemento máximo.

Predecessor (S, x): Uma consulta que, dado um elementox cuja chave é de um conjunto totalmente ordenado S, retorna um ponteiro para o menor elemento seguinte em S, ou NIL se x é o elemento mínimo.

As consultas SUCCESSOR e PREDECESSOR frequentemente são estendidas a conjuntos com chaves não-distintas. Para um conjunto sobre n chaves, a suposição normal é que uma chamada a MINIMUM seguida por n – 1 chamadas a SUCCESSOR enumera os elementos no conjunto em sequência ordenada.

O tempo empregado para executar uma operação de conjunto é medido normalmente em termos do tamanho do conjunto dado como um de seus argumentos. Por exemplo, uma estrutura de dados que pode admitir quaisquer das operações listadas anteriormente sobre um conjunto de tamanho n no tempo O(log n).

Grafo

É uma noção simples, abstrata e intuitiva, usada para representar a ideia de alguma espécie de relação entre os objetos. Graficamente, aparece representado por uma figura com nós ou vértices.

Um grafo é uma estrutura de dados consistida em um conjunto de nós (ou vértices) e um conjunto de arcos (ou arestas).

Grafos são generalizações de árvores sendo cada nó chamado de vértice. É tipicamente uma representação de vértices ligados por arestas que eventualmente, podem ser direcionadas por meio de setas.

Grafo e Heap são casos típicos de estruturas não lineares.

Um algoritmo que pode ser usado para caminhar pela estrutura e retornar informações úteis para a resolução do problema. Uma estrutura de links do tipo “Wikipedia” é um modelo que pode ser representado por esta categoria de algoritmo, ou seja, os vértices são os artigos e “existe uma aresta do artigo X para o artigo Y se e somente se X contém um link para Y”. As características elencadas representam um algoritmo de exploração de grafo.

O comprimento do caminho: No grafo abaixo, o caminho V1, V2, V4, V3 tem comprimento igual a 3. Pois não é um grafo valorado, sendo assim basta contar a quantidade de arestas utilizadas no caminho.

Tipos de Grafos

Um grafo G = (V, A) é definido por um conjunto de vértices V e um conjunto de arestas A, as quais consistem em pares de vértices contidos em V. Há diversas propriedades fundamentais dos grafos que influenciam na escolha de estruturas de dados utilizadas para representá-los e os algoritmos para analisá-los. Vamos determinar quais são essas propriedades:

Indireto vs. Direto – Um grafo G = (V, A) é indireto se a aresta (x, y) pertencer a A e isso implicar que (y, x) também pertence. Se não, é tido como grafo direto. Ex: Ligações por estradas entre cidades são tipicamente indiretas, porque as estradas são de mão-dupla.

Valorado vs. Não-Valorado – Em grafos valorados, cada aresta (ou vértice) de G é assinalada com um valor numérico, ou peso. Uma aplicação típica são estradas, as quais são valoradas com a distância ou o tempo para percorrê-la. A diferença entre esses tipos é basicamente para encontrar o menor “caminho” entre dois vértices. Também conhecido como ponderado.

Simples vs. Não-Simples – Certos tipos de arestas complicam a tarefa de trabalhar com grafos. Um laço é uma aresta (x, x) envolvendo somente um vértice. Uma aresta (x, y) é múltipla se ocorre mais de uma vez no mesmo grafo. Um grafo que não possui nenhum desses tipos de aresta é chamado Grafo Simples.

Grafo conexo: Um gravo G(V,A) é dito conexo se há pelo menos uma cadeia ligando cada par de vértices deste grafo G.

Grafo fortemente conexo: se todo par de vértice está ligado por pelo menos um caminho em cada sentido, ou seja, se cada par de vértice participa de um circuito. Isso significa que cada vértice pode ser alcançável partindo-se de qualquer outro vértice do grafo. Como o grafo abaixo:

Grafo não orientado: Quando não há direção das arestas. Um grafo orientado difere de um não orientado comum, em que o último é definido em termos de pares não ordenados de vértices, que são normalmente chamados arestas. Cada arco em um grafo é especificado por um par de nós. Se os pares de nós que formam o arco forem pares ordenados, diz-se que o grafo é orientado.

Em grafos valorados, cada aresta (ou vértice) de G é assinalada com um valor numérico, ou peso. Uma aplicação típica são estradas, as quais são valoradas com a distância ou o tempo para percorrê-la. A diferença entre esses tipos é basicamente para encontrar o menor “caminho” entre dois vértices. Também conhecido como ponderado. O grafo em que os arcos possuem um número ou peso associados a eles é chamado de grafo ponderado.

Um grafo cujo nó de partida de um caminho coincide com o nó de chegada caracteriza um Grafo Cíclico.

Matriz de Incidência/Matriz de Adjacência

Uma matriz de incidência representa computacionalmente um grafo através de uma matriz bidimensional, onde uma das dimensões são vértices e a outra dimensão são arestas.

Dado um grafo G com n vértices e m arestas, podemos representá-lo em uma matriz n x m M. A definição precisa das entradas da matriz varia de acordo com as propriedades do grafo que se deseja representar, porém de forma geral guarda informações sobre como os vértices se relacionam com cada aresta (isto é, informações sobre a incidência de um vértice em uma aresta).

Para representar um grafo sem pesos nas arestas e não direcionado, basta que as entradas da matriz M contenham 1 se o vértice incide na aresta, 2 caso seja um laço (incide duas vezes) e 0 caso o vertice não incida na aresta.

Por exemplo, a matriz de incidência do grafo ao lado é

As entradas de uma matriz de incidência que representa um grafo onde uma das dimensões são vértices (vertical) e a outra são arestas (horizontal), são representadas apenas por três valores:

• 0 – Quando não há incidência

• 1 – Quando ocorre incidência (+ quando saí, – quando chega – em grafos direcionados).

• 2 – Quando a incidência é proveniente de um Loop.

“Para representar um grafo sem pesos nas arestas e não direcionado, basta que as entradas da matriz M contenham 1 se o vértice incide na aresta, 2 caso seja um laço (incide duas vezes) e 0 caso o vertice não incida na aresta.”

Na representação dos grafos em matrizes podemos fazê-los por:

1) matrizes INCIDENTES: relacionam os vértices as arestas – verifica qual vértice está ligado a qual aresta. (0=aresta não incide no vértice, 1=aresta incide no vértice, 2=aresta sai e incide no mesmo vértice)

2) matrizes ADJACENTES: Relacionam os vértices aos outros vértices – verifica quais vértices estão ligados entre si. (0 = vértice não ligado, 1 = vértice ligado). Quando for um grafo direcionado, deve ser atribuído 1 apenas no V_i até V_j, sendo que na matriz o i representa liha e o j colunas.

Árvores

Ao contrário das Lista, pilha, fila e array que são casos típicos de estruturas lineares, árvore, grafo e heap são casos típicos de estruturas não lineares.

Árvore, no contexto da programação, é uma estrutura de dados, não linear, que herda as características das topologias em árvore. Conceitualmente diferente das listas encadeadas, em que os dados se encontram numa sequência, nas árvores os dados estão dispostos de forma hierárquica.

A Árvore é composta por 1 (um) Elemento principal chamado Raiz, que possui ligações para outros Elementos, que são denominados de Ramos ou filhos. Estes ramos levam a outros elementos que também possuem outros ramos. O elemento que não possui ramos é conhecido como Folha e/ou Nó-terminal.

O conjunto de Árvores é conhecido como Floresta.

Na árvore cada elemento tem um ou mais elementos associados, podendo definir-se uma árvore recursivamente como:

• uma estrutura (uma árvore);

• um nó (designado por raiz), que contém a informação a armazenar e um conjunto finito de árvores (sub-árvores);

O número máximo de ramos em um elemento é chamado Ordem da Árvore. Uma árvore binária é aquela de ordem 2, i.e., em que cada elemento possui no máximo 2 ramos.

Uma das operações importantes consiste em percorrer cada elemento da árvore uma única vez. Esse percurso, também chamado de travessia da árvore, pode ser feito em pré-ordem (os filhos de um nó são processados após o nó) ou em pós-ordem (os filhos são processados antes do nó). Em árvores binárias é possível ainda fazer uma travessia em-Ordem, em que se processa o filho à esquerda, o nó, e finalmente o filho à direita.

• Pré-ordem (Pré-fixa): Se processa o nó, e depois os filhos a esquerda e depois a direita;

• Central (Infixa): processa o filho à esquerda, o nó, e por último o filho a direita.

• Pós-ordem (Pós-fixa): Se processa os filhos, e após o nó, , e depois os filhos a esquerda e depois a direita.

Outra Operação, utilizada nas árvores de pesquisa é a travessia da Raiz até uma das Folhas. Essa operação tem um custo computacional proporcional ao número de níveis da árvore. O pior caso é a travessia de todos os elementos até a folha de nível mais baixo. Árvores balanceadas apresentam o melhor pior caso possível, para um certo número de Nós. O pior caso apresenta-se na árvore degenerada em que cada Nó possui exatamente Um filho, e a árvore tem o mesmo número de níveis que de Nós, assemelhando-se a uma lista ligada.

Como ocorre no caso dos grafos, existem muitas noções de árvores relacionadas entre si, embora ligeiramente diferentes.

O número de subárvores de um nodo denomina-se grau

Uma árvore pode não conter elemento nenhum, ou seja, uma árvore vazia, ou nula.

Quando se elimina o nó raiz de uma estrutura em árvore, o que dela restar forma duas árvores, ou uma floresta.

A árvore também é conhecida por árvore livre, porém este segundo termo fica subentendido.

Árvores livres

Árvore livre é um grafo acíclico não orientado conectado. Com frequência, omitimos o adjetivo “livre” quando dizemos que um grafo é uma árvore. Se um grafo não orientado é acíclico mas possivelmente desconectado, ele é uma floresta. Muitos algoritmos que funcionam para árvores também funcionam para florestas.

1. Uma árvore linear

2. 3 árvores lineares, ou uma floresta

3. Um grafo que contém um ciclo, por essa razão, não é uma árvore nem uma floresta.

Árvores Enraizadas

Uma árvore enraizada é uma árvore livre na qual um dos vértices se distingue dos outros. O vértice distinto é chamado raiz da árvore. Com frequência, faremos referência a um vértice de uma árvore enraizada como um nó da árvore.

Árvores enraizadas e ordenadas. (a) Uma árvore enraizada com altura 4 (raiz não conta). A árvore é desenhada de um modo padrão: a raiz (nó 7) está na parte superior, seus filhos (os nós com profundidade 1) estão abaixo dela, os filhos dos filhos (nós com profundidade 2 – quantidade de níveis abaixo do nó que deseja se saber a profundidade) estão abaixo deles e assim por diante. Se a árvore é ordenada, a ordem relativa da esquerda para a direita dos filhos de um nó é importante; caso contrário, ela não é importante. (b) Outra árvore enraizada. Sendo uma árvore enraizada, ela é idêntica a árvore em (a) mas, como árvore ordenada é diferente, pois os filhos do nó 3 aparecem em uma ordem distinta.

O número de filhos de um nó x em uma árvore enraizada T é chamado grau de x. O comprimento do caminho desde a raiz r até um nó x é a profundidade de x em T (conta apartir do 0). A altura de um nó em uma árvore é o número de arestas no caminho descendente simples mais longo desde o nó até uma folha, e a altura de uma árvore é a altura de sua raiz. A altura de uma árvore também é igual a maior profundidade de qualquer nó na árvore. Uma árvore ordenada é uma árvore enraizada na qual os filhos de cada nó estão ordenados. Isto é, se um nó tem k filhos, então existe um primeiro filho, um segundo filho, … E um k-ésimo filho. As duas árvores da Figura são diferentes quando consideradas árvores ordenadas, mas são idênticas quando são consideradas apenas árvores enraizadas.

Observe que o grau de um nó depende de T ser considerada uma árvore enraizada ou uma árvore livre. O grau de um vértice em uma árvore livre é, como em qualquer grafo não orientado, o número de vértices adjacentes. Porém, em uma árvore enraizada, o grau é o número de filhos – o pai de um nó não conta para definir seu grau.

Árvore Binária

As árvores binárias são definidas de modo recursivo. Uma árvore binária T é uma estrutura definida em um conjunto finito de nós que:

• Não contém nenhum nó, ou

• É formada por três conjuntos disjuntos de nós: um nó raiz, uma árvore binária chamada sua subárvore da esquerda, e uma árvore binária chamada sua subárvore da direita.

A árvore binária que não contém nenhum nó é chamada árvore vazia ou árvore nula, algumas vezes denotada por NIL. Se a subárvore da esquerda é não vazia, sua raiz é chamada filho da esquerda da raiz da árvore inteira. Da mesma forma, a raiz de uma subárvore da direita não nula é o filho da direita da raiz da árvore inteira. Se uma subárvore é a árvore nula NIL, dizemos que o filho está ausente ou faltando. A Figura mostra uma árvore binária.

Árvores binárias: (a) Uma árvore binária desenhada de um modo padráo. O filho da esquerda de um nó é desenhado abaixo do nó e a esquerda. O filho da direita é desenhado abaixo e a direita do nó. (b) Uma árvore binária diferente da que está em (a). Em (a), o filho da esquerda do nó 7 é 5, e o filho da direita está ausente. Em (b), o filho da esquerda do nó 7 está ausente e o filho da direita é 5. Como árvores ordenadas, essas árvores são idênticas mas, como árvores binárias, elas sáo distintas. (c) A árvore binária em (a) representada pelos nós internos de uma árvore binária completa: uma árvore ordenada na qual cada nó interno tem grau 2. As folhas na árvore são mostradas como quadrados.

Existe um nodo especial denominado raiz e os demais nodos são particionados em T1 e T2 estruturas disjuntas de árvores binárias. T1 é denominado subárvore esquerda e T2 subárvore direita da raiz.

Árvore Binária é um caso especial de árvore em que nenhum nodo tem grau superior a 2, isto é, nenhum nodo tem mais que dois filhos.

As informações de posicionamento em uma árvore binária podem ser representadas pelos nós internos de uma árvore ordenada, como mostra a Figura (c). A ideia é substituir cada filho que falta na árvore binária por um nó que não tem nenhum filho. Esses nós folhas estão desenhados como quadrados na figura. A árvore resultante é uma árvore binária completa: cada nó é ou uma folha ou tem grau exatamente igual a 2. Não existe nenhum nó de grau 1. Em conseqüência disso, a ordem dos filhos de um nó preserva as informações de posição.

A figura acima mostra uma árvore binária completa de altura 3 com 8 folhas e 7 nós internos.

Uma árvore é uma coleção infinita de nós. Uma árvore binária só pode ter de 0 a 2 filhos.

As informações de posicionamento que distinguem árvores binárias de árvores ordenadas podem ser estendidas a árvores com mais de 2 filhos por nó. Em uma árvore posicional, os filhos de um nó são identificados com inteiros positivos distintos. O i-ésimo filho de um nó é ausente se nenhum filho é identificado com o inteiro i. Uma árvore k-ária é uma árvore posicional na qual, para todo nó, todos os filhos com rótulos maiores que k estão faltando. Desse modo, uma árvore binária é uma árvore k-ária com k = 2.

Uma árvore k-ária completa é uma árvore k-ária na qual todas as folhas têm a mesma profundidade e todos os nós internos têm grau k. A Figura acima mostra uma árvore binária completa de altura 3. Quantas folhas tem uma árvore k-ária completa de altura h? A raiz tem k filhos a profundidade l, cada um dos quais tem k filhos a profundidade 2 e assim por diante. Portanto, o número de folhas a profundidade h é k^h. Consequentemente, a altura de uma árvore k-ária completa com n folhas é log_k n. O número de nós internos de uma árvore k-ária completa de altura h é

Uma árvore binária, cuja raiz armazena o elemento R, é denominada árvore de busca binária se todo elemento armazenado na subárvore esquerda é menor que R, nenhum elemento armazenado na subárvore direita é menor que R e as subárvores esquerda e direita também são árvores de busca binária.

Árvore binária é um caso especial de árvore em que nenhum nodo tem grau superior a 2, isto é, nenhum nodo tem mais que dois filhos.

Existe um nodo especial denominado raiz e os demais nodos são particionados em T1 e T2 estruturas disjuntas de árvores binárias. T1 é denominado subárvore esquerda e T2 subárvore direita da raiz.

Árvore binária pode ser nula.

Uma árvore binária, cuja raiz armazena o elemento R, é denominada Árvore de Busca Binária se todo elemento armazenado na subárvore esquerda é menor que R, nenhum elemento armazenado na subárvore direita é menor que R e as subárvores esquerda e direita também são árvores de busca binária:

Exemplo 01: Uma árvore binária completa tem, no 5º nível, uma quantidade de nós igual a 16. Observe que a se pede o 5º Nível e não o nível 5. Assim, ele deseja o nível 4, uma vez que o nível inicia pelo 0.

• nível 0 = 1 nó

• nível 1 = 2 nós

• nível 2 = 4 nós

• nível 3 = 8 nós

• nível 4 = 16 nós

• nível 5 = 32 nós

Quantidade de Nós em uma árvore binária completa = 2^N

Exemplo 02: Uma árvore binária completa, estritamente binária, cuja raiz está no nível 0 e a altura da árvore é 5, possui uma quantidade de nós igual a 63

• Altura 00 (raiz): 2⁰ = 1

• Altura 01: 2¹ = 2

• Altura 02: 2² = 4

• Altura 03: 2³ = 8

• Altura 04: 2⁴ = 16

• Altura 05: 2⁵ = 32

Então até a altura 05 de uma árvore binária completa haverá a soma de todos os nós, de todas as alturas: 1 + 2 + 4 + 8 + 16 + 32 = 63.

O nível da árvore binária equivale à sua altura e começa a contar de zero. Logo, se tem 5 de altura, conta-se de 0 a 5. Não esquecer: NIVEL = ALTURA. Inicia-se em ZERO (0).

Para facilitar mais ainda basta usar a fórmula: 2 ^(altura+1) – 1 = 2 ⁵⁺¹-1 = 2⁶-1 = 64-1 = 63

Se a altura é 5, então existem 6 camadas.

Árvore AVL ou Árvore Balanceada pela Altura

É uma árvore de busca binária auto-balanceada. Em tal árvore, as alturas das duas sub-árvores a partir de cada nó difere no máximo em 1 unidade (fator de balanceamento). As operações de busca, inserção e remoção de elementos possuem complexidade O( log2 n ) (no qual é o número de elementos da árvore). Inserções e remoções podem também requerer o rebalanceamento da árvore, exigindo uma ou mais rotações.

Á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á igual a -1, 0 ou 1.

Se a árvore não estiver balanceada é necessário reavaliar o balanceamento através de rotação simples ou dupla à direita ou à esquerda.

As operações de busca, inserção e remoção tem complexidade O(log n).

Árvore AVL: Ou árvore balanceada pela altura. É uma árvore de busca binária auto-balanceada.

Exemplo de árvore não-AVL:

Exemplo da mesma árvore após o balanceamento:

Uma estrutura de dados onde cada nó mantém uma informação adicional, chamada fator de balanceamento, que indica a diferença de altura entre as subárvores esquerda e direita, é conhecida por árvore AVL

Árvore AVL é uma árvore de busca binária auto balanceada, onde a altura da subárvore esquerda e da subárvore da direita difere de 1, sendo este denominado fator de balanceamento. Se a árvore não estiver balanceada é necessário reavaliar o balanceamento através de rotação simples ou dupla à direita ou à esquerda. As operações de busca, inserção e remoção tem complexidade O(log n).

O FATOR DE BALANCEAMENTO DE UM NÓ É DADO PELO SEU PESO EM RELAÇÃO A SUA SUB-ÁRVORE. UM NÓ COM FATOR BALANCEADO PODE CONTER 1, 0, OU -1 EM SEU FATOR. Um nó com fator de balanceamento diferente dos citados é considerado uma árvore não-AVL e requer um balanceamento por rotação ou dupla-rotação.

Árvore B

Proposta por Bayer e mcCreight em 1972 a árvore B opera junto com o armazenamento secundário e pode ser sintonizada para reduzir os transtornos impostos por essa armazenagem.

Uma propriedade importante das árvores B é o tamanho de cada nó, que pode ser tão grande quanto é o tamanho de um bloco.

Uma árvore B é uma árvore de busca múltipla com as seguintes propriedades:

• A raiz tem pelo menos duas subárvores, a menos que ela seja uma folha;

• Cada nó não-raiz e não-folha contém k-1 chaves e k ponteiros para as subárvores onde [m/2] ≤ k ≤ [m/2]-1 e n-1 elementos.;

• As folhas vão estar no mesmo nível.

Abaixo vemos um exemplo de uma árvore B de ordem 5.

• A raiz tem pelo menos duas subárvores, a menos que ela seja uma folha – OK

• Cada nó não-raiz e não folha contém

  • K-1 chaves: K = ordem 5, K – 1 = 4 chaves (No máximo)

  • K ponteiro: K = ordem 5, K = 5 ponteiros

    • Teto de 5/2 = teto de 2,5 = 3

    • m = 5

      • 3 ≤ 5 ≤ 5 – OK

• As folhas vão estar no mesmo nível – OK.

Heap

A estrutura de dados heap (binário) é um objeto arranjo que pode ser visto como uma árvore binária praticamente completa. Cada nó da árvore corresponde a um elemento do arranjo que armazena o valor no nó. A árvore está completamente preenchida em todos os níveis, exceto talvez no nível mais baixo, que é preenchido a partir da esquerda até certo ponto.

Um arranjo A que representa um heap é um objeto com dois atributos: comprimento[A], que é o número de elementos no arranjo, e tamanho-do-heap(A], o número de elementos no heap armazenado dentro do arranjo A. Ou seja, embora A[1 .. Comprimento[ A]] possa conter números válidos, nenhum elemento além de A[ tamanho-do-heap [A]], onde tamanho-do-heap[A] <= comprimento(A], é um elemento do heap. A raiz da árvore é A[ 1] e, dado o índice i de um nó, os índices de seu pai PARENT(t), do filho da esquerda LEFT(t) e do filho da direita RIGHT(t) podem ser calculados de modo simples:

Um heap máximo visto como (a) uma árvore binária e (b) um arranjo. O número dentro do círculo em cada nó na árvore é o valor armazenado nesse nó. O número acima de um nó é o índice correspondente no arranjo. Acima e abaixo do arranjo encontramos linhas mostrando relacionamentos pai-filho; os pais estão sempre à esquerda de seus filhos. A árvore tem altura três; o nó no índice 4 (com o valor 8) tem altura um.

PARENT(t) – return Li/2J

LEFT(t) – return 2i

RIGHT(t) – return 2i + 1

Em ciência da computação, um heap é uma estrutura de dados organizada como árvore binária balanceada, seguindo algumas regras. Este pode ser implementado em um arranjo, para que ele seja acessado como uma árvore binária, usando as seguintes operações: Pai, Esquerda, Direita. (Pré-Fixa)

Se estiver bem implementado estas são macros ou procedimentos “inline”. Estas operações podem ser executadas rapidamente usando operações bit a bit.[2] Para o filho esquerdo desloca os bits a esquerda, para o direito desloca os bits para a esquerda e aplica a operação “ou” com 1. Para encontrar o pai, desloca um bit a direita. A vantagem de usar operações bit a bit, é que cada uma delas usa apenas um clock do processador, sendo altamente eficiente.

Existem dois tipos de heaps: Os heaps de máximo (max heap), em que o valor de todos os nós são menores que os de seus respectivos pais; e os heaps de mínimo (min heap), em que o valor todos os nós são maiores que os de seus respectivos pais. Assim, em um heap de máximo, o maior valor do conjunto está na raiz da árvore, enquanto no heap de mínimo a raíz armazena o menor valor existente.

A árvore binária do heap deve estar completa até pelo menos seu penúltimo nível e, se o seu último nível não estiver completo, todos os nós do último nível deverão estar agrupados à esquerda.

Uma das utilizações mais tradicionais do heap é no algoritmo de ordenação Heap Sort, que utiliza a propriedade do heap de o maior (ou menor valor) localizar-se na raiz do mesmo e fazer a ordenação dos dados de uma maneira bastante eficiente.

Também pode ser usada como heaps de prioridades onde a raiz é a maior prioridade. Com relação ao vetor a, inserção e remoção, é da ordem O(log(n)).

Outra utilização de heaps são em algoritmos de seleção. Operações de encontrar o maior, ou menor, elemento de um conjunto de números é realizado de uma forma bastante eficiente, em comparação com a utilização de uma lista ligada ordenada.

Algoritmos

Um algoritmo é qualquer procedimento computacional bem definido que toma algum valor ou conjunto de valores como entrada e produz algum valor ou conjunto de valores como saída. Portanto, um algoritmo é uma sequência de passos computacionais que transformam a entrada na saída.

A ordem de crescimento do tempo de execução de um algoritmo fornece uma caracterização simples da eficiência do algoritmo, e também nos permite comparar o desempenho relativo de algoritmos alternativos. Uma vez que o tamanho da entrada n se torna grande o suficiente, a ordenação por intercalação, com seu tempo de execução do pior caso E>(n lg n), vence a ordenação por inserção, cujo tempo de execução do pior caso é E>(n2). Embora às vezes seja possível determinar o tempo exato de execução de um algoritmo a precisão extra em geral não vale o esforço de calculá-la. Para entradas grandes o bastante, as constantes multiplicativas e os termos de mais baixa ordem de um tempo de execução exato são dominados pelos efeitos do próprio tamanho da entrada.

Quando observamos tamanhos de entrada grandes o suficiente para tomar relevante apenas a ordem de crescimento do tempo de execução, estamos estudando a eficiência assintótica dos algoritmos. Ou seja, estamos preocupados com a maneira como o tempo de execução de um algoritmo aumenta com o tamanho da entrada no limite, à medida que o tamanho da entrada aumenta indefinidamente (sem limitação). Em geral, um algoritmo que é assintoticamente mais eficiente será a melhor escolha para todas as entradas, exceto as muito pequenas.

Notação Assintótica

Notação O Grande (também conhecida como big O notation, no inglês, notação Landau, notação Bachmann–Landau e notação assintótica) descreve o comportamento limitante de uma função quando o argumento tende a um determinado valor ou ao infinito, geralmente em termos de funções mais simples. A notação O Grande permite que seus usuários simplifiquem funções para que se concentrem em suas taxas de crescimento: Funções diferentes com a mesma taxa de crescimento podem ser representadas usando a mesma notação O.

Apesar de ser desenvolvida como parte da matemática pura, atualmente esta notação é comumente utilizada na análise de algoritmos para descrever o uso de recursos computacionais realizado por um determinado algoritmo a partir da análise da complexidade do tempo de execução utilizando a análise do pior caso, caso médio ou melhor caso.

A complexidade de algoritmos é muito importante para avaliar o tempo de execução de qualquer algoritmo. Para responder a questão podemos considerar, por exemplo, n = 100.

Obs: Na análise assintótica Log N é Log na base 2!

Então:

• Tempo de Execução do Algoritmo A = O(log n) = log 100 = 5, onde a base é 2, 2^5, = 100;

• Tempo de Execução do Algoritmo B = O(n²) = 100² = 10000;

• Tempo de Execução do Algoritmo C = O(n log n ) = 100 log 100 = 100×2 = 200,

Logo, tempo de B > tempo de C > tempo de A, B é o que tem a pior eficiência.

Alguns exemplos de algoritmos que possuem complexidade O(log n) são as buscas binárias e buscas em uma árvore binária de busca que esteja balanceada (árvores binárias não balanceadas vão ter complexidade no pior caso de O(n)).

Essa complexidade é conseguida, no caso das buscas, em sempre “eliminar” a metade do total atual da lista em uma única iteração, ou seja, na primeira iteração elimina 50% do total, na segunda 75% (50% + 25%), terceira 87,5%(50% + 25% + 12,5%) e assim vai até achar o resultado. Dessa forma o número máximo de iterações sempre será, no pior caso, um logaritmo na base 2 de n, onde n é igual ao número máximo de elementos contidos na lista.

Por exemplo, realizar uma busca binária em um vetor de 8 posições. Na primeira iteração serão eliminados 04 valores, na segunda 2 e na terceira 1. Caso não seja achado o valor o algoritmo terminará, pois não haverá mais nem um campo a ser pesquisado. Então a complexidade dessa busca é no pior caso de 3 iterações, que é exatamente o valor de log8 na base 2. Pois 2³ = 8.

Vale ressaltar que para ser possível alguma forma de pesquisa binária a lista deve estar ordenada.

Observação, para analisar o limite máximo é utilizado o Ɵ, já o limite inferior é representado pelo símbolo Ω.

Algoritmos de Busca

Busca Linear (Sequencial)

Costuma-se usar o termo busca linear (ou busca sequencial) para expressar um tipo de pesquisa em vetores ou listas de modo sequencial, i. e., elemento por elemento, de modo que a função do tempo em relação ao número de elementos é linear, ou seja, cresce proporcionalmente. Num vetor ordenado, essa não é a pesquisa mais eficiente, a pesquisa (ou busca) binária, por exemplo, é um tipo de pesquisa com o gráfico de tempo logarítmico.

Sequencial – Faz o que o próprio nome diz, percorre todo vetor até encontrar o valor desejado.

No melhor caso, o elemento a ser buscado é encontrado logo na primeira tentativa da busca. No pior caso, o elemento a ser buscado encontra-se na última posição e são feitas N comparações, sendo N o número total de elementos. No caso médio, o elemento é encontrado após N/2 comparações. O algoritmo de busca linear é um algoritmo O(n).

Uma busca linear é realizada pela seleção de um elemento após o outros sendo que para selecionar o último elemento de uma estrutura com 10 elementos teria que percorrer todos os 9 primeiros elementos.

Busca Binária

Os algoritmos de busca binária e de busca sequencial executam processamento repetitivo, e não recursivo. A busca linear não é indicada para vetores ordenados (1,2,3…), para este a melhor indicação é a busca Binária.

Binário – Usa três ponteiros chamados de inicio, meio e fim, e vai diminuindo a busca alternando os ponteiros, consequentemente, diminuindo os espaços até encontrar o valor desejado.

É um método de pesquisa ou busca, cujo algoritmo parte do pressuposto de que o vetor está ordenado e realiza sucessivas divisões do espaço de busca, comparando o elemento buscado (chave) com o elemento no meio do vetor. Se o elemento do meio do vetor for a chave, a busca termina com sucesso. Caso contrário, se o elemento do meio vier antes do elemento buscado, então a busca continua na metade posterior do vetor. E finalmente, se o elemento do meio vier depois da chave, a busca continua na metade anterior do vetor. Trata-se do método denominado busca binária.

A pesquisa ou busca binária (em inglês binary search algorithm ou binary chop) é um algoritmo de busca em vetores que segue o paradigma de divisão e conquista. Ela parte do pressuposto de que o vetor está ordenado e realiza sucessivas divisões do espaço de busca comparando o elemento buscado (chave) com o elemento no meio do vetor. Se o elemento do meio do vetor for a chave, a busca termina com sucesso. Caso contrário, se o elemento do meio vier antes do elemento buscado, então a busca continua na metade posterior do vetor. E finalmente, se o elemento do meio vier depois da chave, a busca continua na metade anterior do vetor.

A complexidade desse algoritmo é da ordem de Θ(log2 n), em que n é o tamanho do vetor de busca. Apresenta-se mais eficiente que a Busca linear cuja ordem é O(n).

A busca binária é definida pela seleção de elementos maiores ou menores que um dado índice da estrutura de dados. Por exemplo: se você está buscando um elemento X na estrutura de dados E inicialmente irá escolher algum elemento (E1) dessa estrutura (pode ser aleatoriamente este primeiro elemento). Logo em seguida irá ver se esse elemento E1 é maior ou menor que X, caso seja maior agora a busca ser realizará entre o próximo elemento maior que E1 e o último elemento de E, caso contrário entre o elemento anterior a E1(o primeiro menor que E1) e o primeiro elemento que E, definindo sempre um intervalo menor para a busca normalmente em metade dos elementos da primeira busca até encontrar, ou não, o elemento X.

O algoritmo conhecido como busca binária é um algoritmo de desempenho ótimo para encontrar a posição de um item em um vetor ordenado.

Por exemplo, realizar uma busca binária em um vetor de 8 posições. Na primeira iteração serão eliminados 4 valores, na segunda 2 e na terceira 1. Caso não seja achado o valor o algoritmo terminará, pois não haverá mais nem um campo a ser pesquisado. Então a complexidade dessa busca é no pior caso de 3 iterações, que é exatamente o valor de log8 na base 2. Pois 2³ = 8.

Busca em Tabelas

Este algoritmo de busca possui a característica de existência de índices para os elementos, também conhecida como busca indexada ou busca em tabelas Hash. Caso queira selecionar um elemento X da tabela esse elemento passará por um processo de tradução em índice e irá diretamente buscar o elemento com apenas uma seleção (caso seja uma tabela resistente a colisões)

Resistência a colisões é uma importante propriedade de tabelas hash que mantém a complexidade de busca em O(1), ou seja apenas uma seleção para encontrar o elemento desejado.

Busca em Cadeia (Busca em String)

Atualmente os dois métodos mais eficientes de busca em cadeias correspondem aos conhecidos métodos de Hnuth-Norris-Pratt (KMP) e o método Boyer-Moore (BM).

Seja T o texto e P o parâmetro procurado em T, o método BM consegue evitar comparações entre P e uma boa parte dos caracteres em T. O único problema desse algoritmo é que ele trabalha com um alfabeto limitado. O método KMP evita o desperdício de informações que ocorrem em outros algoritmos. Possui pré-processamento de P, permitindo que nenhum caractere seja reexaminado.

Algoritmos de Ordenação

Por Divisão e Conquista (Particionamento)

Quick Sort

Características:

Classe: Algoritmo de Ordenação

Estrutura de Dados: Array, Listas Ligadas

Complexidade no Pior Caso: O (n²) – n (número de elementos)

Complexidade no Caso Médio: O (n log n) – n (número de elementos)

Complexidade no Melhor Caso: O (n log n) – n (número de elementos)

Complexidade de espaços no Pior Caso: O (n) – n (número de elementos)

Ótimo: Não

Estabilidade: Não Estável

O algoritmo Quicksort é um método de ordenação muito rápido e eficiente, inventado por C.A.R. Hoare em 1960, quando visitou a Universidade de Moscovo como estudante. Naquela época, Hoare trabalhou em um projeto de tradução de máquina para o National Physical Laboratory. Ele criou o Quicksort ao tentar traduzir um dicionário de inglês para russo, ordenando as palavras, tendo como objetivo reduzir o problema original em subproblemas que possam ser resolvidos mais fácil e rapidamente. Foi publicado em 1962 após uma série de refinamentos.

O Quick Sort (ordenação rápida) é um algoritmo de ordenação cujo tempo de execução do pior caso é E>(n2) sobre um arranjo de entrada de n números. Apesar desse tempo de execução lento no pior caso, o Quick Sort com frequência é a melhor opção prática para ordenação, devido a sua notável eficiência na média: seu tempo de execução esperado é E>(n lg n), e os fatores constantes ocultos na notação E>(n lg n) são bastante pequenos. Ele também apresenta a vantagem da ordenação local e funciona bem até mesmo em ambientes de memória virtual.

O Quicksort é um algoritmo de ordenação por comparação não-estável.

O Quicksort adota a estratégia de divisão e conquista. A estratégia consiste em rearranjar as chaves de modo que as chaves “menores” precedam as chaves “maiores”. Em seguida o Quicksort ordena as duas sublistas de chaves menores e maiores recursivamente até que a lista completa se encontre ordenada. Os passos são:

1. Escolha um elemento da lista, denominado pivô;

2. Rearranje a lista de forma que todos os elementos anteriores ao pivô sejam menores que ele, e todos os elementos posteriores ao pivô sejam maiores que ele. Ao fim do processo o pivô estará em sua posição final e haverá duas sublistas não ordenadas. Essa operação é denominada partição;

3. Recursivamente ordene a sublista dos elementos menores e a sublista dos elementos maiores;

A base da recursão são as listas de tamanho zero ou um, que estão sempre ordenadas. O processo é finito, pois a cada iteração pelo menos um elemento é posto em sua posição final e não será mais manipulado na iteração seguinte.

O método de ordenação Quick Sort (ordenação rápida) é um método sofisticado de ordenação de vetores que é baseado no fato de que as permutações devem ser preferencialmente empregadas para pares de elementos que guardem entre si distâncias grandes, com a finalidade de se conseguir uma eficiência maior.

Complexidade

Complexidade de tempo: θ(n lg2 n) no melhor caso e caso médio e θ(n2) no pior caso;

Complexidade de espaço: θ(lg2 n) no melhor caso e no caso médio e θ(lg2 n) no pior caso. R. Sedgewick desenvolveu uma versão do Quicksort com partição recursão de cauda que tem complexidade θ(n2) no pior caso.

Comparação com outros algoritmos de ordenação

Quicksort é uma versão otimizada de uma árvore binária ordenada. Em vez de introduzir itens sequencialmente numa árvore explicita, o Quicksort organiza-os correntemente na árvore onde está implícito, fazendo-o com chamadas recursivas à mesma. O algoritmo faz exatamente as mesmas comparações, mas com uma ordem diferente.

O algoritmo que mais se familiariza com o Quicksort é o Heapsort. Para o pior caso neste algoritmo temos θ(lg2 n). Mas, o Heapsort em média trata-se de uma algoritmo mais lento que o Quicksort, embora tenha sido muito debatido essa afirmação. No Quicksort permanece o caso do pior caso, à exceção quando se trata de usar a variante IntroSort, que muda para Heapsort quando um pior caso é detectado. Caso se saiba à partida que será necessário o uso do Heapsort é aconselhável usá-lo diretamente, do que usar o IntroSort e depois chamar o Heapsort, torna mais rápido o algoritmo.

O Quicksort também compete com o MergeSort, outro algoritmo de ordenação recursiva, tendo este o benefício de ter como pior caso θ(lg n) . MergeSort, ao contrário do Quicksort e do Heapsort, é estável e pode facilmente ser adaptado para operar em listas encadeadas e em listas bastantes grandes alojadas num tipo de acesso lento a média como um Network-Attached Storage ou num disco. Embora o Quicksort possa ser operado em listas encadeadas, por vezes escolhendo um mau pivô sem acesso aleatório. A maior desvantagem do Mergesort é que quando opera em arrays, requer θ(n) de espaço para o melhor caso, considerando que o Quick sort com um particionamento espacial e com recursão utiliza apenas θ(lg n) de espaço.

Bucket sort com dois buckets é muito idêntico ao Quicksort, o pivô neste caso é garantidamente o valor do meio do vetor.

Merge Sort

Características:

Classe: Algoritmo de Ordenação

Estrutura de Dados: Array, Listas Ligadas

Complexidade no Pior Caso: O (n log n) – n (número de elementos)

Complexidade no Caso Médio: O (n log n) – n (número de elementos)

Complexidade no Melhor Caso Típico: O (n log n) – n (número de elementos)

Complexidade no Melhor Caso Natural: O (n) – n (número de elementos)

Complexidade de espaços no Pior Caso: O (n) – n (número de elementos)

O Merge Sort, ou ordenação por mistura, é um exemplo de algoritmo de ordenação do tipo dividir-para-conquistar.

Sua ideia básica consiste em 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, ordena-as; depois as agrupa em sequências de quatro elementos, e assim por diante, até ter toda a sequência dividida em apenas duas partes.

Classificação por intercalação: Os métodos de classificação por intercalação dividem a tabela em dois ou mais segmentos, ordenam estes segmentos e depois os intercalam, terminando, ao final, com um único segmento (toda a tabela) ordenado. O principal algoritmo desta família é o mergesort (ou Intercalação Simples).

Mergesort (Intercalação Simples): A idéia por traz do mergesort é bastante simples: divide-se a tabela em diversos segmentos menores para a seguir ordenar-se estes segmentos. Feito isto, estes segmentos são agrupados entre si (intercalados) e este processo produz novos segmentos ordenados (maiores que os segmentos iniciais). O processo de agrupamento e ordenação dos segmentos (intercalação) continua até que se obtenha um único segmento que contenha toda a tabela e esteja totalmente ordenado.

Os três passos úteis dos algoritmos dividir-para-conquistar, ou divide and conquer, que se aplicam ao merge sort são:

• Dividir: Dividir os dados em subsequências pequenas;

• Conquistar: Classificar as duas metades recursivamente aplicando o merge sort;

• Combinar: Juntar as duas metades em um único conjunto já classificado.

É possível implementar o merge sort utilizando somente um vetor auxiliar ao longo de toda a execução, tornando assim a complexidade de espaço adicional igual a Θ(n log n).

Desvantagens: Implementação complexa, Ideia complexa, Utiliza funções recursivas.

Tim Sort

Características:

Classe: Algoritmo de Ordenação

Estrutura de Dados: Array, Listas Ligadas

Complexidade no Pior Caso: O (n log n) – n (número de elementos), k (tamanho da string)

Complexidade no Caso Médio: O (n log n) – n (número de elementos), k (tamanho da string)

Complexidade no Melhor Caso: O (n) – n (número de elementos), k (tamanho da string)

Complexidade de Espaços no Pior Caso: O (n) – n (número de elementos), s (tamanho do alfabeto)

Estabilidade: Estável

Tim Sort é um algoritmo de ordenação híbrido derivado do merge sort e do insertion sort, projetado para ter boa performance em vários tipos de dados do mundo real. Foi inventado por Tim Peters em 2002 para ser usado na linguagem de programação Python, e tem sido o algoritmo de ordenação padrão de Python desde a versão 2.3. Ele atualmente é usado para ordenar Arrays em Java SE.

É um método adaptativo, estável, merge sort natural, modestamente chamado de Tim Sort. Tem desempenho sobrenatural em muitos tipos de arrays parcialmente ordenados (menos de lg(N!) comparações necessárias, e tão poucas quanto N-1), no entanto, tão rápido quanto o algoritmo anterior altamente otimizado, híbrido, Sample Sort de Python em matrizes aleatórias. Em suma, a rotina principal passa sobre a matriz uma vez, da esquerda para a direita, alternadamente, identificando o próximo passo, em seguida, fundindo-os em passos anteriores “inteligentemente”. Todo o resto é complicação pela velocidade, e alguma medida duramente conquistada da eficiência de memória.

Por Comparação/Troca

Bubble Sort

Características:

Classe: Algoritmo de Ordenação

Estrutura de Dados: Array, Listas Ligadas

Complexidade no Pior Caso: O (n²) – n (número de elementos)

Complexidade no Caso Médio: O (n²) – n (número de elementos)

Complexidade no Melhor Caso: O (n²) – n (número de elementos)

Complexidade de Espaços no Pior Caso – Auxiliar: O (1)

O Bubble Sort, ou Ordenação por Flutuação (literalmente “por bolha”), é um algoritmo de ordenação dos mais simples. A ideia é percorrer o vector diversas vezes, a cada passagem fazendo flutuar para o topo o maior elemento da sequência. Essa movimentação lembra a forma como as bolhas em um tanque de água procuram seu próprio nível, e disso vem o nome do algoritmo.

No melhor caso, o algoritmo executa n² operações relevantes, onde n representa o número de elementos do vector.

A complexidade desse algoritmo é de Ordem quadrática. Por isso, ele não é recomendado para programas que precisem de velocidade e operem com quantidade elevada de dados.

Comb Sort

Características:

Classe: Algoritmo de Ordenação

Estrutura de Dados: Array, Listas Ligadas

Complexidade no Pior Caso: O (n²) – n (número de elementos)

Complexidade de Espaços no Pior Caso: O (1)

O algoritmo Comb sort (ou Combo sort ou ainda algoritmo do pente) é um algoritmo de ordenação relativamente simples, e faz parte da família de algoritmos de ordenação por troca. Foi desenvolvido em 1980 por Wlodzimierz Dobosiewicz. Mais tarde, foi redescoberto e popularizado por Stephen Lacey e Richard Box em um artigo publicado na revista Byte em Abril de 1991. O Comb sort melhora o Bubble sort, e rivaliza com algoritmos como o Quicksort. A ideia básica é eliminar as tartarugas ou pequenos valores próximos do final da lista, já que em um bubble sort estes retardam a classificação tremendamente. (Coelhos, grandes valores em torno do início da lista, não representam um problema no bubble sort).

O Algoritmo repetidamente reordena diferentes pares de itens, separados por um salto, que é calculado a cada passagem. Método semelhante ao Bubble Sort, porém mais eficiente.

Na Bubble sort, quando quaisquer dois elementos são comparados, eles sempre têm um gap (distância um do outro) de 1. A ideia básica do Comb sort é que a diferença pode ser muito mais do que um. (O Shell sort também é baseado nesta ideia, mas é uma modificação do insertion sort em vez do bubble sort).

O gap (intervalo) começa como o comprimento da lista a ser ordenada dividida pelo fator de encolhimento (em geral 1,3; veja abaixo), e a lista é ordenada com este valor (arredondado para um inteiro se for necessário) para o gap. Então, a diferença é dividida pelo fator de encolhimento novamente, a lista é ordenada com este novo gap, e o processo se repete até que a diferença seja de 1. Neste ponto, o Comb sort continua usando um espaço de 1 até que a lista esteja totalmente ordenada. A fase final da classificação é, portanto, equivalente a um bubble sort, mas desta vez a maioria dos elementos “tartarugas” já foram tratados, assim o bubble sort será eficiente.

Shaker Sort

Características:

Classe: Algoritmo de Ordenação

Estrutura de Dados: Array, Listas Ligadas

Complexidade no Pior Caso: O (n²) – n (número de elementos)

Cocktail sort, também conhecido como Shaker Sort, bubble sort bidirecional (que também pode se referir a uma variante do selection sort), ripple sort, shuttle sort ou happy hour sort, é uma variação do bubble sort que é tanto um algoritmo de ordenação estável quanto uma ordenação por comparação. O algoritmo difere do bubble sort pelo fato de ordenar em ambas as direções em cada passagem através da lista. Este algoritmo de ordenação é apenas ligeiramente mais difícil de implementar do que o bubble sort, e resolve o problema com os chamados coelhos e tartarugas no bubble sort.

Por Seleção

Selection Sort

Características:

Classe: Algoritmo de Ordenação

Estrutura de Dados: Array, Listas Ligadas

Complexidade no Pior Caso: O (n²) – n (número de elementos)

Complexidade no Caso Médio: O (n²) – n (número de elementos)

Complexidade no Melhor: O (n²) – n (número de elementos)

Complexidade de espaços no Pior Caso – Total: O (n) – n (número de elementos)

Complexidade de espaços no Pior Caso – Auxiliar: O (1) – n (número de elementos)

O Selection sort (do inglês, Ordenação por Seleção) ou Seleção Direta é um algoritmo de ordenação baseado em se passar sempre o menor valor do vetor para a primeira posição (ou o maior dependendo da ordem requerida), depois o de segundo menor valor para a segunda posição, e assim é feito sucessivamente com os (n-1) elementos restantes, até os últimos dois elementos.

Heap Sort

Características:

Classe: Algoritmo de Ordenação

Estrutura de Dados: Array, Listas Ligadas

Complexidade no Pior Caso: O (n log n) – n (número de elementos)

Complexidade no Caso Médio: O (n log n) – n (número de elementos)

Complexidade no Melhor Caso: O (n log n) – n (número de elementos)

Complexidade de espaços no Pior Caso – Total: O (n) – n (número de elementos)

Complexidade de espaços no Pior Caso – Auxiliar: O (1) – n (número de elementos)

O algoritmo Heap Sort é um algoritmo de ordenação generalista, e faz parte da família de algoritmos de ordenação por seleção.

Tem um desempenho em tempo de execução muito bom em conjuntos ordenados aleatoriamente, tem um uso de memória bem comportado e o seu desempenho em pior cenário é praticamente igual ao desempenho em cenário médio. Alguns algoritmos de ordenação rápidos têm desempenhos espetacularmente ruins no pior cenário, quer em tempo de execução, quer no uso da memória. O Heapsort trabalha no lugar e o tempo de execução em pior cenário para ordenar n elementos é de O (n lg n). Lê-se logaritmo (ou log) de “n” na base 2. Para valores de n, razoavelmente grande, o termo lg n é quase constante, de modo que o tempo de ordenação é quase linear com o número de itens a ordenar.

O Heap Sort utiliza uma estrutura de dados chamada Heap, para ordenar os elementos a medida que os insere na estrutura. Assim, ao final das inserções, os elementos podem ser sucessivamente removidos da raiz da heap, na ordem desejada, lembrando-se sempre de manter a propriedade de max-heap.

A heap pode ser representada como uma árvore (uma árvore binária com propriedades especiais) ou como um vetor. Para uma ordenação crescente, deve ser construído uma heap mínima (o menor elemento fica na raiz). Para uma ordenação decrescente, deve ser construído uma heap máxima (o maior elemento fica na raiz).

Por Inserção

Insertion Sort

Características:

Classe: Algoritmo de Ordenação

Estrutura de Dados: Array, Listas Ligadas

Complexidade no Pior Caso: O (n²) – n (número de elementos)

Complexidade no Caso Médio: O (n²) – n (número de elementos)

Complexidade no Melhor Caso: O (n²) – n (número de elementos)

Complexidade de Espaços no Pior Caso – Total: O (n) – n (número de elementos)

Complexidade de Espaços no Pior Caso – Auxiliar: O (1)

Estabilidade: Estável

Insertion sort, ou ordenação por inserção ou Inserção Direta, é um simples algoritmo de ordenação, eficiente quando aplicado a um pequeno número de elementos. Em termos gerais, ele percorre um vetor de elementos da esquerda para a direita e à medida que avança vai deixando os elementos mais à esquerda ordenados. O algoritmo de inserção funciona da mesma maneira com que muitas pessoas ordenam cartas em um jogo de baralho como o pôquer.

Menor número de trocas e comparações entre os algoritmos de ordenação O(n) quando o vetor está ordenado.

Shell Sort

Características:

Classe: Algoritmo de Ordenação

Estrutura de Dados: Array, Listas Ligadas

Complexidade no Pior Caso: O (n log² n) – n (número de elementos)

Complexidade no Caso Médio: depende da sequencia do Gap.

Complexidade no Melhor Caso: O (n) – n (número de elementos)

Complexidade de Espaços no Pior Caso: O (n)

Criado por Donald Shell em 1959, publicado pela Universidade de Cincinnati, Shell Sort (ou método de inserção por meio de incrementos Decrescentes), é o mais eficiente algoritmo de classificação dentre os de complexidade quadrática. É um refinamento do método de inserção direta. O algoritmo difere do método de inserção direta pelo fato de no lugar de considerar o array a ser ordenado como um único segmento, ele considera vários segmentos sendo aplicado o método de inserção direta em cada um deles. Basicamente o algoritmo passa várias vezes pela lista dividindo o grupo maior em menores. Nos grupos menores é aplicado o método da ordenação por inserção.

Gnome Sort

Características:

Classe: Algoritmo de Ordenação

Estrutura de Dados: Array, Listas Ligadas

Complexidade: O (n²) – n (número de elementos)

Algoritmo similar ao Insertion sort com a diferença que o Gnome sort leva um elemento para sua posição correta, com uma sequencia grande de trocas assim como o Bubble sort.

O algoritmo percorre o vetor comparando seus elementos dois a dois, assim que ele encontra um elemento que está na posição incorreta, ou seja, um número maior antes de um menor, ele troca a posição dos elementos, e volta com este elemento até que encontre o seu respectivo lugar.

Por Distribuição

Radix Sort

Características:

Classe: Algoritmo de Ordenação

Estrutura de Dados: Array, Listas Ligadas

Complexidade no Pior Caso: O (nk) – n (número de elementos), k (tamanho da string)

Complexidade de Espaços no Pior Caso: O (n+s) – n (número de elementos), s (tamanho do alfabeto)

Ótimo: Exatamente correto

Estabilidade: Estável

O Radix sort é um algoritmo de ordenação rápido e estável que pode ser usado para ordenar itens que estão identificados por chaves únicas. Cada chave é uma cadeia de caracteres ou número, e o radix sort ordena estas chaves numa qualquer ordem relacionada com a lexicografia.

Na ciência da computação, radix sort é um algoritmo de ordenação que ordena inteiros processando dígitos individuais. Como os inteiros podem representar strings compostas de caracteres (como nomes ou datas) e pontos flutuantes especialmente formatados, radix sort não é limitado somente a inteiros.

Computadores, na sua maioria, representam internamente todos os tipo de dados como números binários, por isso processar os dígitos na forma de inteiros em grupos representados por dígitos binários se torna mais conveniente. Existem duas classificações do radix sort, que são:

• Least significant digit (LSD – Dígito menos significativo) radix sort;

• Most significant digit (MSD – Dígito mais significativo) radix sort.

O radix sort LSD começa do dígito menos significativo até o mais significativo, ordenando tipicamente da seguinte forma: chaves curtas vem antes de chaves longas, e chaves de mesmo tamanho são ordenadas lexicograficamente. Isso coincide com a ordem normal de representação dos inteiros, como a seqüência “1, 2, 3, 4, 5, 6, 7, 8, 9, 10”. Os valores processados pelo algoritmo de ordenação são frequentemente chamados de “chaves”, que podem existir por si próprias ou associadas a outros dados. As chaves podem ser strings de caracteres ou números.

Já o radix sort MSD trabalha no sentido contrário, usando sempre a ordem lexicográfica, que é adequada para ordenação de strings, como palavras, ou representações de inteiros com tamanho fixo. A seqüência “b, c, d, e, f, g, h, i, j, ba” será ordenada lexicograficamente como “b, ba, c, d, e, f, g, h, i, j”. Se essa ordenação for usada para ordenar representações de inteiros com tamanho variável, então a representação dos números inteiros de 1 a 10 terá a saída “1, 10, 2, 3, 4, 5, 6, 7, 8, 9”.

O radix sort LSD opera na notação Big O, em O(nk), onde “n” é o número de chaves, e “k” é o comprimento médio da chave. É possível garantir esse desempenho para chaves com comprimento variável agrupando todas as chaves que tem o mesmo comprimento e ordenando separadamente cada grupo de chaves, do mais curto para o mais comprido, de modo a evitar o processamento de uma lista inteira de chaves em cada passo da ordenação.

Em muitas aplicações em que é necessário velocidade, o radix sort melhora as ordenações por comparação, como heapsort e o mergesort, que necessitam de Ω(n · log n) comparações, onde “n” é o número de itens a serem ordenados. Em compensação, algoritmos de ordenação baseados em comparações oferecem flexibilidade por serem aptos a ordenar de outras formas que não a lexicográfica. No entanto, essa habilidade é de pouca importância em várias aplicações práticas.

O algoritmo de ordenação radix foi originalmente usado para ordenar cartões perfurados. Um algoritmo computacional para o radix sort foi inventado em 1954 no MIT por Harold H. Seward.

Outros

Intro Sort

Características:

Classe: Algoritmo de Ordenação

Estrutura de Dados: Array, Listas Ligadas

Complexidade no Pior Caso: O (n log n) – n (número de elementos)

Intro Sort ou Introspective Sort é um algoritmo de ordenação criado por David Musser em 1997. Ele começa com o Quicksort e muda para o Heapsort quando a profundidade da recursividade excede um nível baseado no (logaritmo do) número de elementos a ser classificados. É o melhor dos dois mundos, com um tempo de execução de pior caso de O(n log n) e desempenho prático comparável ao quick sort em conjuntos de dados típicos. Uma vez que ambos os algoritmos que utiliza são ordenações de comparação, ele também é uma ordenação por comparação.

Em Quick Sort, uma das operações críticas é a escolha do pivô: o elemento em torno do qual a lista é particionada. O algoritmo mais simples de seleção do pivô é tomar o primeiro ou o último elemento da lista como o pivô, obtendo um comportamento pobre para o caso de entradas ordenadas ou quase totalmente ordenadas. A variante de Niklaus Wirth usa o elemento do meio para prevenir essas ocorrências, degenerando em O(n²) para sequências inventadas. O algoritmo de seleção de pivô “mediana melhor-de-três” obtém a mediana do primeiro, médio e últimos elementos da lista; no entanto, mesmo que isso funcione bem em muitos exemplos do mundo real, ainda é possível inventar uma lista matadora de mediana melhor-de-três que irá causar desaceleração dramática de um Quick Sort com base nesta técnica de seleção do pivô. Essas contribuições poderiam potencialmente ser explorada por um agressor, por exemplo, enviar essa lista para um servidor de Internet para ordenação como um ataque de negação de serviço.

Musser relatou que em uma sequência ”matadora de mediana melhor-de-três de 100.000 elementos, o tempo de execução do Intro Sort foi de 1/200 do que o do Quick Sort “mediana melhor-de-três”. Musser também considerou o efeito sobre o cache da pequena ordenação atrasada de Sedgewick, onde pequenos intervalos são classificados no final, em uma única passagem do insertion sort. Ele relatou que seria possível dobrar o número de erros de cache, mas que o seu desempenho com deques foi significativamente melhor e deve ser mantido para modelos de bibliotecas, em parte porque o ganho em outros casos, de fazer as ordenações imediatamente não foi grande. Da mesma forma, Musser também introduziu o algoritmo de seleção de pior caso linear com tempo comparável ao algoritmo de Hoare, uma simples adaptação do Quick Sort que é o algoritmo de seleção mais eficiente utilizado na prática. Isso é chamado seleção por introspecção ou “Introselect”.

Bucket Sort

Características:

Classe: Algoritmo de Ordenação

Estrutura de Dados: Array, Listas Ligadas

Complexidade no Pior Caso: O (n²) – n (número de elementos)

Bucket Sort, ou Bin Sort, é um algoritmo de ordenação que funciona dividindo um vetor em um número finito de recipientes. Cada recipiente é então ordenado individualmente, seja usando um algoritmo de ordenação diferente, ou usando o algoritmo Bucket Sort recursivamente. O Bucket Sort tem complexidade linear (Θ(n)) quando o vetor a ser ordenado contém valores que são uniformemente distribuídos.

Bucket sort funciona do seguinte modo:

• Inicialize um vetor de “baldes”, inicialmente vazios.

• Vá para o vetor original, incluindo cada elemento em um balde.

• Ordene todos os baldes não vazios.

• Coloque os elementos dos baldes que não estão vazios no vetor original.

Counting Sort

Características:

Classe: Algoritmo de Ordenação

Estrutura de Dados: Array, Listas Ligadas

Complexidade no Pior Caso: O (n+k) – n (número de elementos), k (tamanho da string)

Complexidade no Caso Médio: O (n+k) – n (número de elementos), k (tamanho da string)

Complexidade no Melhor Caso: O (n+k) – n (número de elementos), k (tamanho da string)

Counting sort é um algoritmo de ordenação estável cuja complexidade é O(n). As chaves podem tomar valores entre 0 e M-1. Se existirem k0 chaves com valor 0, então ocupam as primeiras k0 posições do vetor final: de 0 a k0-1

Esta implementação tem a desvantagem de precisar de vectores auxiliares. O Counting Sort ordena exclusivamente números inteiros pelo fato de seus valores servirem como índices no vetor de contagem.

Trabalha como uma contadora de ocorrências dentro de um programa, especificamente dentro de um vetor. Quando determinado vetor tem números repetidos, números únicos e números que não existem um outro vetor indica a quantidade de ocorrências

Referências Bibliográficas

Algoritmos – Teoria e Prática, Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford.

Resolução de Questões de Concursos Anteriores

TRT 05ª Região – Técnico Judiciário – 2013 – FCC

A maioria das linguagens de programação trabalha com tipos de dados elementares e tipos estruturados. São considerados tipos de dados elementares:

A) boolean, integer e real.

B) real, vector e boolean.

C) queue, integer, real e boolean.

D) list, tree, vector e string.

E) char, boolean, stack e real.

RESPOSTA: A

Vector (Vetor), Queue (Pilha), List (Lista), Tree (Árvore), Vector (Vetor) e Stack (Pilha) são estrutura de dados, também conhecidos como tipos estruturados.

TRF 2ª Região – Técnico Judiciário – 2012 – FCC

Analise o algoritmo abaixo:

Sobre ele é INCORRETO afirmar:

a) Exibirá o maior entre três números lidos, exceto se os três valores forem iguais.

b) Se forem lidos os valores 1, 3 e 6 nas variáveis n1, n2 e n3 respectivamente, a variável m receberá o valor 1, em seguida o valor 3 e, por último, o valor 6.

c) Se forem lidos os valores 7, 2 e 9 nas variáveis n1, n2 e n3 respectivamente, a variável m receberá o valor 7, em seguida o valor 2 e, por último, o valor 9.

d) Se forem lidos os valores 9, 7 e 2 nas variáveis n1, n2 e n3 respectivamente, a variável m receberá apenas o valor 9.

e) Se forem lidos os valores -1, -3 e -8 nas variáveis n1, n2 e n3 respectivamente, a variável m receberá apenas o valor -1.

RESPOSTA: C

O algoritmo vai atribuindo o maior valor recebido na variável m, por esse motivo a letra C está incorreta. Uma vez atribuído o valor 7, o valor 2 como menor que 7, não será atribuído a M.

TRT 6ª Região – Técnico Judiciário – 2012 – FCC

Considere o algoritmo a seguir:

Sobre o algoritmo acima, é correto afirmar:

a) Qualquer valor digitado e armazenado na variável valor menor do que 10 desencadeará a impressão da mensagem “Situação 2”.

b) A mensagem “Situação 3” será exibida apenas se o valor digitado e armazenado na variável valor for maior do que 10.

c) O algoritmo será finalizado apenas quando a resposta da pergunta “Deseja continuar[sim/não]?” for “não”.

d) A mensagem “Situação 2” será exibida se o valor digitado e armazenado na variável valor for maior ou igual a 5 e menor do que 10.

e) A mensagem “Situação 1” será exibida apenas de o valor lido para a variável valor for maior ou igual a zero e menor do que 5.

RESPOSTA: D

A, incorreta pois se o valor for menor que 5 será impresso “Situação 1”.

B, incorreta pois será impresso se o valor for igual a 10.

C, incorreta no gabarito oficial, mas existe dúvida. Observe que mesmo sendo atribuído o valor NÃO a STATUS na situação 3, antes de ser feita a nova avaliação (no comando de repetição) é invocado o comando “Leia” que irá sobrepor o valor NÃO com o valor digitado pelo usuário. então a alternativa C estaria correta. pois, o algoritmo será finalizado apenas quando a resposta da pergunta “Deseja Continuar [Sim/Não]?” for Não.

Resposta para a dúvida: Tive o mesmo pensamento que você quando fiz a questão. Mas depois, fazendo “Engenharia Reversa” do gabarito pensei no seguinte: No comando “leia”, onde pede-se uma entrada do usuário, caso o usuário digite QUALQUER COISA que não seja “sim”, sairá do laço (enquanto). Ele não precisa necessariamente digitar “não” entende? Se ele digitar “abcd” já sairia do laço. Basta não digitar “sim”.

D, correta.

E, incorreta pois se o número for menor que 0 também será exibida a mensagem “Situação 1”.

TER-SP – Analista Judiciário – 2012 – FCC

Analise o texto:

Na compilação, a análise consiste em três fases. Em uma das fases, os caracteres ou tokens são agrupados hierarquicamente em coleções aninhadas com significado coletivo. Essa fase envolve o agrupamento dos tokens do programa fonte em frases gramaticais, que são usadas pelo compilador, a fim de sintetizar a saída. Usualmente, as frases gramaticais do programa fonte são representadas por uma árvore gramatical.

A fase citada no texto é conhecida como análise

a) sintática.

b) semântica.

c) léxica.

d) binária.

e) linear.

RESPOSTA: A

Sintática parte gramatical, semântica se os valores corretos estão sendo atribuído, e léxica se os comandos estão sendo escritos corretamente.

TER-SP – Analista Judiciário – 2012 – FCC

No que se refere a estruturas de dados é INCORRETO afirmar:

a) Numa fila dupla, os elementos podem ser inseridos e removidos de qualquer um dos extremos da fila.

b) Em qualquer situação é possível usar uma única fila dupla para representar duas filas simples.

c) A implementação de uma fila dupla normalmente é mais eficiente com uma lista duplamente encadeada que com uma encadeada simples.

d) Pela definição de fila, se os elementos são inseridos por um extremo da lista linear, eles só podem ser removidos pelo outro.

e) Numa lista singularmente encadeada, para acessar o último nodo é necessário partir do primeiro e ir seguindo os campos de ligação até chegar ao final da lista.

RESPOSTA: B

Uma fila é uma estrutura de dados que admite inserção de novos elementos e remoção de elementos antigos. Mais especificamente, uma fila (= queue) é uma estrutura sujeita à seguinte regra de operação: sempre que houver uma remoção, o elemento removido é o que está na estrutura há mais tempo. Em outras palavras, o primeiro objeto inserido na fila é também o primeiro a ser removido. Essa política é conhecida pela sigla FIFO (= First-In-First-Out).

Uma fila dupla (Deque) é uma lista linear na qual os elementos podem ser inseridos ou removidos de qualquer extremo.

TJ-RJ – Analista Judiciário – 2012 – FCC

O algoritmo conhecido como busca binária é um algoritmo de desempenho ótimo para encontrar a posição de um item em

a) uma árvore B.

b) uma lista ligada ordenada.

c) uma árvore de busca binária.

d) um heap binário.

e) um vetor ordenado.

RESPOSTA: E

TER-CE – Técnico Judiciário – 2012 – FCC

Sobre pilhas é correto afirmar:

a) Uma lista LIFO (Last-In/First-Out) é uma estrutura estática, ou seja, é uma coleção que não pode aumentar e diminuir durante sua existência.

b) Os elementos na pilha são sempre removidos na mesma ordem em que foram inseridos.

c) Uma pilha suporta apenas duas operações básicas, tradicionalmente denominadas push (insere um novo elemento no topo da pilha) e pop (remove um elemento do topo da pilha).

d) Cada vez que um novo elemento deve ser inserido na pilha, ele é colocado no seu topo e, em qualquer momento, apenas aquele posicionado no topo da pilha pode ser removido.

e) Sendo P uma pilha e x um elemento qualquer, a operação Push(P,x) diminui o tamanho da pilha P, removendo o elemento x do seu topo.

RESPOSTA: D

a) Uma lista LIFO (Last-In/First-Out) é uma estrutura Dinâmica, ela pode aumentar e diminuir.

b) Os elementos na pilha são sempre removidos na ordem inversa em que foram inseridos. (LIFO – Last In First Out).

c)Uma pilha suporta apenas três operações básicas, tradicionalmente denominadas push (insere um novo elemento no topo da pilha) e pop (remove um elemento do topo da pilha), e Check que verifica o elemento topo da pilha sem remove-lo

d) Alternativa Correta. Cada vez que um novo elemento deve ser inserido na pilha, ele é colocado no seu topo e, em qualquer momento, apenas aquele posicionado no topo da pilha pode ser removido.

e) Sendo P uma pilha e x um elemento qualquer, a operação Push(P,x) aumenta o tamanho da pilha P, adicionando o elemento x do seu topo.

TER-CE – Técnico Judiciário – 2012 – FCC

Considere o algoritmo seguinte:

A saída na tela será :

a) 0.

b) 2, 4, 8, 16 e 16.

c) 2, 4, 8 e 8.

d) 1.

e) 0, 0, 0, 0 e 0.

RESPOSTA: A

A questão não entrará no While, pois Cont=1 e N=4. Sendo assim ele apenas imprimirá o valor de Res uma única vez, que é 0.

TER-CE – Técnico Judiciário – 2012 – FCC

Com relação a árvores binárias é INCORRETO afirmar:

a) Uma árvore binária é uma coleção finita de n>0 nodos que não pode ser nula.

b) Uma árvore binária, cuja raiz armazena o elemento R, é denominada árvore de busca binária se todo elemento armazenado na subárvore esquerda é menor que R, nenhum elemento armazenado na subárvore direita é menor que R e as subárvores esquerda e direita também são árvores de busca binária.

c) É um caso especial de árvore em que nenhum nodo tem grau superior a 2, isto é, nenhum nodo tem mais que dois filhos.

d) Existe um nodo especial denominado raiz e os demais nodos são particionados em T1 e T2 estruturas disjuntas de árvores binárias. T1 é denominado subárvore esquerda e T2 subárvore direita da raiz.

e) É uma árvore que pode ser nula.

RESPOSTA: A

Letra A está incorreta. Uma árvore binária pode ser nula;

Uma árvore é uma coleção infinita de nós. Uma árvore binária só pode ter de 0 a 2 filhos. E uma árvore binária pode ser nula.

TCE-AP – Analista de Controle Externo – 2012 – FCC

Um grafo consiste num conjunto de nós (ou vértices) e num conjunto de arcos (ou arestas). É correto afirmar que o grau de um nó é

a) o número de arcos incidentes nesse nó.

b) um número associado ao arco, também chamado de peso.

c) a distância entre este nó e um outro nó qualquer do grafo.

d) a posição deste nó em relação ao nó raiz do grafo

e) o número de pares ordenados que formam o arco.

RESPOSTA: A

TRT 11ª Região – Analista Judiciário – 2012 – FCC

Um grafo é uma estrutura de dados consistida em um conjunto de nós (ou vértices) e um conjunto de arcos (ou arestas). O grafo em que os arcos possuem um número ou peso associados a eles, é chamado de grafo

a) predecessor.

b) adjacente.

c) incidente.

d) ponderado.

e) orientado.

RESPOSTA: D

Em grafos valorados, cada aresta (ou vértice) de G é assinalada com um valor numérico, ou peso. Uma aplicação típica são estradas, as quais são valoradas com a distância ou o tempo para percorrê-la. A diferença entre esses tipos é basicamente para encontrar o menor “caminho” entre dois vértices. Também conhecido como ponderado.

TRT 11ª Região – Analista Judiciário – 2012 – FCC

A estrutura de dados chamada grafo consiste num conjunto de nós (ou vértices) e num conjunto de arcos (ou arestas). Cada arco em um grafo é especificado por um par de nós. Se os pares de nós que formam o arco forem pares ordenados, diz-se que o grafo é

a) incidente.

b) ponderado.

c) adjacente.

d) orientado.

e) sucessor.

RESPOSTA: D

Um grafo orientado difere de um nao orientado comum, em que o último é definido em termos de pares não ordenados de vértices, que são normalmente chamados arestas.

TRT 14ª Região – Técnico Judiciário – 2011 – FCC

Considere:

I. Estrutura de dados linear e estática, composta por um número finito de elementos de um determinado tipo de dados.

II. É linear e dinâmica quando encadeada; apresenta um campo para conter o dado a ser armazenado e outro campo para apontar para o próximo elemento.

III. Os elementos associados a cada nó são habitualmente chamados de filhos desses nós, podendo existir nós sem filhos.

IV. É tipicamente uma representação de vértices ligados por arestas que eventualmente, podem ser direcionadas por meio de setas.

Em relação às estruturas de dados, é correto afirmar que os itens I, II, III e IV estão associados, respectivamente, a

a) lista, fila, pilha e vetor.

b) fila, vetor, grafo e árvore.

c) vetor, lista, árvore e grafo.

d) lista, fila, grafos e tabela de hashing.

e) fila, vetor, árvore e tabela de hashing.

RESPOSTA: C

1. Das estruturas apresentadas somente vetor é estático;

2. Filas e Listas são dinâmicas e lineares;

3. Somente a estrutura de árvore apresenta o conceito de filhos;

4. Grafos são generalizações de árvores sendo cada nó chamado de vértice.

TRT 14ª Região – Analista Judiciário – 2011 – FCC

NÃO se trata de um método de ordenação (algoritmo):

a) inserção direta.

b) seleção direta.

c) inserção por meio de incrementos decrescentes.

d) direta em cadeias.

e) particionamento.

RESPOSTA: D

Os métodos de ordenação são: Insertion Sort, Selecion Sort, Bubble Sort, Comb Sort, Quick Sort, Merge Sort, HeapSort, Shell sort, Radix Sort, Gnome Sort, Count Sort, Bogo Sort,, Bucket Sort, Cocktail Sort e Tim Sort. Sabendo disso, temos que:

A) É o Insertion Sort.

B) É o Seletion Sort.

C) É o Shell.

D) Direta em cadeia é um método de pesquisa e não de ordenação.

E) É o Quick Sort ou o MergeSort.

Também é bom saber que os principais métodos de busca são: Linear, Binária, Em Tabelas e Direta Em Cadeias. Atualmente os dois métodos mais eficientes de busca em cadeias correspondem aos conhecidos métodos de Hnuth-Norris-Pratt (KMP) e o método Boyer-Moore.

TRT 4ª Região – Analista Judiciário – 2011 – FCC

No contexto das vinculações de subscritos e categorias de matrizes, NÃO se inclui como uma categoria a matriz

a) estática.

b) dinâmica na pilha.

c) associativa.

d) fixa dinâmica na pilha.

e) dinâmica no monte.

RESPOSTA: C

Matriz Estática

– As faixas de subscrito estão estaticamente vinculadas e a alocação de armazenamento é estática (feita antes da execução)

– Vantagem: eficiência (em alocação dinâmica)

Matriz fixa dinâmica na pilha

– Faixas de subscrito estão estaticamente vinculadas, mas a alocação é feita no momento da declaração durante a execução

– Vantagem: eficiência de espaço

Matriz Dinâmica na Pilha

– Faixas de subscritos estão dinamicamente vinculadas e a alocação de armazenamento é dinâmica (feita durante a execução)

– Vantagem: flexibilidade (o tamanho de uma matriz não precisa ser conhecido antes da sua utilização)

Matriz Dinâmica no Monte:

– A vinculação das faixas dos índices e a alocação são dinâmicas e podem mudar várias vezes

– Vantagem: flexibilidade (matrizes podem crescer ou encolher durante a execução do programa)

TRT 24ª Região – Técnico Judiciário – 2011 – FCC

Considere: zero é um número natural. O sucessor de um número natural é um número natural.

Assim, em termos de algoritmo, o enunciado trata da possibilidade de aplicação de uma técnica denominada

a) matriciação.

b) integração.

c) agregação.

d) interação.

e) recursão.

RESPOSTA: E

A técnica é a recursão, através da recursividade poderemos repetir um trecho de código com a chamada para si mesmo.

Recursão na matemática: Um exemplo de conjunto definido recursivamente é dado pelos números naturais: 0 está em N;

Se n está em N, então n + 1 está em N.

O conjunto dos números naturais é o menor conjunto satisfazendo as condições acima.

TRT 10ª Região – Técnico Judiciário – 2011 – FCC

A estrutura de dados linear que obedece o seguinte critério: o último elemento inserido será o primeiro elemento a ser retirado (last in first out ? LIFO) é:

a) pilha.

b) fila.

c) árvore binária.

d) árvore AVL.

e) lista circular.

RESPOSTA: A

TER-RN – Técnico Judiciário – 2011 – FCC

Uma estrutura de dados onde cada nó mantém uma informação adicional, chamada fator de balanceamento, que indica a diferença de altura entre as subárvores esquerda e direita, é conhecida por árvore:

a) hiberbólica.

b) de busca binária.

c) ordenada.

d) AVL.

e) binária.

RESPOSTA: D

Árvore AVL: é uma árvore de busca binária auto balanceada, onde a altura da subárvore esquerda e da subárvore da direita difere de 1, sendo este denominado fator de balanceamento.

Se a árvore não estiver balanceada é necessário reavaliar o balanceamento através de rotação simples ou dupla à direita ou à esquerda.

As operações de busca, inserção e remoção tem complexidade O(log n).

INFRAERO – Analista de Sistemas – 2011 – FCC

O método de ordenação QuickSort (ordenação rápida) é um método sofisticado de ordenação de vetores que

a) considera em cada passo somente um único elemento sucessor na sequência fonte e todos os elementos do vetor destino para encontrar o ponto correto da inserção.

b) ordena todos os elementos que estiverem a intervalos de 4 posições entre si na sequência corrente.

c) é baseado nos princípios de ordenação por inserção direta através de incrementos decrescentes.

d) é baseado no fato de que as permutações devem ser preferencialmente empregadas para pares de elementos que guardem entre si distâncias grandes, com a finalidade de se conseguir uma eficiência maior.

e) é baseado nos princípios de ordenação por seleção direta que consiste na seleção repetitiva da menor dentre as chaves de n elementos, e depois dentre os n-1 elementos restantes, e assim por diante.

RESPOSTA: D

TCE-PR – Analista de Controle – 2011 – FCC

É um tipo de estrutura de dados em que a função de dispersão é a responsável por gerar um índice a partir de determinada chave; por causa das colisões, muitas tabelas de dispersão são aliadas com alguma outra estrutura de dados:

a) vetores.

b) matrizes.

c) listas encadeadas.

d) tabela hash.

e) sort.

RESPOSTA: D

TRT 19ª Região – Técnico Judiciário – 2011 – FCC

Considere os seguintes algoritmos e suas complexidades na notação Big O:

– Algoritmo A: O(log n)

– Algoritmo B: O(n2)

– Algoritmo C: O(n . log n)

Considerando-se o pior caso de execução destes algoritmos, é correto afirmar que o algoritmo

a) A é o menos eficiente.

b) C é o menos eficiente.

c) A não é o mais eficiente nem o menos eficiente.

d) B é o menos eficiente.

e) C é o mais eficiente.

RESPOSTA: E

Notação O Grande (também conhecida como big O notation, no inglês, notação Landau, notação Bachmann–Landau e notação assintótica) descreve o comportamento limitante de uma função quando o argumento tende a um determinado valor ou ao infinito, geralmente em termos de funções mais simples. A notação O Grande permite que seus usuários simplifiquem funções para que se concentrem em suas taxas de crescimento: Funções diferentes com a mesma taxa de crescimento podem ser representadas usando a mesma notação O.

Apesar de ser desenvolvida como parte da matemática pura, atualmente esta notação é comumente utilizada na análise de algoritmos para descrever o uso de recursos computacionais realizado por um determinado algoritmo a partir da análise da complexidade do tempo de execução utilizando a análise do pior caso, caso médio ou melhor caso.

A complexidade de algoritmos é muito importante para avaliar o tempo de execução de qualquer algoritmo. Para responder a questão podemos considerar, por exemplo, n = 100.

Então:

• Algoritmo A -> O(log n) = log 100 = 2, onde a base é 10, 10² = 100;

• Algoritmo B -> O(n²) = 100² = 10000;

• Algoritmo C -> O(n log n ) = 100 log 100 = 100×2 = 200,

Logo, tempo de B > tempo de C > tempo de A, B é o que tem a pior eficiência.

Alguns exemplos de algoritmos que possuem complexidade O(log n) são as buscas binárias e buscas em uma árvore binária de busca que esteja balanceada (árvores binárias não balanceadas vão ter complexidade no pior caso de O(n)).

Essa complexidade é conseguida, no caso das buscas, em sempre “eliminar” a metade do total atual da lista em uma única iteração, ou seja, na primeira iteração elimina 50% do total, na segunda 75% (50% + 25%), terceira 87,5%(50% + 25% + 12,5%) e assim vai até achar o resultado. Dessa forma o número máximo de iterações sempre será, no pior caso, um logarimo na base 2 de n, onde n é igual ao número máximo de elementos contidos na lista.

Por exemplo, realizar uma busca binária em um vetor de 8 posições. Na primeira iteração serão eliminados 4 valores, na segunda 2 e na terceira 1. Caso não seja achado o valor o algoritmo terminará, pois não haverá mais nem um campo a ser pesquisado. Então a complexidade dessa busca é no pior caso de 3 iterações, que é exatamente o valor de log8 na base 2. Pois 2³ = 8.

Vale ressaltar que para ser possível alguma forma de pesquisa binária a lista deve estar ordenada.

TRT 19ª Região – Técnico Judiciário – 2011 – FCC

Em uma árvore binária, todos os nós têm grau:

a) 2.

b) 0, 1 ou 2.

c) divisível por 2.

d) maior ou igual a 2.

e) 0 ou 1.

RESPOSTA: B

De 0 à 2 filhos.

TRT 19ª Região – Técnico Judiciário – 2011 – FCC

FIFO refere-se a estruturas de dados do tipo

a) fila.

b) árvore binária.

c) pilha.

d) matriz quadrada.

e) cubo.

RESPOSTA: A

FIFO = First In / First Out -> Representa a estrutura de dados do tipo Fila, em que o primeiro elemento a chegar será o primeiro a sair.

LIFO = Last In / First Out -> Representa a estrutura de dados do tipo Pilha, em que o último elemento que chega é o primeiro que sai. e Vice-versa.

MPE-RN – Analista de Tecnologia da Informação – 2010 – FCC

Último dado armazenado é o primeiro a ser recuperado caracteriza a estrutura de dados do tipo

a) árvore.

b) pilha.

c) string.

d) fila.

e) boolean.

RESPOSTA: B

MPE-RN – Analista de Tecnologia da Informação – 2010 – FCC

São métodos (algoritmos) de busca em cadeias

a) Boyer-Moore e Knuth-Morris-Pratt.

b) Boyer-Moore e fusão natural.

c) Knuth-Morris-Pratt e fusão balanceada multidirecional.

d) Fusão direta e Knuth-Morris-Pratt.

e) Boyer-Moore e ordenação polifásica.

RESPOSTA: A

Boyer-Moore e o KMP (Knuth-Morris-Pratt).

MPE-RN – Analista de Tecnologia da Informação – 2010 – FCC

As entradas de uma matriz de incidência que representa um grafo onde uma das dimensões são vértices e a outra são arestas, são representadas apenas por

a) um valor (número de vértices).

b) um valor (número de arestas).

c) dois valores (números de vértices e de arestas).

d) três valores (0, 1 e 2).

e) dois valores (0 e 1).

RESPOSTA: D

“Para representar um grafo sem pesos nas arestas e não direcionado, basta que as entradas da matriz M contenham 1 se o vértice incide na aresta, 2 caso seja um laço (incide duas vezes) e 0 caso o vertice não incida na aresta.”

Na representação dos grafos em matrizes podemos fazê-los por:

1)matrizes INCIDENTES: relacionam os vértices as arestas – verifica qual vértice está ligado a qual aresta. (0=aresta não incide no vértice, 1=aresta incide no vértice, 2=aresta sai e incide no mesmo vértice)

2)matrizes ADJACENTES: Relacionam os vértices aos outros vértices – verifica quais vértices estão ligados entre si. (0 = vértice não ligado, 1 = vértice ligado).

MPE-RN – Analista de Tecnologia da Informação – 2010 – FCC

As estratégias de divisão e de conquista são utilizadas pelos algoritmos de ordenação

a) Selection sort e Insertion sort.

b) Selection sort e Bubble sort.

c) Quick sort e Merge sort

d) Bubble sort e Bucket sort.

e) Shell sort e Count sort.

RESPOSTA: C

Relação de algoritmos para memorizar:

Ordenação por inserção: Insertion sort, Shell sort(melhoria do Insertion sort), Gnome sort(similar ao insertion sort e funcionamento do Bubble sort),

Ordenação por seleção: Selection sort, Heap sort

Ordenação por comparação/troca: Bubble sort(ou ordenação por flutuação), Comb sort(melhoria do Bubble sort), Cocktail sort(Bubble em duas direções)

Ordenação por divisão e conquista: Quick sort, Merge sort

Outros: Radix sort, Counting sort, Bogosort(probabilístico), Bucket sort.

Classificação por intercalação Os métodos de classificação por intercalação dividem a tabela em dois ou mais segmentos, ordenam estes segmentos e depois os intercalam, terminando, ao final, com um único segmento (toda a tabela) ordenado. O principal algoritmo desta família é o mergesort (ou Intercalação Simples). Mergesort (Intercalação Simples): A idéia por traz do mergesort é bastante simples: divide-se a tabela em diversos segmentos menores para a seguir ordenar-se estes segmentos. Feito isto, estes segmentos são agrupados entre sí (intercalados) e este processo produz novos segmentos ordenados (maiores que os segmentos iniciais). O processo de agrupamento e ordenação dos segmentos (intercalação) continua até que se obtenha um único segmento que contenha toda a tabela e esteja totalmente ordenado.

MPE-RN – Analista de Tecnologia da Informação – 2010 – FCC

Uma árvore binária completa tem, no 5º nível, uma quantidade de nós igual a

a) 31

b) 32

c) 64

d) 15

e) 16

RESPOSTA: E

Observe que a questão pede o 5º Nível e não o nível 5. Assim, ele deseja o nível 4, uma vez que o nível inicia pelo 0.

• nível 0 = 1 nó

• nível 1 = 2 nós

• nível 2 = 4 nós

• nível 3 = 8 nós

• nível 4 = 16 nós

• nível 5 = 32 nós

Quantidade de Nós em uma árvore binária completa = 2^N

TRT 9ª Região – Técnico Judiciário – 2010 – FCC

É uma estrutura de dados dividida em linhas e colunas. Desta forma, pode-se armazenar diversos valores dentro dela. Para obter um valor é necessário identificá-lo por meio do número da linha e da coluna onde está armazenado. Trata-se de

a) árvore.

b) matriz.

c) pilha.

d) fita.

e) deque.

RESPOSTA: B

TRT 9ª Região – Técnico Judiciário – 2010 – FCC

Quando as inserções e as remoções ocorrem sempre no mesmo lado da lista, trata-se de uma estrutura de dados denominada

a) Fila.

b) Pilha.

c) Vetor.

d) Lista encadeada.

e) Lista circular.

RESPOSTA: B

a) na fila a inserção é feita no final e a remoção é feita no início

b) nas pilhas a remoção e a inserção é feita no topo da pilha

c) no vetor a inserção e remoção podem ser feitas em qualquer elemento(indexada)

d) na lista encadeada a inserção e remoção são feitas dinamicamente em qualquer posição(difere do vetor por não precisar definir inicialmente o tamanho total de elementos)

e) na lista circular as inserções e remoções podem ocorrer em qualquer elemento assim como vetores e as encadeadas, a diferença é que o último elemento dessa estrutura aponta pro primeiro(utilizado em métodos de busca)

Bahiagás – Analista de Processos Organizacionais – 2010 – FCC

Considere o algoritmo de busca:

Testar o elemento a m (a índice m) sorteado aleatoriamente e compará-lo ao argumento de busca x. Se o elemento for igual a x, a busca termina. Se menor que x todos os elementos com índices menores ou iguais a m podem ser descartados dos próximos testes e se for maior que x todos aqueles que possuem índices maiores ou iguais a m também podem ser descartados.

Tal algoritmo é denominado busca

a) linear.

b) em tabelas.

c) binária.

d) Knuth-Morris-Pratt.

e) Boyer-Moore.

RESPOSTA: C

a) linear: uma busca linear é realizada pela seleção de um elemento após o outros sendo que para selecionar o último elemento de uma estrutura com 10 elementos teria que percorrer todos os 9 primeiros elementos.

b) em tabelas: este algoritmo de busca possui a característica de existência de índices para os elementos, também conhecida como busca indexada ou busca em tabelas hash. Caso queira selecionar um elemento X da tabela esse elemento passará por um processo de tradução em índice e irá diretamente buscar o elemento com apenas uma seleção (caso seja uma tabela resistente a colisões*)

c) binária: a busca binária é definida pela seleção de elementos maiores ou menores que um dado índice da estrutura de dados. Por exemplo: se você está buscando um elemento X na estrutura de dados E inicialmente irá escolher algum elemento (E1) dessa estrutura (pode ser aleatoriamente este primeiro elemento). Logo em seguida irá ver se esse elemento E1 é maior ou menor que X, caso seja maior agora a busca ser realizará entre o próximo elemento maior que E1 e o último elemento de E, caso contrário entre o elemento anterior a E1(o primeiro menor que E1) e o primeiro elemento que E, definindo sempre um intervalo menor para a busca normalmente em metade dos elementos da primeira busca até encontrar, ou não, o elemento X.

d)Knuth-Morris-Pratt: é um algoritmo de busca em cadeias ou strings

e) Boyer-Moore: outro algoritmo de busca em cadeias ou strings

*Resistência a colisões é uma importante propriedade de tabelas hash que mantém a complexidade de busca em O(1), ou seja apenas uma seleção para encontrar o elemento desejado.

TRT 22ª Região – Analista Judiciário – 2010 – FCC

Uma fila duplamente terminada, isto é, uma estrutura linear que permite inserir e remover de ambos os extremos é chamada

a) Árvore.

b) Shift-and.

c) Autômato.

d) Deque.

e) Boyer-Moore.

RESPOSTA: D

Árvore: É uma estrutura de dados em que cada elemento tem um ou mais elementos associados, podendo definir-se uma árvore recursivamente como: – uma estrutura (uma árvore); – um nó (designado por raiz), que contém a informação a armazenar e um conjunto finito de árvores (sub-árvores); – não existe árvores vazias, no mínimo haverá um nó raiz (que não possui pai). Cada árvore tem apenas uma raiz, além disso, os elementos associados a cada nó são habitualmente chamados filhos desses nós. Os nós sem filhos de uma árvore são chamados folhas.

Autômato: Modelo matemático de uma máquina de estados finitos. Funciona como um reconhecedor de uma determinada linguagem e serve para modelar uma máquina ou, se quiserem, um computador simples.

Deque: São filas duplamente ligadas, isto é, filas com algum tipo de prioridade. Por exemplo, sistemas distribuídos sempre necessitam que algum tipo de processamento seja mais rápido, por ser mais prioritário naquele momento, deixando outro tipos mais lentos ou em fila de espera, por não requererem tanta pressa.

O nome Deque vem da abreviação de Double-Ended Queue (fila com dois fins).

Metrô-SP – Analista – 2010 – FCC

É uma noção simples, abstrata e intuitiva, usada para representar a ideia de alguma espécie de relação entre os objetos. Graficamente, aparece representado por uma figura com nós ou vértices. Trata-se dos

a) objetos geométricos.

b) triângulos.

c) grafos.

d) dados.

e) registros.

RESPOSTA: C

TRT 15ª Região – Analista Judiciário – 2009 – FCC

São algoritmos de classificação por trocas apenas os métodos

a) SelectionSort e InsertionSort.

b) MergeSort e BubbleSort.

c) QuickSort e SelectionSort.

d) BubbleSort e QuickSort.

e) InsertionSort e MergeSort.

RESPOSTA: D

Os métodos de classificação por trocas caracterizam-se por efetuarem a classificação por comparação entre pares de chaves, trocando-as de posição caso estejam fora da ordem desejada.

Exemplos: método da bolha (bubblesort), método da agitação (shakesort), método do pente(combsort) e método da partição e troca(quicksort).

SITID:

• 02 algoritmos de Seleção: S – SH ( Seleção – SelectSort, HeapSort);

• 03 algoritmos de Inserção: I – BBS (Busca Sequencial, Busca binaria, ShellSort)

• 04 algoritmos de Troca: T – BSCq ( Bubble, Shake, Comb, Quick)

• 01 algoritmo de Interlacação: I – M (merge)

• 01 algoritmo de Distribuição: D – R (rodix)

Métodos de ordenação por troca: A bolha sacode o pente rápido: A Bolha (Bubblesort) Sacode(Shakesort) o Pente(combsort) Rápido(Quicksort).

TRF 4ª Região – Analista Judiciário – 2010 – FCC

Sobre árvores, considere:

I. O número de subárvores de um nodo denomina-se grau.

II. Uma árvore binária não pode ser nula.

III. Toda árvore, inclusive as nulas, possui um nodo especial denominado raiz.

Está correto o que consta em

a) I, apenas.

b) I, II e III.

c) I e II, apenas.

d) I e III, apenas.

e) III, apenas.

RESPOSTA: A

I – CORRETA

II – ERRADA -> Um árvore binária pode não conter elemento nenhum, ou seja, uma árvore vazia, ou nula.

III – ERRADA -> As árvores nulas, ou vazias, não possuem nenhum elemento.

TRF 4ª Região – Analista Judiciário – 2010 – FCC

A estrutura de dados composta por nós que apontam para o próximo elemento da lista, com exceção do último, que não aponta para ninguém, é denominada

a) fila.

b) pilha.

c) árvore.

d) lista.

e) grafo.

RESPOSTA: D

Metrô-SP – Analista – 2010 – FCC

Objeto que se constitui parcialmente ou é definido em termos de si próprio. Nesse contexto, um tipo especial de procedimento (algoritmo) será utilizado, algumas vezes, para a solução de alguns problemas. Esse procedimento é denominado

a) Repetição.

b) Interligação.

c) Condicionalidade.

d) Recursividade.

e) Rotatividade.

RESPOSTA: D

Um objeto é dito recursivo se ele consistir parcialmente ou for definido em termos de si próprio. Nesse contexto, um tipo especial de procedimento (algoritmo) será utilizado, algumas vezes, para a solução de alguns problemas. Esse procedimento é denominado recursivo.

DPE-SP – Agente da Defensoria – 2010 – FCC

Em relação às estruturas de controle, considere abaixo o trecho inicial do algoritmo que exibe o conceito de um aluno, dada a sua nota. Levando-se em conta somente notas inteiras, o critério para conceitos é: notas menor que 3, conceito E; notas de 3 a 5, conceito D; notas 6 e 7, conceito C; notas 8 e 9, conceito B; nota 10, conceito A.

Fimalgoritmo

Continuando a construção do algoritmo acima, a estrutura de controle SE-ENTAO-SENAO-FIMSE será utilizada

a) 3 vezes.

b) 4 vezes.

c) 5 vezes.

d) 6 vezes.

e) 7 vezes.

RESPOSTA: C

SE NOTA < 3 ENTÃO CONCEITO = E

SE (NOTA >= 3) AND (NOTA <= 5) ENTÃO CONCEITO = D

SE (NOTA=6) OR (NOTA=7) ENTÃO CONCEITO = C

SE (NOTA=8) OR (NOTA=9) ENTÃO CONCEITO = B

SE (NOTA = 10) ENTÃO CONCEITO = A

Ou seja, será utilizada 5 vezes a citada estrutura de controle.

Acredito que a alternativa não tenha sido modificada pois SE-ENTAO-SENAO-FIMSE é o nome da estrutura de controle, porém o uso do SENÂO é opcional. A banca não obrigou a utilização do SENAO. Caso fosse, a resposta correta seria a B.

DPE-SP – Agente da Defensoria – 2010 – FCC

Em relação às estruturas de dados, considere:

I. Um tipo abstrato de dados está desvinculado de sua implementação, ou seja, a sua definição visa a preocupação com o que ele faz e não como ele faz.

II. A lista duplamente encadeada além de saber o próximo nó, cada elemento também conhece o nó anterior a ele na lista, o que facilita a remoção de um elemento e a exibição dos elementos na ordem inversa.

III. A implementação dinâmica de pilhas possui as mesmas vantagens que as listas dinâmicas, ou seja, não é necessário saber a quantidade máxima de elementos que serão armazenados.

IV. Lista, pilha, fila e array são casos típicos de estruturas lineares, enquanto árvore, grafo e heap são casos típicos de estruturas não lineares.

É correto o que se afirma em:

a) I e IV, apenas.

b) I, II e III, apenas.

c) II, III e IV, apenas.

d) I, II, III e IV.

e) II e III, apenas.

RESPOSTA: D

TCM-PA – Técnico em Informática – 2010 – FCC

São algoritmos ou métodos de busca em cadeias:

a) Boyer-Moore e Knuth-Morris-Pratt.

b) linear e binária.

c) em tabelas e Knuth-Morris-Pratt.

d) binária e Boyer-Moore.

e) linear e Knuth-Morris-Pratt.

RESPOSTA: A

TER-AM – Analista Judiciário – 2010 – FCC

Em relação à construção de algoritmo, considere:

I. Na estrutura de repetição Enquanto / Faça o bloco de repetição pode ser executado várias vezes ou até nenhuma vez. A condição é testada antes de entrar na estrutura de repetição.

II. A estrutura de repetição Repita / Até efetua um teste lógico no fim do laço, garantindo que pelo menos uma vez as instruções deste são executadas.

III. Toda repetição condicional pode ser representada por uma estrutura do tipo Enquanto / Faça ou Repita / Até, sendo que a primeira repete somente quando a condição é falsa e a segunda somente quando a condição é verdadeira.

IV. Para se impedir a situação conhecida como loop infinito é necessário que, nos laços condicionais, a variável que é testada esteja sempre associada a uma instrução que a atualize no interior do laço.

É correto o que se afirma APENAS em

a) I, II e IV.

b) I, II e III.

c) II, III e IV.

d) I e II.

e) II e III.

RESPOSTA: A

TER-AM – Analista Judiciário – 2010 – FCC

Em subprogramação,

a) na modularização de um programa, as partes que o compõe podem ser desenvolvidas por diferentes equipes, sem necessidade de estabelecimento prévio de padrões de programação.

b) um identificador, uma lista de parâmetros para possibilitar a comunicação com outros procedimentos e as ações que nele serão executadas constituem a essência da criação de um procedimento.

c) um objeto é dito global quando sua definição estiver dentro de um procedimento ou quando for declarado como parâmetro formal do procedimento.

d) na passagem de parâmetros por referência, o parâmetro real é passado para o parâmetro formal, fazendo com que todas as ações do procedimento manipulem somente as referências, evitando a alteração do valor original.

e) na passagem de parâmetros por valor, a relação existente entre os parâmetros formal e real está no conteúdo dos parâmetros e não em seu endereço.

RESPOSTA: B

TER-AM – Analista Judiciário – 2010 – FCC

As coleções de dados podem ser classificadas em estruturas lineares e estruturas não lineares. Nesse contexto, é correto afirmar que

a) a fila de prioridade é uma versão especial da fila, uma estrutura não linear. Quando se retira um elemento desta estrutura é selecionado aquele que tem maior prioridade, tendo portanto a ordenação do tipo FIFO.

b) a lista é uma estrutura linear cuja implementação pode ser feita por meio de lista ligada em que as estruturas são estáticas ou através de um array para permitir que as estruturas sejam ligadas dinamicamente.

c) na pilha, uma estrutura não linear, os elementos são colocados e retirados por um único lado da lista, ou seja, pelo topo, que é alterado sempre que um elemento é adicionado ou retirado da pilha. É um tipo de estrutura que tem a ordenação do tipo LILO.

d) na tabela de Hash a chave é transformada num índice inteiro que é usado para acessar os dados. A chave pode ser um string, desde que haja uma função que transforme essa chave num inteiro. É uma estrutura linear.

e) tendo uma estrutura não linear, um array dinâmico é criado usando técnicas de alocação e gestão dinâmica de memória. Pode ser redimensionado e é alocado durante o tempo de compilação.

RESPOSTA: D

A fila é uma estrutura linear. NA fila de prioridade cada elemento tem associado a ele uma prioridade absoluta ou relativa. Novos elementos passam na frente os elementos com prioridade menor do que ele. A pilha é um estrutura linear e tem uma ordenação LIFO (last in, first out).

a – ERRADO. A fila de prioridade ainda é uma fila e portanto Linear. Além disso não se pode afirmar que é FIFO pois as filas de prioridades tem 3 operações que quebram o FIFO. InsertWithPriority que adiciona elemento com prioridade, GetNext que recupera o elemento com maior prioridade e o PeekAtNext que faz um busca na fila em busca do elemento de maior prioridade sem removê-lo.

b – ERRADO. Não necessariamente uma lista encadeada precisa ser estática.

c – ERRADO. Pilha é linear e é uma estrutura LIFO.

d – CORRETO.

e – ERRADO. Array dinâmico é linear. E alocado em tempo de execução.

DPE-SP – Agente de Defensoria – 2010 – FCC

Uma estrutura de dados que possui três campos: dois ponteiros e campo de informação denomina-se

a) lista encadeada dupla.

b) lista encadeada simples.

c) pilha.

d) fila.

e) vetor.

RESPOSTA: A

Lista duplamente encadeada: Uma lista duplamente encadeada é uma sucessão de nós onde cada nó aponta para o próximo nó da lista e para seu predecessor. Assim, além do campo relativo ao dado, cada nó possui dois ponteiros, que chamaremos de prox e ant. O objetivo do duplo encadeamento é tornar mais simples e mais eficiente a execução dos algoritmos.

PGE-RJ – Técnico Superior de Análise de Sistemas – 2009 – FCC

Uma estrutura de dados array pode ser do tipo

a) lista, vetor ou árvore.

b) lista, vetor ou matriz.

c) árvore, grafo ou matriz.

d) árvore, vetor ou matriz.

e) lista, vetor ou grafo.

RESPOSTA: B

TER-AM – Técnico Judiciário – 2009 – FCC

Com respeito aos algoritmos de escalonamento de CPU, uma classe importante dos métodos de avaliação é a avaliação analítica. O tipo de avaliação que, a partir de uma carga de trabalho específica e predeterminada, define o desempenho de cada algoritmo para essa carga é a

a) avaliação funcional.

b) avaliação de enfileiramento.

c) modelagem determinística.

d) modelagem funcional.

e) simulação.

RESPOSTA: C

Avaliação de Algoritmos:

Modelagem determinística

• Considera uma carga de trabalho particular (pré-determinada)

• Define (calcula) o desempenho de cada algoritmo para a carga

• Utilização de CPU, throughput, tempo de espera, tempo de turnarorund, etc.

Modelos de enfileiramento

• Formulação matemática e estatística envolvendo

• Distribuição de picos de CPU e E/S, probabilidade de ocorrência de picos particulares, etc.

• Permite comparar matematicamente algoritmos de forma tratável

• Comparação pode ser irrealística em função de premissas imprecisas

Avaliação por simulação

• Método mais preciso

• Utiliza um modelo de sistema de computação

• Informações (processos, picos de CPU, chegadas, E/S, términos, etc.) podem ser geradas aleatoriamente

• De acordo com distribuições probabilísticas

• Resultados são usados para verificar o que ocorre na realidade e adota-se a distribuição adequada

Avaliação por implementação

• Mais realista

• Alto custo: necessário implementar no kernel e testar sob as diversas situações reais (usuários são prejudicados pelas modificações)

TER-AM – Técnico Judiciário – 2009 – FCC

Formalização de algoritmo proposto em 1936, universalmente conhecido e aceito. Trata-se de um mecanismo simples, que formaliza a ideia de uma pessoa que realiza cálculos, denominado

a) Recursividade de Bird.

b) Máquina de Redução.

c) Máquina de Turing.

d) Sistema de Post.

e) Máquina com Pilhas.

RESPOSTA: C

A máquina de Turing é um dispositivo teórico conhecido como máquina universal, que foi concebido pelo matemático britânico Alan Turing (1912-1954), muitos anos antes de existirem os modernos computadores digitais (o artigo de referência foi publicado em 1936). Num sentido preciso, é um modelo abstrato de um computador, que se restringe apenas aos aspectos lógicos do seu funcionamento (memória, estados e transições) e não à sua implementação física. Numa máquina de Turing pode-se modelar qualquer computador digital.

PGE-RJ – Técnico Superior de Análise de Sistemas – 2009 – FCC

NÃO está associada a uma estrutura de dados especial, que associa chave de pesquisa a valor, a tabela

a) de escrutínio.

b) de espalhamento.

c) hash.

d) relacional.

e) de dispersão

RESPOSTA: D

Todos os termos estão se relacionando a HASH, exceto o termo Tabela Relacional.

TRT 16ª Região – Técnico Judiciário – 2009 – FCC

O almoxarife de um órgão pediu ao técnico de informática que elaborasse um sistema de custeio que, para cada saída de material, considerasse o custo do mais recente que houvera dado entrada no almoxarifado. O técnico deve desenvolver um algoritmo para tratar com uma estrutura de dados do tipo

a) FIFO.

b) TABLE.

c) LIFO.

d) HEAP.

e) ARRAY.

RESPOSTA: C

LIFO: significa último a entrar, primeiro a sair. refere-se a estruturas de dados do tipo pilha. É equivalente a FILO, que significa First In, Last Out O conceito de pilha é amplamente utilizado na informática, como, por exemplo, durante a execução de um programa, para o armazenamento de valores de variável local a um bloco e também para conter o endereço de retorno do trecho de programa que chamou a função ou procedimento atualmente em execução.

TRT 16ª Região – Técnico Judiciário – 2009 – FCC

São, respectivamente, um método de busca e um método de ordenação:

a) linear e por seleção direta.

b) por permutação e linear.

c) por seleção direta e por permutação.

d) por permutação e binária.

e) linear e binária.

RESPOSTA: A

Métodos de Busca: Linear, Busca Binária.

Métodos de Ordenação: Seleção Direta, Por Permutação.

TRT 16ª Região – Técnico Judiciário – 2009 – FCC

O poder da recursão deve-se à possibilidade de definição de um conjunto

a) finito de objetos por meio de uma formulação finita.

b) finito ou não de objetos por meio de uma formulação infinita.

c) infinito de objetos por meio de uma formulação finita.

d) infinito de objetos por meio de uma formulação infinita.

e) finito de objetos por meio de uma formulação infinita.

RESPOSTA: C

Conjunto Infinito (pois poderá visitar recursivamente a mesma função), como a recursividade envolve apenas um objeto, a função, a formulação é finita.

Recursão é o processo de definir algo em termos de si mesmo e é, algumas vezes, chamado de definição circular. Assim, pode-se dizer que o conceito de algo recursivo está dentro de si, que por sua vez está dentro de si e assim sucessivamente, INFINITAMENTE.

Um algoritmo recursivo sempre deverá ter uma condição de parada (solução trivial) que define quando a recursão se encerra, ou seja a sua formulação é FINITA. Mas, os OBJETOS que serão utilizado no algoritmo recursivo terão definições INFINITAS. Cabe o algoritmo limitá-los.

TRT 16ª Região – Técnico Judiciário – 2009 – FCC

Pilha é uma estrutura de dados

a) cujo acesso aos seus elementos segue tanto a lógica LIFO quanto a FIFO.

b) cujo acesso aos seus elementos ocorre de forma aleatória.

c) que pode ser implementada somente por meio de vetores.

d) que pode ser implementada somente por meio de listas.

e) cujo acesso aos seus elementos segue a lógica LIFO, apenas.

RESPOSTA: E

TRT 15ª Região – Analista Judiciário – 2009 – FCC

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.

RESPOSTA: C

TRE-PI – Técnico Judiciário – 2009 – FCC

Sobre estrutura de dados, considere:

I. Pilha é uma estrutura de dados com acesso restrito aos seus elementos, uma vez que eles são colocados e retirados por um único lado e são ordenados pelo princípio LIFO (last in first out). Assim, sempre que um elemento é adicionado ou retirado seu topo é alterado.

II. Pilha é o tipo de estrutura usada, por exemplo, na avaliação de expressões numéricas, na recursividade e pelos compiladores, na passagem de parâmetros para as funções.

III. Registro é uma estrutura básica que permite guardar coleções de dados de diferentes tipos, sendo normalmente utilizado quando um objeto tem diferentes atributos, isto é, contém campos de diferentes tipos.

IV. Lista pode conter um número qualquer de elementos, expandindo-se ou contraindo-se conforme o elementos são inseridos ou retirados. Nesse tipo de estrutura, os acessos tanto podem ser feitos sequencialmente como diretamente.

V. Fila, assim como a pilha , é uma versão especial de lista, e como tal, seus elementos são ordenados pelo princípio LIFO (last in first out).

Está correto o que se afirma APENAS em

a) I, II e III.

b) I, III, IV e V.

c) I, III e V.

d) II, III, IV e V.

e) II, IV e V.

RESPOSTA: A

O erro da IV é que lista só pode ser acessado sequencialmente e o erro da V é que Fila segue os princípios (FIFO e LILO).

TRE-PI – Técnico Judiciário – 2009 – FCC

Grafo é um objeto formado por

a) vértices, arestas e nós.

b) vértices e arestas, apenas.

c) vértices, apenas.

d) arestas, apenas.

e) nós, apenas.

RESPOSTA: B

TRE-PI – Técnico Judiciário – 2009 – FCC

Uma árvore binária completa, estritamente binária, cuja raiz está no nível 0 e a altura da árvore é 5, possui uma quantidade de nós igual a

a) 63.

b) 62.

c) 32.

d) 31.

e) 30.

RESPOSTA: A

nó 0 : 2 elv 0 = 1

nó 1 : 2 elv 1 = 2

nó 2 : 2 elv 2 = 4

nó 3 : 2 elv 3 = 8

nó 4 : 2 elv 4 = 16

nó 5 : 2 elv 5 = 32

Altura 5 árvore completa

Soma : 1+2+4+8+16+32 = 63 resposta

O nível da árvore binária equivale à sua altura e começa a contar de zero. Logo, se tem 5 de altura, conta-se de 0 a 5. Não esquecer: NIVEL = ALTURA. Inicia-se em ZERO (0).

Para facilitar mais ainda basta usar a fórmula:

2 ^(altura+1) – 1 = 2 ⁵⁺¹-1 = 2⁶-1 = 64-1 = 63

TRE-PI – Técnico Judiciário – 2009 – FCC

Em relação a tipos abstratos de dados, é correto afirmar que

a) o TAD não encapsula a estrutura de dados para permitir que os usuários possam ter acesso a todas as operações disponibilizadas sobre esses dados.

b) algumas pilhas admitem serem declaradas como tipos abstratos de dados.

c) filas não permitem declaração como tipos abstratos de dados.

d) os tipos abstratos de dados podem ser formados pela união de tipos de dados primitivos, mas não por outros tipos abstratos de dados.

e) são tipos de dados que escondem a sua implementação de quem o manipula; de maneira geral as operações sobre estes dados são executadas sem que se saiba como isso é feito.

RESPOSTA: E

Um TAD, em um paradigma procedural (imperativo) usa-se o TAD com objetivo de encapsular detalhes de implementações do código. É uma tentativa de fazer algo que as classes e objetos fazem na programação orientada a objetos.

Um Tipo Abstrato de Dados – TAD – é uma coleção bem definida de dados a serem armazenados, e um grupo de operadores que podem ser aplicados para manipulação desses dados. Posteriormente, essa metodologia foi incorporada à própria linguagem de programação, para um protótipo do que é hoje a orientação a objetos (OOP – Object Oriented Programming). Permitindo o controle do acesso às informações de um tipo, a herança e o polimorfismo.

Características Fundamentais:

• Os operadores do TAD implementam regras bem definidas para manipulação dos valores armazenados;

• Os valores armazenados devem ser manipulados EXCLUSIVAMENTE pelos operadores do TAD.

A especificação de um TAD descreve quais dados podem ser armazenados, e o que é possível fazer com esses dados através dos operadores do TAD. Mas a especificação do TAD não descreve como isso é ou será efetivamente implementado no programa. Isso pode ser definido em um segundo momento. Ou seja, um Tipo Abstrato de Dado é um modelo abstrato do armazenamento e manipulação de um determinado conjunto de dados de um programa.

TRE-PI – Técnico Judiciário – 2009 – FCC

Em relação a estruturas de dados, avalie a correspondência existente entre as estruturas de dados Lineares e Não Lineares com suas respectivas coleções de dados:

O algoritmo do enunciado apresenta estruturas de controle condicional, sendo, sucessivamente,

a) uma composta, uma simples e uma de múltipla escolha.

b) uma simples, uma de repetição e uma de múltipla escolha.

c) duas de múltipla escolha e uma de repetição.

d) uma composta e duas de repetição.

e) três de repetição.

RESPOSTA: E

Uma composta (if/else) e duas de repetição (para, enquanto).

TRE-PI – Técnico Judiciário – 2009 – FCC

No algoritmo do enunciado, são variáveis dependentes de comandos de atribuição:

a) nome e aux.

b) aux e salario.

c) nome e salario.

d) nome e nivel_superior.

e) salario e nivel_superior.

RESPOSTA: B

Somente aux e salario possuem comandos de atribuição no código. Os demais atributos recebem valores somente através de entrada do usuário.

TRE-PI – Técnico Judiciário – 2009 – FCC

Em relação a estruturas de dados, avalie a correspondência existente entre as estruturas de dados Lineares e Não Lineares com suas respectivas coleções de dados:

A correta associação entre os elementos das duas tabelas é:

a) a1, b1, c1, d2, e2, f2.

b) a2, b2, c1, d1, e1, f2.

c) a1, b2, c2, d2, e1, f1.

d) a2, b1, c2, d1, e2, f1.

e) a1, b1, c2, d2, e2, f1.

RESPOSTA: E

Visto isso, definimos estrutura de dados como um tipo derivado de dado concebido com o objetivo de ser manipulado de maneira sistemática por algoritmos e, consequentemente, por programas de computador, por exemplo as listas, que podem ser lineares ou não lineares.

Lista linear é uma estrutura de dados dinâmica na qual seus elementos estão organizados de maneira seqüencial. Os tipos mais comuns de listas lineares são as pilhas, as filas e os deques.

Fila: As filas são estruturas baseadas no princípio FIFO (first in, first out), em que os elementos que foram inseridos no início são os primeiros a serem removidos. Uma fila possui duas funções básicas: ENQUEUE, que adiciona um elemento ao final da fila, e DEQUEUE, que remove o elemento no início da fila. A operação DEQUEUE só pode ser aplicado se a fila não estiver vazia, causando um erro de underflow ou fila vazia se esta operação for realizada nesta situação.

Pilha: As pilhas são estruturas baseadas no princípio LIFO (last in, first out), na qual os dados que foram inseridos por último na pilha serão os primeiros a serem removidos. Existem duas funções que se aplicam a todas as pilhas: PUSH, que insere um dado no topo da pilha, e POP, que remove o item no topo da pilha. Um deque (double-ended queue) é uma lista linear na qual os elementos entram e saem tanto pela frente quanto por trás. Pode ser considerada uma generalização da fila.

Uma lista encadeada é uma lista linear na qual um elemento pode ser incluído em qualquer lugar e excluído de qualquer lugar. A principal caraterística da lista encadeada é o fato de que ela não necessitar estar alocada seqüencialmente na memória do computador. Para isso faz uso de ponteiros ou apontadores, que são variáveis que guardam endereços de memória. A lista simplesmente encadeada usa apenas um ponteiro.

Lista duplamente encadeada é uma lista linear muito parecida com a anterior. A principal diferença entre elas é o uso de duas variáveis do tipo ponteiro (para um lado e para o outro) para guardar endereços dos elementos da lista, e não apenas um como na anterior.

Uma lista não-linear é uma estrutura de dados na qual os elementos estão organizados de maneira diversa à seqüencial. O tipo mais comum de listas não-lineares é a árvore, que é uma estrutura de dados não-linear organizada sob uma forma recursiva, isto é, os elementos da árvores também são árvores.

TRE-PI – Técnico Judiciário – 2009 – FCC

No algoritmo do enunciado, observa-se que os tipos de dados não foram declarados. Nesse caso, para ajustar o algoritmo, os tipos de dados para nome, aux, salario e nivel_superior seriam, respectivamente

a) real, lógico, inteiro e real.

b) caracter, real, inteiro e lógico.

c) real, lógico, inteiro e inteiro.

d) caracter, inteiro, real e lógico.

e) caracter, lógico, real e real.

RESPOSTA: D

Nome deve ser uma string, ou no caso caracter. Aux é utilizado como um contatdor que recebe apenas números inteiros então deve ser Inteiro ou Real, como ele oferece as duas opções o mais correto é inteiro uma vez que não tem valores decimais, Salário como é moeda deve ser real inclusive pois recebe valores multiplicados por 1.5, e nível_superior deve ser booleano ou lógico.

TJ-PI – Analista Judiciário – 2009 – FCC

É um método de pesquisa ou busca, cujo algoritmo parte do pressuposto de que o vetor está ordenado e realiza sucessivas divisões do espaço de busca, comparando o elemento buscado (chave) com o elemento no meio do vetor. Se o elemento do meio do vetor for a chave, a busca termina com sucesso. Caso contrário, se o elemento do meio vier antes do elemento buscado, então a busca continua na metade posterior do vetor. E finalmente, se o elemento do meio vier depois da chave, a busca continua na metade anterior do vetor. Trata-se do método denominado busca

a) por contagem.

b) randômica.

c) linear.

d) binária.

e) por comparação.

RESPOSTA: D

TJ-PI – Analista Judiciário – 2009 – FCC

Considere o trecho do algoritmo (Pseudo-Código):

Em relação às estruturas básicas de controle, o trecho de algoritmo acima refere-se a estrutura

I. condicional simples.

II. condicional composta.

III. de repetição.

IV. de decisão ou seleção.

É correto o que consta APENAS em

a) II, III e IV.

b) II e IV.

c) I e III.

d) II e III.

e) I, III e IV.

RESPOSTA: B

Estruturas de controle:

• Estrutura de condicional, de decisão, de seleção

  • IF/ELSE

• Estruturas de repetição, de loop

  • WHILE

  • FOR

  • DO, DO WHILE

  • REPEAT

Além disso, como esse Pseudo-Código não apresenta nenhuma estrutura de repetição, “mataríamos” a questão fácil-fácil como o item III é falso e o mesmo se encontra nas letras (A, C, D e E) eliminamos essas 4 restando apenas a letra B que é a resposta correta.

TJ-PI – Analista Judiciário – 2009 – FCC

Seja o algoritmo (Pseudo-Código):

Em função dos tipos de dados declarados em Var, é correto concluir que as variáveis Nome e Soma, avaliadas isoladamente, podem representar, respectivamente,

I. um número de telefone e o número de moradores de um condomínio;

II. os nomes e a quantidade de alunos de uma escola;

III. um endereço de e-mail e o resultado de uma divisão;

IV. t0m@T& e 0,25.

É correto o que consta em

a) I, II, III e IV.

b) III e IV, apenas.

c) I e II, apenas.

d) I, II e III, apenas.

e) II, III e IV, apenas.

RESPOSTA: A

Essa é uma típica questão sacana… O código apresentado é só para o candidato perder tempo. Tudo que ele quer saber é se o candidato sabe o que cada tipo de variárel (string e numérica) pode armazenar!

TJ-PI – Analista Judiciário – 2009 – FCC

Uma lista ligada é uma estrutura que corresponde a uma sequência lógica de entradas ou nós. Cada nó armazena a localização do próximo elemento na sequência, ou seja, de seu nó sucessor. Nessa estrutura,

a) para estabelecer a ligação entre um nó já pertencente a uma lista e um novo nó, basta fazer com que o novo nó referencie no, camponext, o nó que anteriormente era referenciado pelo nó original, desde que esse campo não tenha o valor nulo.

b) a existência de um ponteiro apontando para o 1º elemento e outro para o fim da lista permite que a inserção ou deleção de dados de um nó que esteja no meio da lista seja rapidamente executada.

c) enquanto a entrada que determina o topo da lista é mantida em um nó descritor dessa lista, a entrada que marca o fim da lista é mantida fora do descritor.

d) o armazenamento de uma lista requer uma área contígua de memória para permitir a otimização no processamento de criação e remoção de nós da lista.

e) o armazenamento de uma lista não requer uma área contígua de memória. Como listas são estruturas dinâmicas, normalmente são definidos procedimentos que permitem criar e remover nós na memória.

RESPOSTA: B

Uma lista ligada é uma estrutura que corresponde a uma sequência lógica de entradas ou nós. Tipicamente, em uma lista ligada há um ou dois pontos conhecidos de acesso — normalmente o topo da lista (seu primeiro elemento) e eventualmente o fim da lista (seu último elemento). Cada nó armazena também a localização do próximo elemento na sequência, ou seja, de seu nó sucessor. Desse modo, o armazenamento de uma lista não requer uma área contígua de memória.

Toda a informação em um nó pode ser abstraída para dois campos de interesse: info, o conteúdo do nó, e next, uma referência para o próximo nó da lista. A entrada que determina o topo da lista deve ser registrada à parte da lista. Essa informação é tipicamente mantida em um nó descritor da lista. A entrada que marca o fim da lista não precisa de indicação especial — tipicamente, o ponteiro nulo como valor de next marca o final da lista.

TJ-PA – Analista Judiciário – 2009 – FCC

Considere uma estrutura de dados do tipo vetor. Com respeito a tal estrutura, é correto que seus componentes são, caracteristicamente,

a) heterogêneos e com acesso FIFO.

b) heterogêneos e com acesso LIFO.

c) heterogêneos e com acesso indexado-sequencial.

d) homogêneos e acesso não indexado.

e) homogêneos e de acesso aleatório por intermédio de índices.

RESPOSTA: E

homogêneos e de acesso aleatório por intermédio de índices. Significa dizer que o tipo dos dados de um vetor é sempre igual, ou seja, se crio um vetor de caracteres com 10 posições, significa que o tipo de dados dos 10 elementos inseridos será caractere. Acesso aleatório significa que posso acessar qualquer elemento do vetor através do índice, ou seja, quero o elemento da posição 4 então digo vet[4], não preciso passar pela posição 1,2 e 3 para chegar à posição 4, posso acessar diretamente a posição 4 através do nome do vetor e do índice da posição desejada, vet[4] por exemplo.

TJ-PA – Analista Judiciário – 2009 – FCC

Considere a seguinte e somente a seguinte situação: Se um procedimento Px contiver uma referência a um outro procedimento Py que por sua vez contém uma referência direta ou indireta a Px, então

a) Px é subconjunto de Py.

b) Px é categorizado como indiretamente recursivo.

c) Py é subconjunto de Px.

d) Py é categorizado como diretamente recursivo.

e) Py é categorizado como indiretamente recursivo.

RESPOSTA: B

Para se codificar programas de modo recursivo usa-se um procedimento ou sub-rotina, que permite dar um nome a um comando, o qual pode chamar a si próprio.

• Esta chamada pode ser Diretamente Recursiva, quando o procedimento P contiver uma referência explícita a si próprio; ou

• Esta chamada pode ser Indiretamente Recursiva, quando o procedimento P contiver uma referência a outro procedimento Q, que por sua vez contém uma referência direta ou indireta a P.

TJ-PA – Analista Judiciário – 2009 – FCC

A necessidade de rearranjo de um certo conjunto de elementos, de acordo com um critério específico, indica

a) a possibilidade de uso de qualquer algoritmo de ordenação.

b) o uso estrito de algoritmo de ordenação por inserção direta.

c) o uso estrito de algoritmo de ordenação por seleção direta.

d) o uso estrito de algoritmo de ordenação por permutação.

e) o uso estrito de algoritmo de ordenação por particionamento.

RESPOSTA: A

Um arranjo (array, vetor ou matriz) é um agregado HOMOGÊNEO de elementos de dados. Não há possibilidade de que o array seja de elementos heterogêneos. Não confunda um arranjo onde os elementos são registros (onde os componentes do registro podem ser de tipos diferentes) com a ideia de arranjo heterogêneo. Quando o arranjo é um agregado de registros, todos os elementos do arranjo possuem a mesma forma (definida pelo registro), ou seja, o arranjo é homogêneo. Outro cuidado é não confundir o tipo de dado do arranjo (homogêneo = tipos iguais) com o conteúdo de cada elemento do arranjo (valores diferentes).

TJ-PA – Analista Judiciário – 2009 – FCC

O produto da ação de algoritmos que fazem o mapeamento de uma sequência de bits de tamanho arbitrário para uma sequência de bits de tamanho fixo menor, com resistência à colisão e cujo processo reverso também não seja realizável, denomina-se

a) cadeia de certificação.

b) cifra de bloco.

c) resultado hash.

d) mensagem de não repúdio.

e) dispositivo token.

RESPOSTA: C

Tabelas onde é possível fazer pesquisas através do cálculo de endereço são conhecidas por Tabelas HASH. Hash, em inglês, significa dispersão, espalhamento. Este método de pesquisa é bastante útil quando a busca é feita sobre um número muito grande de dados que possuam faixas de valores muito variável. Tabelas HASH são como a maioria das outras tabelas, à exceção que é possível fazer acesso não sequencial a determinados registros da tabela através do uso de funções hash (em português: funções de espalhamento).

TJ-SE – Técnico Judiciário – 2009 – FCC

Sobre os algoritmos de busca pode-se afirmar que o método

a) sequencial necessita que os dados estejam ordenados para realização da pesquisa.

b) linear é adequado para ordenar grande quantidade de dados.

c) binário é o mais adequado para pesquisar grande quantidade de dados.

d) seleção direta é adequado para ordenar pequena quantidade de dados.

e) bolha, além de pesquisar um determinado valor, realiza a ordenação dos dados.

RESPOSTA: C

Pesquisa Sequencial ou Linear: é o método mais simples de pesquisa e consiste em uma varredura serial dos dados, durante a qual um argumento de pesquisa é comparado com a chave de cada entrada até que seja encontrada uma que seja igual, ou ser atingido o final da sequencia de dados. O desempenho do algoritmo de pesquisa sequencial é ruim, considerando que todas as entradas possuem a mesma possibilidade de serem solicitadas. A Pesquisa sequencial não necessita que os dados estejam ordenados. Além disso quanto mais dados, mais lenta se torna o que invalida a alternativa B também.

Pesquisa binária: é um método de pesquisa que só pode ser aplicado em conjunto de dados ordenados (e com acesso direto – memória principal). O método compara a chave de pesquisa com o elemento central do conjunto de dados. Se a chave de busca coincidir com o elemento do conjunto de dados, a pesquisa termina com sucesso. Caso contrário, verifica-se se a chave de pesquisa é maior ou menor do que o elemento comparado. Se for maior, o algoritmo é repetido para a parte do conjunto de dados ordenado que estiver após a posição comparada (centro). O método binário é o mais adequado para pesquisar grande quantidade de dados.

Seleção Direta (SelectSort): é o método mais simples de classificação por seleção, no qual é feita uma busca sequencial para se encontrar o menor elemento da tabela. Quando este é encontrado, ele é permutado com o elemento que se encontra na posição inicial da tabela. A seguir, repete-se o processo para o restante da tabela, desconsiderando-se o 1º elemento da tabela (que já contém o menor elemento). A cada passo encontra-se o menor elemento dentro do segmento com os elementos não selecionados; Troca-se este elemento com o primeiro elemento do segmento; Atualiza-se o tamanho do segmento (menos um elemento); Este processo é repetido até que o segmento fique com apenas um elemento.

Por qual motivo a C, D, E estão incorretas?

TJ-SE – Técnico Judiciário – 2009 – FCC

Uma estrutura de dados em lista duplamente encadeada permite na cadeia movimentos para

a) frente, apenas.

b) trás, apenas.

c) cima e para baixo ou para frente e para trás.

d) cima e para baixo, apenas.

e) frente e para trás, apenas.

RESPOSTA: E

Ele terá um ponteiro para o próximo item, e para o item anterior, o que permite a navegação para frente e para trás, apenas.

TJ-SE – Técnico Judiciário – 2009 – FCC

Um grafo cujo nó de partida de um caminho coincide com o nó de chegada caracteriza um grafo

a) completo.

b) cíclico.

c) simétrico.

d) conexo.

e) regular.

RESPOSTA: B

TJ-SE – Técnico Judiciário – 2009 – FCC

O nível 5 de uma árvore binária completa tem

a) 16 nós, na quarta camada.

b) 16 nós, na quinta camada.

c) 32 nós, na quinta camada.

d) 32 nós, na sexta camada.

e) 64 nós, na sexta camada.

RESPOSTA: D

Observe que ele não está falando do 5º nível, mas do nível 5. 2⁵ = 32. Como o nível 0 é a primeira camada (raiz), então o nível 5 será a 6ª camada.

TJ-SE – Técnico Judiciário – 2009 – FCC

Um órgão público adotou dois sistemas de senhas para atender os cidadãos na ordem de chegada.

O sistema I atende os não idosos.

O sistema II atende os idosos.

Nessa situação,

a) tanto o sistema I, quanto o II, adotam o esquema LIFO de organização de dados.

b) o sistema I, adota o esquema LIFO de organização de dados e o II, o esquema FIFO.

c) tanto o sistema I, quanto o II, adotam o esquema FIFO de organização de dados.

d) o sistema I, adota o esquema FIFO de organização de dados e o II, o esquema LIFO.

e) tanto o sistema I, quanto o II, adotam o esquema Árvore Binária de organização de dados.

RESPOSTA: C

TRT 7ª Região – Analista Judiciário – 2009 – FCC

Um dos valores do tipo fundamental BOOLEAN é denotado pelo identificador

a) CARDINAL.

b) DECIMAL.

c) REAL.

d) TRUE.

e) CHAR.

RESPOSTA: D

Valores possíveis para um dado BOOLEAN são: True e False.

TRT 7ª Região – Analista Judiciário – 2009 – FCC

Os métodos de Knuth-Morris-Pratt (KMP) e de Boyer-Moore (BM) são algoritmos de

a) busca binária.

b) busca em cadeias.

c) ordenação de vetores por inserção.

d) ordenação de vetores por seleção.

e) ordenação de vetores por troca.

RESPOSTA: B

Os métodos de Knuth-Morris-Pratt (KMP) e de Boyer-Moore (BM) são algoritmos de são algoritmos de busca em cadeias. Seja T o texto e P o parâmetro procurado em T, o método BM consegue evitar comparações entre P e uma boa parte dos caracteres em T. O único problema desse algoritmo é que ele trabalha com um alfabeto limitado. O método KMP evita o desperdício de informações que ocorrem em outros algoritmos. Possui pré-processamento de P, permitindo que nenhum caractere seja reexaminado.

MPE-SE – Analista do Ministério Público – 2009 – FCC

Um algoritmo que pode ser usado para caminhar pela estrutura e retornar informações úteis para a resolução do problema. Uma estrutura delinks do tipo “Wikipedia” é um modelo que pode ser representado por esta categoria de algoritmo, ou seja, os vértices são os artigos e “existe uma aresta do artigo X para o artigo Y se e somente se X contém um link para Y”. As características elencadas representam um algoritmo

a) genético.

b) de programação dinâmica.

c) de divisão e conquista.

d) de programação linear.

e) de exploração de grafo.

RESPOSTA: E

TRT 3ª Região – Analista Judiciário – 2009 – FCC

Uma boa função de transformação de chaves tem como requisito essencial a distribuição das chaves tão uniformemente quanto possível dentro do intervalo dos valores dos índices. Exceto esta exigência, a distribuição não é vinculada a nenhum padrão particular, sendo desejável, inclusive, que pareça totalmente aleatória. Tal propriedade deu a este método uma conotação não-científica (o significado é pulverizar o argumento e espalhá-lo desordenadamente) com o nome de

a) factoring.

b) linkage.

c) boolean.

d) hashing.

e) buffering.

RESPOSTA: D

TRT 3ª Região – Analista Judiciário – 2009 – FCC

Dois métodos orientados para busca em cadeias levam o nome de

a) Toby Teorey e Sam Lightstone.

b) Boyer-Moore e Knuth-Morris-Pratt.

c) Horspool e C. J. Date.

d) Boyer-Moore e Sam Lightstone.

e) Knuth-Morris-Pratt e C. J. Date.

RESPOSTA: B

TRF 5ª Região – Analista Judiciário – 2008 – FCC

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.

RESPOSTA: B

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.

Metrô-SP – Analista Trainee – 2008 – FCC

Para responder às questões de números 51 e 52, considere a figura abaixo, relacionada à Teoria dos Grafos.

No grafo exibido, o caminho V1, V2, V4, V3 tem comprimento igual a

a) 6.

b) 5.

c) 4.

d) 3.

e) 2.

RESPOSTA: D

Pois não é um grafo valorado, sendo assim basta contar a quantidade de arestas utilizadas no caminho.

Metrô-SP – Analista Trainee – 2008 – FCC

Para responder às questões de números 51 e 52, considere a figura abaixo, relacionada à Teoria dos Grafos.

O grafo representado é um grafo

a) conexo.

b) fortemente conexo.

c) não orientado.

d) parcial.

e) isolado.

RESPOSTA: B

Grafo conexo: Um gravo G(V,A) é dito conexo se há pelo menos uma cadeia ligando cada par de vértices deste grafo G.

Grafo fortemente conexo: se todo par de vértice está ligado por pelo menos um caminho em cada sentido, ou seja, se cada par de vértice participa de um circuito. Isso significa que cada vértice pode ser alcançável partindo-se de qualquer outro vértice do grafo.

Grafo não orientado: Quando não há direção das arestas.

Metrô-SP – Analista Trainee – 2008 – FCC

Em relação à lógica de programação, considere os pseudocódigos:

a) Somente Alg1 tem consistência em sua representação e chega a um resultado.

b) Ambos os algoritmos abordam o mesmo problema e chegam ao mesmo resultado.

c) Somente Alg2 tem consistência em sua representação e chega a um resultado.

d) O resultado da solução apresentada por Alg2 é maior do que a de Alg1.

e) O resultado da solução apresentada por Alg2 é menor do que a de Alg1.

RESPOSTA: B

Algoritmo 1:

• SalBase = 1000

• Grat = 1000*5/100 = 50

• SalReceber = 1000 + 50 – 0 = 1050

• Imp = 1050 * 7/100 = 73,50

• SalReceber = 1050 – 73,50 = 976,50

Algoritmo 2:

• SalBase = 1000

• SalReceber = 1000 + (1000 * 5/100) = 1050

• Imp = 1050 * 7/100 = 73,50

• SalReceber = 1050 – 73,50 = 976,50

Metrô-SP – Analista Trainee – 2008 – FCC

O objetivo de fazer uma busca rápida a partir de uma chave de pesquisa simples e obter o valor desejado é alcançado pela estrutura de dados especial denominada

a) array.

b) lista.

c) vetor.

d) árvore binária.

e) tabela de hashing.

RESPOSTA: E

Tabela hashing também conhecida por tabela de espalhamento, é 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. É algumas vezes traduzida como tabela de escrutínio.

MPE-RS – Técnico em Informática – 2008 – FCC

A execução de uma expressão lógica obedece como prioridade a ordem dos operadores

a) Or, And e Not.

b) Not, And e Or.

c) And, Not e Or.

d) And, Or e Not.

e) Not, Or e And.

RESPOSTA: B

Prioridade na ordem dos operadores :

Prioridade Mais Alta > Not > And > Or > Prioridade Mais Baixa

Para ficar mais fácil só lembrar da palavra: NAO

MPE-RS – Técnico em Informática – 2008 – FCC

Respeitando as ordens de inserção e de retirada dos dados, uma estrutura de

a) fila é também denominada LIFO ou LILO.

b) fila é também denominada FIFO ou FILO.

c) fila é também denominada FIFO ou LIFO.

d) pilha é também denominada FIFO ou FILO.

e) pilha é também denominada LIFO ou FILO.

RESPOSTA: E

Estrutura de dados Fila:

• LILO significa Last In Last Out –> Último a entrar é o último a sair.

• FIFO significa First In First Out –> Primeiro a entrar é o primeiro a sair.

Estrutura de dados Pilha:

• LIFO significa Last In First Out –> Último a entrar é o primeiro a sair.

• FILO significa First In Last Out –> Primeiro a entrar é o último a sair.

MPE-RS – Técnico em Informática – 2008 – FCC

Uma fila dupla que se trata de uma lista linear na qual os elementos podem ser inseridos ou removidos de qualquer extremo denomina-se

a) hashing.

b) grafo.

c) deque.

d) lista aberta.

e) lista fechada.

RESPOSTA: C

As listas lineares podem ser: Pilha, Fila ou Fila Dupla. É dita FILA DUPLA porque os elementos podem ser inseridos ou removidos de qualquer extremidade. É conhecida também por DEQUE (Double Ended Queue).

TCE-AL – Programador – 2008 – FCC

A estrutura de dados de iteração na qual uma ação será executada pelo menos uma vez, antes da avaliação da condição, é implementada pelo comando básico

a) condicional.

b) faça enquanto.

c) seqüencial.

d) de repetição.

e) de seleção.

RESPOSTA: C

A programação estruturada é composta de 3 estruturas básicas.

• Sequência: Refere-se a ordem de execução das intruções.

• Seleção/Decisão: Refere-se a execução de partes de código apenas sob determinado estado do programa, na prática é alcançado por estruturas como IF ELSE, SWITCH CASE

• Repetição/Iteração: Basea-se em repetições da execução de um trecho de código até o programa chegar a um certo estado cuja repetição possa ser interrompida.

Na prática usa-se

Repetição pré-testada: while () , for ( )

Repetição pós-testada: do … while (), repeat … until ()

É possível que essa questão tenha sído anulada pois há duas alternativas corretas.

b) “faça enquanto” refere-se ao do { } while ( ); onde as instruções são executadas pelo menos uma vez e até que a condição seja falsa.

d) “de repetição” refere-se ao repeat { } until( ); onde as instruções são executadas pelo menos uma vez e até que a condição seja verdadeira.

Talvez por citar Estrutura, a letra D tenha prevalecido, uma vez que “Faça Enquanto” não é uma estrutura, mas um comando.

TRT 18ª Região – Analista Judiciário – 2008 – FCC

Na execução de um programa, uma estrutura pode ser usada na chamada de procedimentos para armazenar o endereço de retorno (e os parâmetros reais). À medida que procedimentos chamam outros procedimentos, mais e mais endereços de retorno devem ser montados em determinada ordem para, posteriormente, serem recuperados corretamente à medida que os procedimentos chegam ao seu fim. Esta estrutura é adequadamente representada por

a) array.

b) espelhamento.

c) pilha.

d) árvore binária.

e) fila.

RESPOSTA: C

Pilha que é muito utilizada para o armazenamento do endereço dos parâmetros em funções recursivas.

TRT 18ª Região – Analista Judiciário – 2008 – FCC

Dentre os métodos para construção de algoritmos, o Cartesiano é aquele que segue o princípio de

a) dividir para conquistar.

b) primeiro que entra, primeiro que sai.

c) planejamento reverso.

d) pseudo-linguagem.

e) primeiro que entra, último que sai.

RESPOSTA: A

O método cartesiano consiste justamente em atacar o problema abrangente DIVIDINDO-O EM PARTES MENORES, a fim de torná-lo mais simples ou específico e, se necessário, dividir novamente as partes não compreendidas.

Pode-se esquematizar o seguinte procedimento (algoritmo) para o método:

• Dividir o problema em suas partes principais.

• Analisar a divisão obtida para garantir coerência.

• Se alguma parte não for bem compreendida, aplicar a ela o método.

• Analisar o objeto para garantir entendimento e coerência.

TRT 18ª Região – Analista Judiciário – 2008 – FCC

Á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.

RESPOSTA: E

Árvore AVL (ou árvore balanceada pela altura), em Ciência da Computação, é uma árvore de busca binária auto-balanceada. Em tal árvore, as alturas das duas sub-árvores a partir de cada nó difere no máximo em uma unidade.

O FATOR DE BALANCEAMENTO DE UM NÓ É DADO PELO SEU PESO EM RELAÇÃO A SUA SUB-ÁRVORE. UM NÓ COM FATOR BALANCEADO PODE CONTER 1, 0, OU -1 EM SEU FATOR. Um nó com fator de balanceamento diferente dos citados é considerado uma árvore não-AVL e requer um balanceamento por rotação ou dupla-rotação.

Fonte: http://pt.wikipedia.org/wiki/%C3%81rvore_AVL

TRT 18ª Região – Analista Judiciário – 2008 – FCC

No espectro que representa os tipos possíveis de coesão entre tarefas que se relacionam em um módulo, a mais INDESEJÁVEL é a

a) temporal.

b) seqüencial.

c) coincidental.

d) funcional.

e) comunicacional.

RESPOSTA: C

Tipos de coesão entre módulos:

• Coincidente (pior)

• Lógico

• Temporal

• Procedural

• De comunicação

• Sequencial

• Funcional (melhor)

Indesejáveis

• Acidental/Coincidental (pior): aleatória e coincidente

• Lógica: fazem a mesma coisa mesmo diferentes por natureza (agrupamento de rotinas E/S).

• Temporal: ocorre quando um módulo realiza um conjunto de tarefas que devem ser executadas dentro do mesmo decurso de tempo.

Intermediárias

• Procedural: seguem uma sequência específica de execução (Ex. uma função que verifica as permissões do arquivo e depois o abre).

• Comunicação: operam sobre os mesmos dados

• Sequencial: a saída de uma parte é a entrada de outra parte

Desejável

• Funcional (melhor): partes de um módulo ou classes são agrupados porque todos contribuem para uma única tarefa definida do módulo.

TCE-AL – Programador – 2008 – FCC

Quando se elimina o nó raiz de uma estrutura em árvore, o que dela restar forma:

a) outra árvore.

b) uma floresta.

c) uma árvore binária.

d) uma sub-árvore.

e) um conjunto de sub-árvores.

RESPOSTA: B

Quando se remove, transforma-se uma árvore em duas árvores. Mais que uma árvore é o que chamamos de Floresta.

MPU – Analista de Informática – 2007 – FCC

Considere:

I. Os algoritmos de busca binária e de busca sequencial executam processamento repetitivo.

II. Os algoritmos de busca binária e de busca sequencial utilizam a técnica de recursão.

III. A busca sequencial executa cada fase da repetição na forma de uma subtarefa da fase anterior.

IV. A busca binária trabalha com uma forma circular de repetição.

Está correto o que consta em

a) I, apenas.

b) II, apenas.

c) I e II, apenas.

d) I, III e IV, apenas.

e) I, II, III e IV.

RESPOSTA: A

A pesquisa ou busca binária (em inglês binary search algorithm ou binary chop) é um algoritmo de busca em vetores que requer acesso aleatório aos elementos do mesmo. Ela parte do pressuposto de que o vetor está ordenado e realiza sucessivas divisões do espaço de busca (divisão e conquista) comparando o elemento buscado (chave) com o elemento no meio do vetor. Se o elemento do meio do vetor for a chave, a busca termina com sucesso. Caso contrário, se o elemento do meio vier antes do elemento buscado, então a busca continua na metade posterior do vetor. E finalmente, se o elemento do meio vier depois da chave, a busca continua na metade anterior do vetor.

A busca linear não é indicada para vetores ordenados (1,2,3…), para este a melhor indicação é a busca Binária.

Sequencial – Faz o que o próprio nome diz, percorre todo vetor até encontrar o valor desejado.

Binário – Usa três ponteiros chamados de inicio, meio e fim, e vai diminuindo a busca alternando os ponteiros, consequentemente, diminuindo os espaços até encontrar o valor desejado.

• I) Correta

• II) Sequencial não é recursivo

• III) Subtarefa nada haver

• IV) Circular nada haver