Questões de Concurso Sobre algoritmos e estrutura de dados

Analise as seguintes afirmações relacionadas a conceitos básicos de estruturas de dados.

I. Em uma árvore genérica, não binária, cada nó pode ter qualquer quantidade de nós filhos.

II. Em uma árvore binária de pesquisa, a busca é feita de tal forma que se o dado procurado está na raiz a pesquisa será encerrada. Caso contrário, a busca continua e deve ser feita em apenas uma das duas sub-árvores.

III. Uma árvore binária é considerada balanceada quando, para cada nó, a altura das duas sub-árvores diferem, no máximo, da somatória da quantidade de nós existentes nos níveis pares, dividido pela quantidade de níveis considerados.

IV. Um circuito em um grafo é um caminho único que tem origem no primeiro nó e se encerra no último nó.

Indique a opção que contenha todas as afirmações verdadeiras.

Analise as seguintes afirmações relativas a estruturas de dados:

I. Uma árvore binária qualquer de altura 3 tem no máximo 8 folhas.

II. Ao se transformar uma árvore genérica, formada apenas pela raiz e seus quatro filhos, em uma árvore binária, a árvore resultante terá apenas uma folha.

III. A única condição para uma árvore binária de pesquisa ser considerada balanceada é que, para cada nó, a altura da sub-árvore da esquerda seja igual à altura da sub-árvore da direita.

IV. Uma árvore binária de pesquisa balanceada deve ter o número de folhas igual ao número de nós.

Estão corretos os itens:

Se na linha "leia MAT[1, 1]...MAT[3, 4]" forem fornecidos os valores da planilha abaixo,

qual será o valor da variável "T" na linha "escreva T"?

Os registros em uma lista, duplamente encadeada com 20 elementos possuem cada um três campos:

próximo: um ponteiro para o próximo elemento da lista;
valor: informação armazenada pelo elemento;
anterior: um ponteiro para o elemento anterior da lista.

Sendo "Z" o décimo elemento desta lista e "X" e "Y" dois outros elementos que não pertencem à lista, com seus respectivos ponteiros "pZ", "pX" e "pY", considere o trecho de código abaixo.

Este trecho de código é usado para inserir na lista os elementos:

"V" é variável composta unidimensional contendo os 10 elementos numéricos abaixo.

Pode-se afirmar que o valor da variável "AUX" na linha "escreva AUX" é:

A tabela abaixo mostra as operações para a manipulação de uma pilha.

Utilizando as definições acima, a seqüência de instruções a seguir foi implementada para avaliar o resultado de uma expressão, sendo A, B, C, D e E os operandos desta expressão. O resultado da avaliação é acumulado em F.

PUSH A
PUSH B
SUB
PUSH C
PUSH D
PUSH E
MPY
ADD
DEC
DIV
POP F

Com base no que foi exposto acima, se A, B, C, D e E apresentarem, respectivamente, os valores 9, 3, 2, 1 e 1, qual o valor armazenado em F após a execução da instrução POP F?

Considere os algoritmos a seguir e as suas correspondentes complexidades indicadas:

Estão corretas apenas as complexidades indicadas para os algoritmos:

Insira as chaves {Lina, Ana, Lia, Ada, Lua, Sol, Cris, Bia, Rita, Mel, Rosa, Val} em uma árvore binária de busca (considere que a árvore está inicialmente vazia). Considere agora, a execução dos seguintes percursos sobre a estrutura após a inserção das chaves.

I - Um percurso em pré-ordem seria: { Ada, Bia, Cris, Lia, Ana, Mel, Rosa, Rita, Val, Sol, Lua, Lina}

II - Um percurso em ordem simétrica seria: {Val, Sol, Rosa, Rita, Mel, Lua, Lina, Lia, Cris, Bia, Ana, Ada}

III - Um percurso em nível seria: {Lina, Ana, Lua, Ada, Lia, Sol, Cris, Rita, Val, Bia, Mel, Rosa}

IV - Um percurso em pós-ordem seria: {Lina, Ana, Ada, Lia, Cris, Bia, Lua, Sol, Rita, Mel, Rosa, Val}

Estão corretos apenas os percursos indicados em: