ISRO Answer Key and Solutions CS Scientist Engineer 2015

basThe ISRO Computer Science (CS) Scientist Engineer test held on October 11, 2015 (Sunday), 1530 Hrs. to 1700 Hrs. Total questions were 80 and test duration were 90 Minutes. Here is the solution of paper according to me of set B.

• The Final Answer Key 2015 for All Sets by ISRO: Click here 
• For complete preparation for ISRO Computer Science visit my this article: Click Here
• For ISRO Answer Key and Solutions Computer Science Scientist Engineer 2016: Click here
• For ISRO Answer Key and Solutions Computer Science Scientist Engineer 2014: Click here
• For ISRO Answer Key and Solutions Computer Science Scientist Engineer 2013: Click here
• For ISRO Answer Key and Solutions Computer Science Scientist Engineer 2011: Click here
• For ISRO Answer Key and Solutions Computer Science Scientist Engineer 2009: Click here
• For ISRO Answer Key and Solutions Computer Science Scientist Engineer 2008: Click here
• For ISRO Answer Key and Solutions Computer Science Scientist Engineer 2007: Click here

---

1. Consider the following log sequence of two transactions on a bank account, with initial balance 12000, that transfer 2000 to a mortgage payment and, then apply a 5% interest
(i)    T1 start
(ii)   T1 B old = 12000 new = 10000
(iii)  T1 M old = 0 new = 2000
(iv)  T1 commit
(v)   T2 start
(vi)  T2 B old = 10000 new = 10500
(vii) T2 commit
Suppose the database system crashed just before log record 7 is written. When the system is restarted, which one statement is true of the recovery procedure?
(a)   We must redo log record 6 set B to 10500
(b)   We must undo log record 6 to set B to 10000 and then redo log record 2 and 3
(c)   We need not redo log records 2 and 3 because transaction T1 has committed
(d)   We can apply redo and operations in arbitrary order because they are idempotent

Correct Answer: (b), ISRO Answer: (c)
Explanation: The database can be modified using two approaches by executing logs:

1. Deferred database modification: permanent database update happens when transaction commits and only new values needs in logs.
2. Immediate database modification: permanent database update happens immediately and old and new both values needs in logs.

By looking on logs and options in this question, it seems to follow immediate database modification. It means till crash of system, few of log records has written in database. But system do not know after crashing that how many log records already written in database. So after restart system, undo all uncommitted transactions like T2 (reverse log record 6 to set B back to 10000) and then redo all committed transactions like T1 (log records 2  and 3). Thus, it needs to undone active transactions (T2) and redo committed transactions (T1). Process Steps: 

1. Go to log record (vii) where system crashed and reads the logs backwards.
2. If find some committed transaction then puts to Redo List; If find some uncommitted transaction then executes its logs in reverse like T2 writes B to 10000.
3. Redo T1's log records like write B to 10000 and M to 2000 without caring already existing values of A & B in database.

Note: Same question had asked in GATE 2006 CS exam.
Reference: http://gateoverflow.in/981/gate2006_20, https://www.youtube.com/watch?v=8rSlq4TaboA

---

2. Given a block can hold either 3 records or 10 key pointers. A database contains n records, then how many blocks do we need to hold the data file and the dense index
(a)   13n/30
(b)   n/3
(c)   n/10
(d)   n/30

Correct Answer: (a)
Explanation:In dense index, there is a key pointer for every search key value in the database. So, we will be need n key pointers for n records. So we need to hold n records and key pointers.

Since 3 records can hold by 1 block => n records file can hold by n/3 blocks
And since 10 key pointers can hold by 1 block => for n records indices do we need n/10 blocks
=> So, totally we need n/3 + n/10 = 13n/30

In sparse index, there is a key pointer for every block of records. So, we will be need n/no-of-blocks key pointers for n records. So we need to hold n records and n/no-of-blocks key pointers.

Since 3 records can hold by 1 block => n records file can hold by n/3 blocks
And since 10 key pointers can hold by 1 block => for n/3 key pointers do we need n/30 blocks
=> So, totally we need n/3 + n/30 = 11n/30
Reference: http://crschmidt.livejournal.com/231405.html?thread=1015533

---

3. The maximum length of an attribute of type text is
(a)   127
(b)   255
(c)   256
(d)   It is variable

Correct Answer: (d), ISRO Answer: (c)
Explanation: This question seems to ask about length of MySQL Database data type 'text' in bytes. As per documentation by MySQL Database, following is written:

• Text is variable-length string type, is stored using a length prefix plus data.
• The length prefix requires from one to four bytes depending on the data type.
• TINYTEXT: 1 Byte + Data and Data < 2⁸, So max length is 256 Bytes
• TEXT: 2 Byte + Data and Data < 2¹⁶, So max length is 65536 Bytes + 1 Byte
• MEDIUMTEXT: 3 Bytes + Data and Data < 2²⁴, So max length is 16 Megabytes + 2 Bytes
• LONGTEXT: 4 Bytes + Data and Data < 2³², So max length is 4 Gigabytes + 3 Bytes

---

4. Let R = (A, B, C, D, E, F) be a relation scheme with the following dependencies
C → F,
E  → A,
EC → D,
A  → B.
Which of the following is a key for R?
(a)  CD
(b)  EC
(c)  AE
(d)  AC

Correct Answer: (b)
Explanation:
To find candidate key follow this easy approach suggested by stinaq.me, draw diagram of dependencies. The diagram shows that we need both E and C to reach every attribute of relation. So EC is only the candidate key in this relation.

Note: Same question had asked in GATE 1999 CS exam.

Reference: http://www.btechonline.org/2013/01/gate-questions-dbms-functional.html

---

5. If D1, D2,..., Dn are domains in a relational model, then the relation is a table, which is a subset of 
(a)  D1 ⊕ D2 ⊕ ... ⊕ Dn
(b)  D1 X D2 X Dn
(c)  D1 ∪ D2 ∪ ... ∪ Dn
(d)  D1 ∩ D2 ∩ ... ∩ Dn

Correct Answer: (b)
Explanation:

Every column in table is bound to have a specific range of values that range is called domain. Table is a subset of cross product of domains.

Note: Same question had asked in UGC NET CS paper II - June 2013 exam and in many other exams.
Reference: http://www.netcomputerscience.com/p/ugc-net-computer-science-solved.html

---

6. Consider the following relational schema:
Suppliers(sid:integer, sname:string, city:string, street:string)
Parts(pid:integer, pname:string, color:string)
Catalog(sid:integer, pid:integer, cost:real)

Consider the following relational query on the above database:
SELECT S.sname
FROM Suppliers S
WHERE S.sid NOT IN (SELECT C.sid
                                       FROM Catalog C
                                       WHERE C.pid NOT IN (SELECT P.pid
                                                                               FROM Parts P
                                                                               WHERE P.color<> 'blue'))

Assume that relations corresponding to the above schema are not empty. Which one of the following is the correct interpretation of the above query?
(a) Find the names of all suppliers who have supplied a non-blue part.
(b) Find the names of all suppliers who have not supplied a non-blue part.
(c) Find the names of all suppliers who have supplied only non-blue parts.
(d) Find the names of all suppliers who have not supplied only non-blue parts.

Correct Answer: None of These, ISRO Answer: (a,c)

Explanation: 

• The subquery “SELECT P.pid FROM Parts P WHERE P.color<> ‘blue’” gives pids of all parts which are not blue. 
• The bigger sub-query “SELECT C.sid FROM Catalog C WHERE C.pid NOT IN (list-of-non-blue-pids)” gives sids of all those suppliers who have supplied blue parts (this will also include who have supplied blue and non-blue both).
• The complete query finds the names of all suppliers who have either supplied only non-blue parts or not supplied anything.

Note: Same question had asked in GATE 2009 CS exam.
Reference: http://gateoverflow.in/1339/gate2009-55

---

7. Consider the following schema:
Emp (Empcode, Name, Sex, Salary, deptt)
A simple SQL query is executed as follows:
SELECT deptt FROM Emp
WHERE sex = 'M'
GROUP by deptt
Having avg (Salary) > { select avg (Salary) from Emp}
The output will be
(a)  Average salary of male employee is the average salary of the organization
(b)  Average salary of male employee is less than the average salary of the organization
(c)  Average salary of male employee is equal to the average salary of the organization
(d)  Average salary of male employee is more than the average salary of the organization

Correct Answer: (d)
Note: Same question had asked in GATE 2004 CS exam.
Reference: http://geeksquiz.com/gate-gate-cs-2004-question-53/

---

8. Given the following expression grammar:
E → E * F | F + E | F
F → F - F | id
Which of the following is true?
(a)  * has higher precedence than +
(b)  - has higher precedence than *
(c)  + and - have same precedence
(d)  + has higher precedence than *

Correct Answer: (b)
Explanation:

      E
   /  |  \
  E   *   F
  |     / | \
  F    F  -  F
  |    |     |
 id    id    id

By looking on this parse tree, first we will require to solve F-F to make it F. So, here - is having higher precedence than any other symbols + and *. There + and * are having same precedence. 

Note: Same question had asked in GATE 2000 CS exam.
Reference: http://geeksquiz.com/gate-gate-cs-2000-question-44/

---

9. The number of token the following C statement is
printf("i  = %d, &i = %x", i&i);
(a)   13
(b)   6
(c)   10
(d)   11

Correct Answer: None of These
Explanation:

(c) could be a correct answer if printing mistake would not happened.
Tokens are:

1. printf 
2. (
3. "i=%d, &i=%x"
4. ,
5. i
6. , ← this comma missed in statement (if not count this as token, then ans is 9 but it not present in given options)
7. &
8. i
9. )
10. ;

Note: Same question had asked in GATE CS 2000 exam.
Reference: http://gateoverflow.in/641/gate2000_1-18

---

10. Which grammar rules violate the requirement of the operator grammar? A, B, C are variables and a, b, c are terminals
(i)    A → BC
(ii)   A → CcBb
(iii)  A → BaC
(iv)  A  → ε
(a)  (i) only
(b)  (i) and (ii)
(c)  (i) and (iii) 
(d)  (i) and (iv)

Correct Answer: (d)
Explanation:

An operator precedence grammar is a kind of context-free grammar that can be parsed with an operator-precedence parser. It has the property that no production has either an empty (ε) right-hand side or two adjacent non terminals in its right-hand side.

Note: Similar question had asked in GATE CS 2004 exam.
Reference: http://www.geeksforgeeks.org/compilers-set-1/

---

11. Which one of the following is a top down parser? 
(a)  Recursive descent parser
(b)  Shift left associative parser
(c)  SLR(k) parser
(d)  LR(k) parser

Correct Answer: (a)
Explanation: Recursive Descent parsing is LL(1) parsing which is top down parsing.
Note: Same question had asked in GATE CS 2007 exam.
Reference: http://geeksquiz.com/gate-gate-cs-2007-question-18/

---

12. Yacc stands for
(a)  Yet accept compiler constructs
(b)  Yet accept compiler compiler
(c)  Yet another compiler constructs
(d)  Yet another compiler compiler

Correct Answer: (d)

---

13. Which statement is true?
(a)  LALR parser is most powerful and costly as compare to other parser
(b)  All CFG's are LP and not all grammars are uniquely defined
(c)  Every SLR grammar is unambiguous but not every unambiguous grammar is SLR
(d)  LR(k) is the most general back tracking shift reduce parsing method

Correct Answer: (c)
Explanation:

(a) Most powerful and costly order
LR(0) < SLR(1) < LALR(1) < CLR(1)
LR (0) is the basic machine on which other three are built (Reference)
(d) LR(k) is the most general non back tracking shift reduce parsing method(Reference)

---

14. Semaphores are used to solve the problem of
(i)    race condition
(ii)   process synchronization
(iii)  mutual exclusion
(iv)  none of the above
(a)   (i) and (ii)
(b)   (ii) and (iii)
(c)   All of the above
(d)   None of the above

Correct Answer: (b)
Note: option (b) looks most perfect answer instead of other options.
Explanation: Race condition can also be avoided by using mutual exclusion or synchronization, so indirectly by semaphore. But there is no option with saying that (i), (ii) and (iii), so only answer is looking nearest is (b).
Reference: http://gateoverflow.in/19489/isro2015-30

---

15. If there are 32 segments, each size 1 k bytes, then the logical address should have
(a)   13 bits
(b)   14 bits
(c)   15 bits
(d)   16 bits

Correct Answer: (c)
Explanation: To specify a particular segment, 5 bits are required. To select a particular byte after selecting a segment, 10 more bits are required. Hence 15 bits are required.
Reference: http://gateoverflow.in/51212/isro2015-31

---

16. In a lottery scheduler with 40 tickets, how we will distribute the tickets among 4 processes P1, P2, P3 and P4 such that each process gets 10%, 5%, 60% and 25% respectively?
        P1    P2   P3    P4
(a)   12     4     70    30
(b)   7       5     20    10
(c)   4       2     24    10
(d)   8       5     40    30

Correct Answer: (c)
Explanation: Just distribute the tickets according given % to each process.
P1 = 40's 10% = 4, P2 = 40's 5% = 2, P3 = 40's 60% = 24, P4 = 40's 25% = 10

---

17. Suppose a system contains n processes and system uses the round-robin algorithm for CPU scheduling then which data structure is best suited ready queue of the processes
(a)   stack
(b)   queue
(c)   circular queue
(d)   tree

Correct Answer: (c)
Reference: https://en.wikipedia.org/wiki/Round-robin_scheduling

---

18. A hard disk system has the following parameters:
Number of track = 500
Number of sectors/track = 100
Number of bytes/sector = 500
Time taken by the head to move from one track to adjacent track = 1 ms
Rotation speed = 600 rpm 
What is the average time taken for transferring 250 bytes from the disk?
(a)  300.5 ms
(b)  255.5 ms
(c)  255 ms
(d)  300 ms

Correct Answer: (d)
Explanation: Average time to transfer 250 bytes from the disk =
average seek time (time taken by read-write head to move between sectors on the disk)  +
average rotational latency (time taken by platters to spin the data under the head) +
the transfer time for 250 bytes

average seek time = (1/2) × (no. of tracks-1)  × time taken to  move from one track to adjacent track
                            = (1/2) × 499 × 1 ms = 249.5 ms
average rotational latency = time required for (1/2) of a full rotation
                                       = (1/2) × (1/600) minutes = (1/2) × (60/600) seconds = (1/20) seconds
                                       = 0.05 seconds = 50 ms
transfer time for 250 bytes = (rotational delay X number of bytes to transfer) / whole data in a track
                                         = ((60/600) s X 250) / (100X500)
                                         = (0.1 s X 250) / 50000 = 1 s / 2000 = 0.5 ms

Average time to transfer 250 bytes from the disk = 249.5 ms + 50 ms  + 0.5 ms = 300 ms
Note: Same question had asked in GATE IT 2007 exam.
Reference: https://www.assignmentexpert.com/free-answers/Math-Answer-44427.pdf, http://gateoverflow.in/3479/gate2007-it_44 

---

19. At a particular time of computation the value of a counting semaphore is 7. Then 20 P operations and 15 V operations were completed on this semaphore.The resulting value of the semaphore is
(a)   42
(b)   2
(c)   7
(d)   12

Correct Answer: (b)
Explanation: P represents Wait and V represents Signal. Thus, 7 + 15 - 20 = 2
Note: Same question had asked in GATE CS 1992 exam.
Reference: http://www.jkinfoline.com/voip-codec/446-counting-semaphore.html

---

20. Increasing the RAM of a computer typically improves performance because
(a)   Virtual memory increases
(b)   Larger RAMs are faster
(c)   Fewer page faults occur
(d)   Fewer segmentation faults occur

Correct Answer: (c)
Explanation: When there is more RAM, there would be more mapped virtual pages in physical memory, hence fewer page faults. A page fault causes performance degradation as the page has to be loaded from secondary device.
Note: Same question had asked in GATE CS 2005 exam.
Reference: http://geeksquiz.com/operating-systems-memory-management-question-3/

---

21. Consider the following program
main()
{
fork();
fork();
fork();
}
How many processes will be created?

(a)   9
(b)   6
(c)   7
(d)   5

Correct Answer: (c)
Explanation: 7 child process will be created because 1 process is already present at the start.
Reference: http://stackoverflow.com/questions/19106576/how-many-processes-are-created-with-these-fork-statements

---

22. Suppose two jobs, each of which needs 10 min of CPU time, start simultaneously. Assume 50% I/O wait time.
How long will it take for both to complete if they run sequentially.
(a)   10
(b)   20
(c)   30
(d)   40

Correct Answer: (c), ISRO Answer: (d)
Explanation:
CPU time for each job = 10 min
I/O time for each job = 50% of job's total time = 10 min
A job's total time =  CPU time + I/O time
                            =  10 min + 50% of job's total time
                            =  10 min + 10 min

Before I/O of any process, CPU time of that process should used.

Completion time of jobs =
10 min (Job A CPU time) + 10 min (Job B CPU time & Job A IO) + 10 min (Job B IO) = 30 minutes
Reference: http://gateoverflow.in/19455/how-long-will-it-take-for-both-complete-they-run-sequentially

---

23. If a node has K children in B tree, then the node contains exactly ______ keys.
(a)   K^2
(b)   K-1
(c)   K+1
(d)   √K
 
Correct Answer: (b)
Explanation: 

• B-tree is a self-balancing tree data structure that keeps data sorted.
• B-tree is a generalization of a binary search tree in that a node can have more than two children.
• Commonly used in databases and file systems.
• A node with k children contains k−1 keys.

Reference: https://en.wikipedia.org/wiki/B-tree

---

24. The time complexity of the following C function is (assume n > 0).
int recursive (int n) {
if (n==1)
return (1);
else
return (recursive (n-1) + recursive (n-1));
}
(a)   O(n)
(b)   O(n log n)
(c)   O(n^2)
(d)   O(2^n)

Correct Answer: (d)
Explanation:  Recursive expression for the function is:   
T(n) = 2T(n-1) + c
T(1) = c1
And calls will be done like this:
T(n) = 2(2T(n-2) + c) + c        = 4T(n-2) + 3c
T(n) = 8T(n-3) + 6c + c          =  8T(n-3) + 7c
T(n) = 16T(n-4) + 14c + c      =  16T(n-4) + 15c
...........................................................................
...........................................................................
T(n) = (2^(n-1))T(1) +  (2^(n-1) - 1)c = O(2^n)
Note: Same question had asked in GATE CS 2004 exam.
Reference: http://geeksquiz.com/algorithms-analysis-of-algorithms-question-24/

---

25. The number of spanning trees for a complete graph with seven vertices is
(a)   2^5
(b)   7^5
(c)   3^5
(d)   2^(2X5)

Correct Answer: (b)
Explanation:
For a complete graph with n vertices, Cayley's formula gives the number of spanning trees as: nⁿ⁻².
Reference: https://en.wikipedia.org/wiki/Spanning_tree

---

26. If one uses straight two-way merge sort algorithm to sort the following elements in ascending order : 20, 47, 15, 8, 9, 4, 40, 30, 12, 17, then the order of these elements after second pass of the algorithm is
(a)   8, 9, 15, 20, 47, 4, 12, 7, 30, 30
(b)   8, 15, 20, 47, 4, 9, 30, 40, 12, 17
(c)   15, 20, 47, 4, 8, 9, 12, 30, 40, 17
(d)   4, 8, 9, 15, 20, 47, 12, 17, 30, 40

Correct Answer: (b)
Explanation:
20   47   15   8   9    4   40   30   12   17
  \    /       \    /     \    /       \    /       \    /
 20 47     8  15    4 9      30 40     12  17    after 1st pass
   \         /               \         /             \   /
    \       /                 \       /               \ /
8,15,20,47          4,9, 30,40         12,17     after 2nd pass
Note: Same question had asked in GATE CS 1999 exam. 
Reference: https://www.gatementor.com/viewtopic.php?f=263&t=11091

---

27. Let R1 and R2 be regular sets defined over the alphabet, then
(a)   R1 ∩ R2 is not regular
(b)   R1 ∪ R2 is not regular 
(c)   ∑ *- R1 is regular
(d)   R1* is not regular

Correct Answer: (c)
Explanation:

• A regular expression is a sequence of characters that define a pattern. Its opposite is not regular. Example: a(aa)* is a regular expression.
• Any set that represents the value of the Regular Expression is called a Regular Set. Example: {a, aaa, aaaaa,.....} is a regular set.
• Let R1 and R2 be Regular sets:
• R1 ∩ R2; Common of two regular sets will be regular set.
• R1 ∪ R2; Union of two regular sets will be regular set.
• Let ∑ is any alphabet, ∑* is a universal language which is accepted by finite automata. Also R1 is regular language and ∑* - R1 is also accepted by FA. Thus, ∑ *- R1 is regular.
• Complement of R1 means (∑ * - R1) can be obtained by interchanging the finale and non-final states from FA of R1. So, R1* is also regular.

Reference 1: https://en.wikipedia.org/wiki/Regular_language and link
Reference 2: http://www.tutorialspoint.com/automata_theory/regular_sets.htm 

---

28. The DNS maps the IP address to
(a)   A binary address as strings
(b)   An alphanumeric address
(c)   A hierarchy of domain names
(d)   A hexadecimal address

Correct Answer: (c)
Reference: https://en.wikipedia.org/wiki/Domain_Name_System

---

29. To add a background color for all <h1> elements, which of the following HTML syntax is used
(a)   h1 { background-color : #FFFFFF} 
(b)  { background-color : #FFFFFF}.h1 
(c)  { background-color : #FFFFFF}.h1(all)
(d)  h1.all{ bgcolor= #FFFFFF} 

Correct Answer: (a)
Reference: http://www.w3schools.com/html/html_css.asp

---

30. The correct syntax to write "Hi There" in Javascript is
(a)   jscript.write("Hi There") 
(b)   response.write("Hi There") 
(c)   print("Hi There") 
(d)   print.jscript("Hi There")
  
Correct Answer: None of these
Explanation: All given options are not correct syntax. Following are the possible way to write "Hi There":

• Writing into an alert box, use window.alert("Hi There")
• Writing into the HTML output use document.write("Hi There")
• Writing into an HTML element, use innerHTML
• Writing into the browser console, use console.log("Hi There")

Reference: http://www.w3schools.com/js/js_output.asp

---

31. To declare the version of XML, the correct syntax is
(a)   <?xml version='1.0'/>
(b)   <*xml version='1.0'/> 
(c)   <?xml version="1.0"/>
(d)   <?xml version='1.0'/> 

Correct Answer: (c)
Reference: http://www.w3schools.com/xml/xml_syntax.asp

---

32. A T-switch is used to
(a)   Control how message are passed between computers
(b)   Echo every character that is received 
(c)   Transmit characters one at a time 
(d)   Rearrange the connections between computing equipment

Correct Answer: (d)
Reference: https://physics.ucsd.edu/neurophysics/Manuals/Inmac/Inmac%20An%20Applications%20Guide%20for%20Inmac%20T-Switches.pdf

---

33. What frequency range us used for microwave communications, satellite and radar?
(a)   Low frequency: 30 kHz to 300 kHz
(b)   Medium frequency: 300 kHz to 3 MHz
(c)   Super high frequency: 3000 MHz to 30000 MHz
(d)   Extremely high frequency: 30000 MHz

Correct Answer: (d)
Explaination:

Data Communications And Networking by Forouzan - 4th Edition - Page 481
Reference: http://www.indiabix.com/computer-science/networking/discussion-288 and book link

---

34. How many bits internet address is assigned to each host on a TCP/IP internet which is used in all communication with the host?
(a)   16 bits
(b)   32 bits 
(c)   48 bits
(d)   64 bits

Correct Answer: (b)
Explanation: Each host on the internet is assigned a unique 32 bit internet address (IPV4 address) that is used in all communication with that host.
Reference: http://www4.ncsu.edu/~kksivara/sfwr4c03/lectures/se4c03lecture3.pdf

---

35. How many characters per sec (7 bits + 1 parity ) can be transmitted over a 2400 bps line if the transfer is synchronous (1 start and 1 stop bit)? 
(a)    300
(b)    240 
(c)    250
(d)    275

Correct Answer: (a)
Explanation: Synchronous transmission uses no start and stop bits, but Asynchronous transmission uses start and stop bits to signify the beginning bit component. => Start and stop bits are not needed so characters per sec is 2400/8 = 300
Reference: https://en.wikipedia.org/wiki/Data_transmission

---

36. In CRC if the data unit is 100111001 and the divisor is 1011 then what is dividend at the receiver?
(a)   100111001101
(b)   100111001011 
(c)   100111001
(d)   100111001110

Correct Answer: (b)
Explanation: In CRC we send a dividend to receiver generated by CRC procedure at sender.
Dividend that require to send to receiver = data unit padded by (number of divisor bits -1) remainder bits at sender

Data unit = 1001 11001
Divisor = 1011
Remainder = 011
Dividend that require to send to receiver = 1001 11001 011

1001 11001 000 <--- data unit's right side padded by 3 zero bits
1011                   <--- divisor
    1011 001 000 <--- result (note the first four bits are the XOR with the divisor beneath, the rest of the bits are unchanged)
    1011               <--- divisor
                  1000 <--- note that the divisor moves over to align with the next 1 in the dividend (since quotient for that step was zero)
                  1011        (in other words, it doesn't necessarily move one bit per iteration)
-----------------
0000 00000 011 <--- remainder (3 bits).  Division algorithm stops here as quotient is equal to zero.
Reference: https://en.wikipedia.org/wiki/Cyclic_redundancy_check

---

37. An ACK number of 1000 in TCP always means that
(a)   999 bytes have been successfully received
(b)   1000 bytes have been successfully received
(c)   1001 bytes have been successfully received
(d)   None of the above
  
Correct Answer: (d)
Explanation: with ACK number, does not possible to comment about the total received data. It only means that next SEQ number should be 1000 and some data received after last acknowledgement sent.
Reference: Forouzan Mixed Quiz Chapter 22 and https://www.gatementor.com/viewtopic.php?f=269&t=2277&view=next

---

38. In a class B subnet, we know the IP address of one host and the mask as given below:
(a)   125.134.96.0
(b)   125.134.112.0
(c)   125.134.112.66
(d)   125.134.0.0
  
Correct Answer: (a)
Explanation:
Given Subnet is:   11111111.11111111.11100000.00000000 => 255.255.224.0 
Given IP is:        01111101.10000110.01110000.01000010 => 125.134.112.66
AND of both is: 01111101.10000110.01100000.00000000 => 125.134.96.0
We have found the first IP address (network address): 125.134.96.0
Reference: https://in.answers.yahoo.com/question/index?qid=20081220063018AAO3zVa

---

39. A certain population of ALOHA users manages to generate 70 request/sec. If the time is slotted in units of 50 msec, then channel load would be
(a)   4.25
(b)   3.5
(c)   450
(d)   350
  
Correct Answer: (b)
Explanation:
In slotted ALOHA we divide the time into slots and force the station to send only at the beginning of the time slot. Here slot time is 50 ms, so number of slots in 1 second = 1/(50 X 10^-3) => 20 slots/sec

• Requests per second = 70
• Time slots per second = 20
• Channel load = No. of Requests / No. of Slots = 70 / 20 = 3.5

Reference: http://www.cs.wichita.edu/~chang/lecture/cs742/homework/hwk3-sol.txt

---

40. Which statement is false?
(a)   PING is a TCP/IP application that sends datagrams once every second in the hope of an echo response from the machine being PINGED
(b)   If the machine is connected and running a TCP/IP protocol stack , it should respond to the PING datagram with a datagram of its own
(c)   If PING encounters an error condition, an ICMP message is not returned
(d)   PING display the time of the return response in milliseconds or one of several error message

Correct Answer: (c)
Explanation: if PING encounters an error condition, an ICMP message is returned.
Note: All four options text has taken from reference book (Computer Networking for LANS to WANS: Hardware, Software and Security  By Kenneth Mansfield, Jr., James Antonakos).
Reference: http://gateoverflow.in/19458/which-statement-is-false and book link

---

41. A router uses the following routing table:

Destination	Mask	Interface
144.16.0.0	255.255.0.0	eth0
144.16.64.0	255.255.224.0	eth1
144.16.68.0	255.255.255.0	eth2
144.16.68.64	255.255.255.224	eth3

A packet bearing a estimation address 144.16.68.117 arrives at the router. On which interface will it be forwarded?
(a)   eth0
(b)   eth1
(c)   eth2
(d)   eth3

Correct Answer: (c)
Explanation:
Destination address = 144.16.68.117

We should select a interface that covers less number of IP addresses and our destination address fall in that addresses.
 
Destination address falling in all the networks except eth3. In eth3 IP range is: 144.16.68.64 to 144.16.68.95 due to its mask.

eth0 network can have 255 X 255 IP addresses
eth1 network can have 31 X 255 IP addresses
eth2 network can have 255 IP addresses
eth3 does not a cover for our IP

So, packet will be forwarded to eth2.
Note: Same question had asked in GATE 2006 IT exam.
Reference: http://gateoverflow.in/3607/gate2006-it_63

---

42. Which layers of the OSI reference model are host-to-host layers?
(a)   Transport, session, presentation, application
(b)   Session, presentation, application
(c)   Datalink, transport, presentation, application
(d)  Physical, datalink, network, transport

Correct Answer: (a)
Reference: http://www.proprofs.com/quiz-school/quizshow.php?title=computer-networking-set-2&q=5&next=n

---

43. Alpha and beta testing are forms of
(a)   Acceptance testing
(b)   Integration testing
(c)   System testing
(d)   Unit testing

Correct Answer: (a)
Explanation:

• Alpha testing usually comes after system testing and involves both white and black box testing techniques. The company employees test the software for functionality and give the feedback. After this testing phase any functions and features may be added to the software.
• Beta testing is considered to be the last step in software testing and QA process. The software is delivered to end users and they check the functionality of the software.

Reference: http://blog.bughuntress.com/software-testing-tools/alpha-and-beta-phases-of-software-testing

---

44. If in a software project the number of user input, user output, enquiries, files and external interfaces are (15, 50, 24, 12, 8), respectively, with complexity average weighing factor. The productivity if effort = 70 person-month is
(a)    110.54 
(b)    408.74 
(c)    304.78
(d)    220.14 

Correct Answer: None of These, ISRO Answer: (b)
Explanation: Productivity values in terms of FP/PM does not go as high as given in options.
Software productivity is the ratio between the amount of software produced to the labor and expense of producing it. The effort (expense of producing) is already given 70 person-month. We need to find out amount of software produced. There is a "Function Point Analysis" method that can operate on given data to find out amount in terms of function points.

FP (Functional Points) = UFP X CAF

1. Calculate UFP (Unadjusted Function Point)

There is standard values for functional units according complexity of software project:
Functional units            Low         Average         High
External Inputs               3                  4                6
External Outputs            4                  5                7
External Inquiries           3                 4                5
Internal logical files       7                  10             15
External interface files   5                  7               10

Given numbers of functional units:
External Inputs             15
External Outputs          50
External Inquiries         24
Internal logical files       12
External interface files   8

Given complexity weighing factor: average

UFP       5      3
        =    ∑     ∑    ZijXWij
              i=1   j=1
        = 15X4 + 50X5 + 24X4 + 12X10 + 8X7 = 60+250+96+120+56 = 582

2. Calculate CAF (Complexity Adjustment Factor)

Each complexity weighting factor is assigned a value (complexity adjustment value) that ranges between 0 (not important) to 5 (absolutely essential). For average we can take 3 for each of 14 factors.

CAF = 0.65 + (0.01 * Total complexity adjustment value)
        =  0.65 + (0.01 * (14X3))
        =  0.65 + 0.42 = 1.07

FP = UFP X CAF
     = 582  X  1.07 = 622.74
 
Productivity = Function Points / Effort in person-month
                      = 622.74/70 = 8.90 FP/PM

Reference 1: http://www.slideshare.net/PiyushGogia/chapter-4-software-project-planning
Reference 2: Software Engineering by Roger S. Pressman - Edition 7 - Page 703

---

45. The contents of the flag register after execution of the following program by 8085 microprocessor will be
Program
SUB A
MVI B, (01)_H
DCR B
HLT
(a) (54)_H (b) (00)_H (c) (01)_H (d) (45)_H

My Answer: None of These, ISRO Answer: (a)
Explanation: 8085 microprocessor has a 8 bit flag register to indicate certain conditions arising after arithmetic and logical operations or to control certain operations.

• Carry flag indicates whether there is carry or not after an arithmetic and logical operation.
• Parity flag indicates whether the result contains odd number of 1s or even number of 1s.
• Auxiliary carry (or half carry) flag indicates that is there carry from the 3rd bit to 4th.
• Zero flag indicates whether the result of an arithmetic or logical operation is zero or nonzero.
• Sign flag indicates whether the result is positive or negative.
• Other bits in this register are undefined.

Lets traverse the program:

• SUB A: subtracts the content of accumulator (A) from the content of the accumulator (A); Content of A will become (00)_H; Flag Register: 0100 0100 because result is zero and result contains 0 (even) number of 1s.
• MVI B, (01)_H : stores 01 in register B; No computation, no change in Flag Register.
• DCR B: decreases content of register B; Content of B will become (00)_H; Flag Register: 0100 0100 because result is zero and result contains 0 (even) number of 1s.

So, flag register after execution will be 0100 0100 = (44)_H.

Reference: http://labs.kitiyo.com/8085/free-online-assember-simulator-8085.html

---

46. The minimum time delay between the initiations of two independent memory operations is called
(a) Access Time 
(b) Cycle Time 
(c) Rotational time 
(d) Latency time

Correct Answer: (b)

Explanation: Cycle time is the minimum time delay between the initiations of two independent memory operations. Access time is the time that elapses between the initiation of an operation and the completion of the operation.

Reference: http://nptel.ac.in/courses/106103068/module03_memory/lecture_01/slides/slide8.htm

---

47. Which of the following compression algorithms is used to generate a .png file?
(a) LZ78
(b) Deflate
(c) LZW
(d) Huffman

Correct Answer: (b)
Reference: http://www.libpng.org/pub/png/book/chapter09.html#png.ch09.div.2

---

48. Dirty bit for a page in a page table
(a) helps avoid unnecessary writes on a paging device
(b) helps maintain LRU information
(c) allows only read on a page
(d) none of these

Correct Answer: (a)

Explanation: When a block of memory is to be replaced, its corresponding dirty bit is checked to see if the block needs to be written back to secondary memory before being replaced or if it can simply be removed.

Note: Same question had asked in GATE CS 1997 exam and ISRO 2008 exam.
Reference: http://gateoverflow.in/2241/gate1997_3-10

---

49. Which of the following is not an image type used in MPEG?
(a) A frame
(b) B frame
(c) D frame
(d) P frame

Correct Answer: (a)

Explanation: A frame is a single still image within the sequence of images that comprise the video. To compress video signals, the MPEG system categorizes video images (frames) into different types. 

Reference: http://www.althos.com/tutorial/MPEG-tutorial-video-frame-types.html

---

50. Consider an uncompressed stereo audio signal of CD quality which is sampled at 44.1 kHz and quantized using 16-bits. What is required storage space if a compression ratio of 0.5 is achieved for 10 seconds of this audio?
(a) 172 KB
(b) 430 KB
(c) 860 KB
(d) 1720 KB

Correct Answer: (c)
Explanation: Given sample frequency = 44.1 kHz = 44100 bits per second
This is stereo audio signal, it will need 2 channels.
While converting to MP3 it will need 16 bits to represent 1 sound signal.
Bit Rate = 2 * 16 * 44100 = 1411200 bps
Given compression ratio = 0.5
Compressed Bit Rate will be = 705600 bps
For 10 seconds, data will be = 7056000 bits = 882000 Bytes = 882 KB
Reference: http://www.theaudioarchive.com/TAA_Resources_File_Size.htm

---

51. What is the compression ratio in typical mp3 audio file?
(a) 4:1
(b) 6:1
(c) 8:1
(d) 10:1

Correct Answer: (d)

Explanation: MP3 is an audio coding format for digital audio which uses a form of lossy data compression. The rate of 128 kbps is commonly used at a compression ratio of 11:1, offering adequate audio quality in a relatively small space.

Reference: http://gateoverflow.in/49764/isro2015-67 and https://en.wikipedia.org/wiki/MP3

---

52. Consider the following program fragment
if (a > b)
if (b > c)
    s1;
else s2;
s2 will be executed if
(a) a <= b
(b) b > c
(c) b >= c and a <= b
(d) a > b and b <= c

Correct Answer: (d)
Explanation: Given program fragment is without braces, it is equivalent with braces will be like this:
if (a > b)
{
    if (b > c) { s1; }
    else { s2; }
}
Note: A expression's scope remains until its sub expressions does not complete.
Reference: Executed program on URL: https://ideone.com/GmMM5E

---

53. If n has the value 3, the the statement a[++n] = n++;
(a) assigns 3 to a[5]
(b) assigns 4 to a[5]
(c) assigns 4 to a[4]
(d) what is assigned is compiler dependent

Correct Answer: (d)
Explanation: Given statement is modify the value of n two times so it depends on compiler whether it will evaluate ++n inside array subscript or assign n++ to array index.
Reference: http://gateoverflow.in/19372/isro_a-2015-69

---

54. The following program
main()
{
  inc(); inc(); inc();
}
inc()
{
  static int x;
  printf(“%d”,++x);
}
(a) prints 012 
(b) prints 123 
(c) prints 3 consecutive, but unpredictable numbers 
(d) prints 111

Correct Answer: (b)

Explanation: static variable auto initialize by zero. And have last updated value always. So on every call of function inc() it is printing value with increment in last updated value of x.

Reference: http://gateoverflow.in/52131/isro2015-70

---

55. Consider the following program fragment
i = 6720; j = 4;
while((i%j)==0)
 {
   i = i/j;
   j = j+1;
 }
on termination j will have the value
(a) 4 (b) 8 (c) 9 (d) 6720

Correct Answer: (c)

Explanation: Traverse the code with evaluating values till while become false.
6720%4 = 0 => i = 1680, j = 5
1680%5 = 0 => i = 336,   j = 6

336%6   = 0 => i = 56,     j = 7

56%7     = 0 => i = 8,       j = 8

8%8       = 0 => i = 1,       j = 9

1%9       = 1 => while became false 

Reference: http://gateoverflow.in/52135/isro2015-71

---

56. Consider the following declaration,
int a, *b = &a, **c = &b;
the following program fragment
a = 4;
**c = 5;
(a) does not change the value of a
(b) assigns address of c to a
(c) assigns the value of b to a
(d) assigns 5 to a

Correct Answer: (d)

Explanation:

Reference: http://gateoverflow.in/19444/isro2015-72

---

57. The output of the following program is
main()
{
  static int x[] = {1,2,3,4,5,6,7,8};
  int i;
  for(i=2;i<6;++i)
    x[x[i]] = x[i];
  for(i=0;i<8;++i)
   printf(“%d”,x[i]);
}
(a) 1 2 3 3 5 5 7 8 
(b) 1 2 3 4 5 6 7 8 
(c) 8 7 6 5 4 3 2 1 
(d) 1 2 3 5 4 6 7 8

Correct Answer: (a)

Explanation: 1st for loop is modifying array values and second for loop is printing whole modified array. Do traverse modifications for i =  2 to i = 5. Array index is 0 to 7.
i = 2, x[x[2]] = x[2] => x[3] = 3 => Modified Array x[] = {1,2,3,3,5,6,7,8}
i = 3, x[x[3]] = x[3] => x[3] = 3 => Modified Array x[] = {1,2,3,3,5,6,7,8}
i = 4, x[x[4]] = x[4] => x[5] = 5 => Modified Array x[] = {1,2,3,3,5,5,7,8}
i = 5, x[x[5]] = x[5] => x[5] = 5 => Modified Array x[] = {1,2,3,3,5,5,7,8}

Reference: http://gateoverflow.in/52137/isro2015-73

---

58. Which of the following has the compilation error in C?
(a) int n = 17;
(b) char c = 99;
(c) float f = (float) 99.32;
(d) #include<stdio.h>

Correct Answer: (d)
Explanation: There is only possibility of compilation error, option (d). When stdio.h file is not available on specified location then error can occur.
Reference: http://gateoverflow.in/19791/isro-2015

---

59. The for loop
for(i = 0;i < 10; ++i)
     printf(“%d”,i&1);
prints
(a) 0101010101 
(b) 0111111111 
(c) 0000000000 
(d) 1111111111

Correct Answer: (a)
Explanation: The & operation of 0 to 9 numbers with 1 will be print one by one. Numbers having last bit as 0 gives output 0 and numbers having last bit as 1 gives output 1.
00....000 & 00...001 = 00...000 will print 0
00....001 & 00...001 = 00...001 will print 1
00....010 & 00...001 = 00...000 will print 0
00....011 & 00...001 = 00...001 will print 1 and so on
Reference: http://gateoverflow.in/19441/isro_a-2015-75

---

60. Consider the following statements
#define hypotenuse (a, b) sqrt (a*a+b*b);
The macro call hypotenuse(a+2,b+3);
(a) Finds the hypotenuse of a triangle with sides a+2 and b+3
(b) Finds the square root of (a+2)2 and (b+3)2
(c) Is invalid
(d) Find the square root of 3*a+4*b+5

Correct Answer: d
Explanation: after macro expansion hypotenuse(a+2,b+3) will become:
sqrt(a+2*a+2+b+3*b+3)
= sqrt(a+2a+2+b+3b+3)
= sqrt(3a+4b+5)
Reference: gateoverflow.in/37955/isro2015-76

---

61. In X = (M + N X O)/(P X Q), how many one address instructions are required to evaluate it?
(a) 4 
(b) 6 
(c) 8 
(d) 10

Correct Answer: (c)
Explanation: To use one address instructions we need to put one operand in accumulator and other operand in any other register or memory. Load and Store will be used as need.
I1: Load P loads value of P from memory
I2: MUL Q multiplies accumulator value and Q value
I3: Store K stores accumulator value to some memory place
I4: Load N loads value of N from memory to accumulator
I5: MUL O 
I6: Add M
I7: Div K divides accumulator value by K memory location value
I8: Store X stores final result from accumulator to some memory location
Reference: http://gateoverflow.in/37956/isro2015-77

---

62. A decimal number has 64 digits. The number of bits needed for its equivalent binary representation is
(a) 200 
(b) 213 
(c) 246 
(d) 277

Correct Answer: (b)
Explanation: There is concept to determine: baseX^{no. of digits} = baseY^{no. of digits}
By following the concept: 10⁶⁴ = 2ⁿ
=> 64 log 10 = n log 2 => n = 64 log₂10 => n = 64 * 3.32 => n = 212.61
Reference: http://gateoverflow.in/50363/decimal-digits-number-needed-equivalent-binary-representation

---

63. Consider the following C declaration
struct{
  short s[5];
  union{
    float y;
    long z;
  }u;
}t;
Assume that objects of type short, float and long occupy 2 bytes, 4 bytes and 8 bytes, respectively. The memory requirement for variable t, ignoring alignment considerations, is
(a) 22 bytes (b) 18 bytes (c) 14 bytes (d) 10 bytes

Correct Answer: (b)
Explanation: Union allocates memory only for large variable in it and same uses for other variables. And structure allocates memory need by all variables. Here:
struct{
  short s[5]; //10 bytes
  union{
    float y; //4 bytes
    long z; //8 bytes
  }u; //8 bytes
}t; //18 bytes
Note: Same question had asked in GATE CS 2000 exam.
Reference: http://gateoverflow.in/640/gate2000_1-17

---

64. Consider the following code segment
void foo(int x, int y)
{
  x += y;
  y += x;
}
main()
{
  int x = 5.5;
  foo(x, x);
}
What is the final value of x in both call by value and call by reference, respectively?
(a) 5 and 16 (b) 5 and 12 (c) 5 and 20 (d) 12 and 20

Correct Answer: (c)

Explanation: When a floating point constant is assigned to an integer value, it gets truncated and only the integer part gets stored.

• Call by Value: Whatever happens will happen in the called activation block in the stack and when we return it will not effect actual x so value will be 5.
• Call by reference: A reference to original memory location is passed. So, in foo, x and y are aliases of the x in main (having same memory location). So, x in main will change and final value will be 20.

Reference: http://gateoverflow.in/52145/isro2015-80

---

65. Which of the given number has its IEEE-754 32-bit floating-point representation as
(0 10000000 110 0000 0000 0000 0000 0000)
(a) 2.5 (b) 3.0 (c) 3.5 (d) 4.5

Correct Answer: (c)

Explanation:
Sign = 0
Exponent = 10000000
Mantissa = 110 0000 0000 0000 0000 0000

Actual exponent = Exponent - Bias =128-127 = 1

Value = (-1)s * (1.110000.......) * 21
          = (-1)0 * (1⨉20 + 1⨉2-1  + 1⨉ 2-2  + 0⨉2-3 + ...)* 21

          = 1 * (1+.5+.25 + 0 + ...) * 2 = 3.5

Ref: http://gateoverflow.in/44821/floating-point-representation-10000000-0000-0000-0000-0000

---

66. The range of integers that can be represented by an n-bit 2’s complement number system is
(a) -2n-1 to (2n-1 – 1)
(b) -2(2n-1 – 1) to (2-n-1 – 1)
(c) -2n-1 to 2n-1
(d) -2(2n-1 + 1) to (2n-1 – 1)

Correct Answer: (a)

Explanation: The most common format used to represent signed integers in modern computers is two's complement.
Reference: https://en.wikipedia.org/wiki/Two%27s_complement

---

67. How many 32 K x 1 RAM chips are needed to provide a memory capacity of 256 K-bytes?
(a) 8 (b) 32 (c) 64 (d) 128

Correct Answer: (c)

Explanation: Total RAM chips need
= Total Size / 1 RAM Size
= 256 K-bytes / 32 K
= (256 K * 8) / 32 K
= 64
Note: Same question had asked in GATE CS 2009 exam.
Reference: http://gateoverflow.in/1299/gate2009-7-isro2015-3

---

68. A modulus-12 ring counter requires a minimum of
(a) 10 flip-flops 
(b) 12 flip-flops 
(c) 8 flip-flops 
(d) 6 flip-flops

Correct Answer: (b)

Explanation: In ring counter n flip flops generate n states and in twisted ring counter n flip flops generate 2n states.
Reference: http://gateoverflow.in/19487/isro2015-4

---

69. The complement of the Boolean expression AB(B'C + AC) is
(a) (A' + B') + (B + C') . (A' + C')
(b) (A' . B') + (B C' + A' C')
(c) (A' + B') . (B + C') + (A + C')
(d) (A + B) . (B' + C) (A + C)

Correct Answer: (a)

Explanation: Complement of AB(B'C + AC) is
= (AB(B'C + AC))'
= (AB)' + (B'C + AC)'
= (A' + B') + (B'C)' . (AC)'
= (A' + B') + (B + C') . (A' + C')

---

70. The code which uses 7 bits to represent a character is
(a) ASCII 
(b) BCD 
(c) EBCDIC 
(d) Gray

Correct Answer: (a)

Explanation:

• ASCII encodes 128 specified characters into seven-bit integers (Extended ASCII uses 8 bits).
• Binary coded decimal (BCD) is a system of writing numerals that assigns a four-digit binary code to each digit 0 through 9 in a decimal (base-10) numeral.
• Extended Binary Coded Decimal Interchange Code (EBCDIC) is an eight-bit character encoding.
• The reflected binary code (RBC), also known as Gray code, is a binary numeral system where two successive values differ in only one bit.

Reference: http://gateoverflow.in/46690/isro2015-6

---

71. If half adders and full adders are implements using gates, then for the addition of two 17 bit numbers (using minimum gates) the number of half adders and full adders required will be
(a)   0, 17 
(b)   16, 1 

(c)   1, 16 
(d)   8, 8

Correct Answer: (c)
Explanation: To add bits without carry half adder is appropriate and with carry full adder is appropriate. So for 17 bit numbers, initial 1 bit of each number add using half adder and other 16 bits and carry from each step will need full adder. So, 1 half adder and 16 full adders required.
Reference: http://gateoverflow.in/19462/isro2015-7

---

72. Minimum number of 2 x 1 multiplexers required to realize the following function,

Assume that inputs are available only in true form and Boolean a constant 1 and 0 are available.
(a)   1
(b)   2 
(c)   3 
(d)   7

Correct Answer: (b)
Explanation: A'B'C + A'B'C' = A'B' = (A+B)' => NOR
NOR gate can be realize using two 2 x 1 multiplexers.

Reference: http://gateoverflow.in/48660/no-of-multipexers-isro-2015

---

73. The number of 1s in the binary representation of (3*4096+15*256+5*16+3) are
(a)   8 
(b)   9 
(c)   10 
(d)   12

Correct Answer: (c)
Explanation:
4096 (2^12) in binary is:  1000000000000
3 in binary is:                                          11
multiply of both is:           11000000000000 ← 11 is left shifted by 12 bits

256 (2^8) in binary is:      100000000
15 in binary is:                             1111
multiply of both is:        111100000000 ← 1111 is left shifted by 8 bits

16 (2^4) in binary is:        10000
5 in binary is:                       101
multiply of both is:       1010000 ← 101 is left shifted by 4 bits

3 in binary is:                 11

Finale binary is:
11000000000000
+   111100000000
+           1010000
+                     11
-----------------------
11111101010011
-----------------------
Note: Same question had asked in GATE CS 1995 exam.
Reference: http://gateoverflow.in/2624/gate1995_2-12

---

74. The Boolean expression AB+AB’+A’C+AC is independent of the Boolean variable
(a)    A 
(b)    B 
(c)    C 
(d)    None of the above

Correct Answer: (b)
Explanation:
AB+AB’+A’C+AC = A(B+B')+C(A'+A) = A+C => expression is independent of the B

---

75. If the sequence of operations – push(1), push(2), pop, push(1), push(2), pop, pop, pop, push(2), pop are performed on a stack, the sequence of popped out values
(a)   2, 2, 1, 1, 2
(b)   2, 2, 1, 2, 2
(c)   2, 1, 2, 2, 1
(d)   2, 1, 2, 2, 2

Correct Answer: (a)
Explanation:
Operation           Stack Status
push(1)               1
push(2)               1 2
pop                     1                   ← 2 popped out
push(1)               1 1
push(2)               1 1 2
pop                     1 1                ← 2 popped out
pop                     1                   ← 1 popped out
pop                     empty            ← 1 popped out
push(2)                2
pop                     empty           ← 2 popped out
Reference: http://questionbankstacks.blogspot.in/2012/07/stacks-queues.html

---

76. A machine needs a minimum of 100 sec to sort 1000 names by quick sort. The minimum time needed to sort 100 names will be approximately
(a)   50.2 sec
(b)   6.7 sec
(c)   72.7 sec
(d)   11.2 sec

Correct Answer: (b)
Explanation:
Running time of quick sort = c n lg n
For n = 1000, we get 100 = c * 1000 * lg 1000
                            => c = 0.01
So, for n = 100, we get running time = 0.01 * 100 * lg 100 = 6.7
Reference: http://gateoverflow.in/10595/machine-need-sort-1000names-quicksort-time-needed-sort-names and https://www.gatementor.com/viewtopic.php?f=265&t=11170

---

77. Six files F1, F2, F3, F4, F5 and F6 have 100, 200, 50, 80, 120, 150 records respectively. In what order should they be stored so as to optimize act. Assume each file is accessed with the same frequency
(a)    F3, F4, F1, F5, F6, F2
(b)    F2, F6, F5, F1, F4, F3
(c)    F1, F2, F3, F4, F5, F6
(d)    Ordering is immaterial as all files are accessed with the same frequency

Correct Answer: (a)
Explanation:

Since each file has same frequency of access, it's good if we put small files first because to read a particular file we need to start from beginning of tape. Here goal is to find such order of storage that cost to access file is minimum. In order to achieve this, the files are stored in increasing order of file size: F3 F4 F1 F5 F6 F2.

This is basically optimal storage on tapes problem. Greedy approach is used to solve this problem. The files are to be stored sequentially on tape.

Reference: http://gateoverflow.in/19474/files-have-records-respectively-what-order-should-they-stored and book link

---

78. A hash table with 10 buckets with one slot per bucket is depicted in fig. The symbols, S1 and S7 are initially entered using a hashing function with linear probing. The maximum number of comparisons needed in searching an item that is not present is

0	S7
1	S1
2
3	S4
4	S2
5
6	S5
7
8	S6
9	S3

(a)   4
(b)   5
(c)   6
(d)   3

Correct Answer: (b)
Explanation:

It will be one more than the size of the biggest cluster (which is 4) because, assume a search key hashing onto in 8. By linear probing the next location for searching is bin 9. Then 0, then 1. If all these resulted in a miss, we try at bin 2 and stop as it is vacant. This logic may not work if deletion operation is done before the search.

Reference 1: http://punecomsc.blogspot.in/2013/09/symbol-tables-dsps.html
Reference 2: https://courses.cs.washington.edu/courses/cse326/00wi/handouts/lecture16/sld015.htm

---

79. The queue data structure is to be realized by using stack. The number of stacks needed would be
(a)    It cannot be implemented 
(b)    2 stacks 
(c)    4 stacks 
(d)    1 stacks
  
Correct Answer: (b)
Explanation: A queue can be implemented using two stacks.

1st method (Make enQueue operation costly): To insert, first move all from stack 1 to stack 2 and then insert item and then move all back from stack 2 to stack 1. To delete, simply delete from top of stack 1.

2nd method (Make deQueue operation costly): To insert, simply insert in stack 1. To delete, first check if empty then move all from stack 1 to stack 2 and after that delete top from stack 2.
Reference: http://www.geeksforgeeks.org/queue-using-stacks/

---

80. Consider the following Entity Relationship Diagram (ERD)

Which of the following possible relations will not hold if the above ERD is mapped into a relation model?
(a)       Person (NID, Name)
(b)       Qualification (NID, ExamID, QualifiedDate)
(c)       Exam (ExamID, NID, ExamName)
(d)       Exam (ExamID, ExamName)

Correct Answer: (c)
Explanation:

By looking ERD, its clear that we need to make 3 relations (tables) in database that are Person, Exam and Qualification. The exam relation should contain only columns: ExamID and ExamName because it is having N to M connectivity and a strong entity so does not need any other column from any other relation.

---

Key References:

• http://www.gripinit.com/2015/10/12/isro-entrance-test-answer-keys-for-computer-science-oct-11-2015/