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

Um grafo consiste num conjunto de nós (ou vértices) e num conjunto de arcos (ou arestas). É correto afirmar que o grau de um nó é

• A.

  o número de arcos incidentes nesse nó.

• B.

  um número associado ao arco, também chamado de peso.

• C.

  a distância entre este nó e um outro nó qualquer do grafo.

• D.

  a posição deste nó em relação ao nó raiz do grafo.

• E.

  o número de pares ordenados que formam o arco.

A instrução MOV CX, DX utiliza o modo de endereçamento:

• A.

  por registrador.

• B.

  imediato.

• C.

  indireto.

• D.

  indexado.

• E.

  direto.

Acerca de estruturas de informação, assinale a opção correta.

• A.

  Em uma árvore de expressão, os nodos terminais armazenam operadores aritméticos e os nodos nãoterminais armazenam valores.

• B.

  Uma splay tree é uma estrutura de pesquisa balanceada que usa regras explícitas para forçar seu balanceamento. A operação de espalhamento é realizada no nodo mais alto encontrado durante uma inserção, uma deleção ou uma pesquisa.

• C.

  Em árvores parcialmente ordenadas, as chaves dos nós de nível N+1 são necessariamente maiores que as chaves de nível N.

• D.

  Um nó com grau maior que zero indica que o nó possui, pelo menos, um filho.

• E.

  A ordem de execução das operações para percorrer as subárvores da esquerda e da direita e para visitar o nó independe do tipo de caminhamento, seja ele prefixado, central ou pós-fixado.

Acerca de tipos básicos de estruturas de dados, assinale a opção correta.

• A.

  Uma estrutura do tipo pilha, também conhecida como stack, permite que as operações sejam realizadas em seu topo a partir do primeiro elemento inserido por meio de acesso FIFO (first in first out).

• B.

  Os grafos se assemelham às filas em termos de estrutura, mas, enquanto nas filas as operações são realizadas no topo, nos grafos elas podem ser realizadas tanto no início quanto no fim da estrutura.

• C.

  Nos grafos, devido à sua estrutura, não há operações possíveis para a determinação de vértices adjacentes, somente os vértices que estão no início (topo) e no fim (base) podem ser determinados.

• D.

  Nas estruturas do tipo árvores, as operações push( ) e pop( ) permitem retirar e inserir nós, respectivamente.

• E.

  Árvores são grafos dirigidos mais específicos que os acíclicos, em que existe um nó raiz a partir do qual os demais vértices podem ser acessados e onde cada vértice, exceto o raiz, possui apenas um nó antecessor.

No que se refere a estruturas de dados é INCORRETO afirmar:

• A.

  Numa fila dupla, os elementos podem ser inseridos e removidos de qualquer um dos extremos da fila.

• B.

  Em qualquer situação é possível usar uma única fila dupla para representar duas filas simples.

• C.

  A implementação de uma fila dupla normalmente é mais eficiente com uma lista duplamente encadeada que com uma encadeada simples.

• D.

  Pela definição de fila, se os elementos são inseridos por um extremo da lista linear, eles só podem ser removidos pelo outro.

• E.

  Numa lista singularmente encadeada, para acessar o último nodo é necessário partir do primeiro e ir seguindo os campos de ligação até chegar ao final da lista.

Assinale a opção que apresenta uma estrutura de dados embasada no princípio last in, first out (LIFO) — último a entrar, primeiro a sair —, na qual, conforme a inserção, os dados inseridos primeiramente na estrutura são os últimos a serem removidos.

• A.

  pilhas

• B.

  árvores

• C.

  vetores

• D.

  listas

• E.

  filas

Sobre pilhas é correto afirmar:

• A.

  Uma lista LIFO (Last-In/First-Out) é uma estrutura estática, ou seja, é uma coleção que não pode aumentar e diminuir durante sua existência.

• B.

  Os elementos na pilha são sempre removidos na mesma ordem em que foram inseridos.

• C.

  Uma pilha suporta apenas duas operações básicas, tradicionalmente denominadas push (insere um novo elemento no topo da pilha) e pop (remove um elemento do topo da pilha).

• D.

  Cada vez que um novo elemento deve ser inserido na pilha, ele é colocado no seu topo e, em qualquer momento, apenas aquele posicionado no topo da pilha pode ser removido.

• E.

  Sendo P uma pilha e x um elemento qualquer, a operação Push(P,x) diminui o tamanho da pilha P, removendo o elemento x do seu topo.

Com relação a árvores binárias é INCORRETO afirmar:

• A.

  Uma árvore binária é uma coleção finita de n>0 nodos que não pode ser nula.

• B.

  Uma árvore binária, cuja raiz armazena o elemento R, é denominada árvore de busca binária se todo elemento armazenado na subárvore esquerda é menor que R, nenhum elemento armazenado na subárvore direita é menor que R e as subárvores esquerda e direita também são árvores de busca binária.

• C.

  É um caso especial de árvore em que nenhum nodo tem grau superior a 2, isto é, nenhum nodo tem mais que dois filhos.

• D.

  Existe um nodo especial denominado raiz e os demais nodos são particionados em T1 e T2 estruturas disjuntas de árvores binárias. T1 é denominado subárvore esquerda e T2 subárvore direita da raiz.

• E.

  É uma árvore que pode ser nula.

As pilhas e as filas são estruturas de dados essenciais para os sistemas computacionais. É correto afirmar que

• A.

  a fila é conhecida como lista LIFO − Last In First Out.

• B.

  a política de atendimento aos processos por um único processador, implementada por fila circular, seria adequada para controlar a fila de arquivos a serem impressos em uma impressora.

• C.

  a pilha é conhecida como lista FIFO − First In First Out.

• D.

  uma política de acesso dos processos ao processador por tempo compartilhado é implementada por uma pilha.

• E.

  a pilha pode ser utilizada para armazenar informações sobre as sub-rotinas (funções) ativas em um programa de computador em execução.

Considere a estrutura de dados Árvore Binária de Busca (ABB). Se inserirmos numa ABB os nós:

60, 10, 20, 80, 15, 75, 12 e 77,

nessa ordem, a altura da árvore e o nível do nó 15, respectivamente, serão

• A.

  5 e 5

• B.

  5 e 4

• C.

  6 e 4

• D.

  6 e 3

• E.

  7 e 4