Uma tabela recebe chaves do tipo string e armazena os dados internamente como um vetor. A função de espalhamento da tabela Hash utiliza o seguinte procedimento para mapear as strings em inteiros: 1 – Mapeamento de caracteres: os três primeiros caracteres são mapeados em inteiros da forma: De a até f: mapeado para 1 De g até n: mapeado para 3 De o até s: mapeado para 5 De t até z: mapeado para 11 2 – Os inteiros associados a cada um dos três primeiros caracteres são multiplicados entre si. 3 – O resto da divisão por 11 é computado, dado que o vetor possui tamanho 11. Dadas as seguintes strings: ULISSES, DANIELLE e LARISSA, aplicando a função de espalhamento apresentada, indique a alternativa correta que apresenta a string e a posição obtida.
As tabelas hash minimizam a complexidade de tempo para as operações dinâmicas como Inserção, Remoção, Busca e Modificação. Admita as seguintes afirmações: A função hash(chave) deve ser determinística. Para uma determinada chave, a função sempre retorna o mesmo valor de hash. Por ser utilizada como uma função de indexação, a função de hash deve sempre retornar um valor de hash dentro dos limites da tabela [0,N], em que N é o tamanho da tabela. O método aproveita a possibilidade de acesso randômico à memória para alcançar uma complexidade média de O(log(n)). Assinalar a alternativa correta:
Um procedimento natural para resolver os problemas de colisões consiste em guardar as chaves sinônimas em listas encadeadas. Existem duas opções: as listas podem se localizar no exterior da tabela ou compartilhar o mesmo espaço da tabela. O encadeamento exterior consiste em manter _____________, uma para cada endereço-base possível. Os _________ correspondentes aos endereços-base serão apenas os principais dessas listas. Um campo para o encadeamento deve ser adicionado a cada nó. A __________ interna consiste nos nós que correspondem a cada endereço de encadeamento possível. Preencha as lacunas escolhendo a alternativa CORRETA:
Para evitar desperdício de memória e a determinação incorreta de uma fila cheia quando na verdade há posições vagas, pode-se deixá-la circular. Para esse fim, qual operação matemática é feita sobre os índices ( back e front ) ao se inserir ou remover os elementos de uma fila?
Quando uma variável do tipo ________ é declarada em C/C++, deve haver um * antes do nome dela. Quando se quer obter o endereço de memória, utiliza-se esse recurso, ele proporciona uma descrição de variáveis pontuais de forma direta. Possui um valor, que indicará onde devemos encontrar a variável de interesse. A alternativa que completa, corretamente, as lacunas é:
A linguagem de programação pode ser definida como uma sequência de códigos e comandos que fornece um resultado escolhido pelo autor. Dessa forma, sobre essa linguagem, analise as afirmativas a seguir. I) É muito importante e só é viável quando se utiliza a linguagem de programação C. II) Para se orientar objetos, é recomendável o Java. III) Existem alguns tipos de linguagem de modelagem, que são, muitas vezes, definidas com baixo nível, um exemplo disso é a Assembly. IV) Quando se usa um Android, recomenda-se utilizar a linguagem Java. V) A linguagem de programação C# foi desenvolvida pela Microsoft. Está correto o que se afirma em:
Pilhas são listas nas quais o acesso somente pode ser feito em uma das extremidades, denominada topo da pilha. Todas as consultas, alterações, inclusões e remoções de nodos podem ser realizadas somente sobre um nodo, que está na extremidade considerada o topo da pilha. EDELWEISS, N.; GALANTE, R. Estruturas de dados . Porto Alegre: Bookman, 2014. 18 v. Topo Fonte: Elaborada pelo autor Com relação às características de Last In, First Out (LIFO) de uma pilha, assinale a alternativa CORRETA.
Filas são ordenamentos de valores em que apenas os dois nós em cada extremidade do ordenamento podem ser acessados. A adição de novos nós é sempre feita no final da lista e as funções de consulta, alteração de dados e exclusão são feitas no início. Com relação às características de First In, First Out (FIFO) de uma fila, assinale a alternativa CORRETA .
A tentativa linear h(x,k) é uma implementação muito simples, em que o endereço-base x é h'(x) (k=0), suponhamos que existe outra chave, x', ocupando o mesmo endereço de h'(x). A ideia da tentativa linear é buscar armazenar um novo nó, no endereço próximo, que consiste em h'(x) + 1 (k=1), se por acaso já estiver ocupado, ele irá tentar em h'(x) + 2 (k=2), e assim sucessivamente. Com base nos aspectos que existem no método de tentativa linear, assinale a alternativa que descreve a função da tentativa linear para a (k+1)-ésima tentativa.
Dada as propriedades de estruturas de dados a seguir: Estrutura 1: estrutura que mapeia a chave de busca diretamente para um endereço de memória (endereço base). Estrutura 2: estrutura linear em que o primeiro elemento a entrar tem que ser o primeiro a sair. Estrutura 3: estrutura linear em que as inserções e remoções ocorrem na mesma posição. Assinale a alternativa que apresenta, em ordem, as estruturas para as quais se referem as definições.
É dada a implementação da função de hash abaixo (incompleta) apresentada na videoaula. Considere que nesta implementação estamos simplesmente garantindo que não colocaremos um registro fora dos limites do vetor (considera a não existência de colisões). Indique qual é alternativa correta para a linha 15 do código a seguir:
A presença de colisões, quando duas chaves k1 e k2 geram h(k1) = h(k2), impede que se faça imediatamente a inserção de um novo item (k,v) diretamente em A[h(k)] no arranjo A. Para resolver essa colisão, devemos:
Seja uma tabela hash implementada como um vetor de tamanho 13, com elementos indexados de 0 a 12. Nesse caso, para obter a posição a partir de uma chave, a função de espalhamento computa o resto da divisão da chave por 13. Indicar a alternativa correta que apresenta a chave (93,2,24) e o índice resultado da função de espalhamento aplicada a essa chave.
Como o teste linear é usado quando há uma colisão em uma tabela de hash ? Existem dois jeitos de lidar com uma colisão presente na tabela hash: separate chaining e open addressing. Diante disso, assinale a alternativa correta que demonstra o que cada um desses métodos faz.
Um método de busca bastante utilizado, conhecido como hash, baseia-se na utilização que mapeia chaves em endereços de memória, de modo que os dados associados a cada chave possam ser rapidamente localizados e lidos. Quando há conflitos de localização, algum algoritmo de separação é adotado. Considere uma tabela hash armazenada em um arquivo no disco rígido. Supondo-se que a mesma possua uma função de hash razoavelmente protegida de conflitos, o número médio de acessos ao disco, necessários para localizar uma chave em um universo de N chaves, é mais próximo de:
Sobre sistemas de bancos de dados disponíveis no mercado: O MySQL é um banco de dados com licença GNU-GPL. O MongoDB é um banco de dados do tipo NoSQL. O Cassandra é um banco de dados baseado em documentos. O Oracle é um banco de dados com licença open-source. O Elasticsearch é um banco de dados apropriado para realizar escala horizontal. De acordo com as afirmações apresentadas, indique a alternativa correta:
Ao projetar Bancos de Dados (BD) relacionais, é possível seguir algumas diretrizes informais que ajudam a nortear os esquemas de relação para que seja possível mensurar a qualidade de um projeto acerca de seu esquema de relação. Tratam-se, na realidade, de heurísticas, isto é, recomendações para que os projetistas de BD possam estruturá-los de uma maneira assertiva, principalmente, para BD Relacionais. Considerando o contexto dado, avalie as seguintes asserções e a relação proposta entre elas. Garantir que a semântica dos atributos seja clara no esquema. PORQUE Reprova a possibilidade de gerar tuplas falsas. A respeito dessas asserções, assinale a alternativa correta.
No contexto de Banco de Dados (BD), existem uma série de conceitos, modelagens, técnicas e heurísticas que norteiam o modo como os dados devem ser captados, organizados, armazenados e consultados. Entre elas, existe uma restrição que é imposta a dois conjuntos de atributos de um BD e, geralmente, essa restrição é estabelecida pelo projetista do banco de dados, de acordo com as regras que valem no mundo real que está sendo modelado, servindo, até mesmo, para a formalizar a avaliação da qualidade de um projeto de banco de dados. Nesse cenário, assinale a alternativa que corresponde ao conceito supracitado.
No contexto de Banco de Dados (BD), a dependência funcional corresponde a uma propriedade semântica dos atributos que a faz ser derivada do conhecimento que o projetista do BD tem do mundo real que está sendo modelado, isto é, a dependência funcional dependerá da leitura e interpretação do projetista sobre os fatos que lhe são apresentados. Assinale a alternativa que indica o principal uso de um dependência funcional.
Considere verdadeiras (V) ou falsas (F) as afirmações a seguir sobre o banco de dados SQL Server: ( ) O fabricante é a Microsoft. ( ) Não suporta SQL. ( ) Funciona apenas com Windows. ( ) Necessário pagar licença comercial de uso, mas disponibiliza uma versão express. ( ) É um banco de dados relacional. A sequência correta de preenchimento dos parênteses, de cima para baixo, é:
Considere verdadeiras (V) ou falsas (F) as afirmações a seguir sobre diretrizes de projeto informais para esquemas de tabelas: ( ) É importante que a projeção de um esquema de tabela seja algo que possa ser explicado com facilidade. ( ) Busque sempre combinar atributos de várias entidades para construir uma única tabela. ( ) Evite informação redundante nas tabelas, de forma que minimize a quantidade de espaço de armazenamento. ( ) Procure sempre evitar esquemas que possam ter valores NULL com frequência. Os valores NULL devem ser aplicados a casos excepcionais. A sequência correta de preenchimento dos parênteses, de cima para baixo, é:
No contexto dos Sistemas Gerenciadores de Bancos de Dados (SGBD), e na estruturação de um Banco de Dados (BD), existem algumas formas de se mensurar a qualidade de um projeto, uma delas pode ser através da verificação de formas normais que ele alcança. Essa escala de mensuração de qualidade pode ser identificada como: primeira forma normal; segunda forma normal; terceira forma normal; e boyce-codd normal form (BCNF), que corresponde a um processo de normalização. Assinale a alternativa que corresponde ao conceito de normalização.
No contexto do Bancos de Dados (BD), é recorrente a presença da técnica de modelagem de dados para que se possa criar estruturas de dados cada vez mais organizadas e voltadas para o domínio de uso desses dados. Por exemplo, existe um modelo de dados que visa representar um banco de dados como uma coleção de relações, sendo que uma relação remete a uma tabela de valores, na qual cada linha representa uma coleção de valores (colunas) relacionados. Assinale a alternativa que corresponde ao modelo supracitado.
No contexto de Bancos de Dados (BD), existem diferentes tipos de técnicas, orientações, modelos e heurísticas que norteiam como deve ser feita a organização e estruturação dos dados. Em específico, no que tange o Modelo de Entidade-Relacionamento Relacional, existe um elemento que visa uma forma de projetar um esquema de como o banco de dados relacional (um projeto lógico) tendo como base o esquema de um projeto conceitual. Nesse cenário, assinale a alternativa que corresponde ao elemento supracitado no enunciado.
No contexto de _____________________, os valores de chave primária não devem ser do tipo __________ em razão de o valor da _________________ ser utilizado na identificação de _____________. Escolha a alternativa que completa, correta e respectivamente, as lacunas.
Em Banco de Dados (BD), um modelo relacional visa representar o BD como se fosse uma coleção de relação. De maneira informal, cada relação é semelhante a uma tabela de valores ou, até certo ponto, a um arquivo de plano de registros, por exemplo. Nesse sentido, tem-se conceitos e termos bastante presentes, tais como tupla, atributo, relação e domínio. Considerando o contexto dado, avalie as seguintes asserções e a relação proposta entre elas. Domínio visa descrever os tipos de valores que aparecem em cada coluna. PORQUE Um domínio é um conjunto de valores atômicos, sendo que atômico significa que cada valor desse domínio é indivisível. Pode-se concluir que:
Em Bancos de Dados (BD), em específico sobre o modelo relacional e as restrições de integridade, é importante mencionar que nesse tipo de BD relacional existem, obviamente, muitas relações, mas para que isso ocorra de maneira equilibrada e controlada, é necessário determinar certas restrições, tal como restrições de implícitas, restrições baseadas em esquemas e restrições baseadas na aplicação. Considerando o contexto dado, avalie as seguintes asserções e a relação proposta entre elas. As restrições baseadas em esquema têm a possibilidade de serem expressas diretamente nos esquemas de modelos de dados, nos quais, geralmente, são especificadas em DDL. PORQUE São expressas e impostas pelos programas (aplicações), pois não podem ser expressas através dos modelos de dados. Pode-se concluir que:
Em restrições de domínio, no contexto de Banco de Dados (BD), existe uma especificidade relacionada à tipagem de dados, na qual tem-se que restringir formatos, tamanhos e tipos dos dados que serão inseridos em cada uma das tuplas da BD. Isso é necessário para que se possa manter um padrão e controle dos dados inseridos no sistema e manutenção dos existentes. Considerando o contexto dado, avalie as seguintes asserções e a relação proposta entre elas. Tratando-se de restrições de domínio, elas visam especificar valores dentro de uma das tuplas, sendo que esse valor existente em cada atributo é um valor indivisível dentro do domínio. PORQUE Os tipos de dados associados aos domínios costumam incluir valores numéricos por padrão para números inteiros e reais, dados numéricos padrão para inteiros (como show integer , integer e long integer ) e os números reais ( float e double ). Pode-se concluir que:
Observe a tabela a seguir: PEDIDO Nro_Pedido Cod_Produto Qtde Valor_Unit 1 1929292 1 230,50 1 7667701 2 499,90 2 9888221 3 56,00 3 7654884 1 619,99 Agora observe o seguinte comando: DELETE FROM PEDIDO WHERE NRO_PEDIDO=1 OR VALOR_UNIT < 100; Analise as informações abaixo. Todos os registros da tabela serão excluídos. Serão excluídos 3 registros da tabela. O comando tem um erro de sintaxe e não será executado. O registro que tem o nro_pedido igual a 2 será excluído. O registro que tem o cod_produto igual a 1929292 não será excluído. De acordo com as afirmações apresentadas, indique qual alternativa é a correta:
