Questões de Ciência da Computação do ano 2004

Com relação a conceitos de estruturas de dados, julgue os itens a seguir.

Uma pilha é uma estrutura ordenada e homogênea, na qual é possível empilhar ou desempilhar elementos em uma única posição, que é o topo da pilha, seguindo uma política do tipo FIFO (first in, first out).

• C. Certo
• E. Errado

Com relação a conceitos de estruturas de dados, julgue os itens a seguir.

Um dos problemas da implementação dinâmica de listas mediante enlaces simples é que, em determinadas circunstâncias, torna-se necessário percorrer a lista desde o princípio para poder acessar um elemento em posição anterior ao último elemento acessado. Além do mais, somente é possível percorrer esse tipo de lista em uma única direção. Para solucionar ambos os problemas, pode-se utilizar uma lista duplamente enlaçada, em que cada nó aponta tanto para o nó posterior quanto para o nó anterior.

• C. Certo
• E. Errado

Com relação a conceitos de estruturas de dados, julgue os itens a seguir.

Uma fila é um conjunto ordenado de elementos homogêneos, no qual os elementos são eliminados a partir de um dos extremos e adicionados pelo outro extremo.

• C. Certo
• E. Errado

Acerca de conceitos de estruturas de dados, julgue os seguintes itens.

A estrutura linear ‘deque’ permite a inserção e a retirada de elementos em ambas as extremidades, não seguindo, portanto, os regimes LIFO e FIFO.

• C. Certo
• E. Errado

Acerca de conceitos de estruturas de dados, julgue os seguintes itens.

As pilhas sofrem inserções e retiradas no seu topo, enquanto as filas exigem retirada no começo e a inserção no término da fila.

• C. Certo
• E. Errado

Acerca de conceitos de estruturas de dados, julgue os seguintes itens.

A alocação encadeada não constitui, na maioria dos casos, uma maneira conveniente para representar árvores, devido às dificuldades que ela oferece para manipulações da estrutura, como inserção, remoção e localização.

• C. Certo
• E. Errado

Acerca de conceitos de estruturas de dados, julgue os seguintes itens.

A pesquisa binária é um método que pode ser aplicado a tabelas ordenadas, armazenadas em dispositivos de acesso direto. O passo inicial da pesquisa consiste na comparação do argumento de pesquisa, arg, com a chave da entrada localizada no meio da tabela.

• C. Certo
• E. Errado

No problema das torres de Hanói, encontramos 3 colunas de discos que funcionam tais quais pilhas (estruturas de dados). Adicionalmente, neste problema, nenhum disco pode estar acima de um outro de menor tamanho.

Obedecendo-se à política da estrutura de dados acima, assinale a alternativa que indica a quantidade de operações (push e pop) que deveriam ser realizadas para mover um número arbitrário N de discos de uma coluna para outra.

• A.

  2^N

• B.

  2^N -1

• C.

  2^N + 1

• D.

  2^{N -1}

• E.

  2^{N + 1}

Sobre o tempo de inserção, atualização e remoção em estruturas de dados, assinale a alternativa correta.

• A.

  O tempo de atualização de índice em uma lista ligada é maior que em um array.

• B.

  Filas implementam estruturas de dados com políticas LIFO.

• C.

  A ordem de busca em uma árvore AVL balanceada é de O(log n).

• D.

  A busca em profundidade se diferencia da busca em largura, por visitar todos os vértices adjacentes primeiro.

• E.

  O número máximo de nós em um nível i de uma árvore binária é 2ⁱ –1.

O número máximo de arcos bidirecionais distintos (com o vértice de origem e de destino diferentes), em um grafo com N vértices, é:

• A.

  N²

• B.

  2^{N -1}

• C.

  2^{N -1} -1

• D.

  N (N –1) /2

• E.

  N (N –1)