05 AVL - Preguntas test AVL PDF

Preview

Summary

Preguntas test AVL...

Description

DEFINICIONES_002, •  La,altura,H(T),de,un,árbol,binario,T,con, subárboles,izquierdo,Ti,y,derecho,Td,es:, –  0,si,el,árbol,T,está,vacío,y,1)+)min)(H(Ti),)H(Td)),en, otro,caso., –  1)+)min)(H(Ti),)H(Td)),en,cualquier,caso., –  1)+)max)(H(Ti),)H(Td)),en,cualquier,caso., –  0,si,el,árbol,T,está,vacío,y,1)+)max)(H(Ti),)H(Td)),en, otro,caso.,

DEFINICIONES_007, •  ¿Cuál,es,el,peor,árbol,AVL,posible,de,una, altura,dada?, I.,El,que,Jene,un,menor,número,de,nodos., II.,El,que,Jene,todos,los,nodos,no,hoja,con, factor,de,equilibrio,no,nulo., –  I:,sí,,II:,sí., –  I:,sí,,II:,no., –  I:,no,,II:,sí., –  I:,no,,II:,no.,

DEFINICIONES_001, •  Respecto,a,la,evitación,de,la,degeneración,de,un, árbol,binario,de,búsqueda,,¿cuál,de,las,siguientes, respuestas,considera,verdadera?, –  La,reestructuración,completa,de,un,árbol,binario,de, búsqueda,requiere,excesivas,reorganizaciones., –  Las,reorganizaciones,necesarias,para,la, reestructuración,completa,de,un,árbol,binario,de, búsqueda,pueden,mantenerse,bajo,control., –  Las,reorganizaciones,en,un,árbol,AVL,afectan,a,todo, el,árbol., –  Las,operaciones,de,mantenimiento,en,un,árbol,AVL, son,O(n).,

DEFINICIONES_006, •  Determinar,cuál,de,las,siguientes,afirmaciones,es, cierta:, I.,Un,árbol,AVL,es,siempre,más,adecuado,que,un,árbol, binario,de,búsqueda., II.,Un,árbol,binario,de,búsqueda,que,por,construcción,es, perfectamente,balanceado,es,el,que,presenta,mejor, coste,computacional,en,la,búsqueda., –  I:,sí,,II:,sí., –  I:,sí,,II:,no., –  I:,no,,II:,sí., –  I:,no,,II:,no.,

DEFINICIONES_003, •  Si,T,es,un,árbol,binario,no,vacío,con, subárboles,izquierdo,Ti,y,derecho,Td,,T,es,AVL, si,y,sólo,si:, –  Ninguna,de,las,otras,respuestas,es,verdadera., –  Ti,y,Td,son,AVL., –  Ti,y,Td,son,AVL,y,H(Ti)0H(Td))=))01,)0,)+1., –  H(Ti)0H(Td))=))01,)0,)+1.,

DEFINICIONES_004, •  Indicar,cuál,de,las,siguientes,afirmaciones,es,cierta, cuando,el,número,de,elementos,es,muy,elevado:, I.,El,coste,promedio,de,la,búsqueda,en,un,árbol,binario, de,búsqueda,es,siempre,mejor,que,en,una,lista, encadenada., II.,El,coste,promedio,de,la,búsqueda,en,un,árbol,AVL,es, siempre,mejor,que,en,una,lista,encadenada., –  I:,sí,,II:,sí., –  I:,sí,,II:,no., –  I:,no,,II:,sí., –  I:,no,,II:,no.,

INSERCION_003, •  En,un,árbol,AVL,,el,factor,de,equilibrio,del, nodo,críJco:, –  Antes,de,la,inserción,es,Z1,ó,+1,y,después,es,Z2,ó, +2., –  Antes,de,la,inserción,es,Z2,ó,+2,y,después,es,Z1,ó, +1., –  Antes,de,la,inserción,es,0,y,después,es,Z1,ó,+1., –  Antes,de,la,inserción,es,Z1,ó,+1,y,después,es,0.,

INSERCION_006, •  Antes,de,la,inserción,,el,nodo,discriminante, (hijo,del,críJco),de,un,árbol,AVL,debe,tener, un,factor,de,equilibrio:, –  +2,ó,Z2., –  0., –  Ninguna,de,las,otras,respuestas,es,verdadera., –  +1,ó,Z1.,

INSERCION_002, •  En,un,árbol,AVL,,se,necesita,una,rotación, cuando:, –  Aumenta,la,altura,del,subárbol,de,mayor,altura., –  Aumenta,la,altura,del,subárbol,de,menor,altura., –  El,factor,de,equilibrio,pasa,de,0,a,Z1,ó,+1., –  Ninguna,de,las,otras,respuestas,es,verdadera.,

INSERCION_001, •  Respecto,a,las,longitudes,de,los,caminos,de, búsqueda:, –  Ninguna,de,las,otras,respuestas,es,verdadera., –  Las,del,AVL,no,exceden,en,más,del,45%,a,las,del, árbol,ópJmo., –  Son,similares,en,el,AVL,y,en,el,árbol,ópJmo., –  Las,del,AVL,superan,en,más,de,un,50%,a,las,del, árbol,ópJmo.,

INSERCION_004, •  En,un,árbol,AVL,,el,antecesor,más,cercano,con, factor,de,equilibro,+2,ó,Z2,después,de,la, inserción,es:, –  El,antecesor,más,cercano,con,factor,de,equilibrio,Z2,ó, +2,antes,de,la,inserción., –  Ninguna,de,las,otras,respuestas,es,verdadera., –  El,antecesor,más,cercano,con,factor,de,equilibrio,0, antes,de,la,inserción., –  El,antecesor,más,cercano,con,factor,de,equilibrio,+1,ó, Z1,antes,de,la,inserción.,

INSERCION_005, •  En,un,árbol,AVL,,los,factores,de,equilibrio,que, están,en,el,camino,desde,el,nodo,críJco,al, nuevo,punto,de,inserción,deben,ser:, –  +2,ó,Z2,antes,de,la,inserción., –  Ninguna,de,las,otras,respuestas,es,verdadera., –  0,antes,de,la,inserción., –  +1,ó,Z1,antes,de,la,inserción.,

ROTACIONESINSERCION_002, •  En,las,rotaciones,simples,tras,una,inserción,en, un,árbol,AVL:, –  La,altura,del,subárbol,antes,de,la,inserción,y, después,del,reequilibrado,es,disJnta., –  Antes,de,la,inserción,el,factor,de,equilibrio,del, nodo,discriminante,es,disJnto,de,0., –  Se,necesita,examinar,el,resto,del,árbol., –  Después,del,reequilibrado,,los,factores,de, equilibrio,de,los,nodos,críJco,y,discriminante,son, 0.,

ROTACIONESINSERCION_003, •  En,las,rotaciones,dobles,tras,una,inserción,en, un,árbol,AVL:, –  Antes,de,la,inserción,el,factor,de,equilibrio,del, nodo,críJco,es,0., –  Se,necesita,examinar,el,resto,del,árbol., –  La,altura,del,subárbol,antes,de,la,inserción,y, después,del,reequilibrado,es,la,misma., –  Antes,de,la,inserción,el,factor,de,equilibrio,del, nodo,discriminante,es,disJnto,de,0.,

ROTACIONESINSERCION_001, •  En,las,rotaciones,simples,tras,una,inserción,en,un, árbol,AVL:, –  La,altura,del,subárbol,antes,de,la,inserción,y,después, del,reequilibrado,es,la,misma., –  Se,necesita,examinar,el,resto,del,árbol., –  La,altura,del,subárbol,antes,de,la,inserción,es,menor, que,la,altura,del,subárbol,después,del,reequilibrado., –  Después,del,reequilibrado,,los,factores,de,equilibrio, de,los,nodos,críJco,y,discriminante,son,disJntos,de,0.,

ROTACIONESINSERCION_010, •  Tras,la,inserción,de,un,nodo,en,un,árbol,AVL,, ¿cuántas,rotaciones,son,necesarias,para, reequilibrar,el,árbol?, –  Ninguna,,siempre,es,posible,insertar,el,nodo,de, forma,que,no,se,altere,el,equilibrio,del,árbol., –  Sólo,una,,tras,la,rotación,se,restablece,la,altura, original,del,subárbol., –  Tantas,como,ascendientes,tenga,el,nodo, insertado., –  Tantas,como,nodos,tenga,el,árbol.,

ROTACIONESINSERCION_006, •  Tras,una,rotación,después,de,una,inserción,en, un,árbol,AVL,,¿qué,respuesta,considera, verdadera?, –  Se,necesita,recalcular,los,factores,de,equilibrio,del, resto,del,árbol., –  Ninguna,de,las,otras,respuestas,es,verdadera., –  La,altura,antes,de,la,inserción,y,después,del, reequilibrado,es,disJnta., –  Los,únicos,nodos,que,pueden,variar,su,factor,de, equilibrio,son,los,implicados,en,la,rotación.,

ROTACIONESINSERCION_004, •  En,las,rotaciones,dobles,tras,una,inserción,en, un,árbol,AVL:, –  La,altura,antes,de,la,inserción,y,después,del, reequilibrado,es,disJnta., –  Ninguna,de,las,otras,respuestas,es,verdadera., –  Antes,de,la,inserción,el,factor,de,equilibrio,del, nodo,discriminante,es,disJnto,de,0., –  Se,necesita,examinar,el,resto,del,árbol.,

ROTACIONESINSERCION_009, •  Sea,N,el,nodo,raíz,de,un,subárbol,AVL,,tal,que, antes,de,una,inserción,su,factor,de,equilibrio,es, 1,,y,sea,Ni,su,hijo,izquierdo.,Se,inserta,un, elemento,en,el,subárbol,izquierdo,de,Ni,que, altera,su,factor,de,equilibrio.,Antes,de,la, inserción,el,factor,de,equilibrio,de,Ni,es,0., Entonces:, –  Es,necesario,un,reequilibrado,en,Ni., –  El,nodo,críJco,a,considerar,es,Ni,y,no,N., –  Es,necesario,reequilibrar,en,N,con,una,rotación,doble., –  Ninguna,de,las,otras,respuestas,es,verdadera.,

ROTACIONESINSERCION_005, •  ¿Qué,rotaciones,son,posibles,tras,una, inserción,en,un,árbol,AVL?, –  I,,D,,ID,,DI., –  I,,D,,ID,,II,,DI,,DD., –  I,,D,,II,,DD., –  I,,D.,

ROTACIONESINSERCION_007, •  En,un,árbol,AVL,,¿por,qué,conviene, implementar,las,rotaciones,dobles,en,lugar,de, aplicar,las,dos,simples,correspondientes?, –  Porque,se,evita,colapsar,la,memoria,dinámica., –  Ninguna,de,las,otras,respuestas,es,verdadera., –  Porque,es,conteptualmente,conveniente., –  Porque,se,evita,recalcular,enlaces.,

ROTACIONESINSERCION_008, •  Sea,N,el,nodo,raíz,de,un,subárbol,AVL,,tal,que, antes,de,una,inserción,su,factor,de,equilibrio,es, Z1,,y,sea,Ni,su,hijo,izquierdo.,Se,inserta,un, elemento,en,el,subárbol,izquierdo,de,Ni.,Antes, de,la,inserción,el,factor,de,equilibrio,de,Ni,es,Z1., Entonces:, –  Es,necesario,un,reequilibrado,en,Ni., –  El,nodo,críJco,a,considerar,es,N,y,no,Ni., –  Es,necesario,reequilibrar,en,N., –  Ninguna,de,las,otras,respuestas,es,verdadera.,

ASOCIATIVA_001, •  En,un,árbol,AVL,,la,propiedad,asociaJva, {{T1ʼ(B)T2}(A)T3}0>{T1ʼ(B){T2)(A)T3}},,¿a,qué, rotación,representa?, –  A,dos,rotaciones,simples., –  A,una,rotación,simple., –  A,una,rotación,doble., –  A,dos,rotaciones,dobles.,

ASOCIATIVA_002, •  En,un,árbol,AVL,,la,propiedad,asociaJva,{T1(A) {{T2’(C)T3}(B)T4}})0>){{T1(A)T2ʼ}(C){T3(B)T4}},,¿a, qué,rotación,representa?, –  A,una,rotación,doble., –  A,una,rotación,simple., –  A,dos,rotaciones,dobles., –  Ninguna,de,las,otras,respuestas,es,verdadera.,

EXTRACION_004, •  Cuando,la,extracción,en,un,árbol,AVL,provoca,una, disminución,de,altura,de,la,rama,de,donde,se,extrajo,el, nodo:, –  Siempre,existe,una,Jpo,de,rotación,que,con,una,sola,aplicación, resuelve,el,desequilibrio., –  Necesariamente,,la,disminución,de,altura,y,la,consiguiente, corrección,de,los,factores,de,equilibrio,y,las,posibles,rotaciones, se,propagan,desde,el,lugar,donde,se,produce,la,extracción, hasta,llegar,a,la,raíz., –  Ninguna,de,las,otras,respuestas,es,verdadera., –  La,disminución,de,altura,y,la,consiguiente,corrección,de,los, factores,de,equilibrio,y,las,posibles,rotaciones,se,pueden, propagar,desde,el,lugar,donde,se,produce,la,extracción,hasta, llegar,a,la,raíz.,

EXTRACION_002, •  Cuando,en,un,árbol,AVL,se,quiere,eliminar,un,nodo, con,sus,dos,enlaces,no,nulos,,¿qué,se,ha,de,hacer?, –  SusJtuir,el,nodo,a,extraer,por,su,sucesor,o,predecesor,en, orden,simétrico,ya,que,Jene,ambos,hijos,a,nulo., –  SusJtuir,el,nodo,a,extraer,por,su,sucesor,o,predecesor,en, orden,simétrico,ya,que,Jene,un,hijo,nulo., –  SusJtuir,el,nodo,a,extraer,por,su,hijo,derecho,o,izquierdo, con,independencia,de,a,cuántos,nulos,apunte., –  SusJtuir,el,nodo,a,extraer,por,su,sucesor,o,predecesor,en& preorden,ya,que,Jene,un,hijo,nulo.,

EXTRACION_003, •  Cuando,la,extracción,en,un,árbol,AVL,provoca, una,disminución,de,altura,de,la,rama,de,donde, se,extrajo,el,nodo:, –  Ninguna,de,las,otras,respuestas,es,verdadera., –  Siempre,es,necesario,al,menos,dos,operaciones,de, rotación., –  No,queda,más,remedio,que,realizar,una, reorganización,global., –  Siempre,existe,un,Jpo,de,rotación,que,con,una,sola, aplicación,resuelve,el,desequilibrio.,

EXTRACION_001, •  ¿En,cuántos,pasos,se,resuelve,una,extracción, en,un,árbol,AVL?, –  En,O(n2),pasos., –  En,O(n),pasos., –  En,O(log2n),pasos., –  En,O(nlog2n),pasos.,

ROTACIONESEXTRACCION_001, •  ¿Antes,de,la,extracción,y,después,de,qué,Jpos, de,rotaciones,en,un,árbol,AVL,la,altura,del, subárbol,se,manJene,invariante?, –  En,un,caso,de,rotación,simple,y,en,uno,de,la, doble., –  Ninguna,de,las,otras,respuestas,es,verdadera., –  En,dos,casos,de,la,rotación,simple., –  En,todos,los,casos,de,la,rotación,doble.,

ROTACIONESEXTRACCION_005, •  ¿Qué,rotaciones,dobles,son,posibles,tras,una, extracción,en,un,árbol,AVL?, –  I,,D,,II,,DD., –  Ninguna,de,las,otras,respuestas,es,verdadera., –  ID,,DI., –  I,,D.,

ROTACIONESEXTRACCION_002, •  Si,en,un,árbol,AVL,antes,de,la,extracción,y, después,de,la,rotación,correspondiente,la, altura,del,subárbol,disminuye,,¿hasta,dónde, se,propagan,las,rotaciones?, –  Nunca,se,producirán,propagaciones., –  Hasta,que,su,ascendiente,no,quede, desequilibrado., –  Necesariamente,hasta,la,raíz., –  Hasta,que,cubra,por,completo,el,árbol.,

ROTACIONESEXTRACCION_007, •  Determinar,cuál,de,las,siguientes,afirmaciones,es, cierta,en,relación,con,los,árboles,AVL:, I.,La,inserción,de,un,nodo,puede,producir,como, máximo,una,rotación,,simple,o,doble., II.,La,extracción,de,un,nodo,puede,producir,como, máximo,una,rotación,,simple,o,doble., –  I:,sí,,II:,sí., –  I:,sí,,II:,no., –  I:,no,,II:,sí., –  I:,no,,II:,no.,

ROTACIONESEXTRACCION_003, •  En,las,rotaciones,dobles,para,reequilibrar,el, desequilibro,producido,por,una,extracción:, –  Siempre,se,producirán,reducciones,de,altura., –  En,algunos,casos,se,producirán,reducciones,de, altura., –  Necesariamente,se,desencadenará,una,rotación, simple,tras,la,doble., –  Nunca,se,producirán,reducciones,de,altura.,

ROTACIONESEXTRACCION_006, •  Dado,un,árbol,AVL,,el,factor,de,equilibrio,de, un,nodo,es,0,,si,se,elimina,un,nodo,por,su, izquierda.,Entonces:, –  No,es,necesario,ningún,reequilibrado., –  Es,necesario,reequilibrar,con,una,rotación,D., –  Es,necesario,reequilibrar,con,una,rotación,I., –  Ninguna,de,las,otras,respuestas,es,verdadera.,

ROTACIONESEXTRACCION_008, •  Determinar,cuál,de,las,siguientes,afirmaciones,es, cierta,en,relación,con,la,extracción,en,los,árboles,AVL,:, I.,Cuando,se,elimina,un,nodo,a,la,derecha,de,un,nodo, con,factor,de,equilibrio,+1,puede,necesitarse,una, rotación,simple,I., II.,Cuando,se,elimina,un,nodo,a,la,derecha,de,un,nodo, con,factor,de,equilibrio,+1,puede,necesitarse,una, rotación,doble,ID., –  I:,sí,,II:,sí., –  I:,sí,,II:,no., –  I:,no,,II:,sí., –  I:,no,,II:,no.,

ROTACIONESEXTRACCION_004, •  ¿Qué,encuentra,significaJvamente,diferente, entre,el,tratamiento,de,los,desequilibrios, durante,la,inserción,y,la,extracción?, –  Nada,,tanto,en,la,inserción,como,en,la,extracción, siempre,se,produce,propagación., –  En,la,inserción,siempre,se,produce,propagación,y,en, la,extracción,sólo,con,cierta,frecuencia., –  Ninguna,de,las,otras,respuestas,es,verdadera., –  En,la,inserción,nunca,se,produce,propagación,y,en,la, extracción,sí,se,puede,producir.,...