Estructuras

de

Datos I

Curso: 1º

Ingeniería Técnica Informática de Sistemas

Universidad de Las Palmas de Gran Canaria

Examen Diciembre de 2002

Ejercicio 1

Implementación TArchivo<TDocumento> es

Tipo TNodo es estructura

Campo TSeguridad Nivel

Campo Archivo Sig

Campo TDocumento Doc

Fin tipo

Tipo TSeguridad es Público, Reservado, Secreto fin tipo

Tipo Archivo es puntero <TNodo>

Operaciones

Procedimiento constructor Inicia(A)

Variable entrada/salida Archivo A

A nulo

Retornar

Fin procedimiento

Procedimiento Insertar(A,D,N)

Variables entrada/salida Archivo A

entrada TDocumento D

TSeguridad N

local Archivo Aux,Aux2

logico e

si A = nulo entonces

Asignador(A,D,N)

Aux A; Aux2 A

si no

e falso

Aux A; Aux2 A

mientras Aux " nulo y e = falso hacer

si Identificador(D)"Identificador(AuxDoc) entonces

si AuxSig = nulo entonces

Aux AuxSig

si no

Aux AuxSig; Aux2 Aux

fin si

si no

e verdadero

fin si

fin mientras

si e = falso entonces

Asignador(Aux,D,N)

Aux2Sig Aux; Aux2 Aux

si no

si Aux Nivel = Público y N " Público entonces

AuxNivel N

si no

si AuxNivel = Reservado y N = Secreto entonces

AuxNivel N

fin si

fin si

fin si

fin si

retornar

fin procedimiento {Insertar(A,D,N}

procedimiento Asignador(A,D,N)

variables entrada Archivo A

TDocumento D

TSeguridad N

A TomarBloque(TNodo)

ASig nulo

ADoc D

ANivel N

retornar

fin procedimiento{Asignador(A,D,N)}

función TDocumento (A,I,N)

variables entrada Archivo A

entero I

TSeguridad N

local TDocumento D

Archivo Aux

Aux A

mientras Aux " nulo hacer

si Identificador(AuxDoc) " I entonces

Aux AuxSig

si no

si N " AuxNivel entonces

D AuxDoc

devolver(D)

si no

devolver(DOCNULL)

fin si

fin si

fin mientras

devolver(DOCNULL)

fin funcion

funcion entera Cuantos(A,N)

variables entrada Archivo A

TSeguridad N

local Archivo Aux

entero C

Aux A; C 0

mientras Aux " nulo hacer

si AuxNivel " N entonces

C C+1

Aux AuxSig

si no

Aux AuxSig

fin si

fin mientras

devolver(C)

fin funcion

fin tipo

fin implementacion{TArchivo<TDocumento>}

Ejercicio 2

Funcion TLista<entero> MaxMin(L,Minimo,Maximo)

Variable entrada TLista<entero> L

entero Minimo, Maximo

local TLista<entero> Aux

Asigna (Aux,L)

si no EsVacia(L) entonces

si Primero(L) < minimo entonces

Aux MaxMin(Resto(Aux),minimo,maximo)

sino

si Primero(L) " minimo y Primero(L) " maximo entonces

Aux Crear(Primero(L),MaxMin(Resto(Aux),minimo,maximo)

sino

si Primero(L) > maximo entonces

Aux MaxMin(Resto(Aux),Minimo,Maximo)

fin si

fin si

fin si

fin si

devolver (Aux)

fin funcion

Ejercicio 3

Funcion logica Arbol(T,N)

variables entrada puntero<TNodo> T

entero N

si T " nulo entonces

si N - TInfo > 0 entonces

N N - TInfo

si Arbol(TIzq,N) entonces

devolver Arbol(TDer,N)

fin si

sino

si TInfo - N = 0 entonces

si TIzq = nulo entonces

devolver verdadero

sino

devolver falso

fin si

fin si

devolver falso

fin si

fin si

fin funcion

Ejercicio 4 - Junio 2002

Funcion logica DobleArco(G)

variables entrada Grafo<n> G

local entero i,j,e,int

i 1;e 0;int 0

mientras i " Vértices(G) y e = 0 hacer

j 1

mientras j " Vertices hacer

si ExisteArco(i,j,G) y i " j entonces

e e+1

fin si

si ExisteArco(j,i,G) y i " j entonces

int int+1

fin si

j j+1

fin mientras

si e " 0 y e/2 = int entonces

devolver verdadero

sino

e 0

fin si

i i+1

fin mientras

si i > Vertices(G) entonces

devolver falso

fin si

fin funcion

Examen Diciembre de 2001

Ejercicio 1

Procedimiento Ordena(Arb,V1,V2,C)

variables entrada ArbolBin<TElemento> Arb

TElemento V1,V2

salida TCola<TElemento> C

si no EsVacio(Arb) entonces

si Raiz(Arb) < V1 entonces

Ordena(Derecho(Arb),V1,V2,C)

sino

si Raiz(Arb) > V2 entonces

Ordena(Izquierdo(Arb),V1,V2,C)

sino

Ordena(Izquierdo(Arb),V1,V2,C)

Insertar(C,Raiz(Arb))

Ordena(Derecho(Arb),V1,V2,C)

fin si

fin si

fin si

retornar

fin procedimiento

Ejercicio 2

Funcion logica Inconexo(G)

variables entrada Grafo<n> G

locales entero i,j,e,n

logico p

i 1; j 1; e 0; n 0

mientras i " Vertices(G) y n " 0,3 hacer

p verdadero

mientras j " Vertices(G) hacer

si ExisteArco(i,j,G) y i " j entonces

p falso

fin si

si ExisteArco(j,i,G) y i " j entonces

p falso

fin si

j j+1

fin mientras

si p = verdadero entonces

e e+1

n e/Vertices(G)

fin si

i i+1

fin mientras

si n > 0,3 entonces

devolver verdadero

sino

devolver falso

fin si

fin funcion

Ejercicio 3

Implementación Acceso es

tipo TNodo es estructura

Campo ristra DNI

Campo logico entrada

Campo Acceso Sig

Fin tipo

tipo Acceso es puntero <TNodo>

operaciones

Procedimiento constructor Inicia(T,FS)

variables entrada ristra FS

entrada/salida Acceso T

local Acceso Aux,Aux1

FicheroTexto F

ristra DNIS

si Abrir(F,FS,Lectura) entonces

T nulo

si no FinFichero(F) entonces

Leer(F,DNIS)

Asignador(T,DNIS)

Aux1 T

si no FinFichero(F) entonces

mientras no FinFichero(F) hacer

Leer(F,DNIS)

Asignador(Aux,DNIS)

Aux1 Sig Aux

Aux1 Aux

fin mientras

fin si

fin si

Cerrar(F)

fin si

retornar

fin procedimiento

Procedimiento Asignador(Aux,DNIS)

variables entrada ristra DNIS

salida Acceso Aux

Aux TomarBloque(TNodo)

Aux Sig nulo

Aux DNI DNIS

Aux entrada falso

retornar

fin procedimiento

Funcion logica AutorizaEntrada(T,DNI)

variables entrada/salida Acceso T

entrada ristra DNI

local Acceso Aux

logico encontrado

Aux T; encontrado falso

mientras Aux " nulo y no encontrado hacer

si Aux DNI = DNI entonces

encontrado verdadero

si no

Aux Aux Sig

fin si

fin mientras

si Aux = nulo entonces

devolver falso

si no

si Aux entrada = falso entonces

Aux entrada verdadero

devolver verdadero

si no

devolver falso

fin si

fin si

fin funcion

Funcion logica ControlaSalida(T,DNI)

variables entrada ristra DNI

entrada/salida Acceso T

local Acceso Aux

logica encontrado

Aux T; encontrado falso

mientras Aux " nulo y no encontrado hacer

si Aux DNI = DNI entonces

encontrado verdadero

si no

Aux Aux Sig

fin si

fin mientras

si Aux = nulo entonces

devolver falso

si no

si Aux entrada = verdadero entonces

Aux entrada falso

devolver verdadero

si no

devolver falso

fin si

fin si

fin funcion

Procedimiento destructor Finaliza(T)

variable entrada Acceso T

local Acceso Aux,Aux1

Aux T;Aux1 T; T nulo

mientras Aux " nulo hacer

Aux Aux Sig

Liberar(Aux1)

Aux1 Aux

fin mientras

retornar

fin procedimiento

fin tipo {Acceso}

fin Implementacion {Acceso}

Examen Diciembre 2000

Ejercicio 1

Implementacion TadBalanza es

Tipo Balanza es estructura

Campo real PlatIzq, PlatDer

fin tipo

Operaciones

Procedimiento Vacia(B)

variable entrada/salida Balanza B

B.PlatIzq 0; B.PlatDer 0

retornar

fin procedimiento

Procedimiento Carga(B,P,M)

variable entrada/salida Balanza B

entrada caracter P

real M

si P = “I” entonces

B.PlatIzq B.PlatIzq + M

si no

B.PlatDer B.PlatDer + M

fin si

retornar

fin procedimiento

Funcion real Fiel(B)

variable entrada Balanza B

devolver B.PlatDer - B.PlatIzq

fin funcion

fin implementacion {TadBalanza}

Ejercicio 2

Funcion logica PAlante(G)

variables entrada Grafo<n> G

local entero i,j

logico p, Visit[Vertices(G)]

p verdadero

para i desde 1 hasta Vertices(G) hacer

Visit[i] falso

fin para

i 1

mientras i " Vertices(G) y p = verdadero hacer

j 1

mientras j " Vertices(G) y p = verdadero hacer

si ExisteArco(i,j,G) entonces

si i " j entonces

p falso

si no

si Visit[j] = falso entonces

Visit[j] verdadero

si no

p falso

fin si

fin si

fin si

j j+1

fin mientras

i i+1

fin mientras

mientras i " Vertices(G) y j = 0 hacer

si Visit[i] = verdadero entonces

j 1

fin si

i i+1

fin mientras

si j = 0 entonces

devolver falso

si no

devolver p

fin si

fin funcion

Ejercicio 3

Funcion real Expresion(Arb)

variables entrada ArbolBin<ristra> Arb

local real v1,v2

si (Raiz(Arb) = “+”) o (Raiz(Arb) = “-“) o (Raiz(Arb) = “x”) o

(Raiz(Arb) = “/”) entonces

v1 Izquierdo(Arb)

v2 Derecho(Arb)

segun Raiz(Arb) hacer

“+” : devolver (v1+v2)

“-“ : devolver (v1-v2)

“x” : devolver (v1 x v2)

“/” : devolver (v1/v2)

fin segun

si no

devolver (Valor(Raiz(Arb)))

fin si

fin funcion

Examen Septiembre 2000

Ejercicio 1

Procedimiento Postorden(C)

variable entrada TCola<TReg> C

local TReg Dato

Tipo TReg es estructura

campo <TElemento> Info

campo entero Nivel

fin tipo

si no EsVacia(C) entonces

Dato Extraer(C)

mientras no EsVacia(C) y Dato.Nivel " Examinar(C).Nivel hacer

Postorden(C)

fin mientras

escribir Dato

fin si

retornar

fin procedimiento

Ejercicio 2

Funcion logica Complementario(G1,G2)

variables entrada Grafo<n> G1,G2

local entero i,j

logico Res

para i desde 1 hasta Vertices(G1) hacer

para j desde 1 hasta Vertices(G1) hacer

si ExisteArco(i,j,G1) y no ExisteArco(i,j,G2) entonces

Res verdadero

si no

si no ExisteArco(i,j,G1) y ExisteArco(i,j,G2) entonces

Res verdadero

si no

Res falso

devolver Res

fin si

fin si

fin para

fin para

devolver Res

fin funcion

Ejercicio 3

Implementacion TContador es

Tipo TContador es estructura

campos enteros Actual,Inicial,Final,Paso

operaciones

Procedimiento ValorInicial(C,I)

variables entrada entero I

entrada/salida TContador C

C.Inicial I

C.Actual I

retornar

fin procedimiento

Procedimiento ValorFinal(C,F)

variables entrada entero F

entrada/salida TContador C

C.Final F

C.Actual C.Inicial

retornar

fin procedimiento

Procedimiento Paso(C,P)

variables entrada entero P

entrada/salida TContador C

C.Paso P

C.Actual C.Inicial

retornar

fin procedimiento

Procedimiento Reset(C)

variable entrada/salida TContador C

C.Actual C.Inicial

retornar

fin procedimiento

Procedimiento Inc(C)

variable entrada/salida TContador C

si C.Actual < C.Actual + C.Paso entonces

C.Actual C.Actual + C.Paso

fin si

retornar

fin procedimiento

Funcion entera Examinar(C)

variable entrada/salida TContador C

Devolver C.Actual

fin funcion

fin tipo {TContador}

fin implementacion {TContador}

Algoritmo PosiNega

variables Contador CN,CP

entero V

Iniciar(CN)

Iniciar(CP)

ValorInicial(CN,0)

ValorInicial(CP,0)

Paso(CN,1)

Paso(CP,1)

repetir

escribir “Introduzca un valor entero por favor: “

leer V

si V > 0 entonces

Inc(CP)

si no

si V < 0 entonces

Inc(CP)

fin si

fin si

hasta que V = 0

fin repetir

V Examinar(CP)

escribir “Valores positivos: “,V

V Examinar(CN)

escribir “Valores negativos: “,V

parar

fin algoritmo

Examen Junio 2000

Ejercicio 2

Tipo Valores es estructura

campo <TElemento> TClave

campo <TElemento> TValor

campo Tabla Ant,Sig

fin tipo

Tipo Tabla es puntero a Valores fin tipo

Procedimiento Asignar(T1,T2)

variables entrada tabla T1

entrada/salida tabla T2

local tabla Aux,Aux2,Aux3

si T1 " nulo entonces

si T1 Ant = nulo entonces

AsignaNodos(T1,Aux)

Aux2 Aux

T1 T1 Sig

si no

mientras T1 Sig " nulo hacer

AsignaNodos(T1,Aux2)

Aux Sig Aux2

Aux2 Ant Aux

Aux Aux Sig

fin mientras

AsignaNodos(T1,Aux2)

Aux Sig Aux2

Aux2 Ant Aux

mientras Aux Ant " nulo hacer

Aux Aux Ant

fin mientras

fin si

si no

Aux nulo

fin si

si T2 " nulo entonces

Aux3 T2

mientras T2 Sig " nulo hacer

T2 T2 Sig

Liberar(Aux3)

Aux3 T2

fin mientras

T2 Aux

Liberar(Aux3)

si no

T2 Aux

fin si

retornar

fin procedimiento

Procedimiento AsignaNodos(T1,Aux2)

variables entrada tabla T1

entrada/salida tabla Aux2

Aux2 TomarBloque(Valores)

Aux2 TClave T1 TClave

Aux2 TValor T1 TValor

Aux2 Sig nulo

Aux2 Ant nulo

retornar

fin procedimiento

Ejercicio 3

Funcion entero Aislado(G)

variables entrada Grafo<n> G

locales entero i,j,Res

logico Visit[Vertices(G)]

para i desde 1 hasta Vertices(G) hacer

Visit[i] falso

fin para

para i desde 1 hasta Vertices(G) hacer

j 1

mientras j " Vertices(G) hacer

si ExisteArco(j,i,G) y i " j entonces

Visit[i] verdadero

j Vertices(G)

fin si

j j+1

fin mientras

fin para

Res 0

para i desde 1 hasta Vertices(G) hacer

si no Visit[i] entonces

Res Res+1

fin si

fin para

devolver Res

fin funcion

Examen Septiembre 1999

Ejercicio 2

Funcion Puntero<TNodo> Arbol(P)

variable entrada/salida TPila<Reg> P

local Puntero<TNodo> T

Reg Dato

TPila<Reg> Aux

Tipo Reg es estructura

campo TElemento Info

campo entero Grado

fin tipo

si no EsVacia(P) entonces

T TomarBloque<TNodo>

Dato Examinar(P)

Desapilar(P)

T Info Dato.Info

T Izq nulo

T Der nulo

si Dato.Grado = 2 entonces

T Der Arbol(P)

T Izq Arbol(P)

si no

si Dato.Grado = 0 entonces

devolver T

si no

T Izq Arbol(P)

devolver T

fin si

fin si

si no

T nulo

fin si

devolver T; fin funcion

Examen Junio 1999

Ejercicio 1

Funcion TConjunto<TE> Union(C1,C2)

variables entrada TConjunto<TE> C1,C2

local TConjunto<TE> C3

puntero<TE> P

C3 CrearVacio

si EsVacio(C1) y EsVacio(C2) entonces

devolver C3

si no

si EsVacio(C1) entonces

devolver Copia(C2)

si no

si EsVacio(C2) entonces

devolver Copia(C1)

si no

C3 Copia(C1)

P C2.Primero

mientras P " nulo hacer

si no Pertenece(C3,PElemento) entonces

Q TomarBloque(TNodo)

Q Elemento P Elemento

Q Siguiente C3.Primero

C3.Primero Q

fin si

P P Siguiente

fin mientras

devolver C3

fin si

fin si

fin si

fin funcion

Ejercicio 3

Procedimiento Arbol(T,N,O)

variables entrada/salida entero O

entrada puntero<TNodo> T

entero N

si T " nulo entonces

T Nivel N

Arbol(TIzq,N+1,O)

T Orden O

O O+1

Arbol(TDer,N+1,O)

fin si

retornar

fin procedimiento