Aula 02

Question 1

Qual a diferença de dados Homogêneos e Heterogêneos?

Answer 1

Os primeiros são aqueles que possuem só um tipo básico de dados (Ex: Inteiros); os segundos são aqueles que possuem mais de um tipo básico de dados (Ex: Inteiros + Caracteres).

Question 2

Qual a diferença entre Estruturas Lineares e Estruturas Não-
Lineares

Answer 2

As Estruturas Lineares são aquelas em que cada elemento pode ter um único predecessor (exceto o primeiro elemento) e um único sucessor (exceto o último elemento). Como exemplo, podemos citar Listas, Pilhas, Filas, Arranjos, entre outros.
Já as Estruturas Não-Lineares são aquelas em que cada elemento pode ter mais de um predecessor e/ou mais de um sucessor. Como exemplo, podemos citar Árvores, Grafos e Tabelas de Dispersão.

Question 3

O que são Tipos Abstratos de Dados?

Answer 3

são simplesmente um modelo para um certo tipo de estrutura de dados. Como assim, professor? Quando eu falo em pilha, eu estou falando de um tipo abstrato de dados que tem duas operações com comportamentos bem definidos e conhecidos: push (para inserir elementos na pilha); e pop (para retirar elementos da pilha)

Question 4

Em geral, um Tipo Abstrato de Dados é especificado por meio de uma especificação algébrica que, em geral, contém três partes: Especificação Sintática, Semântica e de Restrições. Explique-as

Answer 4

A Especificação Sintática define o nome do tipo, suas operações e o tipo dos argumentos das operações, definindo a assinatura do TAD. A Especificação Semântica descreve propriedades e efeitos das operações de forma independente de uma implementação específica. E a Especificação de Restrições estabelece as condições que devem ser satisfeitas antes e depois da aplicação das operações.

Question 5

Uma lista encadeada linear trata-se por uma sequência encadeada de elementos chamados nós, que contem dois campos, quais são e para que servem?

Answer 5

Campo de informação: armazena o real elemento da lista
Campo de endereço: contém o endereço do próximo nó da lista.

Question 6

Qual a diferença da Lista Encadeada Linear para a Lista Circular (ou Fechada)?

Answer 6

Na lista Circular o campo próximo no último nó contem um ponteiro de volta para o primeiro nó, em vez de um ponteiro nulo como na Encadeada Linear

Question 7

Como o nome da lista que Cada nó desse tipo de lista contém dois ponteiros, um para seu predecessor e outro para seu sucessor?

Answer 7

lista duplamente ligada

Question 8

Quais as cinco operações básicas sobre uma lista encadeada?

Answer 8

Criação, Busca, Inclusão, Remoção e Destruição

Question 9

Qual a diferença entre as operações de Remoção e Destruição em uma lista encadeada?

Answer 9

Remoção, em que se elimina um elemento da lista; e, por fim, Destruição, em que se destrói a lista junto com todos os seus nós.

Question 10

Qual a diferença entre fragmentação Interna e Externa?

Answer 10

Interna sobra espaço entre um arquivo e outro, externa sobre espaço após um bloco de dados contíguo.

Question 11

O conjunto ordenado Pilha, também chamado de Lista LIFO possui 3 operações básicas, quais são e o que fazem?

Answer 11

push(que insere um novo elemento no topo da pilha).
pop (que remove um elemento do topo da pilha.
top (também conhecido como check, acessa e consulta o elemento do topo da pilha).

Question 12

Pilhas podem ser implementadas de duas formas, como?

Answer 12

Vetores (Pilha Sequencial - Alocação Estática de Memória) ou
Listas (Pilha Encadeada - Alocação Dinâmica de Memória).

Question 13

Quais as operações básicas de uma fila também conhecida como Lista FIFO?

Answer 13

As operações básicas são Enqueue
(Enfileirar) e Dequeue (Desenfileirar).

Question 14

Qual o conceido de filas duplamente encadeadas, também conhecidas como Deque(Double Ended Queue)?

Answer 14

São as filas que permitem a eliminação e inserção de itens em ambas as extremidades.

Question 15

Na estrutura de dados em árvore qual o conceito de grau?

Answer 15

O Grau informa a quantidade de filhos de um determinado nó

Question 16

Qual o conceito de árvore binária? E da Estritamente Binária?

Answer 16

É uma estrutura de dados hierárquica em que todos os nós têm grau 0, 1 ou 2. Já uma Árvore Estritamente Binária é aquela em que todos os nós têm grau 0 ou 2.

Question 17

Como se calcula os nós de uma árvore binária completa a partir de sua altura ou nível?

Answer 17

Uma árvore binária completa de altura h e nível n contém (2^h -1) ou (2^n+1 -1) nós. e usa-se (2^n), para calcular a quantidade de nós em determinado nível.

Question 18

Qual a definição de uma árvore AVL?

Answer 18

É uma árvore binária, em que em qualque nó, a diferença da altura da subárvore da esquerda pela altura da subárvore da direita não pode ser maior que 1.

Question 19

qual a complexidade logarítimica da árvore binária de busca e da árvore B/AVL? Nos algoritmos de Espaço, Busca, Inserção e Remoção?

Answer 19

Árvore Binaria de Busca
Algoritmo | Caso Médio | Pior caso
Espaço O(n) O(n)
Busca O(log n) O(n)
Inserção O(log n) O(n)
Remoção O(log n) O(n)

Árvore B/AVL
Algoritmo | Caso Médio | Pior caso
Espaço O(n) O(n)
Busca O(log n) O(log n)
Inserção O(log n) O(log n)
Remoção O(log n) O(log n)

Question 20

O que são Bitmaps?
pag 37

Answer 20

Mapas de Bits, uma estrutura de indexação que facilita o acesso a informações em banco de dados relacionais.

O bitmap é uma tabela onde as linhas são os possíveis valores da coluna selecionada para criar o índice e as colunas são os números da tuplas (ROWID). Para cada linha do bitmap, serão preenchidos os valores 0 e 1 caso o valor da referida tupla da tabela ser ou não verdadeiro.