Questões sobre Análise de Algorítimos

Uma aplicação está instalada em um computador sequencial de um único processador, que é capaz de executar cada instrução em tempo x. Esse computador será substituido por um novo, também sequencial e de processador único, capaz de realizar cada instrução em tempo y. Dadas as incompatibilidades entre os dois computadores, a aplicação será executada na máquina nova a partir de um emulador do computador antigo. O emulador introduz um retardo percentual de z na realização de cada instrução na nova máquina. A relação entre tempo de execução da aplicação na nova máquina e tempo de execução na máquina anterior será

• A. x /yz
• B. x/y+z
• C. x/(y+yz)
• D. xy/(xy+yz)
• E. (y-x)/(zy-x)

Considere duas tabelas relacionais P e Q, cujas chaves representam códigos de tamanho fixo usando as 26 letras maiúsculas do alfabeto e os algarismos de 0 a 9. A tabela P tem como chave um campo do tipo CHAR(8), e a tabela Q, um campo do tipo CHAR(5). Havendo a necessidade de criar uma tabela para representar um relacionamento N:M entre as duas tabelas P e Q, qual é a previsão para o tamanho máximo de linhas dessa tabela?

• A. 8³⁶×5³⁶
• B. 13³⁶
• C. 36¹³
• D. 36⁴⁰
• E. 40³⁶

• A. 1250
• B. 2320
• C. 3110
• D. 3570
• E. 6680

Todos os N nomes de uma lista de assinantes de uma companhia telefônica foram inseridos, em ordem alfabética, em três estruturas de dados: uma árvore binária de busca, uma árvore AVL e uma árvore B.

As alturas resultantes das três árvores são, respectivamente,

• A. O(Log(N)), O(Log(N)), O(1)
• B. O(Log(N)), O(N), O(Log(N))
• C. O(N), O(Log(N)), O(1)
• D. O(N), O(Log(N)), O(Log(N))
• E. O(N), O(N), O(Log(N))

Existem dois vetores, chamados A e B, que estão ordenados e contêm N elementos cada, respeitando a propriedade A[N-1]<B[0], onde os índices de ambos os vetores vão de 0 a N-1. Retiram-se primeiro todos os elementos de A na ordem em que se apresentam e inserem-se esses elementos em uma árvore binária de busca, fazendo o mesmo depois com os elementos de B, que são inseridos na mesma árvore de busca que os de A. Depois, retiram-se os elementos da árvore em um percurso pós ordem, inserindo-os em uma pilha. Em seguida retiram-se os elementos da pilha, que são inseridos de volta nos vetores, começando pelo elemento 0 do vetor A e aumentando o índice em 1 a cada inserção, até preencher todas as N posições, inserindo, então, os N elementos restantes no vetor B da mesma maneira.

 Ao final do processo, tem-se que os vetores

• A. estão ordenados e A[i] < B[i], para todo i=0,...., N-1.
• B. estão ordenados e A[i] > B[i], para todo i=0,...., N-1.
• C. estão ordenados e não existe mais uma propriedade que relacione A[i] e B[i].
• D. não estão ordenados e A[i] < B[i], para todo i=0,...., N-1.
• E. não estão ordenados e A[i] > B[i], para todo i=0,...., N-1.

• A.
• B.
• C.
• D.
• E.

Considere as definições a seguir.

• O nível do nó raiz de uma árvore é 1.

• O nível de qualquer nó subsequente é igual ao nível do seu nó pai mais 1.

• A profundidade de uma árvore é igual ao maior nível encontrado dentre todos os seus nós.

Partindo-se das premissas acima, a menor e a maior quantidade de nós, respectivamente, que poderiam existir em uma árvore binária de profundidade 4 são

• A.

  3 e 15

• B.

  4 e 15

• C.

  3 e 16

• D.

  4 e 16

• E.

  5 e 16

Qual das seguintes sentenças NÃO é equivalente às demais?

• A.

  

• B.

  

• C.

  

• D.

  

• E.

  

Assinale a opção correta.

• A.

  Buscas booleanas retornam resultados baseados no uso de operadores lógicos como ADD, FOR e NOC.

• B.

  Buscas conceituais retornam resultados em que os documentos exibidos como mais relevantes necessariamente contêm as palavras-chaves escolhidas.

• C.

  Buscas com inferência booleana apresentam resultados baseados na frequência com que as palavras selecionadas aparecem em cada descritor.

• D.

  Buscas com inferência bayesiana apresentam resultados baseados na frequência com que as palavras selecionadas aparecem em cada documento.

• E.

  Buscas bayesianas retornam resultados baseados no uso de operadores lógicos como AND, OR e NOT.

Considere o trecho de código a seguir.

Ao final da execução do trecho de código acima, os valores de X e J são iguais, respectivamente, a

• A.

  7 e 11.

• B.

  6 e 12.

• C.

  8 e 11.

• D.

  9 e 12.