Exame - Gabarito - Estrutura de Dados II

Prévia do material em texto

<p>GABARITO</p><p>Protocolo: 892771</p><p>Página 1 - 30/06/2024 às 08:53</p><p>Exame</p><p>Data de aplicação: 29/06/2024</p><p>Curso: Engenharia de Software</p><p>Disciplina: Estrutura de Dados II</p><p>Ano: 20241 / Semestre: 4</p><p>RGM: 123.1513 / Aluno: RHUAN PABLO DA SILVA</p><p>PROVA 01</p><p>Questão 1</p><p>Um dos exemplos de estrutura de dados é a lista encadeada simples. Com relação a esse tipo de lista, é correto</p><p>afirmar:</p><p>a) Possui a característica de que o último elemento da lista possui um ponteiro para o primeiro elemento da</p><p>lista.</p><p>b) É necessário definir o seu tamanho no momento da sua criação, pois se trata de uma estrutura de dados</p><p>estática.</p><p>c) Quando essa estrutura é utilizada, os elementos da lista sempre estarão armazenados sequencialmente na</p><p>memória física.</p><p>d) Na inserção de um novo elemento, é necessário realizar a atualização dos ponteiros dos elementos</p><p>envolvidos, não sendo necessário realizar o deslocamento físico dos elementos. (correta)</p><p>e) Na recuperação de qualquer elemento da lista, não é necessário percorrer os outros elementos. Dessa forma,</p><p>o elemento buscado é acessado diretamente na posição onde se encontra.</p><p>Questão 2</p><p>Sobre listas encadeadas, é INCORRETO afirmar que:</p><p>a) os dados são armazenados dinamicamente.</p><p>b) são acessadas pelo primeiro nó da lista.</p><p>c) o final da lista faz uma referência para nulo.</p><p>d) pilhas e filas podem ser implementadas como listas encadeadas.</p><p>e) possuem tamanho fixo. (correta)</p><p>Questão 3</p><p>Suponha que temos números entre 1 e 1000 em uma árvore de pesquisa binária e queremos procurar pelo</p><p>número 363. Quais das sequências a seguir não poderia ser uma sequência de nós examinados?</p><p>a) 2, 252, 401, 398, 330, 344, 397, 363.</p><p>b) 994, 220, 911, 244, 798, 258, 362, 363.</p><p>c) 925, 202, 911, 240, 912, 245, 363. (correta)</p><p>d) 2, 399, 387, 219, 266, 382, 381, 278, 363.</p><p>e) 935, 278, 347, 621, 299, 392, 358, 363.</p><p>Questão 4</p><p>Uma árvore de busca binária cheia tem, no 5º nível, uma quantidade de nós igual a:</p><p>a) 31 (correta)</p><p>b) 32</p><p>c) 64</p><p>d) 15</p><p>GABARITO</p><p>Protocolo: 892771</p><p>Página 2 - 30/06/2024 às 08:53</p><p>e) 16</p><p>Questão 5</p><p>O algoritmo de Huffman, comumente utilizado em procedimentos para compressão de dados, baseia-se na</p><p>utilização de códigos de tamanho:</p><p>a) fixo, que dependem da probabilidade de ocorrência de cada possível símbolo de entrada.</p><p>b) variável, que dependem da probabilidade de ocorrência de cada possível símbolo de entrada. (correta)</p><p>c) fixo, que estabelecem uma espécie de índice, que é associado a cada possível símbolo de entrada.</p><p>d) variável, que dependem da ordenação lógica de todos os possíveis símbolos de entrada.</p><p>e) fixo, que são importados de uma biblioteca padrão previamente estabelecida para cada tipo de símbolo.</p><p>Questão 6</p><p>Uma certa tabela de dispersão (hash) em um programa de computador utiliza a função de espalhamento h(k) =</p><p>k mod m, em que k é a chave e m é o tamanho de um vetor de listas ligadas indexado por h(k). Para m = 5013,</p><p>o índice obtido para k = 10034 é:</p><p>a) 2.</p><p>b) 8. (correta)</p><p>c) 5013.</p><p>d) 5021.</p><p>e) 15047.</p><p>Questão 7</p><p>A altura de um nó em uma árvore binária é a distância entre o nó e o seu descendente mais afastado. A altura</p><p>de uma árvore binária é a altura da raiz da árvore. Se a árvore possui somente o nó raiz, então sua altura é 0</p><p>(zero). Dentre as árvores binárias que possuem sete nós, a maior altura de árvore possível é:</p><p>a) 4</p><p>b) 5</p><p>c) 6 (correta)</p><p>d) 7</p><p>e) 8</p><p>Questão 8</p><p>Em uma árvore de busca binária do tipo AVL, as alturas das duas sub-árvores de um nó qualquer diferem em no</p><p>máximo 1. A construção de uma árvore desse tipo, inicialmente vazia, por meio da inserção sucessiva de nós,</p><p>utiliza uma certa operação para manter o balanceamento desejado quando necessário. Essa operação é:</p><p>a) empilhamento.</p><p>b) desempilhamento.</p><p>c) concatenação.</p><p>d) rotação. (correta)</p><p>e) poda.</p><p>Questão 9</p><p>A busca binária é conhecida também como busca logarítmica. Sobre a busca binária, assinale a alternativa</p><p>INCORRETA.</p><p>a) Para um conjunto de 15 elementos, ocorreria, no mínimo, 1 comparação e, no máximo, 4 comparações.</p><p>b) Quando comparada com a busca sequencial, a busca binária, há uma redução logarítmica dos elementos a</p><p>serem pesquisados.</p><p>c) Em uma sequência ordenada de forma crescente, caso o elemento procurado seja menor que o elemento do</p><p>GABARITO</p><p>Protocolo: 892771</p><p>Página 3 - 30/06/2024 às 08:53</p><p>meio, continua-se a busca com o subconjunto da direita. Em caso contrário, com o subconjunto da esquerda.</p><p>(correta)</p><p>d) Considerando uma sequência qualquer, deve-se dividir o conjunto ao meio e verificar se o elemento</p><p>procurado é igual ao elemento central.</p><p>e) Se o elemento procurado estiver entre os últimos ou não estiver no conjunto, a busca linear poderá ser mais</p><p>lenta do que a busca binária.</p><p>Questão 10</p><p>Uma estrutura de dados onde cada nó mantém uma informação adicional, chamada fator de balanceamento,</p><p>que indica a diferença de altura entre as subárvores esquerda e direita, é conhecida por árvore:</p><p>a) de busca binária.</p><p>b) ordenada.</p><p>c) AVL. (correta)</p><p>d) binária.</p><p>e) hiberbólica.</p><p>Questão 11</p><p>Uma lista ligada é uma estrutura que corresponde a uma sequência lógica de entradas ou nós. Cada nó</p><p>armazena a localização do próximo elemento na sequência, ou seja, de seu nó sucessor. Nessa estrutura,</p><p>a) para estabelecer a ligação entre um nó já pertencente a uma lista e um novo nó, basta fazer com que o novo</p><p>nó referencie no, campo next, o nó que anteriormente era referenciado pelo nó original, desde que esse campo</p><p>não tenha o valor nulo.</p><p>b) a existência de um ponteiro apontando para o 1º elemento e outro para o fim da lista permite que a inserção</p><p>ou deleção de dados de um nó que esteja no meio da lista seja rapidamente executada.</p><p>c) enquanto a entrada que determina o topo da lista é mantida em um nó descritor dessa lista, a entrada que</p><p>marca o fim da lista é mantida fora do descritor.</p><p>d) o armazenamento de uma lista não requer uma área contígua de memória. Como listas são estruturas</p><p>dinâmicas, normalmente são definidos procedimentos que permitem criar e remover nós na memória. (correta)</p><p>e) o armazenamento de uma lista requer uma área contígua de memória para permitir a otimização no</p><p>processamento de criação e remoção de nós da lista.</p><p>Questão 12</p><p>Seja T uma árvore balanceada do tipo AVL vazia. Supondo que os elementos 5, 10, 12, 8, 7, 11 e 13 sejam</p><p>inseridos nessa ordem em T, a sequência que corresponde a um percurso de T em pré-ordem é:</p><p>a) 10, 8, 5, 7, 12, 11 e 13.</p><p>b) 5, 7, 8, 10, 11, 12 e 13.</p><p>c) 5, 8, 7, 11, 13, 12 e 10.</p><p>d) 5, 10, 12, 8, 7, 11 e 13.</p><p>e) 10, 7, 5, 8, 12, 11 e 13. (correta)</p><p>Questão 13</p><p>Seja T uma árvore balanceada do tipo AVL vazia. Supondo que os elementos 5, 10, 12, 8, 7, 11 e 13 sejam</p><p>inseridos nessa ordem em T, a sequência que corresponde a um percurso de T em pós-ordem é:</p><p>a) 10, 8, 5, 7, 12, 11 e 13.</p><p>b) 10, 7, 5, 8, 12, 11 e 13.</p><p>c) 5, 7, 8, 10, 11, 12 e 13.</p><p>d) 5, 8, 7, 11, 13, 12 e 10. (correta)</p><p>e) 5, 10, 12, 8, 7, 11 e 13.</p><p>GABARITO</p><p>Protocolo: 892771</p><p>Página 4 - 30/06/2024 às 08:53</p><p>Questão 14</p><p>Considere uma tabela de espalhamento (tabelas hash) de comprimento igual a 11, na qual a técnica de</p><p>resolução de colisões utilizada é a de encadeamento. Nessa tabela, as posições são numeradas (indexadas)</p><p>com os valores 0, 1, 2, ..., 10, o mapeamento de chaves para posições usa a função hash definida por h(k) = k</p><p>mod 11, onde k é o valor da chave, e mod é o operador de módulo, e os números 1, 5, 18, 20, 4, 12, 10, 34, 15,</p><p>28 e 17 foram as chaves inseridas, nessa ordem, nessa tabela de espalhamento que estava inicialmente vazia.</p><p>Qual a quantidade de posições em que houve colisão durante as inserções das chaves?</p><p>a) 0</p><p>b) 1</p><p>c) 2</p><p>d) 3 (correta)</p><p>e) 4</p><p>Questão 15</p><p>Uma estrutura de dados que possui dois campos: um ponteiro e campo de informação denomina-se:</p><p>a) lista encadeada dupla.</p><p>b) lista encadeada simples. (correta)</p><p>c) pilha.</p><p>d) árvore binária.</p><p>e) vetor.</p><p>Questão 16</p><p>A estrutura de dados que consiste no armazenamento de cada elemento em um endereço calculado a partir da</p><p>aplicação de uma função sobre a chave de busca denomina-se:</p><p>a) lista encadeada.</p><p>b) tabela hash. (correta)</p><p>c) árvore AVL.</p><p>d) árvore B.</p><p>e) árvore binária.</p><p>Questão 17</p><p>Considere as definições a seguir.</p><p>I. O nível do nó raiz de uma árvore é 1.</p><p>II. O nível de qualquer nó subsequente é igual ao nível do seu nó pai mais 1.</p><p>III. A profundidade de uma árvore é igual ao maior nível encontrado dentre todos os seus nós.</p><p>Partindo-se das premissas acima, a menor e a maior quantidade de nós, respectivamente, que poderiam existir</p><p>em uma árvore binária de profundidade 3 são</p><p>a) 3 e 15</p><p>b) 3 e 7 (correta)</p><p>c) 3 e 16</p><p>d) 4 e 7</p><p>e) 5 e 16</p><p>Questão 18</p><p>O caminhamento com percurso pós-ordem em uma árvore binária resultou na sequência “A X K D C J B”, em</p><p>que cada caractere refere-se a um nó visitado. Nesse caso, o nó raiz refere-se ao caractere:</p><p>a) A</p><p>GABARITO</p><p>Protocolo: 892771</p><p>Página 5 - 30/06/2024 às 08:53</p><p>b) C</p><p>c) B (correta)</p><p>d) X</p><p>e) D</p><p>Questão 19</p><p>Considere uma estrutura de dados T como sendo uma árvore binária do tipo AVL. Como característica, essa</p><p>estrutura de dados é uma árvore binária:</p><p>a) balanceada, em que, para qualquer nó de T, as alturas de suas duas subárvores (esquerda e direita) diferem</p><p>de até uma unidade. (correta)</p><p>b) balanceada, em que, para qualquer nó de T, as alturas de suas duas subárvores (esquerda e direita) são</p><p>sempre idênticas.</p><p>c) não balanceada, em que, para qualquer nó de T, as alturas de suas duas subárvores (esquerda e direita)</p><p>diferem de até uma unidade.</p><p>d) não balanceada, em que, para qualquer nó de T, as alturas de suas duas subárvores (esquerda e direita) são</p><p>sempre idênticas.</p><p>e) não balanceada, em que, para qualquer nó de T, as alturas de suas duas subárvores (esquerda e direita)</p><p>diferem exatamente de uma unidade.</p><p>Questão 20</p><p>Em uma árvore de busca binária, qual é o percurso que apresenta os nós em ordem crescente?</p><p>a) Pós-ordem.</p><p>b) Pré-ordem.</p><p>c) Recursivo.</p><p>d) In-ordem. (correta)</p><p>e) Iterativo.</p>