LÓGICA E ESTRUTURA DE DADOS

01. (FCC-TRT-SP/2008) Uma ou mais instruções são executadas ou não, dependendo do resultado do teste efetuado. Esta afirmação define uma estrutura de controle de programação do tipo

(A) pilha.

(B) seleção.

(C) fila.

(D) repetição.

(E) seqüência.

Solução:

· A pilha é uma estrutura de dados do tipo LIFO (Last In First Out) onde as inserções e remoções são feitas pelo mesmo lado, mas o último a entrar é o primeiro a sair.

· Seleção é uma estrutura de controle que permite a escolha de um grupo de ações (bloco) a ser executado quando determinadas condições, representadas por expressões lógicas ou relacionais, são ou não satisfeitas. Podem ser de 3 tipos:

o Seleção simples – quando precisamos testar uma certa condição antes de executar uma ação. Se houver mais de um comando a ser executado, estes devem estar num bloco delimitados por início e fim.

se condição então

início

comando 1;

comando 2; //sequência de comandos

comando n;

fim;

fimse;

o Seleção composta – quando tivermos situações em que duas alternativas dependem de uma mesma condição, uma de a condição ser verdadeira e a outra, falsa.

se condição então

início

comando 1;

comando 2; //sequência de comandos

comando n;

fim;

senão

comando ; //ação primitiva

fimse;

o Seleção encadeada – quando, devido à necessidade de processamento, agruparmos várias seleções. Podem ser de dois tipos:

§ Heterogênea – quando não conseguimos identificar um padrão lógico na estrutura.

se condição 1 então

se condição 2 então

comando;

fimse;

senão

se condição 3 então

comando;

senão

se comando 4 então

se comando 5 então

comando; //comando verdade

fimse;

senão

comando; //comando falsidade

fimse;

fimse;

fimse;

§ Homogênea – quando a construção de diversas estruturas seguem um padrão lógico.

se condição 1 então

se condição 2 então

se condição 3 então

se condição 4 então

comando;

fimse;

fimse;

fimse;

fimse;

· A fila é uma estrutura de dados do tipo FIFO (First In First Out) onde todas as inserções de novas entidades são realizadas numa extremidade da lista e todas as remoções são feitas na outra extremidade.

· Repetição é uma estrutura de controle onde determinado trecho de código é repetido, também chamado de laço de repetição. O número de repetições pode ser indeterminado, mas necessariamente finito.

o Repetição com teste no início – consiste em uma estrutura de controle do fluxo de execução que permite repetir diversas vezes um mesmo trecho do algoritmo, porém sempre verificando antes de cada execução se é permitido executar o mesmo trecho.

enquanto condição faça

comando 1;

comando 2;

comando n;

fimenquanto;

o Repetição com teste no final – permite que um bloco ou ação primitiva seja repetido até que uma determinada condição seja verdadeira.

repita

comando 1;

comando 2;

comando n;

até condição;

o Repetição com variável de controle – repete a execução do bloco um número determinado de vezes, pois ela não prevê uma condição e possui limites fixos.

para V de vi até vf passo p faça

comando 1;

comando 2;

comando n;

fimpara;

· Sequência é uma estrutura de controle, também chamada de estrutura seqüencial, que corresponde ao fato de que um conjunto de ações primitivas será executado em uma sequência linear de cima para baixo e da esquerda para direita.

início

comando 1;

comando 2;

comando n;

Fim.

Gab: B

02. (FCC-TRT-GO/2008) O endereço de memória 3510, no sistema decimal, corresponde ao hexadecimal

(A) 5FA.

(B) 15F.

(C) D87.

(D) DB6.

(E) 41D.

Solução: Da base decimal para qualquer outra base, basta dividir o número pela base correspondente para a qual queremos que o número seja convertido. No exemplo do número 3510, podemos convertê-lo para outras bases:

· Binária – Para convertermos este número para a base binária, é só fazermos sucessivas divisões por 2. Quando o quociente de uma divisão atingir um número menor que o divisor, as divisões acabam e o número é lido do fim para o início, usando o último quociente.

1ª divisão: 3510/2 = 1755 – resto: 0

2ª divisão: 1755/2 = 877 – resto: 1

3ª divisão: 877/2 = 438 – resto: 1

4ª divisão: 438/2 = 219 – resto: 0

5ª divisão: 219/2 = 109 – resto: 1

6ª divisão: 109/2 = 54 – resto: 1

7ª divisão: 54/2 = 27 – resto: 0

8ª divisão: 27/2 = 13 – resto: 1

9ª divisão: 13/2 = 6 – resto: 1

10ª divisão: 6/2 = 3 – resto: 0

11ª divisão: 3/2 = 1 – resto: 1

Resultado: 110110110110

· Octal – Usamos o mesmo raciocínio explicado para a base binária. As divisões agora serão por 8.

1ª divisão: 3510/8 = 438 – resto: 6

2ª divisão: 438/8 = 54 – resto: 6

3ª divisão: 54/8 = 6 – resto: 6

Resultado: 6666

· Hexadecimal – As divisões aqui são por 16. Restos a partir de 10 até 15 são substituídos por A até F.

1ª divisão: 3510/16 = 219 – resto: 6

2ª divisão: 219/16 = 13 (D) – resto: 11 (B)

Resultado: DB6

Gab: D

03. (FCC-TRT-GO/2008) Se um programa aponta para um endereço de registrador com deslocamento zero representado pelo hexadecimal de mais baixa ordem B7, seu correspondente binário é

(A) 1101011.

(B) 10110111.

(C) 10110110.

(D) 1111011.

(E) 10100111.

Solução: A solução desta questão é compararmos as tabelas binária e hexadecimal e substituir os números correspondentes. Segundo a tabela abaixo, B7 (hexa) corresponde a 10110111.

Binária	Hexadecimal
0000	0
0001	1
0010	2
0011	3
0100	4
0101	5
0110	6
0111	7
1000	8
1001	9
1010	A
1011	B
1100	C
1101	D
1110	E
1111	F

Gab: B

04. (FCC-TRT-GO/2008) 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.

Solução: No Método cartesiano, deve-se procurar atacar o problema dividindo-o em partes menores, a fim de torná-lo mais simples ou específico e, se necessário, dividi-lo novamente.

O planejamento reverso é o processo muito utilizado na área técnica, que possui a finalidade de determinar o material de construção e a sequência de montagem, partindo-se do produto desejado, desmontando-o até chegar a seus componentes básicos.

Pseudolinguagem é um modo de representar algoritmos que procura empregar uma linguagem que esteja o mais próximo possível de uma linguagem de programação de computadores de alto nível, mas evitando definir regras de construção gramaticais muito rígidas.

O primeiro que entra, primeiro que sai é o conceito de fila, visto na questõa 01.

O primeiro que entra, último que sai é o conceito de pilha, também visto na questão 01.

Gab: A

05. (FCC-TRT-GO/2008) Árvore AVL balanceada em altura significa que, para cada nó da árvore, a diferença entre as alturas das suas subárvores (direita e esquerda) sempre será

(A) menor ou igual a 2.

(B) igual a 0 ou −1.

(C) maior que 1.

(D) igual a 1.

(E) igual a −1, 0 ou 1.

Solução: Uma árvore AVL é dita balanceada quando, para cada nó da árvore, a diferença entre as alturas das suas subárvores (direita e esquerda) não é maior do que um. Caso a árvore não esteja balanceada é necessário seu balanceamento através da rotação simples ou rotação dupla. O balanceamento é requerido para as operações de adição e exclusão de elementos. Para definir o balanceamento é utilizado um fator específico para nós.

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.

Gab: E

06. (FCC-TRT-PB/2005) É uma estrutura de dados do tipo LIFO (last in first out),

(A) fila.

(B) array.

(C) pilha.

(D) árvore.

(E) tabela de hashing.

Solução: De acordo com a solução da questão 01, a resposta é a letra C.

GAB: C

07. (FCC-TRT-PR/2004) A respeito de algoritmos e estrutura de dados, é correto afirmar que:

(A) o percurso em pré-ordem segue recursivamente os seguintes passos, para cada subárvore da árvore binária: 1 − percorrer sua subárvore esquerda em pré-ordem; 2 − percorrer sua subárvore direita em pré-ordem; 3 − visitar a raiz.

(B) pilha é uma estrutura do tipo FIFO (first in – first out).

(C) uma ordem parcial de um conjunto S é uma relação entre objetos de S que satisfaz algumas propriedades; uma destas propriedades é a relação simétrica.

(D) toda árvore binária com n nós possui exatamente n+2 subárvores vazias entre suas subárvores esquerdas e direitas.

(E) Deque é um caso particular de lista em que as inserções e remoções são permitidas apenas nas extremidades.

Solução:

· Para percorrer de forma sistemática por cada um dos nodos de uma árvore no modo pré-ordenado, visita-se primeiro a raiz, depois a subárvore esquerda e por último a subárvore direita. No modo pós-ordenado, visita-se primeiro a subárvore esquerda, depois a direita e por último a raiz.

· Pilha é uma estrutura do tipo LIFO (Último a entrar, primeiro a sair).

· Uma relação de ordem total é definida para pares de elementos de um conjunto S. Ela necessariamente tem que possuir três características:

o Totalidade

o Antissimetria

o Transitividade

Uma relação de ordem parcial (conjunto parcialmente ordenado) possui as seguintes propriedades:

o Antissimetria

o Transitividade

· Toda árvore binária com n nós possui exatamente n+1 subárvores vazias.

· Um deque é um tipo de lista em que as inserções, remoções ou acessos são realizados em qualquer extremo. O deque pode ainda gerar dois casos especiais:

o Fila dupla de entrada restrita

o Fila dupla de saída restrita

GAB: E

08. (CETRO-TRT-SC/2008-adaptada) Uma pilha é uma estrutura de dados do tipo LIFO (Last In First Out), enquanto uma fila é uma estrutura de dados do tipo FIFO (First In First Out); além disso, a operação push() insere valores em uma estrutura, enquanto a operação pop() remove valores de uma estrutura, sempre respeitando o seu tipo. Considere que os seguintes comandos foram realizados e manipularam duas estruturas de dados, uma do tipo pilha e outra do tipo fila: push(A), push(B), push(C), pop(), push(D), pop(), pop(), push(E), push(F). Após essa seqüência de comandos, o conteúdo ordenado da pilha e da fila será, respectivamente,

(A) BEF e BEF.

(B) CEF e AEF.

(C) AEF e DEF.

(D) DEF e CEF.

(E) DEF e AEF.

Solução: Vamos representar sua solução em forma de tabela representando as estruturas citadas.

PILHA

Topo ->	F
	E
	D
	C
	B
Fundo ->	A

FILA

Fim

F

E

D

C

B

A

Início

GAB: C

09. (CETRO-TRT-SC/2008) Em relação à estrutura de dados “Árvores”, seguem as afirmações:

I. “Árvores” são estruturas de dados dinâmicas, em que os dados possuem ordem pré-definida e seus elementos são dispostos de acordo com uma hierarquia.

II. toda “Árvore” possui um nó (nodo) principal, conhecido como raiz, que é representado na sua parte superior.

III. cada nodo de uma “Árvore” dá origem a uma subárvore. O grau de uma “Árvore” é definido de acordo com o número de subárvores daquele nodo.

Sobre as afirmações acima, pode-se concluir que

(A) I e II são corretas.

(B) I, II e III são corretas.

(C) apenas III é correta.

(D) apenas II é correta.

(E) I e III são corretas.

Solução: Árvores são estruturas de dados dinâmicas em que os dados possuem uma ordem predefinida, os elementos são dispostos de acordo com uma hierarquia e existe um nodo principal conhecido como raiz, que é representado na parte superior da árvore. Em uma árvore genérica, não-binária, cada nodo pode ter qualquer quantidade de nodos filho.

Cada nodo de uma árvore dá origem a uma subárvore. O grau de uma árvore é definido de acordo com o número de subárvores daquele nodo, isto é, o número de filhos. O nível mais elevado de uma árvore é conhecido como altura ou profundidade.

GAB: B

10. (FJG-TCM-RJ/2003) Observe a estrutura de dados PILHA, que suporta três operações básicas definidas no Quadro I e a seqüência de operações indicadas no Quadro II.

Considerando-se que a pilha TCM está inicialmente vazia, ao final das operações o elemento que se encontra no topo da pilha é:

A) dólar

B) peso

C) libra

D) real

Solução: A PILHA é uma estrutura do tipo LIFO (último a entrar e primeiro a sair). Sendo assim e de acordo com os quadros acima, temos:

Topo ->	Peso
	Peso
	Libra
	Dólar
Fundo ->	Real

O primeiro elemento a entrar vai para o fundo da pilha e, depois das inserções e remoções, a libra ficou no topo.

GAB: C

11. (FJG-TCM-RJ/2003) Analise o algoritmo em pseudocódigo, em que se observa a passagem de parâmetros por valor e por referência, respectivamente, para as variáveis BETA e ALFA, e responda às questões de números 11 e 12.

Após a execução do algoritmo, os valores para as variáveis DELTA e GAMA são, respectivamente:

A) 2 e 4

B) 2 e 9

C) 7 e 4

D) 7 e 9

Solução: Na passagem de parâmetro por valor, a variável, no caso DELTA não é alterada depois que o procedimento é concluído. Na passagem por referência, a variável, no caso GAMA é alterada para o valor com que a variável ALFA do procedimento termina. Portanto, já podemos concluir que, independentemente do procedimento PROC_TCM, a variável DELTA, no final, terá valor igual a 7. Precisamos fazer uma tabela de variáveis apenas para saber o valor final de GAMA.

DELTA/BETA	GAMA/ALFA	ÔMEGA
7	4	F
2	9	V
1
0

Como GAMA é passado por referência, ela recebe o valor final de ALFA no procedimento que é igual a 9.

GAB: D

12. (FJG-TCM-RJ/2003) A estrutura de controle ENQUANTO ... FAÇA ..., equivalente a REPETIR ... ATÉ QUE ..., está indicada na seguinte alternativa:

Solução: A diferença entre as duas é que a estrutura de controle ENQUANTO...FAÇA pode não executar nenhuma vez enquanto que a estrutura REPETIR...ATÉ QUE deve executar pelo menos uma vez. Assim, entre as letras acima, aquela com estrutura ENQUANTO que executa pelo menos uma vez e que equivale ao código da questão anterior é a letra A.

GAB: A

13. (CONESUL-TRENSURB/2006) Em uma estrutura de dados onde a regra de retirada de um elemento diz que o primeiro a sair deve ser o último que foi armazenado refere-se

a) a uma pilha

b) a um grafo

c) a uma fila.

d) a uma arvore binária.

e) a uma tabela hash

Solução: De acordo com a solução da questão 01, a resposta é a letra A.

GAB: A

14. (CONESUL-TRENSURB/2006) Seja uma matriz MAT [4,4] inicialmente vazia que será preenchida com os seguintes valores do vetor VET[16] inicialmente preenchido com os seguintes valores:

Após a execução do algoritmo abaixo, quais os valores estarão contidos respectivamente, nas células M[1,2] e M[2,1]?

INICIO

L = 0;

PARA k = 4 ATE 1 COM PASSO -1 FAÇA

PARA w = 1 ATE 4 FAÇA

L = L + 1;

MAT[w,k] = VET[L];

FIM w;

FIM k;

FIM

a) 30 e 23.

b) 01 e 30.

c) 01 e 24.

d) 23 e 24.

e) 01 e 23

Solução: Observem que o código começa com a matriz na posição MAT[1,4] = VET[1] = 22. Na continuação do algoritmo, vemos que temos que variar primeiro o w, matendo k contante, até chegarmos a 4 quando saímos do primeiro PARA. Sendo assim, temos MAT[2,4], MAT[3,4] e MAT[4,4]. No PARA mais externo, diminuímos o k de 1 e entramos no PARA do w e repetimos todo o processo até a conclusão dos dois loops. Sendo assim, o k passa a ser 3 e o w vai variar novamente de 1 a 4. Se fizermos toda a sequência, veremos que MAT[1,2] = VET[9] = 01 e MAT [2,1] = VET[14] = 24.

GAB: C

15. (FCC-TRT-CAMP/2009) São algoritmos de classificação por trocas apenas os métodos

a) BublleSort e QuickSort.

b) InsertionSort e MergeSort.

c) SelectionSort InsertionSort.

d) MergeSort e BubbleSort.

e) QuickSort e SelectionSort.

Solução: Existem 4 principais categorias de métodos de classificação:

· Classificação por trocas – Caracteriza-se pela comparação aos pares de chaves, trocando-as de posição caso estejam fora de ordem no par. Principais algoritmos:

o BubbleSort (Bolha)

o QuickSort

o CombSort (Método do pente)

· Classificação por seleção – é um método baseado em se passar sempre o menor valor do vetor para a primeira posição (ou o maior dependendo da ordem requerida), depois o segundo menor valor para a segunda posição, e assim é feito sucessivamente com os n-1 elementos restantes, até os últimos dois elementos. Principais algoritmos:

o SelectionSort

o HeapSort

· Classificação por inserção - Cada elemento a classificar é considerado como um elemento a INSERIR na lista de elementos a classificar até que TODOS os elementos estejam classificados (inseridos), em suas corretas posições. Principais algoritmos:

o InsertionSort

o ShellSort

· Classificação por intercalação – Este método classifica um array dividindo-o pela metade, classificando recursivamente cada metade e depois intercalando as metades classificadas. Caracteriza-se pela utilização do padrão de projeto Divisão e Conquista. Principais algoritmos:

o MergeSort

GAB: A

16. (FCC-TRT-CAMP/2009) 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) árvore binária.

b) lista encadeada.

c) vetor de dispersão.

d) matriz de dispersão.

e) tabela hash.

Solução:

· Árvore binária – é uma estrutura de dados dinâmica em que os dados possuem uma ordem predefinida, os elementos são dispostos de acordo com uma hierarquia e existe um nó (nodo) principal conhecido como raiz, que é representado na parte superior da árvore. Nessa estrutura, cada nodo pode ter, no máximo, 2 nodos filhos, ou seja, o grau máximo de um nodo é dois.

· Lista encadeada – é um conjunto de elementos dispostos em uma dada organização física, não linear, isto é, espalhados pela memória. Os elementos da lista possuem apenas um ponteiro que aponta para o elemento sucessor ou próximo.

· Matriz de dispersão – é uma técnica de projeção geométrica que é utilizada para representação de dados de alta dimensionalidade em uma representação bidimensional. A matriz de dispersão permite a visualização do relacionamento entre os atributos. Para isto, esta visualização projeta os atributos aos pares formando células associadas a dois atributos que são mapeados pelo eixo x (linha horizontal) e eixo y (linha vertical). Para a projeção da visualização da matriz de dispersão são necessárias n(n-1)/2 células para representar uma base de dados com “n” atributos.

· Tabela hash – 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.

GAB: E

17. (ESAF-AFRF/2005) - Analise as seguintes afirmações relacionadas a noções básicas de programação:

I. A idéia básica do algoritmo de ordenação bubble sort é montar uma árvore com os dados a serem ordenados, percorrer esses dados pela última camada denominada folhas e, a cada passagem, comparar cada elemento da folha com o seu sucessor. Se os elementos não estão ordenados deve-se trocá-los de posição.

II. Na orientação a objetos, uma classe é uma abstração de software que pode representar algo real ou virtual. Uma classe é formada por um conjunto de propriedades (variáveis) e procedimentos (métodos).

III. Uma função é dita recursiva quando em seu código existe uma chamada a si própria, podendo utilizar os mesmos parâmetros de entrada (correndo o risco de provocar um ciclo infinito) ou outros.

IV. Uma árvore binária é um conjunto finito de elementos que ou está vazio ou está dividido em 3 subconjuntos: um elemento chamado raiz da árvore e dois subconjuntos, cada um dos quais é, por si só, uma árvore binária, chamadas sub-árvore direita e sub-árvore esquerda.

Indique a opção que contenha todas as afirmações verdadeiras.

a) I e II

b) II e IV

c) II e III

d) I e III

e) III e IV

Solução:

I. Algoritmos de ordenação são algoritmos que colocam os elementos de uma dada sequência em uma certa ordem. Podem ser simples ou sofisticados.

a. Simples

i. Insertion sort – ou ordenação por inserção é um simples algoritmo de ordenação que percorre um vetor de elementos da esquerda para a direita e à medida que avança vai deixando os elementos mais à esquerda ordenados.

ii. Selection sort – ou ordenação por seleção é um algotirmo 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 segundo menos e assim sucessivamente até o final do vetor.

iii. Bubble sort – ou ordenação por flutuação ou por bolha é um algoritmo de ordenação que varre um vetor comparando pares de elementos a partir dos dois primeiros e trocando-os caso o primeiro seja maior do que o segundo. Isto deve ser feito para todos os pares até os dois últimos. Ao final da primeira varredura, o último elemento deve ser o maior de todos. Na segunda varredura, repete os passos para todos os elementos exceto o último. As varreduras seguintes continuam sempre com um elemento a menos até que não haja mais pares a serem comparados. (Assim, o item I é FALSO)

b. Sofisticados

i. Quick sort – é um método de ordenação muito rápido e eficiente. Adota a estratégia dedivisão e conquista. 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.

ii. Merge sort – ou ordenação por mistura é um método de ordenação que adota a estratégia dedivisão e conquista. A idéia deste algoritmo é dividir a sequência original em pares de dados, ordená-las e depois agrupá-las em sequência de 4 elementos e assim por diante até ter toda a sequência dividida em apenas duas partes que devem ser juntas em um único conjunto já classificado.

iii. Heapsort – utiliza uma estratura de dados chamada heap (organizada como árvore binária) para organizar os elementos à medida que os insere na estrutura. Ela pode ser representada como uma árvore ou como um vetor. Para uma ordenação crescente, deve ser construído um heap máximo, em que o valor de todos os nós são menores que os de seus respectivos pais (o maior elemento fica na raiz). Para uma ordenação decrescente, deve ser construído um heap mínimo, em que o valor de todos os nós são maiores que os de seus respectivos pais (o menor elemento fica na raiz).

iv. Shell sort – é um algoritmo baseado em trocas. Ele usa uma variável denominada distância de comparação (h). O valor de h é iniciado com um valor próximo de n/2. A troca é feita entre elementos que estão distanciados h posições e fora de ordem. Após fazer todas as trocas de elementos cuja distância é h, o valor de h deve ser reduzido: h=h/2, h=h/3,... . O algoritmo é repetido até que a distância de comparação h seja igual a um (h=1). Para h=1 (última passada) é executado o algoritmo de inserção.

v. 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 ordem qualquer relacionada com a lexicografia.

vi. Gnome sort – Algoritmo similiar ao Insertion sort com a diferença que o Gnome sort leva um elemento para sua posição correta, com uma seqüencia 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.

vii. Count sort – A ordenação por contagem pressupõe que cada um dos n elementos do vetor de entrada é um inteiro entre 1 e k (k representa o maior inteiro presente no vetor). A idéia básica é determinar, para cada elemento de entrada x, o numero de elementos menores ou iguais a x. Com essa informação é possível determinar exatamente onde o elemento x será inserido.

viii. Bogosort – é um algoritmo probabilístico por natureza. Tenta ordenar uma sequência de elementos de um vetor aleatoriamente. O tempo exato de execução esperado depende do quantos diferentes valores de elementos ocorrem, e quantas vezes cada um deles ocorre.

ix. Cocktail sort – Este método de ordenação funciona como o Bubble Sort, mas de forma bidirecional e também é conhecido como Shaker Sort.

x. 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. Funciona do seguinte modo:

1. Inicialize um vetor de "baldes", inicialmente vazios.

2. Vá para o vetor original, incluindo cada elemento em um balde de forma que os elementos do primeiro balde não-vazio sejam menores que os elementos do segundo não-vazio e assim sucessivamente.

3. Ordene todos os baldes não-vazios

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

II. Uma classe define o comportamento dos objetos através de seus métodos, e quais estados ele é capaz de manter através de seus atributos. (Assim, o item é falso)

Resposta: E

18. (FCC–TRT–CE/2009) O decimal 310 é representado pelo hexadecimal

a) 168.

b) 142.

c) 136.

d) 120.

e) 112.

Solução: Divide-se o número decimal por 16 como mostrado na questão 02.

1ª Divisão: 310/16 = 19 – Resto: 6

2ª Divisão: 19/16 = 1 – Resto: 3

Resultado: 136

Resposta: C

19. (FCC–TRT–CE/2009) Na mais baixa ordem, somando-se o binário 111000 com o hexadecimal 10F, o resultado no sistema decimal será

a) 436.

b) 327.

c) 256.

d) 212.

e) 156.

Solução: Como queremos o resultado no sistema decimal, vamos converter os números da soma para decimal também.

1º Passo: Transforme o Hexadecimal para binário. Consultando a tabela da questão 03, podemos observar que 10F (hexadecimal) = 000100001111.

2º Passo: Transformar os números binários obtidos em decimal. Para a transformação desconsidere os zeros à esquerda antes do primeiro 1. Veja que eles foram riscados porque não precisam entrar na conta. Crie uma tabela e faça a conta como mostrado abaixo.

Número binário	1	0	0	0	0	1	1	1	1
Expoente (Base 2)	2⁸	2⁷	2⁶	2⁵	2⁴	2³	2²	2¹	2º
Multiplicação	1x2⁸	0x2⁷	0x2⁶	0x2⁵	0x2⁴	1x2³	1x2²	1x2¹	1x2º
Resultados	256	0	0	0	0	8	4	2	1
Número binário				1	1	1	0	0	0
Expoente (Base 2)				2⁵	2⁴	2³	2²	2¹	2º
Multiplicação				1x2⁵	1x2⁴	1x2³	0x2²	0x2¹	0x2º
Resultados				32	16	8	0	0	0

Somando-se os resultados de cada número temos:

100001111 = 256 + 8 + 4 + 2 + 1 = 271 (decimal)

111000 = 32 + 16 + 8 = 56 (decimal)

Somando-se os números decimais, temos: 271 + 56 = 327

Resposta: B

20. (FCC–TRT–CE/2009) Os métodos de Knuth-Morris-Pratt (KMP) e de Boyer-Moore (BM) são algoritmos de

a) ordenação de vetores por troca.

b) busca binária.

c) busca em cadeias.

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

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

Solução: Esses métodos 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.

Resposta: C