Estructuras de Datos y de la Informacion I

Problemas

Introduccion

1. (E) La asignatura FEJ I tiene 4 temas en su programa, y en su examen se preguntan 2.Un estudiante la aprueba si responde a un tema. ¿Cuantos temas hay que estudiar parapara tener una probabilidad del 50% de aprobar?

2. (E) En el curso 2003–2004 se cambian las normas de evaluacion de FEJ I y aunque en suexamen se preguntan 2 de los 4 temas, una de las preguntas es de aprobado obligatoriopara aprobar. ¿Cuantos temas hay que saberse en 2003–2004 para tener una probabilidaddel 50% de aprobar?

3. (P) Un problema de Algebra: Otto y Fritz son dos estudiantes de Ingenierıa Informaticaen la UAM. Otto, que atiende con regularidad a las clases de Algebra, propone a Fritz elsiguiente truquete aritmetico:

• piensa un numero entre 6 y 15;

• multiplıcalo por 9 y restale 6;

• mientras el numero resultante tenga dos cifras, sumalas;

• suma 1 al numero resultante;

• piensa ahora un paıs europeo cuyo nombre empiece por la letra del abecedario cuyoorden corresponde al del numero obtenido;

• piensa en un animal cuyo nombre empiece por la letra siguiente;

• dime el color de dicho animal.

Fritz efectua diligentemente estas operaciones, respondiendo finalmente que gris, a lo queOtto contesta que el paıs es Dinamarca y el animal el elefante. Fritz queda entonces mar-avillado por que precisamente habıa pensado en ese paıs y ese animal. ¿Como consiguioOtto leer el pensamiento de Fritz?

4. (P) Otro problema de Algebra: Tras lo anterior Otto intenta explicar el truco a Fritz, peroeste sale de estampida a hacer un programa con memoria dinamica mediante TurboHIntercalada y que se linke al diccionario de su procesador de textos WordGuay paraencontrar el paıs y el animal. A los pocos dıas Fritz, que no atiende con regularidad alas clases de Algebra, busca desesperado a Otto y le dice que pese a haber compiladoel programa con siete modos de memoria distintos y debuggeado hasta el agotamiento,la respuesta ya no es Dinamarca y elefante. Otto pide a Fritz el pseudocodigo de suprograma y este le muestra lo siguiente:

• piensa un numero entre 6 y 15;

• restale 6 y multiplıcalo por 9;

1

• mientras el numero resultante tenga dos cifras, sumalas;

• suma 1 al numero resultante;

• piensa ahora un paıs europeo cuyo nombre empiece por la letra del abecedario cuyoorden corresponde al del numero obtenido;

• piensa en un animal cuyo nombre empiece por la letra siguiente;

• dime el color de dicho animal (Fritz indica que su respuesta es tambien gris)

Tras un momento, Otto comenta que el programa dara como paıs probablemente Alemaniay ballena como animal. Otra vez Fritz queda maravillado porque esa es la respuesta desu programa. ¿Como ha conseguido Otto predecirla de nuevo?

5. (P) Un problema de Ingenierıa Informatica: Los dos problemas anteriores tienen moraleja.¿Cual es?

C basico

6. (E) Reescribir la siguiente funcion para que haga lo mismo de manera mas transparente:

void HaceAlgo(int *uno, int *otro)

{

*uno = *otro - *uno;

*otro = *otro - *uno;

*uno = *otro + *uno;

}

7. (E) Hacer lo mismo con:

void Pregunta(int *a17, int *algo)

{

int uno, otro, otromas;

uno=otro;otromas=*a17;

otro=*algo;uno=otromas;*a17=otro;

unomas=otro;

*algo=uno;uno=otro;otro=*algo;

}

8. (E) Escribir una funcion C que calcule la media, varianza y la desviacion tıpica de unasucesion de numeros.

9. (P) Si y es una aproximacion a la raız cubica de x, z definida como

z =2y + x/y2

3

lo es aun mejor. Usar este hecho para escribir una funcion que calcule por sucesivasiteraciones la raiz cubica de un numero, y un programa que la use. Prestar atencion aldiseno de la funcion y a su validacion.

10. (E) Disenar pruebas funcionales para comprobar lo siguiente

2

• una funcion que devuelve el maximo de sus tres parametros, siendo estos floats;

• una funcion que calcule la raiz cuadrada de un numero x iterando el hecho de quesi y es una aproximacion a dicha raiz

z =1

2

(y +

x

y

)

lo es aun mejor;

• una funcion que devuelve el maximo comun divisor de sus dos parametros, siendoestos ints (construir esta funcion sobre el algoritmo de Euclides).

11. (E) Disenar y programar una funcion que calcule las raıces (posiblemente complejas) dela ecuacion de segundo grado ax2 + bx + c.

12. (Q) En C el operador sizeof(type) da el tamano en bytes de los datos de un ciertotipo type. Hallar el tamano de los tipos predefinidos en C, incluyendo su variantes.Hacer lo mismo con los correspondientes punteros y con tablas de datos de dichos tiposrelacionandolas con sus dimensiones.

13. (Q) ¿Que valores puede devolver la siguiente llamada a fscanf

fscanf(p_file,"%d %s %d", &int1, string, &int2); ?

Dar ejemplos de situaciones en que dichos retornos se produzcan.

14. (Q) Supongamos que en un programa C una tabla se declara como int ii[20]; yse inicializa mediante la sentencia ii[i]=i;. ¿Cual es el resultado de las siguientesexpresiones?

(int) *((float *) (ii+2) + 2);

65 + (char) * (int *) ((char *) (ii + 1) +16);

15. (Q) ¿Cuales son los valores en tu compilador C de las constantes EOF y NULL?

16. (E) Sobre el siguiente codigo para el calculo del mcd de dos enteros

#include<stdio.h>

main()

{

int A,B,R,T;

printf("\nA, B? ");

scanf("%d %d", &A, &B);

if (A<B) {

T=A;

A=B;

B=T;

3

}

R=A%B;

while(R>0) {

A=B;

B=R;

R=A%B;

}

printf("\nmcd = %d", B);

}

y sucesivamente:

(a) eliminar una variable;

(b) eliminar la sentencia if;

(c) reducir al maximo el bloque while;

¿Como habrıa que modificarlo para hacerlo a prueba de crashes?

17. (Q) A la hora de comprobar la validez de un programa hay que utilizar para las pruebasdatos normales, datos extremos (esto es, datos aceptables, pero que aparecen en rarasocasiones) y datos ilegales (esto es, datos que el programa no puede aceptar).

Dar ejemplos de estos datos para el programa anterior, comprobar su efecto, y reescribirlopara que pueda recibir y procesar adecuadamente cualquier entrada.

18. (Q) En el programa anterior, reescribir la entrada y salida de datos para que funcionemediante ficheros.

19. (Q) En el programa anterior, reescribir el bloque while como un for.

20. (P) En C los ındices de una tabla de dimension N empiezan desde 0 y acaban en N-1.¿Como se podrıa hacer que empezaran en 1 y acabaran en N? (Sugerencia: punteros).

21. (E) Escribir una funcion que reciba dos vectores float y devuelva su producto escalar,calculado mediante una suma en ındices desde 1 a la dimension de los vectores.

22. (P) Construir una funcion C que intercambie el contenido de dos tablas float intercam-biando punteros a las mismas.

23. (Q) Definir un tipo mes mediante una constante enumerada que contenga los nombresde los meses del ano. Construir una funcion mes siguiente que reciba un dato mes ydevuelva el mes siguiente o un codigo de error.

24. (P) Construir una funcion C que intercambie el contenido de dos matrices (esto es, dostablas bidimensionales) float intercambiando punteros a las mismas.

25. (P) Supongamos que un numero real se representa en C como

4

struct real {

int izqda, unsigned int drcha;

};

donde izqda representa las cifras a la izquierda del punto decimal y drcha las cifrasdecimales. Si izqda es negativo, se supone que el numero es negativo.

• Definir un tipo de dato a partir de struct real.

• Escribir una funcion que transforma floats en reals.

• Escribir una funcion que transforma reals en floats.

• Escribir funciones suma, resta y prod que reciban dos datos real y devuelvan undato real con su suma, resta y producto.

26. (Q) Un programa C necesita unas funciones para manejar numeros complejos y otrasfunciones de proposito general. A su vez las funciones complejas necesitan llamar enocasiones a las funciones de proposito general. Por razones de reusabilidad, interesarepartir el programa en tres ficheros: uno para main y otras funciones espcıficas delprograma, otro para las funciones complejas y otro para las de proposito general. ¿Cualesdeben ser los inicios de los tres ficheros?

27. (E) Escribir una funcion C de nombre Aviso que reciba una cadena de caracteres yla imprima en el dispositivo stderr (pregunta: ¿que es stderr?; solucion: Kernighan–Ritchie).

28. (E) Escribir una funcion C de nombre Error que reciba una cadena de caracteres, laimprima en el dispositivo stderr y fuerce una salida del programa.

Tipos Abstractos de Datos

29. (E) Disenar y programar funciones C que sobre el tipo abstracto fcomplex realicen elproducto y division de numeros complejos, la inversion de un complejo y el calculo delmodulo de un complejo.

30. (E+) Las primitivas de un TAD ent para datos que sean numeros enteros tienen lasespecificaciones siguientes:

ent Suma(ent A, ent B);

ent Neg(ent A);

donde la primera devuelve la suma de dos enteros y la segunda el negativo.

Especificar en detalle y dar el psc de las siguientes rutinas derivadas a partir de las dosanteriores:

ent Resta(ent A, ent B): devuelve la resta de dos enteros;

ent Prod(ent A, ent B): devuelve el producto de dos enteros;

ent Cociente(ent A, ent B): devuelve el cociente de dos enteros;

ent Resto(ent A, ent B): devuelve el resto de dividir dos enteros;

ent Pot(ent A, ent B): devuelve el valor de AB;

ent Log(ent A, ent B): devuelve el valor de la parte entera de logA B.

5

31. (E+) Las primitivas de un TAD CC para cadenas de caracteres tienen las especificacionessiguientes:

bool CCVacia(CC A): devuelve V o F segun A este o no vacıa;

status CCIns(car c, pos i, CC A): intenta insertar el caracter c en la posicion i dela cadena A, y devuelve Ok o Error;

status CCExt(car c, pos i, CC A): intenta extraer en el caracter c el situado en laposicion i de la cadena A, y devuelve Ok o Error;

status CCIni(CC A): intenta crear una cadena vacıa A y devuelve Ok o Error.

Especificar en detalle y dar el psc de las siguientes rutinas derivadas a partir de lasanteriores:

status CCIdent(car c, pos i, CC A): intenta situar en el caracter c el situado en laposicion i de la cadena A sin modificar esta, y devuelve Ok o Error;

ent CCLong(CC A): devuelve la longitud de la cadena A;

status CCConcat(CC A, CC B): intenta concatenar la cadena B tras la cadena A, ydevuelve Ok o Error;

pos CCLocaliza(car c, CC A): devuelve la posicion del caracter c en la cadena o uncodigo de error adecuado.

32. (E+) Para el TAD CC se decide usar como EdD una tabla de caracteres de longitud fijaLONG MAX CC, donde se indica con el sımbolo especial @ el final de la cadena.

Dar el psc de las primitivas del TAD CC indicadas en el problema anterior.

33. (Q) Si se utiliza la EdD anterior, ¿convendrıa, por razones de eficacia u otras, incorporaralgunas de las rutinas derivadas del TAD CC al grupo inicial de primitivas? Dar el pscde las nuevas primitivas.

34. (E+) Para el TAD de datos enteros se va a usar el dato int de C como estructura dedatos y el operador binario de suma y el unario de negativo para las primitivas de sumay negativo de la interfaz del TAD.

Usando unicamente los elementos anteriores y sin efectuar control de errores, dar el codigoC de las siguientes funciones

int Resta(int A, int B): devuelve la resta de dos enteros;

int Prod(int A, int B): devuelve el producto de dos enteros;

int Cociente(int A, int B): devuelve el cociente de dos enteros;

int Resto(int A, int B): devuelve el resto de dividir dos enteros;

int Pot(int A, int B): devuelve el valor de AB;

int Log(int A, int B): devuelve el valor de la parte entera de logA B.

35. (P) Si en el problema anterior se desea controlar posibles overflows, ¿como habrıa quemodificar los prototipos de las funciones? Implementar las correspondientes versiones Cde las rutinas en cuestion.

6

36. (E+) Para el TAD CC se propone usar como estructura de datos en C una tabla dedatos char de longitud fija LONGMAX. Definir el correspondiente tipo de dato CC y darel codigo C de las primitivas bool CCVacia(CC A), status CCIns(char c, int i, CC

A), status CCExt(char c, int i, CC A), status CCIni(CC A) y bool CCLlena(CC

A).

37. (E+) Sobre las primitivas del problema anterior, dar el codigo C del resto de las funcionesconsideradas anteriormente sobre el TAD CC.

Pilas

38. (P) Escribir el psc de una funcion de prototipo status CheckParChap(cadena str)

que compruebe si los parentesis de la cadena de caracteres str estan bien equilibradosutilizando para ello un contador de parentesis.

39. (P) Modificar el psc la funcion anterior construyendo otra de nombre CheckTodoChap

que mediante contadores compruebe el buen equilibrado de parentesis, corchetes y llaves.

40. (E) Sobre las sentencias siguientes, determinar la correccion del equilibrado de sımbolos{, (, [ mediante la evolucion de una pila:

1: ({[a+((b+c)-(d*e)+{h-g}]+{[b-a]*(f-i)}});

2: (a+[b*{c-{d+e/(f)}-g}]+(v-{w*(x+a)}));

41. (P) Escribir el psc de una funcion que reciba una cadena y la imprima mediante una pilaen forma invertida usando para ello las primitivas de este TAD.

42. (P) Escribir el psc de una funcion (o un conjunto de funciones) que proporcionen larepresentacion binaria de un int mediante el algoritmo de division repetida por 2 yacumulacion de restos (Pista: introducir los restos en una pila e imprimir su contenidohasta vaciarla).

Hacer lo mismo para las representaciones octales y hexadecimales.

43. (E+) Dar versiones mas compactas del codigo de las funciones primitivas de pilas discu-tidas en clase.

44. (E) Evaluar mediante pilas las siguientes expresiones sufijo:

5 4 3 2 1 * + 1 2 3 * / 2 * 1 / 2 + - + *;

1 2 * 4 2 / 3 4 + 5 * - +;

2 1 / 4 2 * + 6 5 - 8 2 / + +;

45. (P) Modificar el psc de la funcion de evaluacion mediante pilas de expresiones sufijodescrita en clase incluyendo cuidadosamente posibles condiciones de error.

Hacer tambien lo mismo con la funcion de conversion de expresiones infijo en sufijo.

46. (E) Convertir en sufijo las siguientes expresiones infijo segun las reglas de precedencia yasociatividad de operadores discutidas en clase:

7

A + B * C / D - F + G - H * I * J;

A * B * C / D / E - F * G + H - I;

47. (E) Convertir en sufijo las expresiones anteriores utilizando una pila (senalar adecuada-mente la evolucion de la misma).

48. (E) Escribir una funcion C de nombre Top que reciba un puntero a pila y devuelva eldato en su top sin efectuar un pop del mismo.

49. (E) El operador de exponenciacion suele denotarse como ^ (esto es, A ^ B = AB) y suprecedencia es superior a la de * y /. Convertir a sufijo las siguientes expresiones deacuerdo con las reglas habituales de precedencia y asociatividad:

A + B ^ C / D ^ F + G ^ H * I * J;

A * B * C ^ D ^ E - F * G + H ^ I;

50. (P) Ampliar el algoritmo de evaluacion de expresiones postfijo con respecto al operadorde exponenciacion ^ , que se considera de prioridad superior a * o /.

51. (P) ¿Como habrıa que modificar el algoritmo de conversion infijo–sufijo para que tengaen cuenta el uso de parentesis en la expresion infijo?

52. (E) Convertir a prefijo las siguientes expresiones infijo:

(a) A + B - C;

(b) (A + B) * (C - D);

(c) A ^ B * C - D + E / F / (G + H);

(d) ((A + B) * C - (D - E)) ^ (F + G);

(e) A - B / (C * D ^ E).

53. (E) A la vista del problema anterior, desarrollar un algoritmo de evalucion de expresionesprefijo, y evaluar las expresiones

(a) + - 1 2 3;

(b) + + 4 - * ^ 1 2 1 / + 5 6 * 7 8 9;

(c) + - ^ 2 2 2 * 3 * * 4 5 4.

54. (P) Desarrollar sobre ejemplos un algoritmo de conversion de expresiones postfijo a infijoy comprobarlo adecuadamente.

55. (P) Desarrollar sobre ejemplos un algoritmo de conversion de expresiones infijo a prefijoy comprobarlo adecuadamente.

56. (P) El siguiente pseudocodigo corresponde a una primera version de una rutina de eval-uacion de expresiones sufijo:

8

status EvalSufijo(CC S, valor V)

PilaIni(P) ;

mientras (op = LeerCC(S)) != EOS :

si EsOperando (op) == T :

Push (op, P) ;

else si EsOperador (op) == T :

Pop (op2, P) ;

Pop (op1, P) ;

res = Evaluar(op1, op, op2) ;

Push (res, P) ;

else

devolver Error ;

Pop (V, P) ;

si PilaVacia (P) == T :

devolver Ok;

else :

devolver Error ;

En el mismo,1. la funcion elemento LeerCC(CC S) lee un elemento de una cadena S;2. la funcion bool EsOperando(elemento op) devuelve T o F segun el elemento op seao no un operando;3. la funcion bool EsOperador(elemento op) devuelve T o F segun el elemento op seao no un operador;4. la funcion valor Evaluar (elemento op1, elemento op2, elemento op3) evaluael resultado de la operacion de acuerdo al operador y operandos indicados.

Modificar dicha rutina de manera adecuada para que procese correctamente posibles situa-ciones de error.

57. (P+) Una maquina tiene un unico registro y las siguientes cuatro instrucciones:

• LD A: coloca el contenido de A en el registro;

• ST A: coloca el contenido del registro en A;

• AD A: suma al valor en el registro el valor de A;

• SB A: resta al valor en el registro el valor de A;

Escribir un programa que acepte una expresion postfijo con los operadores +, - e imprimauna sucesion de instrucciones maquina que dejen en el registro el valor de la expresion.Por ejemplo, al recibir

A B C - +

el programa escribira

LD B

SB C

AD A

9

58. (E) Se quiere traducir a sufijo la expresion A + B * C ^ E - F / G; mediante una pila ysegun el algoritmo visto en clase. Leyendo esta expresion de izquierda a derecha, indicarrazonadamente y para cada operando u operador leıdos la evolucion de dicha pila, asıcomo la traduccion parcial efectuada hasta el momento de procesar cada operando uoperador.

59. (P) Una implementacion de pilas tiene como unico interfaz las funciones status PilaIni(pila

S), que inicializa una pila, boolean PilaVacia(pila S), que comprueba si una pila estavacıa, status Push(elemento E, pila S), que coloca el elemento E en la pila, y status

Pop(elemento E, pila S), que saca el elemento que ocupa el top (o la cima) de la pilay lo situa en el elemento pasado como parametro.

Dar razonadamente el pseudocodigo de una funcion de prototipo int PilaCuenta(pila

S) que reciba como parametro un pila como las descritas arriba, y devuelva su numero deelementos. Por supuesto, los datos de la pila pasada como parametro no deben alterarse,y la funcion debiera hacer el control de errores pertinente.

60. (P) Una implementacion de pilas tiene como unico interfaz las funcionesstatus PilaIni(pila S), que inicializa una pila,boolean PilaVacia(pila S), que comprueba si una pila esta vacıa,status Push(elemento E, pila S), que coloca el elemento E en la pila, ystatus Pop(elemento E, pila S), que saca el elemento que ocupa el top (o la cima)de la pila y lo situa en el elemento pasado como parametro.

Dar razonadamente el pseudocodigo de una funcion de prototipo status PilaPrimero(elemento

E, pila S) que situe en el dato E el primer elemento introducido en dicha pila.

Escribir primero una version simple de dicha funcion, que no efectue control de errores,para luego ampliarla con dicho control. Suponer para ello que un Push precedido de unPop sobre la misma pila no causa error.

Colas

61. (E) Se implementa una cola circular mediante un tabla de dimension 5 y se inicializadando a front y rear el valor 0. Ademas, si se intenta efectuar en la cola una operacionno factible, el programa de implementacion lo indica, pero permite continuar el trabajocon ella. Indicar la ubicacion de front y rear tras las siguientes operaciones, considerandosi pueden llevarse a cabo:

• dos Adds; dos Removes; tres Adds; un Remove; tres Adds; un Remove.

• dos Adds; un Remove; tres Adds; cuatro Removes.

62. (P) Una implementacion de colas tiene como unico interfaz las funcionesstatus ColaIni(cola Q),boolean ColaVacia(cola Q),status ColaIns(dato D, cola Q), que inserta el dato D en la cola, devolviendo OK oERR segun proceda, ystatus ColaExt(dato D, cola Q), que extrae el elemento inicial de la cola y situa sudato en D, devolviendo OK o ERR segun proceda.Ademas se dispone de un elemento especial FLAG, generalmente distinto de los almacena-dos en una cola, y que puede insertarse y extraerse de las mismas.

10

Suponiendo que una insercion precedida de una extraccion sobre la misma cola no causaerror, dar razonadamente el pseudocodigo de una funcion int ColaCuenta(cola Q) quereciba una cola sin ningun elemento FLAG y devuelva el numero de datos en la misma.Para ello

• dar una primera version sin control de errores;

• identificar posibles situaciones de error;

• dar una segunda version que detecte dichos errores y efectue la gestion y recuperacionadecuadas.

63. (P) De una implementacion del TAD Cola se dispone solamente de las primitivas statusColaIni(cola Q),bool ColaVacia(cola Q), status ColaInsertar(dato D, cola Q),status ColaExtraer(dato D, cola Q).

Definiendo el tipo dato como una estructura con dos campos de tipo int llamadosPrioridad y Valor insercion, dar el pseudocodigo de una funcion int InsertaConPrioridad(dato

D, cola Q) que actualize Q poniendo D detras de todos los datos con mayor o igual pri-oridad y delante de todos los datos con menor prioridad. Los elementos ya en la coladebe mantenerse tras la insercion en el mismo orden en el que se encontraban.

64. (P) Si se desea definir un TAD Cola de Prioridad, ¿cuales serıan las correspondientesprimitivas?

65. (P) Una implementacion de colas tiene como unico interfaz las funcionesstatus ColaIni(cola Q),boolean ColaVacia(cola Q),status ColaIns(dato D, cola Q), que inserta el dato D en la cola, ystatus ColaExt(dato D, cola Q), que extrae el elemento inicial de la cola y situa sudato en D,int ColaCuenta(cola Q), que devuelve el numero de elementos en la cola.

Dar razonadamente el pseudocodigo de una funcion de prototipo status JuntaColas(cola

A, cola B) que reciba dos tales colas A, B y modifique la primera situando a contin-uacion de su ultimo elemento los de la cola B (que debe de quedar vacıa si la union decolas se efectua con exito) en su orden propio. La funcion solo debe utilizar las primitivasanteriores y hacer el control y recuperacion de errores pertinente. Para ello

• dar una primera version sin control de errores;

• identificar posibles situaciones de error;

• dar una segunda version que detecte dichos errores y efectue la gestion y recuperacionadecuadas. Suponer para ello que una insercion precedida de una extraccion sobrela misma cola no causa error.

C avanzado

66. (Q) En C una tabla bidimensional se declara en la forma tipo ntb[dim1][dim2], dondetipo denota un tipo de dato C, ntb es el nombre de la tabla y dim1, dim2 son numerosenteros con las dimensiones de la tabla. Declarar

11

(a) una tabla bidimensional de datos float y dimensiones DIM1 y DIM2;

(b) una tabla bidimensional de punteros a datos char y dimensiones DIM1 y DIM2.

67. (Q) Una tabla bidimensional se almacena en memoria de tal manera que varıe mas rapidoel ındice mas a la derecha. ¿Cual serıa el orden de almacenamiento de los elementos dela tabla int tbi[2][3]? ¿Cuantos bytes requiere el almacenamiento de dicha tabla?

68. (Q) Supongamos declarada la tabla int tbi[3][2]; C la maneja como una “tabla detablas” en el sentido siguiente: tbi se interpreta como una tabla con 3 elementos, cadauno de los cuales es una tabla con 2 datos int. Por ejemplo, en la declaracion anteriortbi[2] es una tabla de 2 datos int.

Sobre el almacenamiento en memoria de la tabla int tbi[3][2], ¿a donde apuntantbi[0], tbi[1] y tbi[2]?

Expresar el contenido de tbi[j][k] en funcion de tbi[j] y de k.

69. (Q) Sobre la tabla anterior, expresar el valor designado como tbi[j] en funcion de tbi

y de j. ¿Como se expresarıa entonces tbi[j][k] en funcion de tbi, j y k?

70. (Q) Sobre la tabla anterior, dar expresiones equivalentes a &tbi[j], &tbi[j][k], tbi[0][0]

y &tbi[0][0].

71. (P) ¿Como se podrıa hacer que empezaran en 1 los ındices de una tabla bidimensionalde dimensiones M y N?

72. (E) Escribir una funcion C que reciba como argumento un puntero a un vector de datosgenericos y libere la memoria que este ocupe.

73. (P) Escribir una funcion C que reciba como argumento un entero n, reserve memoriapara un vector de floats de ese tamano y devuelva un puntero (esto es, el puntero es elretorno de la funcion) que permita trabajar con dicho vector en un rango de ındices entre1 y n.

74. (P) Escribir un programa C que lea un entero n, reserve mediante una funcion memoriapara dos vectores de dimension n, los lea, llame a una funcion que calcule su productoescalar, lo imprima y libere la memoria ocupada por ambos vectores. El programa debeconsiderar posibles condiciones de error.

75. (P) Escribir una funcion C que reciba como argumentos dos enteros m, n, y reservememoria para una matriz de floats de esas dimensiones de acuerdo al siguiente esquema:

i. se reserva memoria para un vector de m punteros a float, uno para cada una de lasfilas de la matriz;

ii. se reserva memoria para n vectores float guardandose los correspondientes punterosen el vector anteriormente definido;

la funcion debe devolver un puntero (identificar cual) que permita trabajar con dichamatriz segun la notacion habitual a[i][j].

76. (P) Escribir una funcion C que reciba como argumento un puntero a una matriz como ladel problema anterior y libere la memoria que ocupe.

77. (Q) Se define el siguiente macro del preprocesador:

12

#define max (A, B) ((A) > (B) ? (A) : (B))

¿Que problemas puede plantear esta definicion? (observese que supone una doble evalu-acion de las expresiones para A y B).

78. (E) La funcion calloc de la librerıa stdlib.h realiza las mismas funciones que malloc

pero inicializa a 0 los bytes de memoria reservados. Escribir una version de nombremicalloc que con el mismo prototipo que calloc efectue tambien sus mismas tareas.

¿Como se efectuarıa en las mismas el control de errores?

79. (P) Modificar la rutina push de la implementacion de pilas estaticas discutida en clasepara que en caso de que la pila este llena, recoloque sus datos en una pila de tamanoincrementado por una cantidad fija PILAINCR.

80. (P) En el modelo de pila del problema anterior, modificar la funcion pop para que ajusteel tamano de la pila al numero de datos existentes de manera que no esten en uso a losumo el doble de PILAINCR posiciones.

Listas

81. (E) Escribir variantes de la funcion GetNodoLE que1. o bien no reciban ningun argumento;2. o bien no devuelvan dato alguno.

82. (P) Definir macros en C para el acceso a los campos info y next de los nodos de unalista enlazada.

83. (E+) Implementar una funcion C que reciba un puntero a una lista y proporcione elnumero de nodos de una lista enlazada. Escribir primero su pseudocodigo y considerarposibles situaciones de error.

84. (E+) Implementar una funcion C que reciba dos punteros a listas enlazadas y devuelva unpuntero a una lista que concatene ambas. Escribir primero su pseudocodigo y considerarposibles situaciones de error.

85. (E+) Reescribir las funciones basicas sobre listas para su funcionamiento en listas circu-lares enlazadas.

86. (E+) Implementar una funcion que reciba un puntero a un nodo de una lista enlazadae intercambie dicho puntero con el que le sigue. Escribir primero su pseudocodigo yconsiderar posibles situaciones de error.

87. (E+) Implementar una funcion que reciba un puntero a un nodo de una lista doblementeenlazada e intercambie dicho puntero con su anterior. Escribir primero su pseudocodigoy considerar posibles situaciones de error.

88. (E) Implementar las primitivas del TAD cola usando como edd una lista enlazada circular.

13

89. (P) Flavio Josefo fue un famoso historiador del primer siglo. Aparentemente, su talentomatematico le permitio vivir lo suficiente para alcanzar la fama. En efecto, durante laguerra judeo–romana, Josefo formo parte de un grupo de 41 rebeldes judıos que fueroncercados por los romanos. Prefiriendo morir a rendirse, decidieron formar un cırculo yprocediendo en el sentido de las agujas de un reloj, matar a uno de cada tres rebeldeshasta que solo quedaran dos que, en teorıa, se suicidarıan entonces. Sin embargo, aJosefo y a un amigo suyo esta idea no les parecıa demasiado buena y decidieron situarseadecuadamente para ser los dos ultimos supervivientes. ¿Como podrıan Josefo y su amigohaber decidido las posiciones adecuadas de haber dispuesto de un ordenador (portatil) yde una implementacion en C de listas circulares enlazadas?

90. (P) Construir una funcion C que usando como edd una lista enlazada circular, recibados numeros N y M representando respectivamente un numero de rebeldes cercados,supuestamente numerados de 1 a N, y de cuanto en cuanto estos se rebeldes se matan(empezando por la primera posicion y en el sentido de las agujas del reloj); en el casodel problema clasico de Josefo la funcion recibirıa 41 y 3. La funcion debe imprimirlos numeros iniciales de los sucesivos muertos, ası como las posiciones originales de losrebeldes que no mueren (al menos de momento).

91. (E) En una lista circular enlazada inicialmente vacıa y apuntada por un puntero p seanaden sucesivamente nodos en su final. El campo info del nodo anadido en i–esimolugar contiene el valor i, donde i toma los valores 1, 2, 3, etc.

Dar dos diagramas que recojan el estado del puntero p y de los nodos con sus camposinfo y next tras la insercion del primer nodo y del cuarto nodo.

92. (E) En una lista circular doblemente enlazada inicialmente vacıa y apuntada por unpuntero p se anaden sucesivamente nodos en su final. El campo info del nodo anadidoen i–esimo lugar contiene el valor i, donde i toma los valores 1, 2, 3, etc.

Dar dos diagramas que recojan el estado del puntero p y de los nodos con sus camposinfo, prev y next tras la insercion del primer nodo y del cuarto nodo.

93. (E+) Escribir funciones C de nombres LeInsHead, LeInsTail, LeDelHead y LeDelTail

que implementen las correspondientes primitivas para listas enlazadas.

94. (E+) Escribir funciones C de nombres LdeInsHead, LdeInsTail, LdeDelHead y LdeDelTail

que implementen las correspondientes primitivas para listas doblemente enlazadas.

95. (P) Escribir funciones C que inserten un dato en el lugar i–esimo de una lista enlazada,y tambien que lo extraigan del mismo.

96. (P) Escribir una funcion C que intercambie el nodo i–esimo con el que le sigue.

97. (P) Dar versiones de las funciones anteriores para listas doblemente enlazadas.

98. (E+) Escribir una funcion C que reciba un puntero a una lista enlazada e intercambie lasposiciones de sus nodos primero y ultimo. Escribir primero su pseudocodigo y considerarposibles situaciones de error.

99. (P) Escribir una funcion C que reciba un puntero a una lista doblemente enlazada eintercambie las posiciones de sus nodos primero y ultimo.

Escribir primero su pseudocodigo y considerar posibles situaciones de error.

14

100. (P) Escribir una funcion C de nombre LeReset que reinicialice una lista enlazada.

101. (P) Escribir una funcion C de nombre LdeProcInv que recorra una lista circular doble-mente enlazada en sentido inverso y sobre cada nodo haga actuar una cierta funcion, quese pasara a LdeProcInv mediante un puntero a funcion.

102. (E+) Escribir razonadamente una funcion C de prototipo int ListaCuenta(listaC

*lc) que reciba un puntero lc a una lista enlazada circular y devuelva su numero denodos.

Utilizar la siguiente implementacion de nodos y listas enlazadas, suponiendo que un pun-tero del tipo listaC apunta al ultimo nodo de una tal lista.

typedef struct NODO {

generico info;

struct NODO *next;

} nodo;

typedef nodo *listaC;

Arboles

103. (Q) Escribir funciones C que implementen la insercion de un dato en un arbol binario debusqueda, la creacion de un arbol binario de busqueda y la busqueda en un tal arbol deun dato con una clave dada de acuerdo a la implementacion de arboles binarios dada enclase y a los correspondientes pseudocodigos.

104. (E) Dada la lista de enteros

34 43 12 58 17 92 21 67 56 72 80,

dibujar su correspondiente arbol binario de busqueda. ¿Que posiciones ocuparıan losenteros

41 77 30

tras su insercion?

105. (E) Escribir funciones C que implementen el recorrido de un arbol binario en ordenesposterior y simetrico.

106. (Q) Escribir una funcion C de prototipo ab CombinaAB(generic *pg, ab t1, ab t2)

que reciba dos arboles binarios t1, t2 y devuelva un arbol con t1 como nodo izquierdo,t2 como nodo derecho y *pg en su campo info.

107. (E) Definir macros en C para el acceso a los campos info y next de los nodos de unalista enlazada.

15

108. (E) Dadas las expresiones(A + B) * (C - D)

A ^ B * C - D + E / F / (G + H)

((A + B) * C - (D - E)) ^ (F + G)

A - B / (C * D ^ E),construir sus respectivos arboles de expresion y recorrerlos en ordenes simetrico, previo yposterior.

109. (E) Construir el arbol de expresion de las siguientes expresiones sufijo:A B C * D - E F / G / - *

A B + C D - / E F * G - -

A B C D - - E F G + + * *

110. (P) Sobre los ejemplos anteriores disenar un algoritmo de construccion de arboles asoci-ados a expresiones sufijo.

111. (P) Un arbol binario se recorre en nivel si sucesivamente se recorren de izquierda aderecha los nodos a profundidades 0, 1, 2, etc. Dar el pseudocodigo de una funcionNivel(arbol T) que implemente esta forma de recorrido (sugerencia: utilizar una cola ala que se anadan los hijos de un nodo dado tras visitarlo).

112. (P) Un arbol binario se recorre en preorden y proporciona la lista

G B Q A C K F P D E R H;

dibujar una posible estructura de nodos. ¿Hay mas?

113. (E+) Un arbol binario se recorre en simorden y proporciona la lista

Q B K C F A G P E D H R

dibujar posibles estructuras de nodos.

114. (E) Construir el arbol binario de busqueda a partir de las listas siguientesG B Q A C K F P D E R H,15 22 12 35 31 13 10 27 6 9 25.

115. (E) En un arbol binario de busqueda se define el predecesor de un dato D como el mayordato D’ del arbol tal que D’ < D. Sobre los arboles del problema anterior, encontrar lospredecesores de cada uno de sus elementos.

116. (E) En un arbol binario de busqueda se define el sucesor de un dato D como el menordato D’ del arbol tal que D’ > D. Sobre los arboles del problema anterior, encontrar lossucesores de cada uno de sus elementos.

117. (P) Dar el pseudocodigo de funciones que reciban un dato de un arbol binario y encuen-tren su predecesor y su sucesor.

118. (Q) Dar el codigo de una funcion C para buscar un dato en un arbol binario de busqueda.

16

119. (E) Un arbol binario puede usar como edd una tabla con 1 como primer ındice segun elsiguiente esquema:

en el la raız se ubica en la posicion 1, sus hijos en 2 y 3, los hijos respectivos en 4, 5 y 6,7, etc. Comprobar que, en general, los hijos del nodo de ındice k se hallan en los ındices2k y 2k + 1.

120. (P) Suponer que los elementos de la tabla del problema anterior son structs, uno decuyos campos indica si el nodo esta o no vacıo, y que no hay nodos mas alla de la dimensionTREESIZE de la tabla, que supondremos de la forma 2K − 1. ¿Como se implementarıancon esta edd las operaciones primitivas del tad arbol binario?

121. (P) Con la implementacion del tad arbol binario anterior, escribir funciones C que de-vuelvan el numero de nodos, la profundidad del arbol binario y el numero de hojas. Dartambien una funcion C que reciba un ındice de un nodo de tal tabla y devuelva el ındicedel padre de dicho nodo.

Recursion

122. (E+) Identificar en que rutinas de recorrido de arboles hay recursiones de cola, eliminarlas que haya y simplificar al maximo el codigo resultante.

123. (Q) Dar una definicion recursiva de arbol binario de busqueda.

124. (P) Escribir una funcion C que calcule la profundidad de un arbol binario.

125. (E+) Sobre el pseudocodigo de la funcion InsABdB, eliminar posibles recursiones de colay simplificar al maximo el pseudocodigo resultante.

126. (Q) Escribir una funcion recursiva en C que reciba un dato generico y un arbol binariode busqueda y devuelva un puntero al subarbol en cuya raız esta dicho dato o senaleadecuadamente que no hay tal subarbol.

127. (P) Eliminar posibles recursiones de cola en la funcion anterior y simplificar todo loposible el codigo resultante.

128. (P) Los numeros de Fibonacci se definen mediante la formula recurrente

F0 = 0; F1 = 1; Fn = Fn−1 + Fn−2, n > 1.

Escribir una funcion recursiva y otra iterativa en C que reciban n y devuelvan Fn.

17

129. (P) Supongamos que los conejitos se hacen adultos en un mes y que una pareja de conejosadultos, sea cual sea su sexo, producen una pareja de conejitos al mes. Si dos conejosadultos naufragos llegan a una isla desierta, ¿cuantas parejas de conejos habra en la islatras N meses? (por ejemplo, tras dos meses habra dos parejas, una de conejitos y otra deconejos adultos).

130. (P) Simplificar todo lo que sea posible la version no recursiva de la funcion factorial dadaen clase (eliminar gotos, simplificar la pila, etc).

131. (P) Dar una version no recursiva de las torres de Hanoi mediante una pila de maneraanaloga a la version no recursiva de la funcion factorial dada en clase.

132. (P) A partir de la funcion recurrente de impresion de los movimientos de las torres deHanoi, estimar el numero de movimientos necesarios para mover N discos.

133. (Q) Suponiendo que, en efecto, Brahma entrego a los monjes de Hanoi 64 discos alcomienzo de los tiempos, que el mundo acabara cuando todos los discos lleguen al postede destino y que los monjes hacen un movimiento correcto por segundo, ¿cual sera aprox-imadamente la duracion del mundo?

134. (Q) Modificar las funciones basicas sobre listas utilizando la implementacion del datolista obtenido de la definicion recursiva de la misma.

135. (Q) Dar una definicion recursiva de expresion prefijo.

136. P+ Escribir el pseudocodigo de una funcion recursiva que reciba una expresion prefijo yla convierta en sufijo.

137. (E+) Escribir una funcion C que implemente una version recursiva del algoritmo deEuclides de determinacion del maximo comun divisor de dos enteros positivos.

138. (E+) Escribir funciones recursivas en C que calculen el producto y el cociente de dosenteros positivos.

139. (E+) Escribir una funcion recursiva en C que reciba dos enteros positivos X, N y calculeel valor de XN.

140. (E+) En las funciones de los problemas anteriores identificar posibles recursiones decola, eliminarlas y depurar lo mas posible el codigo resultante (en particular, eliminarsentencias goto).

141. (E+) Identificar y eliminar posibles recursiones de cola en el algoritmo recursivo debusqueda binaria explicado en clase.

142. (P) Eliminar mediante una pila la recursion de las funciones anteriores de calculo deproductos y cocientes, y depurar al maximo el codigo resultante.

143. (P) El siguiente pseudocodigo corresponde a una funcion recursiva de multiplicacion dedos enteros positivos:

18

int MultRec(int A, int B)

si B == 0 :

devolver 0 ;

else :

devolver A + MultRec(A, B-1) ;

Suponiendo que sus argumentos son siempre mayores o iguales que 0, eliminar la recursionde la misma mediante los tres pasos siguientes:

a. Efectuar una eliminacion mecanica mediante sentencias goto

b. Eliminar las sentencias goto del codigo del apartado anterior.

c. Modificar el codigo del apartado b hasta llegar a una funcion iterativa con la mismafuncionalidad

144. (P) Sobre la implementacion habitual de arboles binarios, el siguiente pseudocodigo sirvepara intercambiar los hijos izquierdo y derecho de todos los subarboles de un AB T:

CambIzqDer(AB T)

si ABVacio(T) == F :

abTemp = izq(T) ; //abTemp: variable temporal

izq(T) = der(T) ;

der(T) = abTemp ;

CambIzqDer(izq(T)) ;

CambIzqDer(der(T)) ;

Eliminar mediante pilas la recursion de la misma de acuerdo a los pasos siguientes:

a. Definir el elemento de pila y efectuar una eliminacion mecanica mediante sentenciasgoto

b. Eliminar las sentencias goto del codigo del apartado anterior.

19

Problemas de repaso

145. Al igual que lo explicado para tablas bidimensionales, una tabla multidimensional en C secontempla como una tabla de tablas de tablas, etc. Por ejemplo, en char tmdc[2][3][2],tmdc es una tabla con 2 elementos, que a su vez son tablas con 3 elementos, que a su vezson tablas de 2 datos char. ¿Como se almacena en memoria dicha tabla?

146. Dar en funcion de tmdc, i, j y k expresiones equivalentes de tmdc[i], tmdc[i][j] ytmdc[i][j][k]. ¿Que ocurre cuando i=j=k=0?

147. En C una tabla de punteros se declara como tipo *tp[dim]. Un programa concretocontiene las declaraciones

int tbdi[5][10];

int *tpi[5];

¿Como se podrıa utilizar tpi para manejar datos en tbdi[j][k]?

148. Un cierto compilador C proporciona a char e int los tamanos 1 y 2, respectivamente.¿Que produce el siguiente codigo C?

int i,j;

int tbi[10][10];

int *tpi[10];

int **ppi;

ppi=tpi;

for (i=0; i<10; i++)

{

tpi[i]=tbi[i];

for(j=0; j<10; j++)

tbi[i][j]=i+j;

}

printf("%d %d %d \n", **(ppi+1), *(*(ppi+2)+3),

*((char *)(*(ppi+3)) + 8));

149. Un programa de graficos maneja puntos del plano como pares de floats, y tambiencircunferencias, que caracteriza mediante un punto, su centro, y un float, su radio.

(a) Definir razonadamente un tipo de dato C circunf para las circunferencias.

(b) Escribir una funcion C que modifique un dato circunf multiplicando su radio porun factor de dilatacion contenido en una variable dilat.

150. Escribir una funcion C de nombre esint que reciba una cadena de caracteres y unadireccion de variable int, compruebe si dicha cadena corresponde efectivamente a undato int, situe su valor en la direccion recibida y devuelva un codigo status (Sugerencia:usar la funcion sscanf).

Escribir funciones analogas esfloat y esdouble para estos tipos de datos.

20

151. ¿Que hace este programa? ¿Para que sirve? Incluso despues de conocer la especificacioncorrespondiente, es decir, el enunciado del problema que resuelve, imagınate el trabajoque serıa si te dijeran que hay un error y que tu tienes que arreglarlo, o que hay quemodificarlo para que ahora haga mas cosas.

#include <stdio.h>

main () {int v1,res; int li,il,ncrt;

li=0; il=300; ncrt=20;

v1=li; while (v1<=il){res=5*(v1/9-3.5555);

printf("%d\t%d\n",v1,res); v1=v1+ncrt;}}

152. Lo siguiente es otra version del mismo programa. Mucho mejor, pero todavıa incumplealgunas guıas para la buena programacion. ¿Cuales?

#include <stdio.h>

main ()

{int fahr, celsius;

int lower, upper, step;

lower = 0; upper = 300; step = 20; fahr = lower;

while (fahr <= upper) {

celsius = 5 * (fahr - 32) / 9;

printf("%d\t%d\n", fahr, celsius);

fahr = fahr + step;}

}

153. La siguiente version esta muchısimo mejor ¿verdad? Pero todavıa es mejorable. ¿Como?

#include <stdio.h>

/* Imprime una tabla de conversion de temperaturas

entre escalas Fahrenheit y Celsius, para valores

Farenheit = 0, 20, 40, ... 300 */

main ()

{

int fahrenheit, celsius;

int lower, upper, step;

lower = 0; /* limite inferior de temperaturas fahrenheit en la tabla */

upper = 300; /* limite superior idem. */

step = 20; /* incremento de valores fahrenheit en tabla */

fahrenheit = lower;

while (fahrenheit <= upper) {

/* conversion de fahrenheit a celsius */

celsius = 5 * (fahrenheit - 32) / 9;

/* imprimir una fila de la tabla */

printf("%d\t%d\n", fahrenheit, celsius);

21

/* avanzar a la siguiente temperatura fahrenheit */

fahrenheit = fahrenheit + step;

}

}

154. El primer programa hace algunas (no todas) las conversiones incorrectamente, sacandoun grado Celsius de menos. ¿Por que? Modifica uno de esos programas para que:

• los lımites y el incremento de la tabla se lean de la entrada estandar

• los lımites y el incremento de la tabla se tomen como argumentos del programaprincipal

• se utilice un bucle for en vez de un while

• la conversion de cada temperatura se haga llamando a una funcion

• se utilicen el menor numero posible de variables

• ...

155. Las matrices en C pueden inicializarse sin mas que anadir a su declaracion una relacion devalores iniciales dados en el orden habitual de almacenamiento de datos en tablas. Decircual es la salida del siguiente programa C:

void main()

{

int B[5][3]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};

int *pi[5];

int *pp;

int x;

pp = B[0];

x = (int) *( (int *) pp+2 ) + 2; printf("4.1 %d\n", x);

x = (int) *( (char *) pp + 6 ) + 3; printf("4.2 %d\n", x);

pi[1]= B[1];

x = (int) *pi[1]; printf("4.3 %d\n", x);

x = *(pp + 9); printf("4.4 %d\n", x);

x = *(B[4]+ 1); printf("4.5 %d\n", x);

}

156. a. Indicar razonadamente que devuelve el operador sizeof al aplicarse al tipo de datostipoRaro definido como sigue

typedef struct TIPORARO {

char miembro1;

int miembro2;

float miembro3;

} tipoRaro;

b. Indicar razonadamente si el siguiente codigo C es correcto o incorrecto:

22

float tf1[10], tf2[20];

tf1 = tf2;

c. Se ha definido un tipo de dato circunf como sigue

typedef struct CIRCUNF {

struct PUNTO {

float X, Y ;

} centro ;

float radio ;

} circunf ;

Escribir una funcion C que reciba un dato circunf y un dato float factor y que devuelvael area de una circunferencia obtenida dilatando el radio de la recibida segun el valor defactor.

157. Un programa C contiene las lıneas

int i, j;

int ti[20][20], *tpi[20], **ppi1, **ppi2;

for (i=0; i<20; i++) {

for (j=0; j<20; j++)

ti[i][j] = 100*i+j;

tpi[i] = ti[i];

}

ppi1 = tpi;

ppi2 = tpi+1;

a. Sabiendo que un dato char ocupa 1 byte y que uno int 2, dar razonadamente losvalores de las dos expresiones*((int *) ((char *) *(ti + 3) + 16)), y*(*(ppi2 + 3) + 4).(Si se desea, utilizar las expresiones equivalentes *((int *) (((char *) (*(ti + 3)))

+ 16)), y *((*(ppi2 + 3)) + 4).)

b. Escribir razonadamente el prototipo y el cuerpo de una funcion C de nombre ppiSwap

que intecambie el contenido de las variables ppi1, ppi2. ¿Como habrıa que llamar adicha funcion para intercambiar ppi1, ppi2?

158. Una implementacion de pilas tiene como unico interfaz las funcionesboolean PilaVacia(pila S),status Push(elemento E, pila S), que coloca el elemento E en la pila, ystatus Pop(elemento E, pila S), que situa el elemento en el top de la pila en el ele-mento E.Se supone que esta implementacion garantiza que tras una serie de Pops de una pila dada,siempre se puede efectuar el mismo numero de Push sobre la misma.

23

Dar razonadamente el pseudocodigo de una funcion de prototipo status JuntaPilas(pila

A, pila B) que reciba dos tales pilas A, B y modifique la primera apilando encima suyoy en el orden de salida de pilas los elementos de la segunda (que naturalmente ha dequedar vacıa). Seguir estos pasos:

1. dar una primera version que no efectue control de errores;2. dar una segunda version que efectue el control de errores necesario.

Identificar sobre la primera version posibles fuentes de error y justificar la correccion quese les de.

159. a. Indicar mediante una pila y sobre cada uno de los caracteres leıdos la evolucion delalgoritmo de conversion de expresiones infijo a sufijo sobre la expresion(A + B) ^ C - (D - E) * (F + G).

b. Construir razonadamente el arbol de expresion de la siguiente expresion sufijoA B + C * E ^ F G / -

utilizando para ello una pila e indicando su estado en los correspondientes pasos.

c. Construir razonadamente el arbol binario de busqueda asociado a la lista 24 33 2 47

7 13 41 51, y dar el resultado de su recorrido en orden previo y posterior.

160. 1. Convertir a sufijo mediante el algoritmo explicado en clase la expresion (A + B) * (C

- D ^ E) indicando en cada paso el estado de la pila a utilizar.2. Construir el arbol de expresion asociado a la siguiente expresion sufijo A B + C D E ^

F + - * utilizando, de acuerdo con el algoritmo explicado en clase, una pila de punterosa arboles de expresion e indicando en cada paso el estado de la misma.

161. Se tiene una implementacion de listas circulares enlazadas donde sus nodos tienen camposinfo y next, y donde un dato L de tipo lista apunta al ultimo nodo de la misma.Dar el pesudocodigo de una funcion status ListaExtFin(dato D, lista L) que situeen el dato D el contenido del campo info del ultimo nodo y elimine el mismo. Dar unesquema con los pasos efectuados por la funcion en el orden adecuado.

162. 1. Dada la lista [10, 6, 15, 3, 8, 12, 19], construir su arbol binario de busquedaasociado, indicando su evolucion mediante el estado del arbol tras cada insercion.2. Dar razonadamente el recorrido de dicho arbol en orden previo.

163. Dar el prototipo y el codigo de una funcion C de nombre IntMatAlloc que reciba unpar de ints M, N y reserve memoria para una matriz M×N de ints segun el siguienteesquema:1. se reserve memoria para una tabla de M punteros a int;2. en cada uno de estos punteros se situe la direccion de una tabla de N ints, cuyamemoria debera ser tambien reservada.La funcion debe devolver la direccion del primer elemento de la tabla del apartado 1, ydebe efectuar el control de errores pertinente.

164. El logaritmo binario lg satisface lg(N) = 1 + lg(N/2). Utilizar este hecho para dar elpseudocodigo de una funcion recursiva int LogBinEnt(int N) que devuelva la parte en-tera del logaritmo binario de un entero N, esto es LogBinEnt(N) = blg(N)c (por ejemplo,LogBinEnt(3) = 1).

24

165. Se quiere eliminar usando una pila la recursion en la siguiente funcion para el calculo delnumero de nodos de un arbol binario:

int NumNodos(AB T)

si ABVacio(T) == V:

devolver 0;

else:

I = NumNodos(izq(T)); D = NumNodos(der(T));

devolver I+D+1;

Decidir razonadamente que datos guardar en la pila (suponer un mecanismo tipo struct

para su almacenamiento) y eliminar sus llamadas recursivas dando en primer lugar unaversion que use goto y eliminando luego tales sentencias.

166. Se dispone de una funcion C de prototipo int **IntMatAlloc(int M, int N que reservamemoria para una matriz M×N de ints segun el siguiente esquema:1. se reserva memoria para una tabla de M punteros a int;2. en cada uno de estos punteros se situa la direccion de una tabla de N ints, cuyamemoria tambien se reserva.Los posibles errores en dicha funcion se senalan devolviendo NULL.Dar el codigo de una funcion C de prototipo int **IntMatSuma(int **A, int **B,

int M, int N) con A, B matrices de enteros definidas segun el esquema anterior, y siendosus dimensiones ints M, N y devuelva una nueva matriz con la suma de las recibidas. Lafuncion debera hacer el control de errores pertinente.

167. Dada la expresion sufijo A B C + D ^ E + F * + G * H ^,a. dar la expresion prefijo equivalente;b. construir su arbol de expresion.

En cada caso, se seguiran los algoritmos descritos en clase, y se indicara en cada paso elestado de la pila a utilizar, ası como los criterios empleados en cada paso para almacenary extraer datos de la pila.

168. Se tiene una implementacion de listas circulares doblemente enlazadas cuyos nodos tienencampos info, prev y next, y donde un dato de tipo lista es exactamente un puntero alprimer nodo de la lista.Dar el pseudocodigo de una funcion status InsertarFinal(dato D, lista L) queanada un nodo al final de la lista, almacenando D en el campo info de dicho elemento.Dar un esquema con los pasos efectuados por la funcion en el orden adecuado.

169. Dar el pseudocodigo de una funcion recursiva de prototipo int Eval(AB T) que tomacomo parametro la representacion en forma de arbol binario de una expresion aritmeticacuyos nodos contienen valores enteros u operadores, y devuelve el valor entero resultantede evaluar dicha expresion.

Suponer la existencia de una una funcion dato Info(AB T) que devuelve el dato alma-cenado en la raız de un arbol binario T y de otra funcion booleana EsOperador(dato D)

que devuelve V si el dato D es un operador y F si es un operando. Para simplificar elcodigo, no efectuar control de errores.

25

170. Mediante el uso de una pila, se quiere eliminar eliminar la recursion en la siguiente funcionpara el recorrido en orden medio de un arbol binario:

void SimOrden(AB T)

si T == NULL :

volver ;

else :

SimOrden(izq(T)) ;

imprimir info(T) ;

SimOrden(der(T)) ;

Decidir razonadamente que estructura de datos guardar en la pila, y eliminar sus llamadasdando en primer lugar una version que use goto y eliminando luego tales sentencias.

171. De una implementacion del TAD Cola se disponen las primitivas status ColaIni(cola

Q),bool ColaVacia(cola Q), status ColaIns(dato D, cola Q), status ColaRem(dato

D, cola Q).Dar el pseudocodigo de una funcion int ColaNumElem(cola Q) que devuelva el numerode elementos en la cola Q sin alterar, por supuesto, el estado de la misma (10 puntos).

172. De una implementacion del TAD Cola se dispone solamente de las primitivas status

ColaIni(cola Q),bool ColaVacia(cola Q), status ColaInsertar(dato D, cola Q),status ColaExtraer(dato D, cola Q).

Definiendo el tipo dato como una estructura con dos campos de tipo int llamadosPrioridad y Valor insercion, dar el pseudocodigo de una funcion int InsertaConPrioridad(dato

D, cola Q) que actualize Q poniendo D detras de todos los datos con mayor o igual pri-oridad y delante de todos los datos con menor prioridad. Los elementos ya en la coladebe mantenerse tras la insercion en el mismo orden en el que se encontraban.

173. Un programa C contiene las lıneas

int i, j;

int t[3][2], *tp[3], **pp;

for (i=0; i<3; i++) {

for (j=0; j<2; j++)

t[i][j] = 10*i+j;

tp[i] = t[i];

}

pp = tp-1;

a. Sabiendo que un dato char ocupa 1 byte y que uno int ocupa 2 consecutivos, darrazonadamente los valores de las dos expresiones*((int *) ((char *) *(tp + 1) + 2)), y*(*(pp + 1) + 3).

b. Escribir razonadamente el prototipo y el cuerpo de una funcion C de nombre ppa0 queincremente en 1 el valor almacenado en la variable pp.

26

174. Escribir razonadamente una funcion C de prototipo status ListaDelIni(lista *pl,

int *pd) que elimine el primer nodo de una lista enlazada circular apuntada por pl,almacenando el dato en dicho nodo en la variable apuntada por pd.

Dar para ello un esquema que recoja la situacion inicial de la lista, su situacion final, eindique los pasos realizados.

Utilizar la siguiente implementacion de nodos y listas:

typedef struct NODO {

int info;

struct NODO *next;

} nodo;

typedef nodo *lista;

175. Se quiere traducir a sufijo mediante una pila la expresion (A + B) * C ^ (E - F/G),donde se supone que el operador de exponenciacion ^ tiene prioridad mayor que los demasoperadores . Leyendo esta expresion de izquierda a derecha, indicar razonadamente y paracada operando u operador leıdos la evolucion de dicha pila, ası como la traduccion parcialefectuada para cada elemento leıdo.

176. La funcion de Ackermann se define como

A(0, n) = n+1; A(m, 0) = A(m−1, 1),m > 0; A(m,n) = A(m−1, A(m,n−1)),m > 0, n > 0.

Escribir una funcion C con un procedimiento iterativo para el calculo de esta funcion yotra con un procedimiento recursivo.

177. a. Dar sobre una pila la evolucion de la traduccion a sufijo de la expresion(A * B ^ C) / (D - E) ;

indicando para cada elemento leıdo la traduccion parcial y el estado de la pila.

b. Dar la evolucion de la construccion del arbol de expresion asociado a la expresion sufijoA B C + - E F * G / ^

indicando para cada elemento leıdo la traduccion parcial y el estado de la pila de punteros.

c. Sobre el arbol obtenido en el apartado (b), dar la expresion prefijo equivalente a laexpresion sufijo de dicho apartado.

178. Dar razonadamente el codigo de una funcion C void ListaLiberar(lista *pl) quereciba una lista enlazada circular y libere toda la memoria ocupada por la misma.

Indicar en un diagrama los pasos a efectuar y utilizar la siguiente implementacion denodos y listas:

typedef struct NODO {

int info ;

struct NODO *next ;

} nodo;

typedef nodo *lista ;

27

179. Una funcion C tiene el siguiente prototipoint *algo(int *pa, int **ppb).¿Como habrıa que llamarla para pasarle unas variables declaradas como int **ppa,

*pb; como argumentos primero y segundo respectivamente?¿Y como se harıa dicha llamada para que el orden de los argumentos anteriores fuera alreves?

180. Dar el codigo de una funcion C void CambiaIzqDer (ab t) que reciba un dato arbolbinario e intercambie los hijos izquierdo y derecho de cada uno de sus nodos.

Utilizar la siguiente implementacion de nodos y arboles:

typedef struct NODOAB {

int info ;

struct NODOAB *izq ;

struct NODOAB *der ;

} nodoAB ;

typedef nodoAB *ab ;

181. i. Se quiere utilizar la busqueda binaria para encontrar la clave 4 en la tabla 1 2 3 5 6

7 8. Indicar paso a paso contra que elementos de la tabla se comparara el valor 4 y sobreque subtablas se hacen las sucesivas busquedas.

ii. sobre la cola circular Q del esquema inferior se efectuan las siguientes operaciones: a.ColaIns(3, Q); b. ColaRem(A, Q); c. ColaIns(4, Q); d. ColaIns(5, Q).

R F2 1

Indicar para cada operacion la posicion de front y rear y el estado de la cola. ¿Cual es elvalor final de la variable A?

iii. Construir el arbol binario de busqueda asociado a la lista 6 16 3 4 9 31 1 8 2 7

indicando el estado del mismo tras cada insercion.

182. Para una implementacion de pilas dinamicas se utiliza el siguiente tipo C:

typedef struct PILA {

int top ; // primera posicion ocupada

int numElem ; // num. elementos en un momento dado

generic *pg ;

} pila;

a. Utilizando la funcion malloc, dar el codigo C de una funcion status PilaIni(pila

*ps, int numDatos) que inicialize una tal pila con espacio suficiente para almacenarnumDatos elementos.

b. Se quiere escribir una funcion de nombre PilaReset que libere la memoria ocupadapor una pila del tipo anterior. ¿Que datos podrıa recibir y devolver dicha funcion? Darsu prototipo y escribir su codigo C.

28

183. En una implementacion de arboles binarios, se utilizan info(T) para obtener el valor ensu campo info, y izq(T), der(T) para acceder a sus subarboles izquierdo y derecho. Sedispone tambien de una funcion int NumElem(T) que devuelve el numero de nodos de unarbol T y de otra bool ABVacio(T) que devuelve V o F segun T este o no vacio.

Dar razonadamente el pseudocodigo de una funcion int NumElemMen(T, K) que devuelveel numero de nodos de un arbol binario de busqueda T cuyos campos info son menoreso iguales que la clave K.

184. a. Traducir a sufijo la expresion inferior indicando para cada uno de sus elementos latraduccion parcial de la expresion y el estado de la pila en ese momento.

(A * B) ^ (C + D) * E ^ F

b. Construir el arbol de expresion de la expresion sufijo inferior, indicando para cada unode sus elementos el estado de la pila usada para gestionar dicha traduccion.

A B - C / D ^ E F * +

c. Suponiendo que el 1 es el primer elemento y 3 el ultimo, indicar la evolucion de la colacircular Q cuyo estado se refleja en el diagrama inferior tras las siguientes operaciones:

i) ColaIns(4, Q); ii) ColaExt(D, Q); iii) ColaExt(D, Q);iv) ColaIns(5, Q); v) ColaIns(6, Q); vi) ColaIns(7, Q).

1 2 3

185. Dar el codigo de una funcion C que reciba una tabla de N doubles en memoria dinamica,duplique su memoria, copie por duplicado en la nueva tabla cada elemento de la tablaoriginal, libere la memoria de la primera tabla y devuelva un puntero a la nueva tabla.

Por ejemplo, una tabla [a b c] ha de transformarse en [a a b b c c].

186. Escribir razonadamente una funcion C de prototipo int InsPenultimo(listaC lc) quereciba una lista enlazada circular lc e inserte un nuevo nodo antes del situado inicialmenteen ultimo lugar o indique que dicha insercion no ha sido posible.

Dar un diagrama indicativo de los datos implicados y utilizar una funcion

nodo *getNodo()

de obtencion de un nuevo nodo y la siguiente implementacion de nodos y listas enlazadas,suponiendo que un puntero del tipo listaC apunta al ultimo nodo de una tal lista.

typedef struct NODO {

generico info;

struct NODO *next;

} nodo;

typedef nodo *listaC;

187. Una implementacion de pilas tiene como UNICO interfaz las funcionesstatus PilaIni(pila S), que inicializa una pila,boolean PilaVacia(pila S), que comprueba si una pila esta vacıa,status Push(elemento E, pila S), que coloca una copia del elemento E en la pila, y

29

status Pop(elemento E, pila S), que saca el elemento que ocupa el top (o la cima)de la pila y lo situa en el elemento E pasado como parametro.

Dar el pseudocodigo de una funcion status swapPU(pila P) que reciba una pila P y latransforme situando en su top el elemento que entro en primer lugar y en su fondo elelemento que ocupaba el top al llamar a la funcion. Todos los demas elementos, si loshay, deberıan quedar en el mismo orden en que estaban en la pila original.

Efectuar para ello los siguientes pasos: dar una primera version sin control de errores,indicar en que puntos de la misma puede haberlos y modificar finalmente la version inicialcon el control y correccion de errores pertinente. Para simplificar el problema:1. Suponer que un Push precedido de un Pop no causa errores.2. Suponer que la pila tiene 2 o mas elementos.

188. a. Traducir a sufijo la expresion (A ^ B * C) ^ (D - E) ; indicando para cada uno desus elementos la traduccion parcial de la expresion y el estado de la pila en ese momento.

b. Construir el arbol de expresion asociado a la expresion sufijo A B ^ C + D * E F ^

*, indicando en cada paso el estado de los elementos implicados.

c. Construir el ABdB asociado a la lista 16 23 12 37 32 14 11 28 indicando en cadapaso el estado parcial del mismo. Una vez construido, recorrerlo en orden previo y pos-terior.

189. Escribir el pseudocodigo (y NO el codigo C) de una funcion recursiva limpia(lista le,

dato D) que reciba una lista enlazada le y la modifique para que solamente contenganodos cuyos valores info sean menores que el argumento D. Suponer para ello que seidentifica una lista con un puntero a su primer nodo, que NULL indica una lista vacia, yla disponibilidad de las siguientes instrucciones:info(le) devuelve el campo info del nodo apuntado por le;next(le) devuelve un puntero del nodo siguiente a le;del(le) elimina el nodo apuntado por le.

190. El pseudocodigo inferior corresponde al recorrido en orden Posterior de un arbol binario.Eliminar las llamada recursivas del mismo efectuando los siguientes pasos:a. Indicar la estructura del elemento de pila a utilizar.b. Efectuar una primera eliminacion mecanica utilizando si es preciso sentencias goto.c. Dar finalmente un codigo sin sentencias goto.

postOrden(AB T)

si ABVacio(T) == F :

preOrden(izq(T)) ;

preOrden(der(T)) ;

visitar(T) ;

191. Una implementacion de colas tiene como unico interfaz las funciones status ColaIni(cola

Q), boolean ColaVacia(cola Q), status ColaIns(dato D, cola Q), que inserta D enla cola, y status ColaExt(dato D, cola Q), que extrae a D el elemento inicial de lacola. Ademas se dispone de un elemento especial FL que puede insertarse y extraerse dela cola, pero que NO corresponde a nigun dato tıpicamente almacenado en la misma.

30

Dar razonadamente el pseudocodigo de una funcion de prototipo status extrUltimo(dato

D, cola Q) que reciba una cola sin ningun elemento FL y situe en D el elemento inser-tado en dicha cola en ultimo lugar. Suponer para ello que una insercion precedida de unaextraccion sobre la misma cola no causa error.

192. a. Comprobar mediante una pila la correccion de parentesis, corchetes y demas de lasiguiente expresion:(a*[b+{c-d/(f-g)}]+(v-w)*x)b. sobre la cola circular Q del esquema inferior se efectuan las siguientes operaciones:1. ColaIns(2, Q); 2. ColaIns(3, Q); 3. ColaRem(A, Q); 4. ColaIns(4, Q); 5.ColaIns(5, Q); 6. ColaRem(A, Q). Indicar para el estado inicial y para cada operacionlas posiciones de front y rear y el estado de la cola. ¿Cual es el valor final de la variableA?

1

c. Construir el arbol binario de busqueda asociado a la lista 4 15 3 5 9 19 1 7 2 6

indicando el estado del mismo tras cada insercion.

d. Indicar mediante una pila la evolucion de la evaluacion de la siguiente expresion sufijo:2 1 * 4 2 / + 6 5 + 8 2 / - + ;

193. Una implementacion de arboles binarios (AB) usa las expresiones info(T), izq(T),

der(T) para acceder a los correspondientes elementos de un AB. Ademas, NULL identificaa un AB vacıo.

Dar el pseudocodigo de una funcion void acotarAB(dato D, AB T) que situe el valor Den los campos info de todos los subarboles T’ de T para los que info(T’) > D.

194. El pseudocodigo inferior corresponde al recorrido en orden Medio de un arbol binario.Eliminar las llamadas recursivas del mismo efectuando los siguientes pasos:

(a) Eliminar PRIMERO las recursiones de cola que haya.

(b) Indicar la estructura del elemento de pila a utilizar para eliminar las recursiones quepuedan quedar tras el paso anterior.

(c) Para estas, efectuar una eliminacion mecanica utilizando si es preciso sentenciasgoto.

(d) Dar finalmente un codigo sin sentencias goto.

simOrden(AB T)

si T != NULL :

simOrden(izq(T)) ;

visitar(T) ;

simOrden(der(T)) ;

195. a. Se ha definido un tipo de dato fcompl cuyos elementos se almacenan mediante unaestructura de la forma

struct { float Re, Im; }

31

Dar el prototipo y el codigo de una funcion de nombre swapReIm que reciba de maneraadecuada un dato fcompl z e intercambie sus partes real e imaginaria.

b. Dar la evolucion sobre una pila de un algoritmo de comprobacion de la correccion deparentesis, corchetes y llaves en la expresion:

{[A*(B-C)]/([D-E]*F)-G}*H;196. Una implementacion de pilas tiene como unico interfaz las funciones

status PIni(pila P),boolean PVacia(pila P),status Push(dato D, pila P), que inserta el dato D en la pila, ystatus Pop(dato D, pila P), que extrae el elemento D desde la pila.

Dar razonadamente el pseudocodigo de una funcion de prototipo status InvertirPila(pila

A) que reciba una tal pila A y resitue en ella sus elementos en orden inverso al inicial.Para ello, indicar brevemente el metodo a seguir ya. dar primero una version sin control de excepciones;b. identificar sobre dicha version la ubicacion de las posibles excepciones, yc. dar finalmente un pseudocodigo incorporando la deteccion y recuperacion de excep-ciones.

197. Escribir razonadamente una funcion C de prototipo void resetLCE(lec *pl) que liberela memoria de una lista enlazada circular. Usar para ello la siguiente implementacion Cde listas enlazadas circulares:

typedef struct NODO {

gen info ;

struct NODO *next ;

} nodo ;

typedef nodo *lec ;

32