QUESTIONS CARRY 2 MARKS EACH
Consider the following entity relationship diagram (ERD),where two entities E1 and E2 have a relation R of cardinality 1 : m.
The attributes of E1 are A11, A12 and A13 where A11 is the key attribute.the attributes of E2 are A21, A22 and A23 where A21 is the key attribute and A23 is a multi-valued at tribute. Relation R does not have any attribute. A relational database containing minimum number of tables with each table satisfying the requirements of the third normal form(3NF) is designed from the above ERD. The number of tables in the database is
-
Solution
Step 1:1 NF
T1: \(\underline{A11}\), A12, A13
T2: A11, \(\underline{A21}\), A22, \(\underline{A23}\)//because A23 is multivalued ,it has to be included in Key attribute
Step 2: 2NF //A23 is Multivalued attribute and not allowed in 2NF therefore new tables are:
T1:\(\underline{A11}\), A12, A13
T2:A11, \(\underline{A21}\), A22
T3:\(\underline{A21}\), \(\underline{A23}\)
Step 3: 3NF //There is no transitive functional dependency in all tables , So in 3NF Therefore answer is (b)
QUESTIONS CARRY 2 MARKS EACH
Consider the following transition system:
Which of the states are to be marked as starting state and final state respectively,so as to turn the above system into a DFA that accepts all string having odd number of 0’s and even number of 1’s
-
Solution
Consider option(a) is true,means q0 is initial state and q2 is final state then the minimum string from q0 to q2 will be
10(q0→q1→q2)or 01(q0→q3→q2)
Which does not satisfies the condition odd number of 0’s and even number of 1’s.
Similarly, option (b) is also incorrect.
Now, for option (c), q1 is initial state and q2 is final state, the minimum string will be
0(q1→q2) or 011(q1→q2→q3→q2) or
103(q1→q0→q3→q2)Which all contains odd number of 0’s and even number of 1’s.Hence, option (c) is correct.
QUESTIONS CARRY 2 MARKS EACH
Consider the following C program:
#include
typedef struct {
char *a;
char *b;
}t;
void f1 (t, s);
void f2 (t*p);
main()
{ static t s = {“A”, “B”);
printf (“%s %s \n”, s.a, s.b);
f1(s);
printf(“%s %s \n”, s.a, s.b);
f2 (&s)
}
void f1 (t s)
{ s.a = “U’;
s.b =“V’
printf (%s %s \n”, s.a, s.b);
return;
}
void f2 (t * p)
{ p → a = “V”;
p → b = “W”;
printf (%s %s \n”, p →a,p →b);
return;
}
What is the output generated by the program?
-
Solution
First print AB f1 is call by value the changes applicable only for local from f1 U V is printed back in main A B is printed then inf 2V W is printed hence answer is (b)
QUESTIONS CARRY 2 MARKS EACH
Choose the correct option to fill the ?1 and ?2 so that the program prints an input string in reverse order. Assume that the input string is terminated by a new line character.
#include
void wrt_it (void);
int main (void)
{
printf(“Enter Text”);
prinf(“/n”);
wrt_it();
printf(“/n”);
return 0;
}
void wrt_it (void)
{
int c;
if (?1)
wrt_it();
?2
-
Solution
Getchar() is used to get the input character from the user and putchar() to print the entered character, but before printing reverse is called again and again until '\n' is entered. When '\n' is entered the functions from the function stack run putchar() statements one by one. Therefore, last entered character is printed first.
You can try running below program
void reverse (void); /* function prototype */
void reverse(void)
{
int c;
if (((c = getchar()) != '\n'))
reverse();
putchar(c);
}
main()
{
printf ("Enter Text ") ;
printf ("\n") ;
reverse();
printf ("\n") ;
getchar();
}
QUESTIONS CARRY 2 MARKS EACH
Consider a list of recursive algorithms and a list of recurrence relations as shown below. Each recurrence relation corresponds to exactly one algorithm and is used to derive the time complexity of the algorithm.
Recursive Algorithm Recurrence Relation
P. Binary search I. T(n) = T(n – k) + T(k) + cn
Q. Merge sort II. T(n) = 2T(n –1) + 1
R. Quick sort III. T(n) = 2T(n/2) + cn
S. Tower of Hanoi IV. T(n) = T(n/2) + 1
Which of the following is the correct match between the algorithms and their recurrence relations?
-
Solution
P. Binary search – T(n) = T(n/2) + 1
Q. Merge sort –T(n) = 2T(n/2) + Cn
R. Quick sort – T(n) = T(n – k) + T(k) + Cn
S. Tower of Hanoi –T(n)= 2T (n – 1) + 1
QUESTIONS CARRY 2 MARKS EACH
An array of integers of size n can be converted into a heap by adjusting the heaps rooted at each internal node of the complete binary tree starting at the node ⌊(n – 1)/2⌋, and doing this adjustment up to the root node (root node is at index 0) in the order ⌊(n – 1)/2⌋,⌊(n – 3)/2⌋, ….., 0.The time required to construct a heap in this manner is
-
Solution
The above statement is actually algorithm for building a Heap of an input array A.
BUILD - HEAP (A)
heap size : = size (A);
for i := floor(heap size/2) down to 1
do HEAPIFY (A,i);
end for
END
Upper bound of time complexity is O(n)
QUESTIONS CARRY 2 MARKS EACH
A program attempts to generate as many permutations as possible of the string ‘abcd’ by pushing the characters a, b,c, din the same order onto a stack,but it may pop off the top character at any time. Which one of the following strings CANNOT be generated using this program?
-
Solution
Elements are abcd
In stack (based on LIFO) always
top element are poped of f. So
adjacent of a be b or d
adjacent of b be a or c
adjacent of c be b or d
adjacent of d be c or d
So cabd order cannot be possible.
Hence correct answer is (d).
QUESTIONS CARRY 2 MARKS EACH
The storage area of a disk has innermost diameter of 10 cm and outermost diameter of 20 cm. The maximum storage density of the disk is 1400 bits/cm. The disk rotates at a speed of 4200 RPM. The main memory of a computer has 64-bit word length and 1 ms cycle time. If cycle stealing is used for data transfer from the disk, the percentage of memory cycle stolen for transferring one word is ___________.
-
Solution
Inner most diameter = 10 cm
Storage density =1400 bits/cm
Capacity of each track :
= 3.14 *diameter * density
= 3.14* 10 * 1400
= 43960 bits
Rotational latency = 60/4200 =1/70 seconds
It is given that the main memory of a computer has 64-bit word length and 1µs cycle time.
Data transferred in 1 sec =64 * 106 bits
Data read by disk in 1 sec = 43960 * 70 = 3.08 * 106 bits
Total memory cycle =(3.08 * 106) / (64* 106) = 5%
QUESTIONS CARRY 2 MARKS EACH
In an enhancement of a design of a CPU, the speed of a floating point until has been increased by 20% and the speed of a fixed point unit has been increased by 10%. What is the overall speedup achieved if the ratio of the number of floating point operations to the number of fixed point operations is 2:3 and the floating point operation used to take twice the time taken by the fixed point operation in the original design………. ?
-
Solution
Speed up = Original time taken/ new time taken
Let x be the time for a fixed point operation
Original time taken = (3x + 2*2x)/5 = 7x/5
New time taken = ((3x/1.1) + (4x/1.2))/5 = 8x/1.32*5
So, speed up =7*1.32/8 = 1.155
QUESTIONS CARRY 2 MARKS EACH
A CPU has only three instructions I1, I2 and I3, which use the following signals in time steps T1 .. T5:
I1 :T1 : A in, Bout, Cin
T2: PC out, B in
T3: Z out, Aine
T4: Bin, Cout
T5: End
I2 :T1: Cin, Bout,Din
T2: Aout, Bin
T3: Zout, Ain
T4: Bin, Cout
T5: End
I3 :T1: Din, Aout
T2: Din, Bout
T3: Zout, Ain
T4: Dout, Ain
T5: End
Which of the following logic functions will generate the hardwired control for the signal Ain?
-
Solution
We just have to see which all options give 1 whenever Ain is 1 and 0 otherwise.
So, Ain is 1 in T3 of I1, I2 and I3. Also during T1 of I1, and T2 and T4 of I3. So, answer will be
T1.I1+ T2.I3 + T4.I3 + T3.I1 + T3.I2 + T3.I3
Since CPU is having only 3 instructions, T3.I1 + T3.I2 + T3.I3 can be replaced with T3(we don't need to see which instruction and Ain will be activated in time step 3 of all the instructions).
So, T1.I1 + T2.I3+ T4.I3 + T3 is the answer.