Estrutura de dados

UNICEUB CURSO SUPERIOR DE CIÊNCIA DA COMPUTAÇÃO
Disciplina: ESTRUTURAS DE DADOS LISTA 2A Prof: Carlo Kleber da Silva Rodrigues

Conceito: ______________ Duração: 120 minutos

Aluno:___________________________________Nº matrícula:____________ ARRAYS SEÇÃO I: ESCOLHA 03 (TRÊS) DENTRE OS TEMAS ELENCADOS A SEGUIR E ESCREVA UMA REDAÇÃO DE, NO MÍNIMO, 15 (QUINZE) LINHAS. UTILIZE A ESTRUTURA: INTRODUÇÃO, DESENVOLVIMENTO E CONCLUSÃO. a) b) c) d) e) Arrays Arrays ordenados versus não ordenados Algoritmos de busca em arrays Algoritmos de inserção em arrays Algoritmos de remoção em arrays

SEÇÃO II - PARA CADA PARÁGRAFO ABAIXO, SE FOR VERDADEIRO: ESCREVA V ENTRE OS PARÊNTESES; SE FOR FALSO: ESCREVA F ENTRE OS PARÊNTESES E JUSTIFIQUE SUA RESPOSTA, CORRIGINDO O PARÁGRAFO. a. ( ) Em um array, cada dado é identificado por um índice. Dado um índice i é possível computar o endereço de memória correspondente em tempo constante. Se o array é alocado a partir do endereço A0 e cada dado ocupa k posições, então o i-ésimo elemento está no endereço Ai = A0 + i.k b. ( ) Um vetor pode ser visto como um array de uma dimensão. Já as matrizes são construídas analogamente como vetores de vetores ou, ainda, podem ser vistas como arrays de múltiplas dimensões. c. ( ) Sobre o algoritmo de busca em array com sentinela, é correto afirmar que: a) usa-se uma posição a mais no final do array (posição A[n]) que é carregada com uma cópia do dado sendo buscado (dado v) e b) como é garantido que v será encontrado, não é preciso se precaver contra o acesso de uma posição i não existente.

d. ( ) É correto afirmar que a complexidade de pior caso do algoritmo para busca seqüencial (com e sem sentinela) é obviamente O(n), embora a busca com sentinela seja mais rápida.

e. ( ) Considerando-se a busca binária em arrays, é coreto afirmar que o pior caso ocorre quando o elemento procurado é o último a ser encontrado, ou mesmo quando não é encontrado, isto é, a busca prossegue até o array se resumir a um