JNU PhD CS 2019

Question 1
An upper-layer packet is split into 10 frames, each of which has an 80 percent chance of arriving undamaged. If no error control is done by the data link protocol, how many times must the message be sent on average to get the entire thing through (in transmissions)?
A
18.6
B
27.9
C
9.3
D
None of the above
Question 1 Explanation: 
Total frames=10
Each frame has a chance of 80% undamage which is 0.8 of getting through, the chance of the whole message getting through is (0.8)10, which is about 0.107. Call this value p.
The expected number of transmissions for an entire message is then

Now use a = 1-p to get E = 1/p. Thus, it takes an average of 1/0.107, or about 9.3 transmissions.
Question 2
Consider building a CSMA/CD network running at 1Gbps over a 1-km cable with no repeaters. The signal speed in the cable is 200,000 km/sec. What is the minimum frame size?
A
10000 bytes
B
100000 bits
C
1250 bits
D
None of the above
Question 2 Explanation: 
Question 3
If two communicating stations X and Y are linked through two intermediate routers, r1 and r2; then determine the number of times each packet visits Network Layer (NL) and Data Link Layer (DLL) for single transmission from X to Y.
A
NL - 4, DLL - 4
B
NL - 4, DLL - 3
C
NL - 4, DLL - 6
D
NL - 2, DLL - 6
Question 3 Explanation: 
Each router will contain two DLL since it has two interfaces and one network layer. Each host or station will contain one network layer and one data link layer. So the total no. of data link layer will be 2(from stations) + 4(from routers) = 6. No. of network layers will be 2(from stations) + 2(from routers) = 4.
Question 4
To deliver a message to the correct application program running on a host, the address must be consulted is
A
port
B
physical
C
IP
D
None
Question 4 Explanation: 
IP address takes you to the correct host but not to the process in the host. And each host might contain many processes. So the address required to deliver a message to the application program or process within a host is the port address.
Question 5
Manchester encoding is principally designed to
A
ensure that the line remains unbalanced
B
have more than one symbol per bit period
C
increase the bandwidth of a signal transmitted on the medium
D
ensure that a transition occurs in the center of each bit period
Question 5 Explanation: 
In Manchester encoding a logic 0 is indicated by a 0 to 1 transition at the centre of the bit and logic 1 by 1 to 0 transition.
Question 6
The concept of pipelining is most effective in improving performance if the tasks being performed in different stages:
A
require different amount of time
B
require about the same amount of time
C
require different amount of time with time difference between any two tasks being same
D
require different amount with time difference between any two tasks being different
Question 6 Explanation: 
Case 1:
Consider 4 stages in pipeline P1, P2, P3, P4, with each stage requires 1ns.
For large no. of instructions the time taken by pipeline to execute one task is 1ns.

But for non pipeline the time taken to execute one task is,

Case 2:
Now let’s consider 4 stages pipeline P1, P2, P3, P4, with each stage requiring 1ns, 2ns, 3ns, 4ns.

For large no. of instruction the time taken by pipeline to execute one task is max(1, 2, 3, 4)ns = 4ns
But for non pipeline the time taken to execute one task is,
1 + 2 + 3 + 4 = 10ns

Hence from above it can be clearly seen that the concept of pipelining is most effective in improving performance if the tasks being performed in different stages require about the same amount of time.
Question 7
Given that (292)10 = (1204)x in some number system x. The base x of that number system is
A
2
B
8
C
10
D
None of the above
Question 7 Explanation: 
Question 8
Which of the following is not functionally a complete set?
A
AND, OR
B
NOR
C
NAND
D
AND, OR, NOT
Question 8 Explanation: 
Functionally complete sets are NOR,NAND,(OR,NOT),(AND,NOT).
Hence Option (a) set in not functionally complete.
Question 9
Assume that for a certain processor, a read request takes 50 nanoseconds on a cache miss and 5 nanoseconds on a cache hit. Suppose while running a program, it was observed that 70% of the processor’s read requests result in a cache hit. The average read access time in nanoseconds is
A
10
B
12
C
13
D
18.5
Question 9 Explanation: 
ARAT = Hit rate × cache hit time + miss rate × cache miss time
= 0.7 × 5ns + 0.3 × 50ns
= 3.5ns + 15ns
= 18.5 ns
Question 10

The number of min-terms after minimizing the following Boolean expression is

[D’ + AB’ + A’C + AC’D + A’C’D]’
A
1
B
46
C
56
D
76
Question 10 Explanation: 
(D’ + AB’ + A’C + AC’D + A’C’D)’
(D’ + A’C’D + AB’ + A’C + AC’D)’
((D’ + D) (D’ + A’C’) + AB’ + A’C + AC’D)’
(D’ + A’C’ + AB’ + A’C + AC’D)’
(D’ + AC’D + AB’ + A’(C + C’))’
(D’ + AC’ + AB’ + A’)
(D’ + AC’ + (B’ + A’) (A + A’)
(D’ + AC’ + B’ + A’)
(D’ + (A + A’) (C’ + A’) + B’)’
(D’ + C’ + A’ + B’)’ = ABCD
Question 11

The speed up of a pipeline processing over an equivalent non-pipeline processing is defined by the ratio:

where n→no. of tasks, Tn→time of completion of each task, k→no. of segments of pipeline, Tp→clock cycle time, S→speed up ratio.
A
S = n Tn/ (k + n - 1) Tp
B
S = n Tn/ (k + n + 1) Tp
C
S = n Tn/ (k - n + 1) Tp
D
S = (k + n - 1) Tp/ n Tn
Question 11 Explanation: 
Consider a ‘k’ segment pipeline with clock cycle time as ‘Tp’. Let there be ‘n’ tasks to be completed in the pipelined processor. Now, the first instruction is going to take ‘k’ cycles to come out of the pipeline but the other ‘n – 1’ instructions will take only ‘1’ cycle each, i.e, a total of ‘n – 1’ cycles. So, time taken to execute ‘n’ instructions in a pipelined processor:
ET pipeline = k + n – 1 cycles
= (k + n – 1) Tp
In the same case, for a non-pipelined processor, execution time of ‘n’ instructions will be:
ETnon-pipeline = n * k * Tp
but in question k * Tp = Tn
Hence ETnon-pipeline = n * Tn
So, speedup (S) of the pipelined processor over non-pipelined processor, when ‘n’ tasks are executed on the same processor is:
S = Performance of pipelined processor /
Performance of Non-pipelined processor
As the performance of a processor is inversely proportional to the execution time, we have,
S = ETnon-pipeline / ETpipeline
=> S = [n *Tn] / [(k + n – 1) * Tp]

Question 12
Consider a system running ten I/O - bound tasks and one CPU - bound task. Assume that the I/O - bound tasks issue an I/O operation once for every millisecond of CPU computing and that each I/O operation takes 10 milliseconds to complete. Also assume that the context switching overhead is 0.1 millisecond and that all processes are long-running tasks. The CPU utilization for a round-robin scheduler when the time quantum is millisecond?
A
78%
B
91%
C
98%
D
80%
Question 12 Explanation: 
The time quantum is 1 millisecond: Irrespective of which process is scheduled, the scheduler incurs a 0.1 millisecond context-switching cost for every context-switch. This results in a CPU utilization of 1/1.1 * 100 = 91%.
Question 13
Assume we have a demand-paged memory. The page table is held in registers. It takes 8 milliseconds to service a page fault if an empty page is available or the replaced page is not modified, and 20 milliseconds if the replaced page is modified. Memory access time is 100 nanoseconds. Assume that the page to be replaced is modified 70 percent of the time. What is the maximum acceptable page-fault rate for an effective access time of no more than 200 nanoseconds?
A
0.0006
B
0.00006
C
0.006
D
None of the above
Question 13 Explanation: 
Let p be the page fault rate (the probability that a memory access results in a page fault).
Then (1 − p) is the probability that a memory access costs 100 nsec.
The probability that a page fault costs 20 msec is 0.7 ∗ p and the probability that a page fault costs 8 msec is 0.3 ∗ p.
Since 1 nsec = 1000000 msec, (1 − p) ∗ 100 + 0.7 ∗ p ∗ 20000000 + 0.3 ∗ p ∗ 8000000 = 200 (14000000 + 2400000 − 100)p = 100 p = 100/(16400100) = 6.1 ∗ 10^−6 = .0000061 = .00061%
Question 14

Which of the following scheduling algorithms could result in starvation?

i) First-come, first-served

ii) Shortest job first

iii) Round robin

iv) Priority
A
ii and iv
B
i and iii
C
iv only
D
None of the above
Question 14 Explanation: 
In Shortest job first the job with longest burst time may starve if the process with low burst time keeps coming.
In priority scheduling algorithm the job with lowest priority may starve if the process with highest priority keeps coming.
FCFS and round robin scheduling algorithm will never cause starvation.
Question 15
Overlay is
A
A part of an operating system
B
A specific memory location
C
A single contiguous memory that was used in the olden days for running large program by swapping
D
Overloading the system with many user files
Question 15 Explanation: 
In a general computing sense, overlaying means "the process of transferring a block of program code or other data into main memory, replacing what is already stored". Overlaying is a programming method that allows programs to be larger than the computer's main memory.
Question 16
In which of the following directory systems, it is possible to have multiple complete paths for a file, starting from the root directory?
A
Single level directory
B
Two level directory
C
Tree structured directory
D
Acyclic graph directory
Question 16 Explanation: 
In acyclic graph directory we can provide sharing by making the directory an acyclic graph. In this system, two or more directory entry can point to the same file or sub directory. That file or sub directory is shared between the two directory entries.
Question 17
A transparent DBMS
A
Cannot hide sensitive information from users
B
Keep its logical structure hidden from users
C
Keeps its physical structure hidden from users
D
Both (b) and (c)
Question 17 Explanation: 
A transparent DBMS keeps its physical structure hidden from users.
Question 18
A locked file can be
A
Accessed by only one user
B
Modified by users with the correct password
C
Is used to hide sensitive information
D
Both (b) and (c)
Question 18 Explanation: 
A locked file can be accessed by only one user at any specific time otherwise there would be race condition.
Question 19
Let F = {D→AC, A→DB, B→E, E→D} that hold on the attribute set {A, B, C, D, E}, then the highest normal form that hold is
A
BCNF
B
3NF
C
2NF
D
None of the above
Question 19 Explanation: 
The candidate keys for given functional dependencies are A,B,D,E.
So for the given functional dependencies left side of each functional dependencies is super key which satisfies the condition of BCNF. Hence the given relation is in BCNF.
Question 20

Which of the following statements are correct about an array?

1. The array int num[26]; can store 26 elements.

2. The expression num[1] designates the very first element in the array.

3. It is necessary to initialize the array at the time of declaration

4. The declaration num[SIZE] is allowed if SIZE is a macro.
A
1
B
2,4
C
2,3
D
1,4
Question 20 Explanation: 
Statement 1 is true.
Statement 2 is false because the expression num[0] designates the very first element in the array.
Statement 3 is false ,it is not necessary to initialize the array at the time of initialization.
Statement 4 is true, because the declaration num[SIZE] is allowed if SIZE is a macro. This statement is true, because the MACRO just replaces the symbol SIZE with given value.
Question 21

What is the output of the following statements?

int i=3;

printf(“%d%d”, i,i++);
A
34
B
43
C
44
D
33
Question 21 Explanation: 
In printf() function we calculate from right to left and then printing is done from left to right. So first i++ will be calculated but since ++ is post operator here so first i=3 value will be accepted and then value of i will be incremented by 1 .So next time simply i is there which now have value 4 so i=4 will be accepted and the output will be 43.
Question 22

The following program fragment

int a=4, b=6;

print (“%d”, a==b);
A
outputs an error message
B
prints 0
C
prints 1
D
none of the above
Question 22 Explanation: 
“==” is a binary operator which either gives value either 1 or 0 depending on whether it is true or false. Since the value of variable ‘a’ and ‘b’ are different so the == operator will be false and the output will be 0.
Question 23

Consider the following program

float myFunc(float *array, int size)

{

float x=0;

if (size!=0)

X = *array + myFunc(array+1, size-1);

return x;

}



void main ( )

{

float array [5] = {0, 0.5, 1.0, 1.5, 2};

printf (“%f\n”, myFunc(array,5));

}



What is the output of the program and how many times that the function “myFunc” is called?
A
3 and 6
B
5 and 5
C
5 and 6
D
None of the above
Question 23 Explanation: 

Hence the output will be 5 and no. of times the myFunc() function is called is 6.
Question 24
How many RAM chips of size (256K × 1 bit) are required to build 1M byte memory?
A
8
B
10
C
32
D
24
Question 24 Explanation: 
Question 25
Property of locality of reference may fail if a program has
A
Many conditional jumps
B
Many unconditional jumps
C
Many operands
D
All of these
Question 25 Explanation: 
A R locality of reference, also known as the principle of locality,is the tendency of a processor to access the same set of memory locations repetitively over a short period of time.
Question 26
The strategy by which algorithms are expressed in terms of general ideas, each of which can be further developed in general terms is called:
A
Top-Down design
B
Pseudo-coding
C
Software engineering
D
Bottom-Up design
Question 26 Explanation: 
Pseudocode is basically just writing down the logic of your solution to a specific coding challenge using plain English. So we can say that the strategy by which algorithms are expressed in terms of general ideas, each of which can be further developed in general terms is called Pseudo-coding
Question 27

What is the output of the following arithmetic expression?

5+3*2%10-8*6
A
-37
B
-42
C
-32
D
-28
Question 27 Explanation: 
The multiplication, modulus and division are evaluated first in left-to-right order (i.e., they associate from left to right) because they have higher precedence than addition and subtraction. And then addition and subtraction is evaluated in left to right order.
Hence the answer will be 5+3*2%10-8*6
=5+6%10-8*6
=5+6-8*6
=5+6-48
=5-42
=-37
Question 28
What is the expected number of operations needed to examine all the edges terminated at a particular vertex given an adjacency matrix representation of the graph? (assume n vertices are in the graph and m edges terminate at the desired node.)
A
O(m)
B
O(n)
C
O(m2)
D
O(n2)
Question 28 Explanation: 
Given graph with n vertices is represented in adjacency matrix representation so the expected operations are O(n2)
Question 29
Which of the following circuits can be used as parallel to a serial converter?
A
Multiplexer
B
Demultiplexer
C
Decoder
D
Digital counter
Question 29 Explanation: 
A combinational circuit that selects one from many inputs is known as Multiplexer. In multiplexer, different inputs are inserted parallely and then it gives one output which is in serial form.
Question 30
The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the post order traversal sequence of the same tree?
A
10, 20, 15, 23, 25, 35, 42, 39, 30
B
15, 10, 25, 23, 20, 42, 35, 39, 30
C
15, 20, 10, 23, 25, 42, 35, 39, 30
D
15, 10, 23, 25, 20, 35, 42, 39, 30
Question 30 Explanation: 
The given preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42.
Now let’s draw BST from given preorder sequence,
Question 31
The minimum number of nodes in a binary tree of depth d (root is at level 0) is
A
2d - 1
B
2d + 1 - 1
C
d + 1
D
d
Question 31 Explanation: 
The minimum no. of nodes in a binary tree will be present when the tree is completely skewed tree. Since root is at depth 0 so minimum no. of nodes in a binary tree of depth d will be d+1.
Question 32
The number of possible parenthesizations of a sequence of n matrices is
A
(n)
B
Ө(n lg n)
C
Ω(2^n)
D
None of the above
Question 32 Explanation: 

Question 33
Given a hash table T with 25 slots that stores 2000 elements, the load factor for T is
A
80
B
50
C
40
D
30
Question 33 Explanation: 
The load factor is no. of elements divided by no. of slots in the hash table. Hence the value of load factor will be 2000/25 = 80
Question 34

Consider the following array of elements.

〈89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100〉

The minimum number of interchanges needed to convert it into a max-heap is
A
4
B
5
C
2
D
3
Question 34 Explanation: 
The given sequence is
89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100




Question 35
Consider a complete binary tree where the left and right subtrees of the root are max-heaps. The lower bound for the number of operations to convert it into a heap is
A
Ω(log n)
B
Ω(n)
C
Ω(n log n)
D
Ω(n2)
Question 35 Explanation: 
Here we can apply the max heapify() function which takes O(logn) time. So the most appropriate answer is option a.
Question 36
Consider two decision problems Q1, Q2 such that Q1 reduces in polynomial time to 3-SAT and 3-SAT reduces in polynomial time to Q2. Which one of the following is consistent with the above statement?
A
Q1 is in NP, Q2 is NP hard
B
Q2 is in NP, Q1 is NP hard
C
Both Q1 and Q2 are in NP
D
Both Q1 and Q2 are NP hard
Question 36 Explanation: 
3-SAT ⇒ NPC problem
Q1≤p 3-SAT≤p Q2 ≤p ≤p hence → Q1 is in NP
but Q2 is not given in NP
Hence Q2 is in NP-Hard.
Question 37

Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE?

I. Quick sort runs in ⊝(n2) time

II. Bubble sort runs in ⊝(n2) time

III. Merge sort runs in ⊝(n) time

IV. Insertion sort runs in ⊝(n) time
A
I and II only
B
I and III only
C
II and IV only
D
I and IV only
Question 37 Explanation: 
When the input sequence is already in sorted order then
Quicksort runs in worst case complexity of ⊝(n2) time
Bubble sort runs in best case complexity of ⊝(n) time
Merge sort always have same complexity of ⊝(nlogn) both in best case and worst case
Insertion sort runs in best case complexity of ⊝(n) time
Hence statement I and IV are correct.
Question 38
The minimum number of nodes in an AVL tree (height balanced binary tree) of height 9 is
A
54
B
64
C
87
D
None of these
Question 38 Explanation: 
AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes.
Let minimum no. of nodes in an AVL tree with height h be N(h).
So recursively we can write that ,
N(h) = root node + minimum no of nodes in AVL tree with height (h-1) + minimum no. of nodes in AVL tree with height (h-2).
N(h) = 1+N(h-1)+N(h-2)
For base case N(1)=2 and N(2) = 4
So lets now find N(9),
N(3)= 1+ N(2)+N(1)= 1+2+4=7
N(4) = 1+N(3)+N(2)=1+7+4=12
N(5)= 1+N(4)+N(3)= 1+12+7=20
N(6)=1+N(5)+N(4)= 1+20+12= 33
N(7)=N(6)+N(5)+1= 1+33+20=54
N(8)=1+N(7)+N(6)= 1+54+33=88
N(9) = 1 + N(8)+N(7) = 1+88+54=143
Question 39
Every context-free grammar (CFG) can be converted into an equivalent
A
Greibach Normal Form (GNF)
B
Chomsky Normal Form (CNF)
C
(a) and (b) both
D
None of these
Question 40
The cardinality of the power set of {0, 1, 2, 10, 15} is
A
8
B
10
C
32
D
14
Question 40 Explanation: 
Since the set contains 5 elements so the power set will contain 2^5 = 32 elements.
Question 41
Let R be a relation on the set of positive integers such that aRb if and only if a and b are distinct and have a common divisor other than 1. Which of the following statements about R is true?
A
R is symmetric and reflexive but not transitive
B
R is reflexive but not symmetric and not transitive
C
R is transitive but not reflexive and not symmetric
D
R is symmetric but not reflexive and not transitive
Question 41 Explanation: 
R cannot be reflexive since in aRb and and b are distinct.
R cannot be transitive. Let's take an example. Suppose R contains (2,4) and (4,2) then for transitivity to satisfy R must also contain (2,2) which cannot be present in R since in aRb ‘a’ and ‘b’ must be different.
R is symmetric because if (2,4) have common divisors other than 1 then (4,2) also have common divisors other than 1.

Question 42
The Floyd-Warshall algorithm for all-pair shortest paths computation is based on
A
Greedy paradigm
B
Divide-and-Conquer paradigm
C
Dynamic Programming paradigm
D
Neither Greedy nor Divide-and-Conquer nor Dynamic Programming paradigm
Question 42 Explanation: 
The Floyd-Warshall algorithm for all-pair shortest paths computation is based on Dynamic Programming paradigm.
Question 43
Let X be a random variable with PDF given by

The value of constant c is
A
1.5
B
2.5
C
3.5
D
4.5
Question 43 Explanation: 


Question 44
For a Poisson Distribution, if mean(m) = 1, then P(1) is
A
1.5
B
e
C
2/e
D
1/e
Question 44 Explanation: 
Question 45
On a positive edge-triggered S-R flip-flop, the outputs reflect the input condition when
A
The clock pulse is LOW
B
The clock pulse is HIGH
C
The clock pulse transitions from LOW to HIGH
D
The clock pulse transitions from HIGH to LOW
Question 45 Explanation: 
On a positive edge-triggered S-R flip-flop, the outputs reflect the input condition when the clock pulse transitions from LOW to HIGH.
On a negative edge-triggered S-R flip-flop, the outputs reflect the input condition when the clock pulse transitions from HIGH to LOW.
On a positive level-triggered S-R flip-flop, the outputs reflect the input condition when the clock pulse is HIGH.
On a negative level-triggered S-R flip-flop, the outputs reflect the input condition when the clock pulse is LOW.
Question 46
Research ethics do not include
A
Honesty
B
Subjectivity
C
Integrity
D
Objectivity
Question 46 Explanation: 
Research ethics provides guidelines for the responsible conduct of research. In addition, it educates and monitors scientists conducting research to ensure a high ethical standard. The following is a general summary of some ethical principles: Honesty:Honestly report data, results, methods and procedures, and publication status. Do not fabricate, falsify, or misrepresent data.
Objectivity:Strive to avoid bias in experimental design, data analysis, data interpretation, peer review, personnel decisions, grant writing, expert testimony, and other aspects of research.
Integrity:Keep your promises and agreements; act with sincerity; strive for consistency of thought and action.
Carefulness:Avoid careless errors and negligence; carefully and critically examine your own work and the work of your peers. Keep good records of research activities.
Openness:Share data, results, ideas, tools, resources. Be open to criticism and new ideas.
Respect for Intellectual Property:Honor patents, copyrights, and other forms of intellectual property. Do not use unpublished data, methods, or results without permission. Give credit where credit is due. Never plagiarize.
Confidentiality:Protect confidential communications, such as papers or grants submitted for publication, personnel records, trade or military secrets, and patient records.
Responsible Publication:Publish in order to advance research and scholarship, not to advance just your own career. Avoid wasteful and duplicative publication.
Responsible Mentoring:Help to educate, mentor, and advise students. Promote their welfare and allow them to make their own decisions.
Respect for Colleagues:Respect your colleagues and treat them fairly.
Social Responsibility:Strive to promote social good and prevent or mitigate social harms through research, public education, and advocacy.
Non-Discrimination:Avoid discrimination against colleagues or students on the basis of sex, race, ethnicity, or other factors that are not related to their scientific competence and integrity.
Competence:Maintain and improve your own professional competence and expertise through lifelong education and learning; take steps to promote competence in science as a whole.
Legality:Know and obey relevant laws and institutional and governmental policies.
Animal Care:Show proper respect and care for animals when using them in research. Do not conduct unnecessary or poorly designed animal experiments.
Human Subjects Protection:When conducting research on human subjects, minimize harms and risks and maximize benefits; respect human dignity, privacy, and autonomy.
Ref:
https://libguides.library.cityu.edu.hk/researchmethods/ethics
Question 47
In the experimental design, the dependent variable is
A
The one that is not manipulated and in which any changes are observed
B
The one that is manipulated in order to observe any effects on the other
C
A measure of the extent to which personal values affect research
D
An ambiguous concept whose meaning depends on how it is defined
Question 48
Research objectives falls into a number of categories that include
A
planning to get answers for what, why & where type of questions
B
formulate, concept, and planning for research methods
C
exploratory, descriptive, diagnostic and experimentation research
D
considering the logic behind the methods we use in the context of the research
Question 49
If a study is “reliable”, this means that
A
It was conducted by a reputable researcher who can be trusted
B
The measures devised for concepts are stable on different occasions
C
The findings can be generalized to other social settings
D
The methods are stated clearly enough for the research to be replicated
Question 50
What is a research design?
A
A way of conducting research that is not grounded in theory
B
A way of conducting research that is not grounded in theory
C
The style in which you present your research findings, e.g. a graph
D
A framework for every stage of the collection and analysis of data
There are 50 questions to complete.