Operações em Estruturas de Dados

Prévia do material em texto

Pergunta 1
	
	
	
	Seja a fila f = [ 76, 25 ], inicialmente com estes valores, sendo 76 o primeiro item na fila. Considere as operações clássicas enqueue e dequeue e uma operação menos tradicional, peek, que retorna o elemento no início da fila, mas sem eliminá-lo.
Como ficaria finalmente a fila, depois de executar a sequência de comandos Java a seguir?
 
                f.enqueue(60);
                f.enqueue(91);
                Object a = f.dequeue();//tira o primeiro numero a fila
                Object b = f.dequeue();//tira o Segundo numero da fila
                f.enqueue(20);
                Object c = f.peek();//mostra quem esta no topo mas não mexe na estrutura
                f.enqueue(78);
                f.enqueue(f.dequeue());//pega o primero numero da fila e coloca em ultimo.
                f.enqueue(45);
 
      91,20,78,60,45
	
	
	
	
		
	
	
	
Pergunta 2
	
	
	
	Seja a pilha p = [ "Segundo", "Primeiro" ], inicialmente com estes valores, sendo "Segundo" o item que se encontra no topo da pilha (utilizaremos a convenção: p = [topo, a, b, c, d,...]).
Considere as operações clássicas push e pop e uma operação menos tradicional, top, que retorna o elemento que se encontra no topo da pilha, mas sem eliminá-lo.
Como ficaria finalmente a pilha, depois de executar a sequência de comandos Java a seguir?
 
        p.push("a");
        p.push("b");
        Object obj = p.pop();//tira o primeiro numero da pilha
        p.push("c");
        p.push( p.pop() );//coloca no topo da pilha e tira.
        p.push("e");
 
[e,c,a,"Segundo", "Primeiro"]
	
	
	
	
		
	
	
	
Pergunta 3
	
	
	
	Analise o método mostrado a seguir e selecione a resposta que menciona o algoritmo executado:
public void enigma(No no) {     
if (no != null) {       
 System.out.print(no.valor + "  ");      
 enigma (no.filhoEsquerdo);       
 enigma (no.filhoDireito);     
}   
}
Pre - ordem
	
	
	
	
		
	
	
	
Pergunta 4
	
	
	
	A ordenação de elementos desordenados é um assunto muito interessante e frequentemente estudado na disciplina Estrutura de Dados. Os estudiosos apresentam diferentes versões dos métodos de ordenação mais conhecidos e analisam sua eficiência.
Analise os três métodos apresentados a seguir e identifique os algoritmos de ordenação que foram utilizados.
 
    public static boolean enigmaA(double vetor []) {
        if (vetor == null) return false;       
        for (int i = 0; i < vetor.length - 1; i++) {
            for (int j = 0; j < vetor.length - 1 - i; j++) {
              if (vetor[j] > vetor[j+1]) {
                    double tmp = vetor[j];
                    vetor[j] = vetor[j+1];
                    vetor[j+1] = tmp;
               }
            }
        }
        return true;
    }
       
    public static boolean enigmaB(double a []) {
        if (a == null) return false;  
        int i,j;  double x;
        for ( i=0; i < a.length; i++ ) {      
            x = a[i]; j = i;
            while ( j > 0  && x < a[j-1] ) {
                a[j] = a[j-1];
                j--;
            }
            a[j] = x;
        }
        return true;
    } 
   
    public static boolean enigmaC(double vetor []) {
        if (vetor == null) return false;  
        for (int i = 0; i < vetor.length - 1; i++) {
            int min = i;
            for (int j = i+1; j < vetor.length; j++) {
                if ( vetor[j] < vetor[min] ) min = j;
            }
            double temp = vetor[i];
            vetor[i] = vetor[min];
            vetor[min] = temp;
        }
        return true;
    }
 
 
 Buble sort, insert sort, select sort
	
	
	
	
		
	
	
	
	
		
	
	
	
Pergunta 6
	
	
	
	Seja a fila f = [ "white", "yellow" ], inicialmente com estes valores, sendo "white" o primeiro item na fila. Considere as operações clássicas enqueue e dequeue e uma operação menos tradicional, peek, que retorna o elemento no início da fila, mas sem eliminá-lo.
Como ficaria finalmente a fila, depois de executar a sequência de comandos Java a seguir?
                f.enqueue("cyan");
                f.enqueue("black");
                Object a = f.dequeue();
                f.enqueue(a);
                f.enqueue("green");
                Object b = f.peek();
                f.enqueue(f.dequeue());
                f.enqueue("blue");
 
cyan, black, White, green, yellow, blue
 
	
	
	
	
		
	
	
	
Pergunta 7
	
	
	
	Seja a pilha p = [ 30, 20, 10 ], inicialmente com estes valores, sendo 30 o item que se encontra no topo da pilha (utilizaremos a convenção: p = [topo, a, b, c, d,...]).
Considere as operações clássicas push e pop e uma operação menos tradicional, top, que retorna o elemento que se encontra no topo da pilha, mas sem eliminá-lo.
Como ficaria finalmente a pilha, depois de executar a sequência de comandos Java a seguir?
 
        Object obj1 = p.pop();
        Object obj2 = p.pop();
        p.push(obj1);
        p.push(40);
        p.push(50);
        Object obj3 = p.top();
        p.pop();
        p.push( p.pop() );
        p.push(60);
obj1 = 30
obj2 = 20
objt3 = 50
 60, 40, 30 ,10
 
	
	
	
	
		
	
	
	
Pergunta 8
	
	
	
	A ordenação de elementos desordenados é um assunto muito interessante e frequentemente estudado na disciplina Estrutura de Dados. Os estudiosos apresentam diferentes versões dos métodos de ordenação mais conhecidos e analisam sua eficiência.
Analise os três métodos apresentados a seguir e identifique os algoritmos de ordenação que foram utilizados.
 
 
    public static void enigmaA(int vetor[]){
        enigmaA (vetor, 0, vetor.length - 1);
    }
 
    public static void enigmaA(int vetor[], int i, int s) {
        int e=i, d=s;
        int item = vetor[((e+d)/2)];
        while(e <= d){
            while(vetor[e] < item) e++;
            while(vetor[d] > item) d--;
            if(e <= d){
                int aux; // Variável auxiliar para as trocas
                aux = vetor[e];
                vetor[e] = vetor[d];
                vetor[d] = aux;
                d--;
                e++;
            }
        }
        if(d - i > 0) enigmaA (vetor, i, d);
        if(s - e > 0) enigmaA (vetor, e, s);
    }
 
public static void enigmaB(int vetor[]) {
int aux;
int tam = vetor.length;
int j;
for(int i=1; i < tam; i++) {
aux = vetor[i];
j = i - 1;
while(j > = 0 && aux < vetor[j]) {
vetor[j+1] = vetor[j];
j--;
}
vetor[j+1] = aux;
}
}
 
 
Selection,Quick sort, Insert sort
	
	
	
	
		
	
	
	
Pergunta 9
	
	
	
	Uma estrutura de dados muito importante é aquela conhecida como árvore.
Analise com cuidado as árvores mostradas na figura a seguir e selecione a alternativa que descreve corretamente as características das mesmas.
É binário, estritamente binaria, não é completa
É binário, estritamente binaria, é completa
É binário, é estritamente binaria, não é completa
É binaria, não é estritamente binaria, não é completa
	
	
	
	
		
	
	
	
	
	
	
	
	
Pergunta 10
	
	
	
	Observe a árvore de busca binária (ABB) mostrada a seguir:
Qual é a ordem de inserção correta em uma ABB, inicialmente vazia, que se corresponde com o estado final mostrado na figura anterior?
11,6,15,4,7,13,16 
	
	
	
	
	
	
	
	
	
Metodo inserir. Lista ordenada
Piso,janela,cadeira,mesa,sofá,carro,lustre