CIENCIAS DE LA COMPUTACIÓN (PRUEBA 1: TEORÍA)
(Puntuaciones máximas: 70)
(Tiempo permitido: tres horas)
(A los candidatos se les permiten 15 minutos adicionales solo para leer el trabajo. NO deben comenzar a escribir durante este tiempo).
Responda todas las preguntas de la Parte I (obligatorio) y seis preguntas de la Parte II, eligiendo dos preguntas de la Sección A, dos de la Sección B y dos de la Sección C. Todo el trabajo, incluido el trabajo preliminar, debe realizarse en la misma hoja que el resto de la respuesta. Las calificaciones previstas para las preguntas o partes de las preguntas se dan entre paréntesis [ ].
PARTE I (20 puntos)
Responda todas las preguntas.
Mientras responde las preguntas de esta parte, indique brevemente su trabajo y razonamiento, cuando sea necesario.
1(a) Enuncie la ley representada por la siguiente proposición y demuéstrela con la ayuda de una tabla de verdad: PVP = P [1]
Ley : Ley Idempotente . Establece que P v P = P.
P P P V P 0 0 0 1 1 1
(b) Enunciar el Principio de Dualidad. [1] El
principio de dualidad establece que, para cada ecuación booleana, existe otra ecuación que es dual a la ecuación original. Para lograr esto, los AND (.) se convierten en OR (+) y viceversa, los 0 en 1 y viceversa, sin embargo, los complementos permanecen sin cambios.
(c) Encuentre el complemento de la siguiente expresión booleana usando la ley de De Morgan: F(a, b, c) = (b’ + c) + a [1]
Complemento de : F(a, b, c ) =(b ‘ + c ) + a
= (b’ + c)’ . a’
= b”. C’. a’ = b.c’.a’
(d) Dibuje el diagrama lógico y la tabla de verdad para una puerta XNOR de 2 entradas. [1]
A B X 0 0 1 0 1 0 1 0 0 1 1 1
(e) Si (P’ => Q) entonces escribe su: [1]
a. Inversa: (P => Q) O P’ + Q’
b. Recíproco: (Q => P) O Q’ + P’
2(a) ¿Qué es una interfaz? ¿En qué se diferencia de una clase? [2]
(a) La interfaz es un tipo de datos no primitivo que tiene miembros de datos estáticos y finales y un prototipo de funciones (es decir, las funciones no están definidas)
Diferencia entre interfaz y clase: la interfaz admite herencia múltiple, mientras que una clase no admite herencia múltiple.
(b) Convierta la siguiente expresión infija a sufijo: P * Q / R + (S + T) [2]
(b) Infix to postfix :
P*Q/R+(S+T)
= P*Q/R+ ST+
= PQ* /R + ST+
= PQ*R/ + ST+
= PQ*R/ST++
(c) Se almacena una array P[15][10] con cada elemento que requiere 8 bytes de almacenamiento. Si la dirección base en P[0][0] es 1400, determine la dirección en P[10][7] cuando la array se almacena en Row Major Wise. [2]
(c) Fila Mayor Sabio: P[i][j] = BA + W [ (i — lr )* columna + (j — lc]
= 1400 + 8[ (10-0)*10 + (7 -0)]
= 1400 + 856
P[10][7] = 2256
(d) (i) ¿Cuál es la complejidad del caso más desfavorable del siguiente segmento de código: [2]
for (int x = 1; x <= a; x++) {
statements;
}
for (int y = 1; y <= b; y++) {
for (int z = 1; z <= c; z++) {
statements;
}
}
= O(a) + O(bxc)
= O(a + bc)
(ii) ¿Cómo cambiaría la complejidad si los tres bucles fueran a N en lugar de a, b y c?
= O(N) + O(N 2 )
= O(N 2 ), tomando el término dominante.
(e) Diferencie entre un constructor y un método de una clase. [2]
(e) Constructor tiene el mismo nombre de la clase donde un método tiene un nombre diferente. No hay tipo de devolución, ni siquiera vacío en el constructor donde, como en un método, puede devolver un valor
3. La siguiente función magicfun() es parte de alguna clase. ¿Qué devolverá la función magicfun() cuando el valor de n=7 y n=10, respectivamente? Mostrar el funcionamiento en seco/funcionamiento: [5]
int magicfun(int n)
{
if (n = = 0)
return 0;
else
return magicfun(n / 2) * 10 + (n % 2);
}
(i) cuando n = 7
OUTPUT : magicfun(7)
magicfun(3) * 10 + 1
magicfun(1) *10 + 1
magic fun(0) *10 + 1 = 111
(ii) cuando n = 10
OUTPUT : magicfun(10)
magicfun(5) * 10 + 0
magicfun(2) *10 + 1
magicfun(1) *10 + 0
magicfun(0) *10 + 1 = 1010
PARTE – II (50 puntos)
Responda seis preguntas, eligiendo dos preguntas de la Sección A, dos de la Sección B y dos de la Sección C.
SECCIÓN – A (Responda dos preguntas cualesquiera)
4(a) Dada la función booleana F(A, B, C, D) = R (2, 3, 4, 5, 6, 7, 8, 10, 11).
(i) Reduzca la expresión anterior utilizando el mapa de Karnaugh de 4 variables , mostrando los diversos grupos (es decir, octal, cuádruples y pares). [4]
Cuadrado 1: (M2+ M3+ M10, M11 ) = B’C
Cuadrado 2: (M4, M5, M6, M7 ) = A’B
Cuadrado 3: (M8, M10) = AB’D’
Por lo tanto F(A, B, C, D) = B’C+ A’B + AB’D’
(ii) Dibuje el diagrama de puerta lógica para la expresión reducida. Suponga que las variables y sus complementos están disponibles como entradas. [1]
(b) Dada la función booleana F(P, Q, R, S) = R (0, 1, 2, 4, 5, 6, 8, 10).
Cuadrado 1: (M0, M1, M4, M5) = Q + S
Cuadrado 2: (M0, M2, M4, M6) = P + S
Cuadrado 3: (M0, M2, M8, M10) = P + R
Por lo tanto, F (P, Q, R, S) = (P + R) . (P + S) . (Q + S)
(i) Reduzca la expresión anterior utilizando el mapa de Karnaugh de 4 variables, mostrando los diversos grupos (es decir, octal, cuádruples y pares). [4]
(ii) Dibuje el diagrama de puerta lógica para la expresión reducida. Suponga que las variables y sus complementos están disponibles como entradas. [1]
5(a) Una escuela tiene la intención de seleccionar candidatos para una competencia de ensayo entre escuelas según los criterios que se detallan a continuación:
El estudiante ha participado en una competencia anterior y es muy creativo.
O
El estudiante es muy creativo y tiene una excelente conciencia general, pero no ha participado en ninguna competencia anteriormente.
O
El estudiante tiene una excelente conciencia general y ha ganado un premio en un concurso entre casas.
Los aportes son:
APORTES
A participó en un concurso antes
B es muy creativo
C ganó un premio en un concurso entre casas
D tiene una excelente conciencia general
Salida: X [1 indica sí, 0 indica no para todos los casos]
Dibuje la tabla de verdad para las entradas y salidas dadas anteriormente y escriba la expresión POS para X (A, B, C, D). [5]
A B C D X (OUTPUT) 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 1 0 1 1 0 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1
Expresión POS: X (A, B, C, D) = R (0, 1, 2, 4, 6, 8, 9, 10)
(b) Indique la aplicación de una media sumadora . Dibuja la tabla de verdad y el diagrama del circuito para un medio sumador. [3] La
aplicación de Half Adder es realizar una suma parcial de dos bits.
Tabla de verdad de la Media Víbora:
A B Sum CARRY 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1
(c) Convierta la siguiente expresión booleana a su forma POS canónica : F(A, B, C) = ( B + C’) · (A’ + B) [2]
Convertir a forma canónica: F(A, B, C)
= (B + C’).(A’+ B)
= (B + C’+ 0) . (A’+ B + O)
= (B+C’+(A.A’)).(A’+B+(C.C’)) [xx’=0]
= (A+B+C’) .(A’+B+C’).(A’+B+C)
6(a) ¿Qué es un multiplexor ? ¿En qué se diferencia de un decodificador ? Dibuje el diagrama de circuito para un multiplexor 8:1. [5]
(a) Un multiplexor es un circuito combinacional que ingresa datos paralelos y emite datos en serie, mientras que un decodificador es un circuito combinacional que ingresa n líneas y emite 2n líneas o menos.
Diagrama de circuito de un multiplexor 8:1:
(b) Demuestre la expresión booleana usando leyes booleanas. Además, mencione la ley utilizada en cada paso. F = (x’ + z) + [ (y’ + z) • (x’ + y) ]’ = 1 [3]
F = (x’+z) + [ (y’+z).(x’ +y) ] = 1
= (x’+z) + (y’+z)’ + (x’+y)’ (Ley de De Morgan)
= x’+z + y.z’ + xy’
= (x’+ x)(x’+y’) + (z+z’)(z+y) = x’+y’+z+y (Ley Distributiva)
= 1 (como y+y’=1)(Ley de Identidad)
(c) Defina maxtérminos y mintérminos. Encuentra el maxtérmino y el mintérmino cuando: P = 0, Q = 1, R = 1 y S = 0 [2]
Maxtérmino: Es la suma de todos sus literales.
Mintérminos: Es el producto de todos sus literales.
Cuando P=0, Q=1, R=1, S=0
Maxterm = P + Q’ + R’ + S
Miniterms = P’ QR S’
SECCIÓN – B
Responda dos preguntas cualesquiera. Cada programa debe estar escrito de tal manera que represente claramente la lógica del problema. Esto se puede lograr mediante el uso de nombres mnemotécnicos y comentarios en el programa. (No se requieren diagramas de flujo ni algoritmos). Los programas deben estar escritos en Java.
7. Se ha definido una clase Palin para comprobar si un número positivo es un número Palíndromo o no.
El número ‘N’ es palíndromo si el número original y su reverso son iguales.
Algunos de los miembros de la clase se dan a continuación: [10]
Nombre de la clase: Palin
Miembros de datos/variables de instancia:
num: entero para almacenar el número
revnum: entero para almacenar el reverso del número
Métodos/funciones miembro:
Palin ( ) : constructor para inicializar miembros de datos con
valores iniciales legales
void accept() : para aceptar el número
int reverse(int y) : invierte el argumento parametrizado ‘y’ y lo almacena en ‘revnum’ usando una técnica recursiva
void check( ) : verifica si el número es un palíndromo invocando la función reverse() y muestra el resultado con un mensaje apropiado
Especifique la clase Palin dando los detalles del constructor() , void accept() , int reverse( int ) y anula el cheque(). Defina la función main( ) para crear un objeto y llame a las funciones correspondientes para habilitar la tarea.
import java.util.*;
public class Palin {
int num, revnum;
static Scanner x = new Scanner(System.in);
Palin()
num = 0;
revnum = 0;
}
void accept()
System.out.println("Enter a number");
num = x.nextlntO;
}
int reverse(int y)
{
if (y > 0)
revnum = revnum * 10 + y % 10;
return reverse(y / 10);
}
else return revnum;
}
void check()
{
int p = num;
if (num == reverse(p))
System.out.println("palindrome");
else
System.out.println("not a palindrome");
}
static void main()
{
Palin obj = new Palin();
obj.accept();
obj.check();
}
8. Se ha definido un Adder de clase para sumar dos tiempos aceptados cualesquiera. [10]
Ejemplo: Tiempo A – 6 horas 35 minutos
Tiempo B – 7 horas 45 minutos
Su suma es – 14 horas 20 minutos (donde 60 minutos = 1 hora)
Los detalles de los miembros de la clase se dan a continuación:
Nombre de la clase: Adder
Data miembro/variable de instancia:
a[ ] : array de enteros para contener dos elementos (horas y
minutos)
Funciones/métodos miembro:
Adder( ) : constructor para asignar 0 a los elementos de la array
void readtime( ) : para ingresar los elementos de la array
void addtime (Adder X, Adder Y): agrega el tiempo de los dos objetos parametrizados X e Y y almacena la suma en el objeto de llamada actual
void disptime() : muestra los elementos de la array con un mensaje apropiado (es decir, horas = y minutos = )
Especifique la clase Adder dando detalles del constructor() , void readtime() , void addtime(Adder, Adder) y void disptime() . Defina la función main( ) para crear objetos y llame a las funciones en consecuencia para habilitar la tarea.
import java.util.*;
public class Adder {
int a[] = new int[2];
static Scanner x = new Scanner(System.in);
Adder()
{
a[0] = 0;
a[1] = 0;
}
void readtime()
System.out.println("Enter hours and minutes");
a[0] = x.nextInt();
a[1] = x.nextInt();
void disptime()
{
System.out.println("Hours=" + a[0]);
System.out.println("Minutes=" + a[1]);
}
void addtime(Adder X, Adder Y)
{
a[1] = X.a[1] + Y.a[1];
a[0] = a[1] / 60;
a[1] = a[1] % 60;
a[0] += X.a[0] + Y.a[0];
}
static void main()
{
Adder a = new Adder();
Adder b = new Adder();
Adder c = new Adder();
a.readtimeO;
b.readtimeO;
c.addtime(a, b);
c.disptime();
9. Se ha definido una clase SwapSort para realizar operaciones relacionadas con strings en una entrada de palabra. [10]
Algunos de los miembros de la clase son los siguientes:
Nombre de clase: SwapSort
Miembros de datos/variables de instancia:
wrd: para almacenar una palabra
len: entero para almacenar la longitud de la palabra
swapwrd: para almacenar la palabra intercambiada
sortwrd: para almacenar la palabra ordenada
Funciones/métodos miembro:
SwapSort(): constructor predeterminado para inicializar miembros de datos con valores iniciales legales
void readword( ) : para aceptar una palabra en MAYÚSCULAS
void swapchar( ) : para intercambiar/intercambiar el primer y último carácter de la palabra en ‘wrd’ y almacena la nueva palabra en ‘swapwrd’
void sortword( ) : ordena los caracteres de la palabra original en orden alfabético y los almacena en ‘sortwrd’
void display( ) : muestra la palabra original, la palabra intercambiada y la palabra ordenada
Especifique la clase SwapSort, proporcionando los detalles del constructor(), void readword(), void swapchar(), void sortword() y void display(). Defina la función main( ) para crear un objeto y llame a las funciones correspondientes para habilitar la tarea.
import java.util.*;
public class SwapSort {
String wrd, swapwrd, sortwrd;
int len;
static Scanner x = new Scanner(System.in);
SwapSort()
{
swapvvrd = "";
sortwrd = "";
}
void readword()
{
System.out.println("Enter word in Upper case");
wrd = x.nextO;
len = wrd.lengthO;
}
void swapchar()
swapwrd = wrd.charAt(len - 1) + wrd.sub strin g(1, len - 1)
+ wrd.charAt(0);
}
void sortword()
{
char c;
for (int i = 65; i <= 90; i++)
for (int j = 0; j < len; j++)
c = wrd.charAt(j);
if (c == i)
sortwrd += c;
}
}
}
void display()
{
System.out.println("Original word = " + wrd);
System.out.println("Swapped word = " + swapwrd);
System.out.println(" Sorted word = " + sortwrd);
}
static void main()
SwapSort x = new SwapSort();
x.readwordO;
x.swapchar();
x.sortword();
x.display();
}
SECCIÓN – C
Responda dos preguntas cualesquiera.
Cada programa debe escribirse de tal manera que represente claramente la lógica del problema
paso a paso. Esto se puede lograr usando comentarios en el programa y nombres mnemotécnicos o pseudocódigos para algoritmos. Los programas deben estar escritos en Java y los algoritmos deben estar escritos en forma general/estándar, donde sea requerido/especificado. (No se requieren diagramas de flujo).
10. Se ha definido un Producto de clase superior para almacenar los detalles de un producto vendido por un mayorista a un minorista. Defina una subclase Ventas para calcular el monto total pagado por el minorista con o sin multa junto con el impuesto de servicio. [5]
Algunos de los miembros de ambas clases se dan a continuación:
Nombre de la clase:
Miembro de datos del producto/variable de instancia:
nombre: almacena el nombre del
código del producto: número entero para almacenar el código del producto
cantidad: almacena la cantidad total de la venta del producto (en decimales)
Funciones/métodos de miembros:
Producto (String n, int c, doble p): constructor parametrizado para asignar miembros de datos nombre = n, código = c y cantidad = p
void show(): muestra los detalles de los datos miembros
Nombre de la clase: Ventas
Miembro de datos/variable de instancia:
día: almacena el número de días necesarios para pagar el monto de la venta
tax: para almacenar el impuesto de servicio (en decimales)
totamt: para almacenar el monto total (en decimales)
Funciones/métodos de los miembros:
Sales(…) : constructor parametrizado para asignar valores a miembros de datos de ambas clases
void compute() : calcula el impuesto de servicio al 12,4 % del monto de la venta real calcula la multa al 2,5 % del monto de la venta real solo si el monto pagado por el minorista al mayorista supera los 30 días calcula el monto total pagado por el minorista como (monto de venta real + impuesto de servicio + multa)
void show( ) : muestra los datos de los miembros de la clase superior y el monto total
Suponga que se ha definido la superclase Producto. Usando el concepto de herencia, especifique la clase Ventas dando los detalles del constructor (…), void compute() y void show().
NO es necesario escribir la superclase, la función principal y el algoritmo.
public class Sales extends Product {
int day;
double tax, totamt;
Sales(String n, int a, double b, int d)
{
super(n, a, b);
day = d;
}
void compute()
{
double f = 0.0;
tax = (12.4 / 100) * amount;
if (day > 27)
f = (2.5 / 100) * amount;
totamt = amount + tax + f;
void show()
{
super.show();
System.out.println("No of days=" + day);
System.out.println("Sales Tax=" + tax);
System.out.println("Total Amount=" + totamt);
11. Queue es una entidad que puede contener un máximo de 100 enteros. La cola permite al usuario agregar números enteros desde atrás y eliminar números enteros desde el frente. Defina una cola de clase con los siguientes detalles: [5]
Nombre de clase: Miembros de datos de cola
/variables de instancia:
Que[ ]: array para contener los elementos enteros
tamaño: almacena el tamaño de la array
frontal: para señalar el índice de la parte delantera
trasera : para señalar el índice de las
funciones de los miembros traseros:
Constructor de cola (int mm) para inicializar los datos
size = mm, front = 0, rear = 0
void addele(int v ) : para agregar enteros desde atrás si es posible
, de lo contrario mostrar el mensaje «Desbordamiento»
int delele( ) : devuelve los elementos desde el frente si están presentes, de lo contrario muestra el mensaje «Underflow» y devuelve -9999
void display ( ) : muestra los elementos de la array
Especifique la cola de clase dando detalles SOLO de las funciones void addele(int) e int delele ( ). Suponga que las otras funciones han sido definidas. La función principal y el algoritmo NO necesitan escribirse.
public class Queue {
int Quen = new int[100];
int max, f, r;
void addele(int v) if (r < max - 1)
Que[+ - Fr]
= v;
else System.out.println("Overflow");
}
int delele() if (f != r) return Que[++f];
else return -9999;
12(a) Se forma una lista enlazada a partir de los objetos de la clase Node. La estructura de clases del
Node se da a continuación:
class Node
{
int num;
Node siguiente;
}
Escriba un algoritmo O un método para contar los Nodes que contienen solo números enteros impares de una lista vinculada existente y devuelve el recuento. La declaración del método es la siguiente:
int CountOdd( Node startPtr ) [2]
(a) ALGORITMO:
Paso 1. Inicie
el Paso 2. Establezca un puntero temporal en el primer Node
. Paso 3. Repita los pasos 4 y 5 hasta que el puntero llegue a cero. Regresar conteo Paso 4. Verificar impares e incrementar el contador.
Paso 5. Mueva el puntero al siguiente Node
. Paso 6. Finalice el
MÉTODO :
int CountOdd(Node startPtr)
{
int c = 0;
Node temp = new Node(startPtr);
while (temp != null) {
if (temp.num % 2 != 0)
c++;
temp = temp.next;
return c;
(b) Responda las siguientes preguntas del diagrama de un árbol binario que se muestra a continuación:
(i) Escriba el recorrido posterior al orden de la estructura de árbol anterior. [1]
WFYNRZDGM
(ii) Indique los números de nivel de los Nodes N y R si la raíz está en el nivel 0 (cero). [1]
Nivel de N=1 y Nivel de R = 3
(iii) Enumere los Nodes internos del subárbol derecho. [1]
G y Z
Publicación traducida automáticamente
Artículo escrito por aishwaryaagarwal2 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA