BARC 2020: Full Length Mock 1 (App update required to attempt this test) for GATE & PSU CS Exams

Question 1

Consider the polynomial

The minimum number of multiplications needed to evaluate p on an input x is:

Question 2

When RANDOMIZED-QUICKSORT runs, how many calls are made to the random number generator RANDOM in the worst case :

Question 3

Banks often record transactions on an account in order of the times of the transactions, but many people like to receive their bank statements with checks listed in order by check number. People usually write checks in order by check number, and merchants usually cash them with reasonable dispatch. The problem of converting time-of-transaction ordering to check-number ordering is therefore the problem of sorting almost-sorted input. Which sorting algorithm is best in this case ?

Question 4

Consider a hash table of size 10 Hashing is done using the hash function as :

Hf(Key) = key mod 8

Find the number of collisions _________ when the follows keys are inserted in hash table in given order if linear probing is used.

25, 39, 46, 55, 89, 23, 68

Question 5

If f(n) = O(n) and g(n) = Ω(n) , then what can be correct about f(n).g(n) ?

Question 6

Below given is the preorder traversal of a Binary Search Tree. Find the post order traversal of the BST?

PreOrder : 180 80 50 40 45 60 70 90 110 120

Question 7

The property of ______ is static in nature, compile time early binding and user friendly.

Question 8

Number of nodes of degree 2 given that the tree is a binary tree having N leaf nodes

Question 9

Which of the following is/are correct?

1) To say whether an element x does not exist, in worst case in AVL tree is O(n).

2) To find smallest element in worst case, in BST is O(logn)

3) To insert an element in BST, takes O(nlogn) in worst case.

4) To find an element, in Binary tree it takes O(logn) in worst case.

Question 10

Which of the following statement is false?

Question 11

Find the error in the following code
#include <stdio.h>
main(){
int a=6;
static int b=a;
a+;
}

Question 12

Which of the following is illegal statement ?

Question 13

What does the following fragment of C program print?
Char c[ ] = “GATE2011”;
char *p = c;
printf(“%s”, p + p [3] – p [1] ) ;

Question 14

For two relations R (A, B, C) and S (D, E), relation S maintain a foreign key for D on attribute A of relation R. Consider the following statements:
A) Each record of R is related to 0 or more record of S.
B) Each record of S is related to 0 or more record of R.
C) Each record of S is related to 0 or 1 record of R.
D) Each record of R is related to 0 or 1 record of S.
Which of the following is true?

Question 15

Consider a relation R related to 7 entities E1,E2…..E7 respectively, each of them has 2 attributes (A,B) (C,D) (E,F) (G,H) (I,J) (K,L) (M,N) with first attribute as candidate key in all entities. All entities are related to R with one-one mapping. What is the number of candidate keys possible for R?

Question 16

Consider the following action:

Transaction…..

Commit;

Rollback;

What does Rollback do?

Question 17

In the IPv6 header, the traffic class field is similar to which field in the IPv4 header?

Question 18

Which classes are used for connection-less socket programming?

Question 19

Which of the following is true?

Question 20

Which of the following are tasks of Data Link Layer?

Question 21

Given an IP address: 12.55.13.135 find class, limited broadcast address, directed broadcast address, and network IP address respectively.

Question 22

Arrange the following configuration for CPU in decreasing order of operating speeds

1) Hard wired control

2) vertical microprogramming

3) Horizontal microprogramming

Question 23

If a memory system has a total of 16 chips, each with 12 address line and 4 data lines. The size of the memory system is

Question 24

Consider we have a system with 512 KB cache size and tag bit field is 7-bit wide and also block size is 1 KB. System is using 8 way set associative mapping for cache mapping technique. The size of main memory is ?

Question 25

A system having 2-level cache L1 and L2 mechanism. The access time of L1 and L2 is 2ns and 6 ns respectively & main memory access time is 100 ns. Hit rate of L1 and L2 is 0.7 & 0.9. Then the average access time is(up to 1 decimal point)

Question 26

Suppose a DRAM memory has 8K rows in its array of bit cells, its refreshing period is 20ms and 4 clock cycles are needed to access each row. What fraction of memory time is spent performing refreshes, if the clock rate is 133 MHz?

Question 27

Consider a general graph is plotted for the EMAT (effective memory access time) vs TLB miss rate as shown below:

What is the value of x and y respectively? (Note: m is the memory access time, k is the level of page tables and c is the TLB access time.)

Question 28

Consider an operating system that uses 48-bit virtual addresses and 16KB page size. The system uses a hierarchical page table design to store all the page table entries of a process, and each page table entry is 4 bytes in size. What is the total number of pages that are required to store the page table entries of a process, across all levels of the hierarchical page table?

Question 29

Consider five processes of sizes 678 KB, 124 KB, 256 KB, 450 KB and 430 KB and seven memory partitions of size 400 KB, 200 KB, 150 KB, 800 KB, 500 KB, 460 KB, 700 KB.
If the best-fit algorithm is used, total size of left out partitions not alloted to any process is:

Question 30

Test & Set Lock is not free from ?

Question 31

If we give a string of length ‘n’ as input then which one of the following will give the output of length ‘n+1’?

Question 32

Give the RE for the set of strings which are either all b’s or else there is an ‘a’ followed by some b’s also containing

.

Question 33

If L1 is DCFL and L2 is CFL , then which statement is true ?

Question 34

Consider a Language L which is made by alphabets 0's and 1's. The language satisfies the below property :

" and L , x should not be a prefix of y."

If the above property is satisfies then the language L is :

Question 35

Consider the following SDT-
S -> aDBN {B.a =D.a , S.b = B.b}
B -> epsilon {B.b = epsilon}
S -> bDYTN { T.a = D.a, S.b = T.b}
T -> epsilon {T.b =epsilon}
N -> n {N.a =n}
Where .a & .b are the attributes corresponding to the production. Which of the following is correct?

Question 36

Consider the following SDT-
A -> A#B { A.val = A1.val + B.val }
A -> B {A.val = B.val}
B -> B$C {S1}
B -> C {B.val = C.val}
C -> num {C.val= number}
If the expression 8 # 6 $ 2 # 8 $ 6 # 2 $ 1 is evaluated to 70 then which of the following rule will be placed at S1?

Question 37

What type of error is generated by the following program-
int main() {
float b;
b=sum(10,20);
printf("%d",b);
return 0;
}
sum(float a,float b) {
if(a<0)
return b;
sum(a/2,b/2);
}

Question 38

The grammar which is equivalent to -
A -> A+A/A-A/b

After eliminating the left factoring is -

Question 39

Given Counter is:

What can be said about above counter? If the initial states are reset.

Question 40

Which of the following is the slowest adder?

Question 41

Consider the given circuit,

In this circuit, what can be said about the race around condition?

Question 42

Let the two counter be modulus-7 & modulus-3 counter and both are cascaded with 7MHz clock frequency applied on it, then what is the lowest frequency in KHz?

Question 43

Which of the following statement is not true?

Question 44

Let P = {(x, y) |x²+y²=1, x, y ∈ R}. Then P is-

Question 45

Let D₃₀ = {1, 2, 3, 4, 5, 6, 10, 15, 30} and relation I be partial ordering on D30. The all lower bounds of 10 and 15 respectively are

Question 46

The rank of the matrix

is _____.

Question 47

A point on a curve is said to be an extreme m if it is a local minimum or a local maximum. The number of distinct extrema for the curve 3x⁴ – 16x³ + 24x² + 37 is

Question 48

The software equation of putnam is a dynamic multivariable model that assumes a specific distribution of effort. Consider the following parameters.
E = Project effort measured in person-months or person-years
LOC = Lines of Code estimate for the project
t = Length of project measured in months or years
B = "Special skills factor"
P = "Productivity Parameter"
Find Estimation form of the model.

Question 49

What is performed through the entire duration of the project.

Question 50

DTD definition is used along with XML to specify