Wednesday 29 May 2013

Operating System GATE Questions

1. Which of the following is NOT a valid deadlock prevention scheme? (GATE CS 2000)
(a) Release all resources before requesting a new resource
(b) Number the resources uniquely and never request a lower numbered resource than the last one requested.
(c) Never request a resource after releasing any resource
(d) Request and all required resources be allocated before execution.
Answer: (c)
References:
http://www.cs.jhu.edu/~yairamir/cs418/os4/sld013.htm
http://en.wikipedia.org/wiki/Deadlock

2. Let m[0]…m[4] be mutexes (binary semaphores) and P[0] …. P[4] be processes.
Suppose each process P[i] executes the following:


  wait (m[i]); wait(m[(i+1) mode 4]);

  ------

  release (m[i]); release (m[(i+1)mod 4]);
This could cause (GATE CS 2000)
(a) Thrashing
(b) Deadlock
(c) Starvation, but not deadlock
(d) None of the above
Answer: (b)
Explanation:

You can easily see a deadlock in a situation where..
P[0] has acquired m[0] and waiting for m[1]
P[1] has acquired m[1] and waiting for m[2]
P[2] has acquired m[2] and waiting for m[3]
P[3] has acquired m[3] and waiting for m[0]

3. A graphics card has on board memory of 1 MB. Which of the following modes can the card not support? (GATE CS 2000)

(a) 1600 x 400 resolution with 256 colours on a 17 inch monitor
(b) 1600 x 400 resolution with 16 million colours on a 14 inch monitor
(c) 800 x 400 resolution with 16 million colours on a 17 inch monitor
(d) 800 x 800 resolution with 256 colours on a 14 inch monitor

Answer:
(b)
Explanation:
Monitor size doesn’t matter here. So, we can easily deduct that answer should be (b) as this has the highest memory requirements. Let us verify it.
Number of bits required to store a 16M colors pixel = ceil(log2(16*1000000)) = 24
Number of bytes required for 1600 x 400 resolution with 16M colors = (1600 * 400 * 24)/8 which is 192000000 (greater than 1MB).

4 Consider a virtual memory system with FIFO page replacement policy. For an arbitrary page access pattern, increasing the number of page frames in main memory will (GATE CS 2001)

a) Always decrease the number of page faults
b) Always increase the number of page faults
c) Some times increase the number of page faults
d) Never affect the number of page faults
Answer: (c)
Explanation:
Incrementing the number of page frames doesn’t always decrease the page faults (Belady’s Anomaly). For details see http://en.wikipedia.org/wiki/Belady%27s_anomaly

5. Which of the following requires a device driver? (GATE CS 2001)

a) Register
b) Cache
c) Main memory
d) Disk
Answer: (d)

6. Consider a machine with 64 MB physical memory and a 32-bit virtual address space. If the page size is 4KB, what is the approximate size of the page table? (GATE 2001)
(a) 16 MB
(b) 8 MB
(c) 2 MB
(d) 24 MB
Answer: (c)
Explanation:
A page entry is used to get address of physical memory. Here we assume that single level of Paging is happening. So the resulting page table will contain entries for all the pages of the Virtual address space.
Number of entries in page table = 
                    (virtual address space size)/(page size)  
Using above formula we can say that there will be 2^(32-12) = 2^20 entries in page table.
No. of bits required to address the 64MB Physical memory = 26.
So there will be 2^(26-12) = 2^14 page frames in the physical memory. And page table needs to store the address of all these 2^14 page frames. Therefore, each page table entry will contain 14 bits address of the page frame and 1 bit for valid-invalid bit.
Since memory is byte addressable. So we take that each page table entry is 16 bits i.e. 2 bytes long.
Size of page table = 
  (total number of page table entries) *(size of a page table entry) 
   = (2^20 *2) = 2MB



7. Consider Peterson’s algorithm for mutual exclusion between two concurrent processes i and j. The program executed by process is shown below.

   repeat   
      flag [i] = true; 
      turn = j; 
      while ( P ) do no-op; 
      Enter critical section, perform actions, then exit critical 
      section 
      flag [ i ] = false; 
      Perform other non-critical section actions. 
   until false; 
For the program to guarantee mutual exclusion, the predicate P in the while loop should be (GATE 2001)
a) flag [j] = true and turn = i
b) flag [j] = true and turn = j
c) flag [i] = true and turn = j
d) flag [i] = true and turn = i
Answer: (b)
Basically, Peterson’s algorithm provides guaranteed mutual exclusion by using the two following constructs – flag[] and turn. flag[] controls that the willingness of a process to be entered in critical section. While turn controls the process that is allowed to be entered in critical section. So by replacing P with the following,
flag [j] = true and turn = j
process i will not enter critical section if process j wants to enter critical section and it is process j’s turn to enter critical section. The same concept can be extended for more than two processes. For details, refer the following.
References:
http://en.wikipedia.org/wiki/Peterson%27s_algorithm

8 More than one word are put in one cache block to (GATE 2001)

(a) exploit the temporal locality of reference in a program
(b) exploit the spatial locality of reference in a program
(c) reduce the miss penalty
(d) none of the above
Answer: (b)
Temporal locality refers to the reuse of specific data and/or resources within relatively small time durations. Spatial locality refers to the use of data elements within relatively close storage locations.
To exploit the spatial locality, more than one word are put into cache block.
References:
http://en.wikipedia.org/wiki/Locality_of_reference

9. Which of the following statements is false? (GATE 2001)

a) Virtual memory implements the translation of a program’s address space into physical memory address space
b) Virtual memory allows each program to exceed the size of the primary memory
c) Virtual memory increases the degree of multiprogramming
d) Virtual memory reduces the context switching overhead
Answer: (d)
In a system with virtual memory context switch includes extra overhead in switching of address spaces.
References:
http://www.itee.adfa.edu.au/~spike/CSA2/Lectures00/lecture.vm.htm

10. Consider a set of n tasks with known runtimes r1, r2, … rn to be run on a uniprocessor machine. Which of the following processor scheduling algorithms will result in the maximum throughput? (GATE 2001)

(a) Round-Robin
(b) Shortest-Job-First
(c) Highest-Response-Ratio-Next
(d) First-Come-First-Served
Answer: (b)

11. Suppose the time to service a page fault is on the average 10 milliseconds, while a memory access takes 1 microsecond. Then a 99.99% hit ratio results in average memory access time of (GATE CS 2000)
(a) 1.9999 milliseconds
(b) 1 millisecond
(c) 9.999 microseconds
(d) 1.9999 microseconds
Answer: (d)
Explanation:
Average memory access time =
      [(% of page miss)*(time to service a page fault) +
                  (% of page hit)*(memory access time)]/100
So, average memory access time in microseconds is.
(99.99*1 + 0.01*10*1000)/100 = (99.99+100)/1000 = 199.99/1000 =1.9999 µs

12. Which of the following need not necessarily be saved on a context switch between processes? (GATE CS 2000)

(a) General purpose registers
(b) Translation look-aside buffer
(c) Program counter
(d) All of the above
Answer: (b)
Explanation:
In a process context switch, the state of the first process must be saved somehow, so that, when the scheduler gets back to the execution of the first process, it can restore this state and continue.
The state of the process includes all the registers that the process may be using, especially the program counter, plus any other operating system specific data that may be necessary.
A Translation lookaside buffer (TLB) is a CPU cache that memory management hardware uses to improve virtual address translation speed. A TLB has a fixed number of slots that contain page table entries, which map virtual addresses to physical addresses. On a context switch, some TLB entries can become invalid, since the virtual-to-physical mapping is different. The simplest strategy to deal with this is to completely flush the TLB.
References:
http://en.wikipedia.org/wiki/Context_switch
http://en.wikipedia.org/wiki/Translation_lookaside_buffer#Context_switch

13. Where does the swap space reside ? (GATE 2001)

(a) RAM
(b) Disk
(c) ROM
(d) On-chip cache
Answer: (b)
Explanation:
Swap space is an area on disk that temporarily holds a process memory image. When physical memory demand is sufficiently low, process memory images are brought back into physical memory from the swap area. Having sufficient swap space enables the system to keep some physical memory free at all times.
References:
http://docs.hp.com/en/B2355-90672/ch06s02.html

14. Which of the following does not interrupt a running process?
(GATE CS 2001)
(a) A device
(b) Timer
(c) Scheduler process
(d) Power failure
Answer: (c)
Explanation:
Scheduler process doesn’t interrupt any process, it’s Job is to select the processes for following three purposes.
Long-term scheduler(or job scheduler) –selects which processes should be brought into the ready queue
Short-term scheduler(or CPU scheduler) –selects which process should be executed next and allocates CPU.
Mid-term Scheduler (Swapper)- present in all systems with virtual memory, temporarily removes processes from main memory and places them on secondary memory (such as a disk drive) or vice versa. The mid-term scheduler may decide to swap out a process which has not been active for some time, or a process which has a low priority, or a process which is page faulting frequently, or a process which is taking up a large amount of memory in order to free up main memory for other processes, swapping the process back in later when more memory is available, or when the process has been unblocked and is no longer waiting for a resource.

15. Which of the following scheduling algorithms is non-preemptive? (GATE CS 2002)

a) Round Robin
b) First-In First-Out
c) Multilevel Queue Scheduling
d) Multilevel Queue Scheduling with Feedback
Answer: (b)

16. Using a larger block size in a fixed block size file system leads to (GATE CS 2003)
a) better disk throughput but poorer disk space utilization
b) better disk throughput and better disk space utilization
c) poorer disk throughput but better disk space utilization
d) poorer disk throughput and poorer disk space utilization
Answer (a)
If block size is large then seek time is less (fewer blocks to seek) and disk performance is improved, but remember larger block size also causes waste of disk space.

17. Consider the following statements with respect to user-level threads and kernel supported threads
i. context switch is faster with kernel-supported threads
ii. for user-level threads, a system call can block the entire process
iii. Kernel supported threads can be scheduled independently
iv. User level threads are transparent to the kernel

Which of the above statements are true? (GATE CS 2004)
a) (ii), (iii) and (iv) only
b) (ii) and (iii) only
c) (i) and (iii) only
d) (i) and (ii) only
Answer(a)
http://en.wikipedia.org/wiki/Thread_%28computer_science%29

18. The minimum number of page frames that must be allocated to a running process in a virtual memory environment is determined by (GATE CS 2004)

a) the instruction set architecture
b) page size
c) physical memory size
d) number of processes in memory
Answer (a)
Each process needs minimum number of pages based on instruction set architecture. Example IBM 370: 6 pages to handle MVC (storage to storage move) instruction
Instruction is 6 bytes, might span 2 pages.
2 pages to handle from.
2 pages to handle to.

19. In a system with 32 bit virtual addresses and 1 KB page size, use of one-level page tables for virtual to physical address translation is not practical because of (GATE CS 2003)
a) the large amount of internal fragmentation
b) the large amount of external fragmentation
c) the large memory overhead in maintaining page tables
d) the large computation overhead in the translation process
Answer (c)
Since page size is too small it will make size of page tables huge.
Size of page table =
  (total number of page table entries) *(size of a page table entry)
Let us see how many entries are there in page table
Number of entries in page table =
                    (virtual address space size)/(page size)
                    = (2^32)/(2^10) 
                    = 2^22
Now, let us see how big each entry is.
If size of physical memory is 512 MB then number of bits required to address a byte in 512 MB is 29. So, there will be (512MB)/(1KB) = (2^29)/(2^10) page frames in physical memory. To address a page frame 19 bits are required. Therefore, each entry in page table is required to have 19 bits.
Note that page table entry also holds auxiliary information about the page such 
as a present bit, a dirty or modified bit, address space or process ID information, 
amongst others. So size of page table 
    > (total number of page table entries) *(size of a page table entry)
    > (2^22 *19) bytes
    > 9.5 MB
And this much memory is required for each process because each process maintains its own page table. Also, size of page table will be more for physical memory more than 512MB. Therefore, it is advised to use multilevel page table for such scenarios.
References:
http://barbara.stattenfield.org/ta/cs162/section-notes/sec8.txt
http://en.wikipedia.org/wiki/Page_table

20. A process executes the code
  fork ();
  fork ();
  fork ();
The total number of child processes created is
(A) 3
(B) 4
(C) 7
(D) 8
Answer (C)
Let us put some label names for the three lines
  fork ();    // Line 1
  fork ();   // Line 2
  fork ();   // Line 3

       L1       // There will be 1 child process created by line 1
    /     \
  L2      L2    // There will be 2 child processes created by line 2
 /  \    /  \
L3  L3  L3  L3  // There will be 4 child processes created by line 3
We can also use direct formula to get the number of child processes. With n fork statements, there are always 2^n – 1 child processes. Also see this post for more details.


21. consider the 3 processes, P1, P2 and P3 shown in the table
Process     Arrival time    Time unit required
  P1                0                    5
  P2                1                    7
  P3                3                    4
The completion order of the 3 processes under the policies FCFS and RRS (round robin scheduling with CPU quantum of 2 time units) are
(A) FCFS: P1, P2, P3 RR2: P1, P2, P3
(B) FCFS: P1, P3, P2 RR2: P1, P3, P2
(C) FCFS: P1, P2, P3 RR2: P1, P3, P2
(D) FCFS: P1, P3, P2 RR2: P1, P2, P3
Answer (C)



22. Consider the virtual page reference string
1, 2, 3, 2, 4, 1, 3, 2, 4, 1
On a demand paged virtual memory system running on a computer system that main memory size of 3 pages frames which are initially empty. Let LRU, FIFO and OPTIMAL denote the number of page faults under the corresponding page replacements policy. Then

(A) OPTIMAL < LRU < FIFO
(B) OPTIMAL < FIFO < LRU
(C) OPTIMAL = LRU
(D) OPTIMAL = FIFO
Answer (B)
The OPTIMAL will be 5, FIFO 6 and LRU 9.


23. A file system with 300 GByte uses a file descriptor with 8 direct block address. 1 indirect block address and 1 doubly indirect block address. The size of each disk block is 128 Bytes and the size of each disk block address is 8 Bytes. The maximum possible file size in this file system is
(A) 3 Kbytes
(B) 35 Kbytes
(C) 280 Bytes
(D) Dependent on the size of the disk
Answer (B)
Total number of possible addresses stored in a disk block = 128/8 = 16
Maximum number of addressable bytes due to direct address block = 8*128
Maximum number of addressable bytes due to 1 single indirect address block = 16*128
Maximum number of addressable bytes due to 1 double indirect address block = 16*16*128
The maximum possible file size = 8*128 + 16*128 + 16*16*128 = 35KB

24) A thread is usually defined as a ‘light weight process’ because an operating system (OS) maintains smaller data structures for a thread than for a process. In relation to this, which of the followings is TRUE?
(A) On per-thread basis, the OS maintains only CPU register state
(B) The OS does not maintain a separate stack for each thread
(C) On per-thread basis, the OS does not maintain virtual memory state
(D) On per thread basis, the OS maintains only scheduling and accounting information.
Answer (A)
Threads are called ‘light weight process’ because they only need storage for stack and registers. They don’t need separate space for other things like code segment, global data, etc

25) Let the page fault service time be 10ms in a computer with average memory access time being 20ns. If one page fault is generated for every 10^6 memory accesses, what is the effective access time for the memory?
(A) 21ns
(B) 30ns
(C) 23ns
(D) 35ns
Answer (B)
Let P be the page fault rate
Effective Memory Access Time = p * (page fault service time) + 
                               (1 - p) * (Memory access time)
                             = ( 1/(10^6) )* 10 * (10^6) ns +
                               (1 - 1/(10^6)) * 20 ns
                             = 30 ns (approx)    


26) An application loads 100 libraries at startup. Loading each library requires exactly one disk access. The seek time of the disk to a random location is given as 10ms. Rotational speed of disk is 6000rpm. If all 100 libraries are loaded from random locations on the disk, how long does it take to load all libraries? (The time to transfer data from the disk block once the head has been positioned at the start of the block may be neglected)
(A) 0.50s
(B) 1.50s
(C) 1.25s
(D) 1.00s
Answer (B)
Since transfer time can be neglected, the average access time is sum of average seek time and average rotational latency. Average seek time for a random location time is given as 10 ms. The average rotational latency is half of the time needed for complete rotation. It is given that 6000 rotations need 1 minute. So one rotation will take 60/6000 seconds which is 10 ms. Therefore average rotational latency is half of 10 ms, which is 5ms.
Average disk access time = seek time + rotational latency 
                         = 10 ms + 5 ms 
                         = 15 ms
For 100 libraries, the average disk access time will be 15*100 ms

27. Consider the following table of arrival time and burst time for three processes P0, P1 and P2.
Process   Arrival time   Burst Time
P0            0 ms          9 ms
P1            1 ms          4 ms
P2            2 ms          9 ms
The pre-emptive shortest job first scheduling algorithm is used. Scheduling is carried out only at arrival or completion of processes. What is the average waiting time for the three processes?
(A) 5.0 ms
(B) 4.33 ms
(C) 6.33 ms
(D) 7.33 ms
Answer: – (A)
Process P0 is allocated processor at 0 ms as there is no other process in ready queue. P0 is preempted after 1 ms as P1 arrives at 1 ms and burst time for P1 is less than remaining time of P0. P1 runs for 4ms. P2 arrived at 2 ms but P1 continued as burst time of P2 is longer than P1. After P1 completes, P0 is scheduled again as the remaining time for P0 is less than the burst time of P2.
P0 waits for 4 ms, P1 waits for 0 ms amd P2 waits for 11 ms. So average waiting time is (0+4+11)/3 = 5.

28) Let the time taken to switch between user and kernel modes of execution be t1 while the time taken to switch between two processes be t2. Which of the following is TRUE? (GATE CS 2011)
(A) t1 > t2
(B) t1 = t2
(C) t1 < t2
(D) Nothing can be said about the relation between t1 and t2
Answer: - (C)
Process switching involves mode switch. Context switching can occur only in kernel mode.

29) A system uses FIFO policy for page replacement. It has 4 page frames with no pages loaded to begin with. The system first accesses 100 distinct pages in some order and then accesses the same 100 pages but now in the reverse order. How many page faults will occur? (GATE CS 2010)

(A) 196
(B) 192
(C) 197
(D) 195
Answer (A)
Access to 100 pages will cause 100 page faults. When these pages are accessed in reverse order, the first four accesses will node cause page fault. All other access to pages will cause page faults. So total number of page faults will be 100 + 96.


30) Which of the following statements are true? (GATE CS 2010)
I. Shortest remaining time first scheduling may cause starvation
II. Preemptive scheduling may cause starvation
III. Round robin is better than FCFS in terms of response time

(A) I only
(B) I and III only
(C) II and III only
(D) I, II and III
Answer (D)
I) Shortest remaining time first scheduling is a preemptive version of shortest job scheduling. It may cause starvation as shorter processes may keep coming and a long CPU burst process never gets CPU.
II) Preemption may cause starvation. If priority based scheduling with preemption is used, then a low priority process may never get CPU.
III) Round Robin Scheduling improves response time as all processes get CPU after a specified time.

31) Consider the methods used by processes P1 and P2 for accessing their critical sections whenever needed, as given below. The initial values of shared boolean variables S1 and S2 are randomly assigned.
Method Used by P1
while (S1 == S2) ;
Critica1 Section
S1 = S2;

Method Used by P2
while (S1 != S2) ;
Critica1 Section
S2 = not (S1);
Which one of the following statements describes the properties achieved? (GATE CS 2010)
(A) Mutual exclusion but not progress
(B) Progress but not mutual exclusion
(C) Neither mutual exclusion nor progress
(D) Both mutual exclusion and progress
Answer (A)
It can be easily observed that the Mutual Exclusion requirement is satisfied by the above solution, P1 can enter critical section only if S1 is not equal to S2, and P2 can enter critical section only if S1 is equal to S2.
Progress Requirement is not satisfied. Let us first see definition of Progress Requirement.
Progress Requirement: If no process is executing in its critical section and there exist some processes that wishes to enter their critical section, then the selection of the processes that will enter the critical section next cannot be postponed indefinitely.
If P1 or P2 want to re-enter the critical section, then they cannot even if there is other process running in critical section.

32) In which one of the following page replacement policies, Belady’s anomaly may occur?
(A) FIFO
(B) Optimal
(C) LRU
(D) MRU
Answer (A)
Belady’s anomaly proves that it is possible to have more page faults when increasing the number of page frames while using the First in First Out (FIFO) page replacement algorithm.
See the wiki page for an example of increasing page faults with number of page frames.

33) The essential content(s) in each entry of a page table is / are
(A) Virtual page number
(B) Page frame number
(C) Both virtual page number and page frame number
(D) Access right information
Answer (B)
A page table entry must contain Page frame number. Virtual page number is typically used as index in page table to get the corresponding page frame number. See this for details.


34) Consider a system with 4 types of resources R1 (3 units), R2 (2 units), R3 (3 units), R4 (2 units). A non-preemptive resource allocation policy is used. At any given instance, a request is not entertained if it cannot be completely satisfied. Three processes P1, P2, P3 request the sources as follows if executed independently.
Process P1: 
t=0: requests 2 units of R2 
t=1: requests 1 unit of R3 
t=3: requests 2 units of R1 
t=5: releases 1 unit of R2    
        and 1 unit of R1. 
t=7: releases 1 unit of R3 
t=8: requests 2 units of R4 
t=10: Finishes

Process P2: 
t=0: requests 2 units of R3 
t=2: requests 1 unit of R4 
t=4: requests 1 unit of R1 
t=6: releases 1 unit of R3 
t=8: Finishes

Process P3: 
t=0: requests 1 unit of R4 
t=2: requests 2 units of R1 
t=5: releases 2 units of R1 
t=7: requests 1 unit of R2 
t=8: requests 1 unit of R3 
t=9: Finishes
Which one of the following statements is TRUE if all three processes run concurrently starting at time t=0?
(A) All processes will finish without any deadlock
(B) Only P1 and P2 will be in deadlock.
(C) Only P1 and P3 will be in a deadlock.
(D) All three processes will be in deadlock
Answer (A)
We can apply the following Deadlock Detection algorithm and see that there is no process waiting indefinitely for a resource. See this for deadlock detection algorithm.


35) Consider a disk system with 100 cylinders. The requests to access the cylinders occur in following sequence:
4, 34, 10, 7, 19, 73, 2, 15, 6, 20
Assuming that the head is currently at cylinder 50, what is the time taken to satisfy all requests if it takes 1ms to move from one cylinder to adjacent one and shortest seek time first policy is used?

(A) 95ms
(B) 119ms
(C) 233ms
(D) 276ms
Answer (B)
4, 34, 10, 7, 19, 73, 2, 15, 6, 20
Since shortest seek time first policy is used, head will first move to 34. This move will cause 16*1 ms. After 34, head will move to 20 which will cause 14*1 ms. And so on. So cylinders are accessed in following order 34, 20, 19, 15, 10, 7, 6, 4, 2, 73 and total time will be (16 + 14 + 1 + 4 + 5 + 3 + 1 + 2 + 2 + 71)*1 = 119 ms.

36) In the following process state transition diagram for a uniprocessor system, assume that there are always some processes in the ready state: Now consider the following statements:

I. If a process makes a transition D, it would result in another process making transition A immediately.
II. A process P2 in blocked state can make transition E while another process P1 is in running state.
III. The OS uses preemptive scheduling.
IV. The OS uses non-preemptive scheduling.
Which of the above statements are TRUE?

(A) I and II
(B) I and III
(C) II and III
(D) II and IV
Answer (C)
I is false. If a process makes a transition D, it would result in another process making transition B, not A.
II is true. A process can move to ready state when I/O completes irrespective of other process being in running state or not.
III is true because there is a transition from running to ready state.
IV is false as the OS uses preemptive scheduling.

37) The enter_CS() and leave_CS() functions to implement critical section of a process are realized using test-and-set instruction as follows:
void enter_CS(X)
{
    while test-and-set(X) ;
}
void leave_CS(X)
{
   X = 0;
}
In the above solution, X is a memory location associated with the CS and is initialized to 0. Now consider the following statements:
I. The above solution to CS problem is deadlock-free
II. The solution is starvation free.
III. The processes enter CS in FIFO order.
IV More than one process can enter CS at the same time.

Which of the above statements is TRUE?
(A) I only
(B) I and II
(C) II and III
(D) IV only
Answer (A)
The above solution is a simple test-and-set solution that makes sure that deadlock doesn’t occur, but it doesn’t use any queue to avoid starvation or to have FIFO order.


38) A multilevel page table is preferred in comparison to a single level page table for translating virtual address to physical address because
(A) It reduces the memory access time to read or write a memory location.
(B) It helps to reduce the size of page table needed to implement the virtual address space of a process.
(C) It is required by the translation lookaside buffer.
(D) It helps to reduce the number of page faults in page replacement algorithms.
Answer (B)
The size of page table may become too big (See this) to fit in contiguous space. That is why page tables are typically divided in levels.

39) The data blocks of a very large file in the Unix file system are allocated using
(A) contiguous allocation
(B) linked allocation
(C) indexed allocation
(D) an extension of indexed allocation
Answer (D)
The Unix file system uses an extension of indexed allocation. It uses direct blocks, single indirect blocks, double indirect blocks and triple indirect blocks. Following diagram shows implementation of Unix file system. The diagram is taken from Operating System Concept book.




40) The P and V operations on counting semaphores, where s is a counting semaphore, are defined as follows:
P(s) : s =  s - 1;
  if (s  < 0) then wait;
V(s) : s = s + 1;
  if (s <= 0) then wakeup a process waiting on s;
Assume that Pb and Vb the wait and signal operations on binary semaphores are provided. Two binary semaphores Xb and Yb are used to implement the semaphore operations P(s) and V(s) as follows:
P(s) : Pb(Xb);
  s = s - 1;
  if (s < 0) {
   Vb(Xb) ;
   Pb(Yb) ;
  }
  else Vb(Xb); 


V(s) : Pb(Xb) ;
  s = s + 1;
  if (s <= 0) Vb(Yb) ;
  Vb(Xb) ;
The initial values of Xb and Yb are respectively
(A) 0 and 0
(B) 0 and 1
(C) 1 and 0
(D) 1 and 1
Answer (C)
Both P(s) and V(s) operations are perform Pb(xb) as first step. If Xb is 0, then all processes executing these operations will be blocked. Therefore, Xb must be 1.
If Yb is 1, it may become possible that two processes can execute P(s) one after other (implying 2 processes in critical section). Consider the case when s = 1, y = 1. So Yb must be 0.


41) Which of the following statements about synchronous and asynchronous I/O is NOT true?
(A) An ISR is invoked on completion of I/O in synchronous I/O but not in asynchronous I/O
(B) In both synchronous and asynchronous I/O, an ISR (Interrupt Service Routine) is invoked after completion of the I/O
(C) A process making a synchronous I/O call waits until I/O is complete, but a process making an asynchronous I/O call does not wait for completion of the I/O
(D) In the case of synchronous I/O, the process waiting for the completion of I/O is woken up by the ISR that is invoked after the completion of I/O
Answer (A)
In both Synchronous and Asynchronous, an interrupt is generated on completion of I/O. In Synchronous, interrupt is generated to wake up the process waiting for I/O. In Asynchronous, interrupt is generated to inform the process that the I/O is complete and it can process the data from the I/O operation. See this for more details.

42) A process executes the following code
  for (i = 0; i < n; i++) fork(); 
The total number of child processes created is
(A) n
(B) 2^n - 1
(C) 2^n
(D) 2^(n+1) - 1;
Answer (B)
         F0       // There will be 1 child process created by first fork
      /     \
    F1      F1    // There will be 2 child processes created by second fork
   /  \    /  \
 F2   F2  F2   F2  // There will be 4 child processes created by third fork
/ \   / \ / \  / \
 ...............   // and so on
If we sum all levels of above tree for i = 0 to n-1, we get 2^n - 1. So there will be 2^n – 1 child processes. Also see this post for more details.


43) Which of the following is NOT true of deadlock prevention and deadlock avoidance schemes?
(A) In deadlock prevention, the request for resources is always granted if the resulting state is safe
(B) In deadlock avoidance, the request for resources is always granted if the result state is safe
(C) Deadlock avoidance is less restrictive than deadlock prevention
(D) Deadlock avoidance requires knowledge of resource requirements a priori
Answer (A)
Deadlock prevention scheme handles deadlock by making sure that one of the four necessary conditions don't occur. In deadlock prevention, the request for a resource may not be granted even if the resulting state is safe. (See the Galvin book slides for more details)


44) A processor uses 36 bit physical addresses and 32 bit virtual addresses, with a page frame size of 4 Kbytes. Each page table entry is of size 4 bytes. A three level page table is used for virtual to physical address translation, where the virtual address is used as follows
• Bits 30-31 are used to index into the first level page table
• Bits 21-29 are used to index into the second level page table
• Bits 12-20 are used to index into the third level page table, and
• Bits 0-11 are used as offset within the page
The number of bits required for addressing the next level page table (or page frame) in the page table entry of the first, second and third level page tables are respectively
(A) 20, 20 and 20
(B) 24, 24 and 24
(C) 24, 24 and 20
(D) 25, 25 and 24
Answer (D)
Virtual address size = 32 bits
Physical address size = 36 bits
Physical memory size = 2^36 bytes
Page frame size = 4K bytes = 2^12 bytes
No. of bits required to access physical memory frame = 36 - 12 = 24
So in third level of page table, 24 bits are required to access an entry.
9 bits of virtual address are used to access second level page table entry and size of pages in second level is 4 bytes. So size of second level page table is (2^9)*4 = 2^11 bytes. It means there are (2^36)/(2^11) possible locations to store this page table. Therefore the second page table requires 25 bits to address it. Similarly, the third page table needs 25 bits to address it.

45) Consider a disk pack with 16 surfaces, 128 tracks per surface and 256 sectors per track. 512 bytes of data are stored in a bit serial manner in a sector. The capacity of the disk pack and the number of bits required to specify a particular sector in the disk are respectively:
(A) 256 Mbyte, 19 bits
(B) 256 Mbyte, 28 bits
(C) 512 Mbyte, 20 bits
(D) 64 Gbyte, 28 bits
Answer (A)
Capacity of the disk = 16 surfaces X 128 tracks X 256 sectors X 512 bytes = 256 Mbytes.
To calculate number of bits required to access a sector, we need to know total number of sectors. Total number of sectors = 16 surfaces X 128 tracks X 256 sectors = 2^19
So the number of bits required to access a sector is 19.


46) Group 1 contains some CPU scheduling algorithms and Group 2 contains some applications. Match entries in Group 1 to entries in Group 2.
     Group I                          Group II
(P) Gang Scheduling              (1) Guaranteed Scheduling
(Q) Rate Monotonic Scheduling    (2) Real-time Scheduling
(R) Fair Share Scheduling        (3) Thread Scheduling
(A) P – 3 Q – 2 R – 1
(B) P – 1 Q – 2 R – 3
(C) P – 2 Q – 3 R – 1
(D) P – 1 Q – 3 R – 2
Answer (A)
Gang scheduling for parallel systems that schedules related threads or processes to run simultaneously on different processors.
Rate monotonic scheduling is used in real-time operating systems with a static-priority scheduling class. The static priorities are assigned on the basis of the cycle duration of the job: the shorter the cycle duration is, the higher is the job’s priority.
Fair Share Scheduling is a scheduling strategy in which the CPU usage is equally distributed among system users or groups, as opposed to equal distribution among processes. It is also known as Guaranteed scheduling.

47) An operating system uses Shortest Remaining Time first (SRT) process scheduling algorithm. Consider the arrival times and execution times for the following processes:
Process  Execution time  Arrival time
P1             20            0
P2             25            15
P3             10            30
P4             15            45
What is the total waiting time for process P2?
(A) 5
(B) 15
(C) 40
(D) 55
Answer (B)
At time 0, P1 is the only process, P1 runs for 15 time units.
At time 15, P2 arrives, but P1 has the shortest remaining time. So P1 continues for 5 more time units.
At time 20, P2 is the only process. So it runs for 10 time units
At time 30, P3 is the shortest remaining time process. So it runs for 10 time units
At time 40, P2 runs as it is the only process. P2 runs for 5 time units.
At time 45, P3 arrives, but P2 has the shortest remaining time. So P2 continues for 10 more time units.
P2 completes its ececution at time 55
Total waiting time for P2 = Complition time - (Arrival time + Execution time)
                          = 55 - (15 + 25)
                          = 15 
 
48) A virtual memory system uses First In First Out (FIFO) page replacement policy and allocates a fixed number of frames to a process. Consider the following statements:
P: Increasing the number of page frames allocated to a process sometimes increases the page fault rate.
Q: Some programs do not exhibit locality of reference. Which one of the following is TRUE?

(A) Both P and Q are true, and Q is the reason for P
(B) Both P and Q are true, but Q is not the reason for P.
(C) P is false, but Q is true
(D) Both P and Q are false.
Answer (B)
P is true. Increasing the number of page frames allocated to process may increases the no. of page faults (See Belady’s Anomaly).
Q is also true, but Q is not the reason for-P as Belady’s Anomaly occurs for some specific patterns of page references.


49) A single processor system has three resource types X, Y and Z, which are shared by three processes. There are 5 units of each resource type. Consider the following scenario, where the column alloc denotes the number of units of each resource type allocated to each process, and the column request denotes the number of units of each resource type requested by a process in order to complete execution. Which of these processes will finish LAST?

alloc request X Y Z X Y Z P0 1 2 1 1 0 3 P1 2 0 1 0 1 2 P2 2 2 1 1 2 0 (A) P0
(B) P1
(C) P2
(D) None of the above, since the system is in a deadlock
Answer (C)
Once all resources (5, 4 and 3 instances of X, Y and Z respectively) are allocated, 0, 1 and 2 instances of X, Y and Z are left. Only needs of P1 can be satisfied. So P1 can finish its execution first. Once P1 is done, it releases 2, 1 and 3 units of X, Y and Z respectively. Among P0 and P2, needs of P0 can only be satisfied. So P0 finishes its execution. Finally, P2 finishes its execution.


50) Two processes, P1 and P2, need to access a critical section of code. Consider the following synchronization construct used by the processes:Here, wants1 and wants2 are shared variables, which are initialized to false. Which one of the following statements is TRUE about the above construct?

/* P1 */ while (true) { wants1 = true; while (wants2 == true); /* Critical Section */ wants1=false; } /* Remainder section */ /* P2 */ while (true) { wants2 = true; while (wants1==true); /* Critical Section */ wants2 = false; } /* Remainder section */ (A) It does not ensure mutual exclusion.
(B) It does not ensure bounded waiting.
(C) It requires that processes enter the critical section in strict alternation.
(D) It does not prevent deadlocks, but ensures mutual exclusion.
Answer (D)
The above synchronization constructs don’t prevent deadlock. When both wants1 and wants2 become true, both P1 and P2 stuck forever in their while loops waiting for each other to finish.


51) Consider the following statements about user level threads and kernel level threads. Which one of the following statement is FALSE?
(A) Context switch time is longer for kernel level threads than for user level threads.
(B) User level threads do not need any hardware support.
(C) Related kernel level threads can be scheduled on different processors in a multi-processor system.
(D) Blocking one kernel level thread blocks all related threads.
Answer (D)
Since kernel level threads are managed by kernel, blocking one thread doesn’t cause all related threads to block. It’s a problem with user level threads. See this for more details.

52) Consider three CPU-intensive processes, which require 10, 20 and 30 time units and arrive at times 0, 2 and 6, respectively. How many context switches are needed if the operating system implements a shortest remaining time first scheduling algorithm? Do not count the context switches at time zero and at the end.
(A) 1
(B) 2
(C) 3
(D) 4
Answer (B)
Let three process be P0, P1 and P2 with arrival times 0, 2 and 6 respectively and CPU burst times 10, 20 and 30 respectively. At time 0, P0 is the only available process so it runs. At time 2, P1 arrives, but P0 has the shortest remaining time, so it continues. At time 6, P2 arrives, but P0 has the shortest remaining time, so it continues. At time 10, P1 is scheduled as it is the shortest remaining time process. At time 30, P2 is scheduled. Only two context switches are needed. P0 to P1 and P1 to P2.

53) A computer system supports 32-bit virtual addresses as well as 32-bit physical addresses. Since the virtual address space is of the same size as the physical address space, the operating system designers decide to get rid of the virtual memory entirely. Which one of the following is true?
(A) Efficient implementation of multi-user support is no longer possible
(B) The processor cache organization can be made more efficient now
(C) Hardware support for memory management is no longer needed
(D) CPU scheduling can be made more efficient now
Answer (C)
For supporting virtual memory, special hardware support is needed from Memory Management Unit. Since operating system designers decide to get rid of the virtual memory entirely, hardware support for memory management is no longer needed


54) A CPU generates 32-bit virtual addresses. The page size is 4 KB. The processor has a translation look-aside buffer (TLB) which can hold a total of 128 page table entries and is 4-way set associative. The minimum size of the TLB tag is:
(A) 11 bits
(B) 13 bits
(C) 15 bits
(D) 20 bits
Answer (C)
Size of a page = 4KB = 2^12
Total number of bits needed to address a page frame = 32 – 12 = 20
If there are ‘n’ cache lines in a set, the cache placement is called n-way set associative. Since TLB is 4 way set associative and can hold total 128 (2^7) page table entries, number of sets in cache = 2^7/4 = 2^5. So 5 bits are needed to address a set, and 15 (20 – 5) bits are needed for tag.

55) Consider three processes (process id 0, 1, 2 respectively) with compute time bursts 2, 4 and 8 time units. All processes arrive at time zero. Consider the longest remaining time first (LRTF) scheduling algorithm. In LRTF ties are broken by giving priority to the process with the lowest process id. The average turn around time is:
(A) 13 units
(B) 14 units
(C) 15 units
(D) 16 units
Answer (A)
Let the processes be p0, p1 and p2. These processes will be executed in following order.
  p2  p1  p2  p1  p2  p0  p1   p2   p0   p1   p2
0   4   5   6   7   8   9   10    11   12   13   14 
Turn around time of a process is total time between submission of the process and its completion.
Turn around time of p0 = 12 (12-0)
Turn around time of p1 = 13 (13-0)
Turn around time of p2 = 14 (14-0)
Average turn around time is (12+13+14)/3 = 13.


56) Consider three processes, all arriving at time zero, with total execution time of 10, 20 and 30 units, respectively. Each process spends the first 20% of execution time doing I/O, the next 70% of time doing computation, and the last 10% of time doing I/O again. The operating system uses a shortest remaining compute time first scheduling algorithm and schedules a new process either when the running process gets blocked on I/O or when the running process finishes its compute burst. Assume that all I/O operations can be overlapped as much as possible. For what percentage of time does the CPU remain idle?(A) 0%
(B) 10.6%
(C) 30.0%
(D) 89.4%
Answer (B)
Let three processes be p0, p1 and p2. Their execution time is 10, 20 and 30 respectively. p0 spends first 2 time units in I/O, 7 units of CPU time and finally 1 unit in I/O. p1 spends first 4 units in I/O, 14 units of CPU time and finally 2 units in I/O. p2 spends first 6 units in I/O, 21 units of CPU time and finally 3 units in I/O.
 idle   p0    p1     p2    idle
0    2     9     23     44     47

Total time spent = 47
Idle time = 2 + 3 = 5
Percentage of idle time = (5/47)*100 = 10.6 %


57) The atomic fetch-and-set x, y instruction unconditionally sets the memory location x to 1 and fetches the old value of x in y without allowing any intervening access to the memory location x. consider the following implementation of P and V functions on a binary semaphore .

void P (binary_semaphore *s) {
  unsigned y;
  unsigned *x = &(s->value);
  do {
     fetch-and-set x, y;
  } while (y);
}

void V (binary_semaphore *s) {
  S->value = 0;
}
Which one of the following is true?
(A) The implementation may not work if context switching is disabled in P.
(B) Instead of using fetch-and-set, a pair of normal load/store can be used
(C) The implementation of V is wrong
(D) The code does not implement a binary semaphore
Answer (A)
Let us talk about the operation P(). It stores the value of s in x, then it fetches the old value of x, stores it in y and sets x as 1. The while loop of a process will continue forever if some other process doesn’t execute V() and sets the value of s as 0. If context switching is disabled in P, the while loop will run forever as no other process will be able to execute V().


58) Consider the following snapshot of a system running n processes. Process i is holding Xi instances of a resource R, 1 <= i <= n. currently, all instances of R are occupied. Further, for all i, process i has placed a request for an additional Yi instances while holding the Xi instances it already has. There are exactly two processes p and q such that Yp = Yq = 0. Which one of the following can serve as a necessary condition to guarantee that the system is not approaching a deadlock?
(A) min (Xp, Xq) < max (Yk) where k != p and k != q
(B) Xp + Xq >= min (Yk) where k != p and k != q
(C) max (Xp, Xq) > 1
(D) min (Xp, Xq) > 1
Answer (B)
Since both p and q don’t need additional resources, they both can finish and release Xp + Xq resources without asking for any additional resource. If the resources released by p and q are sufficient for another process waiting for Yk resources, then system is not approaching deadlock.

59) Normally user programs are prevented from handling I/O directly by I/O instructions in them. For CPUs having explicit I/O instructions, such I/O protection is ensured by having the I/O instructions privileged. In a CPU with memory mapped I/O, there is no explicit I/O instruction. Which one of the following is true for a CPU with memory mapped I/O?
(a) I/O protection is ensured by operating system routine(s)
(b) I/O protection is ensured by a hardware trap
(c) I/O protection is ensured during system configuration
(d) I/O protection is not possible
Answwer (a)
Memory mapped I/O means, accessing I/O via general memory access as opposed to specialized IO instructions. An example,
  unsigned int volatile const *pMappedAddress const = (unsigned int *)0x100;
So, the programmer can directly access any memory location directly. To prevent such an access, the OS (kernel) will divide the address space into kernel space and user space. An user application can easily access user application. To access kernel space, we need system calls (traps).

60) What is the swap space in the disk used for?
(a) Saving temporary html pages
(b) Saving process data
(c) Storing the super-block
(d) Storing device drivers
Answer (b)
Swap space is typically used to store process data. See this for more details.


61) 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
Answer (c)


62) Suppose n processes, P1, …. Pn share m identical resource units, which can be reserved and released one at a time. The maximum resource requirement of process Pi is Si, where Si > 0. Which one of the following is a sufficient condition for ensuring that deadlock does not occur?

Answer (c)
In the extreme condition, all processes acquire Si-1 resources and need 1 more resource. So following condition must be true to make sure that deadlock never occurs.
\sum\limits_{i=1}^n (Si-1) < m
The above expression can be written as following.
\sum\limits_{i=1}^n Si < (m + n)
See this forum thread for an example.


63) Consider the following code fragment:
  if (fork() == 0)
  { a = a + 5; printf(“%d,%d\n”, a, &a); }
  else { a = a –5; printf(“%d, %d\n”, a, &a); } 
Let u, v be the values printed by the parent process, and x, y be the values printed by the child process. Which one of the following is TRUE?
(a) u = x + 10 and v = y
(b) u = x + 10 and v != y
(c) u + 10 = x and v = y
(d) u + 10 = x and v != y
Answer (c)
fork() returns 0 in child process and process ID of child process in parent process.
In Child (x), a = a + 5
In Parent (u), a = a – 5;
Therefore x = u + 10.
The physical addresses of ‘a’ in parent and child must be different. But our program accesses virtual addresses (assuming we are running on an OS that uses virtual memory). The child process gets an exact copy of parent process and virtual address of ‘a’ doesn’t change in child process. Therefore, we get same addresses in both parent and child. See this run for example.

64. Fetch_And_Add(X,i) is an atomic Read-Modify-Write instruction that reads the value of memory location X, increments it by the value i, and returns the old value of X. It is used in the pseudocode shown below to implement a busy-wait lock. L is an unsigned integer shared variable initialized to 0. The value of 0 corresponds to lock being available, while any non-zero value corresponds to the lock being not available.

  AcquireLock(L){
         while (Fetch_And_Add(L,1))
               L = 1;
   }
  ReleaseLock(L){
         L = 0;
   } 
This implementation
(A) fails as L can overflow
(B) fails as L can take on a non-zero value when the lock is actually available
(C) works correctly but may starve some processes
(D) works correctly without starvation
Answer (B)
Take closer look the below while loop.
     while (Fetch_And_Add(L,1))
               L = 1;  // A waiting process can be here just after 
                       // the lock is released, and can make L = 1.
Consider a situation where a process has just released the lock and made L = 0. Let there be one more process waiting for the lock, means executing the AcquireLock() function. Just after the L was made 0, let the waiting processes executed the line L = 1. Now, the lock is available and L = 1. Since L is 1, the waiting process (and any other future coming processes) can not come out of the while loop.
The above problem can be resolved by changing the AcuireLock() to following.
  AcquireLock(L){
         while (Fetch_And_Add(L,1))
         { // Do Nothing }
   } 
 

Tuesday 28 May 2013

GATE Questions for Data Structures and Algorithms

Following questions have been asked in GATE CS exam


1. Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited in a postorder, inorder and preorder traversal. Respectively, of a complete binary tree. Which of the following is always true? (GATE CS 2000)
(a) LASTIN = LASTPOST
(b) LASTIN = LASTPRE
(c) LASTPRE = LASTPOST
(d) None of the above
Answer (d)
It is given that the given tree is complete binary tree. For a complete binary tree, the last visited node will always be same for inorder and preorder traversal. None of the above is true even for a complete binary tree.
The option (a) is incorrect because the last node visited in Inorder traversal is right child and last node visited in Postorder traversal is root.
The option (c) is incorrect because the last node visited in Preorder traversal is right child and last node visited in Postorder traversal is root.
For option (b), see the following counter example.
     1
   /    \
  2      3
 / \    /
4   5  6  

Inorder traversal is 4 2 5 1 6 3
Preorder traversal is 1 2 4 5 3 6 

2. The most appropriate matching for the following pairs

X: depth first search            1: heap
Y: breadth-first search          2: queue
Z: sorting                       3: stack
is (GATE CS 2000):
(a) X—1 Y—2 Z-3
(b) X—3 Y—1 Z-2
(c) X—3 Y—2 Z-1
(d) X—2 Y—3 Z-1
Answer: (c)
Stack is used for Depth first Search
Queue is used for Breadth First Search
Heap is used for sorting

3. Consider the following nested representation of binary trees: (X Y Z) indicates Y and Z are the left and right sub stress, respectively, of node X. Note that Y and Z may be NULL, or further nested. Which of the following represents a valid binary tree?
(a) (1 2 (4 5 6 7))
(b) (1 (2 3 4) 5 6) 7)
(c) (1 (2 3 4)(5 6 7))
(d) (1 (2 3 NULL) (4 5))
Answer (c)

4. Let s be a sorted array of n integers. Let t(n) denote the time taken for the most efficient algorithm to determined if there are two elements with sum less than 1000 in s. which of the following statements is true? (GATE CS 2000)

a) t (n) is 0 (1)
b) n < t (n) < n {log_2 n}
c) n log 2 n < t (n) <  {n \choose 2}
d) t (n) =  {n \choose 2}
Answer (a)
Let array be sorted in ascending order, if sum of first two elements is less than 1000 then there are  two elements with sum less than 1000 otherwise not. For array sorted in descending order we need to check last two elements. For an array data structure, number of operations are fixed in both the cases and not dependent on n, complexity is O(1)

5. B+ trees are preferred to binary trees in databases because (GATE CS 2000)
(a) Disk capacities are greater than memory capacities
(b) Disk access is much slower than memory access
(c) Disk data transfer rates are much less than memory data transfer rates
(d) Disks are more reliable than memory
Answer (b)
Disk access is slow and  B+ Tree provide search in less number of disk hits. This is primarily because unlike binary seach trees, B+ trees have very high fanout (typically on the order of 100 or more), which reduces the number of I/O operations required to find an element in the tree.


1. Consider the function f defined below.
struct item
{
  int data;
  struct item * next;
};
int f(struct item *p)
{
  return (
          (p == NULL) ||
          (p->next == NULL) ||
          (( P->data &lt;= p->next->data) &amp;&amp; f(p->next))
         );
}
For a given linked list p, the function f returns 1 if and only if (GATE CS 2003)
a) the list is empty or has exactly one element
b) the elements in the list are sorted in non-decreasing order of data value
c) the elements in the list are sorted in non-increasing order of data value
d) not all elements in the list have the same data value.
Answer (b)
The function f() works as follows
1) If linked list is empty return 1
2) Else If linked list has only one element return 1
3) Else if node->data is smaller than equal to node->next->data and same thing holds for rest of the list then return 1
4) Else return 0

2. Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs identify a tree uniquely (GATE CS 2004)?
i) preorder and postorder
ii) inorder and postorder
iii) preorder and inorder
iv) level order and postorder

a) (i) only
b) (ii), (iii)
c) (iii) only
d) (iv) only
Answer (b)


3. The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)? (GATE CS 2004)
a) 2
b) 3
c) 4
d) 6
Answer(b)
Constructed binary search tree will be..
                    10
                  /     \
                 1       15
                 \      /  \
                  3    12   16
                    \
                     5
 
4. A data structure is required for storing a set of integers such that each of the following operations can be done in (log n) time, where n is the number of elements in the set.
   o	Delection of the smallest element 
   o	Insertion of an element if it is not already present in the set
Which of the following data structures can be used for this purpose?
(a) A heap can be used but not a balanced binary search tree
(b) A balanced binary search tree can be used but not a heap
(c) Both balanced binary search tree and heap can be used
(d) Neither balanced binary search tree nor heap can be used
Answer(b)
A self-balancing balancing binary search tree containing n items allows the lookup, insertion, and removal of an item in O(log n) worst-case time. Since it’s a BST, we can easily find out minimum element in O(nlogn).
Since Heap is a balanced binary tree (or almost complete binary tree), insertion complexity for heap is O(logn). Also complexity to get minimum in a min heap is O(logn) because removal of root node causes a call to heapify (after removing the first element from the array) to maintain the heap tree property. But a heap cannot be used for the above purpose as the question says – insert an element if it is not already present. For a heap, we cannot find out in O(logn) if an element is present or not. Thanks to game for providing the correct solution.

5. A circularly linked list is used to represent a Queue. A single variable p is used to access the Queue. To which node should p point such that both the operations enQueue and deQueue can be performed in constant time? (GATE 2004)
ll
a) rear node
b) front node
c) not possible with a single pointer
d) node next to front
Answer(a)
Answer is not “(b) front node”, as we can not get rear from front in O(1), but if p is rear we can implement both enQueue and deQueue in O(1) because from rear we can get front in O(1). Below are sample functions. Note that these functions are just sample are not working. Code to handle base cases is missing.
/* p is pointer to address of rear (double pointer).  This function adds new
   node after rear and updates rear which is *p to point to new node  */
void  enQueue(struct node **p, struct node *new_node)
{
    /* Missing code to handle base cases like *p is NULL */
      
     new_node->next = (*p)->next;
     (*p)->next = new_node;
     (*p) = new_node /* new is now rear */
     /* Note that p is again front and  p->next is rear */
 }
/* p is pointer to rear. This function removes the front element and
    returns the new front */
struct node *deQueue(struct node *p)
{
    /* Missing code to handle base cases like p is NULL,
        p->next is NULL,...  etc */
    struct node *temp = p->next->next;
    p->next = p->next->next;
    return temp;
    /* Note that p is again front and  p->next is rear */
}
 
1. Consider the following C program segment
struct CellNode
{
  struct CelINode *leftchild;
  int element;
  struct CelINode *rightChild;
}
int Dosomething(struct CelINode *ptr)
{
    int value = 0;
    if (ptr != NULL)
    {
      if (ptr->leftChild != NULL)
        value = 1 + DoSomething(ptr->leftChild);
      if (ptr->rightChild != NULL)
        value = max(value, 1 + DoSomething(ptr->rightChild));
    }
    return (value);
}
The value returned by the function DoSomething when a pointer to the root of a non-empty tree is passed as argument is (GATE CS 2004)
a) The number of leaf nodes in the tree
b) The number of nodes in the tree
c) The number of internal nodes in the tree
d) The height of the tree
Answer: (d)
Explanation: DoSomething() returns max(height of left child + 1, height of left child + 1). So given that pointer to root of tree is passed to DoSomething(), it will return height of the tree. Note that this implementation follows the convention where height of a single node is 0.
2. Suppose we run Dijkstra’s single source shortest-path algorithm on the following edge weighted directed graph with vertex P as the source. In what order do the nodes get included into the set of vertices for which the shortest path distances are finalized? (GATE CS 2004)
a) P, Q, R, S, T, U
b) P, Q, R, U, S, T
c) P, Q, R, U, T, S
d) P, Q, T, R, U, S
gate2004
Answer (b)

3. Suppose each set is represented as a linked list with elements in arbitrary order. Which of the operations among union, intersection, membership, cardinality will be the slowest? (GATE CS 2004)
a) union only
b) intersection, membership
c) membership, cardinality
d) union, intersection
Answer (a)
Cardinality and membership are definably not the slowest one. For cardinality, just count the number of nodes in a list. For membership, just traverse the list and look for a match
For getting intersection of L1 and L2, search for each element of L1 in L2 and print the elements we find in L2.
There can be many ways for getting union of L1 and L2. One of them is as follows
a) Print all the nodes of L1 and print only those which are not present in L2.
b) Print nodes of L2.
All of these methods will require more operations than intersection as we have to process intersection node plus other nodes.

4. The time complexity of the following C function is (assume n > 0 (GATE CS 2004)
int recursive (mt n)
{
   if (n == 1)
     return (1);
   else
     return (recursive (n-1) + recursive (n-1));
}
a) 0(n)
b) 0(nlogn)
c) 0(n^2)
d) 0(2^n)
Answer(d)
Explanation:
Recursive expression for the above program will be.
  T(n) = 2T(n-1) + c
  T(1) = c1.
Let us solve it.
  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

  T(n) = O(2^n)
 
 
1. Suppose you are given an array s[1...n] and a procedure reverse (s,i,j) which reverses the order of elements in a between positions i and j (both inclusive). What does the following sequence
do, where 1 < k <= n: reverse (s, 1, k); reverse (s, k + 1, n); reverse (s, 1, n); (GATE CS 2000)
(a) Rotates s left by k positions
(b) Leaves s unchanged
(c) Reverses all elements of s
(d) None of the above
Answer: (a)
Effect of the above 3 reversals for any k is equivalent to left rotation of the array of size n by k. If we rotate an array n times for k = 1 to n, we get the same array back.

2. The best data structure to check whether an arithmetic expression has balanced parentheses is a (GATE CS 2004)
a) queue
b) stack
c) tree
d) list
Answer(b)
There are three types of parentheses [ ] { } (). Below is an arbit c code segment which has parentheses of all three types.
void func(int c, int a[]) { return ((c +2) + arr[(c-2)]) ; } Stack is a straightforward choice for checking if left and right parentheses are balanced. Here is a algorithm to do the same.
/*Return 1 if expression has balanced parentheses */ bool areParenthesesBalanced(expression ) { for each character in expression { if(character == ’(’ || character == ’{’ || character == ’[’) push(stack, character); if(character == ’)’ || character == ’}’ || character == ’]’) { if(isEmpty(stack)) return 0; /*We are seeing a right parenthesis without a left pair*/ /* Pop the top element from stack, if it is not a pair bracket of character then there is a mismatch. This will happen for expressions like {(}) */ else if (! isMatchingPair(pop(stack), character) ) return 0; } } if(isEmpty(stack)) return 1; /*balanced*/ else return 0; /*not balanced*/ } /* End of function to check parentheses */ /* Returns 1 if character1 and character2 are matching left and right parentheses */ bool isMatchingPair(character1, character2) { if(character1 == ‘(‘ && character2 == ‘)’) return 1; else If(character1 == ‘{‘ && character2 == ‘}’) return 1; else If(character1 == ‘[‘ && character2 == ‘]’) return 1; else return 0; }
3. Level order traversal of a rooted tree can be done by starting from the root and performing (GATE CS 2004)

a) preorder traversal
b) in-order traversal
c) depth first search
d) breadth first search
Answer(d)


4. Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true?
i. 9679, 1989, 4199 hash to the same value
ii. 1471, 6171 has to the same value
iii. All elements hash to the same value
iv. Each element hashes to a different value
(GATE CS 2004)

a) i only
b) ii only
c) i and ii only
d) iii or iv
Answer (c)

5. Postorder traversal of a given binary search tree, T produces the following sequence of keys
10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29
Which one of the following sequences of keys can be the result of an in-order traversal of the tree T? (GATE CS 2005)

a) 9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95
b) 9, 10, 15, 22, 40, 50, 60, 95, 23, 25, 27, 29
c) 29, 15, 9, 10, 25, 22, 23, 27, 40, 60, 50, 95
d) 95, 50, 60, 40, 27, 23, 22, 25, 10, 9, 15, 29
Answer (a)
Inorder traversal of a BST always gives elements in increasing order. Among all four options, a) is the only increasing order sequence.

1. Consider the following C function.
float f(float x, int y) 
{ 
  float p, s; int i; 
  for (s=1, p=1, i=1; i < y; i ++) 
  { 
    p*= x/i; 
    s+=p; 
  } 
  return s; 
}   
For large values of y, the return value of the function f best approximates (GATE CS 2003)
a) x^y
b) e^x
c) ln(1 + x)
d) x^x
Answer (b)
The function f() is implementation of Taylor’s Series to calculates e^x
   e^x = 1 + x + x^2/2! + x^3/3! + ---
More is the value of y more precise value of e^x will be returned by f()
References:
http://en.wikipedia.org/wiki/E_%28mathematical_constant%29

2. In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is (GATE CS 2002)
a) log 2 n
b) n/2
c) log 2 n – 1
d) n
Answer(d)
In the worst case, the element to be searched has to be compared with all elements of linked list.
3. The elements 32, 15, 20, 30, 12, 25, 16 are inserted one by one in the given order into a Max Heap. The resultant Max Heap is.
tree
Answer (a)
4. Consider the following three claims
I (n + k)^m = \theta(n^m), where k and m are constants
II 2^(n + 1) = 0(2^n)
III 2^(2n + 1) = 0(2^n)
Which of these claims are correct? (GATE CS 2003)

(a) I and II
(b) I and III
(c) II and III
(d) I, II and III
Answer(a)
(I)  (n+m)^k = n^k + c1*n^(k-1) + ... k^m = \theta(n^k)
(II)  2^(n+1) = 2*2^n = O(2^n)
 
5. A single array A[1..MAXSIZE] is used to implement two stacks. The two stacks grow from opposite ends of the array. Variables top1 and top2 (topl< top 2) point to the location of the topmost element in each of the stacks. If the space is to be used efficiently, the condition for “stack full” is (GATE CS 2004)
a) (top1 = MAXSIZE/2) and (top2 = MAXSIZE/2+1)
b) top1 + top2 = MAXSIZE
c) (top1= MAXSIZE/2) or (top2 = MAXSIZE)
d) top1= top2 -1
Answer(d)
If we are to use space efficiently then size of the any stack can be more than MAXSIZE/2.
Both stacks will grow from both ends and if any of the stack top reaches near to the other top then stacks are full. So the condition will be top1 = top2 -1 (given that top1 < top2)

1. The usual \theta(n^2) implementation of Insertion Sort to sort an array uses linear search to identify the position where an element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the position, the worst case running time will (GATE CS 2003)
(a) remain \theta(n^2)
(b) become \theta(n(log n)^2)
(c) become \theta(n log n)
(d) become \theta(n)
Answer (a)
If we use binary search then there will be \lceil \log_2(n!) \rceil comparisons in the worst case, which is \Theta(n log n) ( If you want to know how \lceil \log_2(n!) \rceil can be equal to \Theta(n log n), then see this for proof). But the algorithm as a whole will still have a running time of \Theta(n^2) on average because of the series of swaps required for each insertion.
Reference:
http://en.wikipedia.org/wiki/Insertion_sort

2. The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of

a) n
b) n^2
c) nlogn
d) n(log^2)n
Answer (c)
The number of comparisons that a comparison sort algorithm requires increases in proportion to nlog(n), where n is the number of elements to sort. This bound is asymptotically tight:
Given a list of distinct numbers (we can assume this because this is a worst-case analysis), there are n factorial permutations exactly one of which is the list in sorted order. The sort algorithm must gain enough information from the comparisons to identify the correct permutations. If the algorithm always completes after at most f(n) steps, it cannot distinguish more than 2^f(n) cases because the keys are distinct and each comparison has only two possible outcomes. Therefore,
2^f(n) \geq n!, or equivalently f(n)\geq[Tex]\log_2[/Tex](n!).
References:
http://en.wikipedia.org/wiki/Comparison_sort
http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15451-s07/www/lecture_notes/lect0130.pdf

3. The problem 3-SAT and 2-SAT are

a) both in P
b) both NP complete
c) NP-complete and in P respectively
d) undecidable and NP-complete respectively
Answer (c)
The Boolean satisfiability problem (SAT) is a decision problem, whose instance is a Boolean expression written using only AND, OR, NOT, variables, and parentheses. The problem is: given the expression, is there some assignment of TRUE and FALSE values to the variables that will make the entire expression true? A formula of propositional logic is said to be satisfiable if logical values can be assigned to its variables in a way that makes the formula true.
3-SAT and 2-SAT are special cases of k-satisfiability (k-SAT) or simply satisfiability (SAT), when each clause contains exactly k = 3 and k = 2 literals respectively.
2-SAT is P while 3-SAT is NP Complete. (See this for explanation)
References:
http://en.wikipedia.org/wiki/Boolean_satisfiability_problem

4. Consider the following graph

grap2003

Among the following sequences
I) a b e g h f
II) a b f e h g
III) a b f h g e
IV) a f g h b e
Which are depth first traversals of the above graph? (GATE CS 2003)

a) I, II and IV only
b) I and IV only
c) II, III and IV only
d) I, III and IV only
Answer (d)

1. In a binary max heap containing n numbers, the smallest element can be found in time (GATE CS 2006)
(A) 0(n)
(B) O(logn)
(C) 0(loglogn)
(D) 0(1)
Answer (A)
In a max heap, the smallest element is always present at a leaf node. So we need to check for all leaf nodes for the minimum value. Worst case complexity will be O(n)
         12
        /  \
      /      \
    8         7
   / \        / \
 /     \    /     \
2      3   4       5
2. A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i+1]. To be able to store any binary tree on n vertices the minimum size of X should be. (GATE CS 2006)
(A) log2n
(B) n
(C) 2n + 1
(D) 2^n — 1
Answer (D)
For a right skewed binary tree, number of nodes will be 2^n – 1. For example, in below binary tree, node ‘A’ will be stored at index 1, ‘B’ at index 3, ‘C’ at index 7 and ‘D’ at index 15.
A
 \
   \
    B
      \
        \
         C
           \
             \
              D
3. Which one of the following in place sorting algorithms needs the minimum number of swaps? (GATE CS 2006)
(A) Quick sort
(B) Insertion sort
(C) Selection sort
(D) Heap sort
Answer (C)
For selection sort, number of swaps required is minimum ( \theta(n) ).
4. An element in an array X is called a leader if it is greater than all elements to the right of it in X. The best algorithm to find all leaders in an array (GATE CS 2006)
(A) Solves it in linear time using a left to right pass of the array
(B) Solves it in linear time using a right to left pass of the array
(C) Solves it using divide and conquer in time 8(nlogn)
(D) Solves it in time 8(n2)
Answer (B)
Please see this post for explanation.
5. Consider a weighted complete graph G on the vertex set {v1,v2 ,v} such that the weight of the edge (v,,v) is 2|i-j|. The weight of a minimum spanning tree of G is: (GATE CS 2006)
(A) n — 1
(B) 2n — 2
(C) nC2
(D) 2
Answer (B)
Minimum spanning tree of such a graph is
v1
  \
    v2
      \
       v3
         \
          v4
            .
              .
                .
                 vn
 
Weight of the minimum spanning tree
= 2|2 – 1| + 2|3 – 2| + 2|4 – 3| + 2|5 – 4| …. + 2| n – (n-1) |
= 2n – 2

1. Consider the following functions
formula
Which of the following is true? (GATE CS 2000)

(a) h(n) is 0(f(n))
(b) h(n) is 0(g(n))
(c) g(n) is not 0(f(n))
(d) f(n) is 0(g(n))
Answer (d)
g(n) = 2^(\sqrt{n} \log{n} ) = n^(\sqrt{n})
f(n) and g(n) are of same asymptotic order and following statements are true.
f(n) = O(g(n))
g(n) = O(f(n)).
(a) and (b) are false because n! is of asymptotically higher order than n^(\sqrt{n}).

2. Let G be an undirected connected graph with distinct edge weight. Let emax be the edge with maximum weight and emin the edge with minimum weight. Which of the following statements is false? (GATE CS 2000)

(a) Every minimum spanning tree of G must contain emin
(b) If emax is in a minimum spanning tree, then its removal must disconnect G
(c) No minimum spanning tree contains emax
(d) G has a unique minimum spanning tree
Answer (c)
(a) and (b) are always true.
(c) is false because (b) is true.
(d) is true because all edge weights are distinct for G.

3. Let G be an undirected graph. Consider a depth-first traversal of G, and let T be the resulting depth-first search tree. Let u be a vertex in G and let v be the first new (unvisited) vertex visited after visiting u in the traversal. Which of the following statements is always true? (GATE CS 2000)

(a) {u,v} must be an edge in G, and u is a descendant of v in T
(b) {u,v} must be an edge in G, and v is a descendant of u in T
(c) If {u,v} is not an edge in G then u is a leaf in T
(d) If {u,v} is not an edge in G then u and v must have the same parent in T
Answer (c)

4. Consider an undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r. Let d(r, u) and d(r, v) be the lengths of the shortest paths from r to u and v respectively, in G. lf u is visited before v during the breadth-first traversal, which of the following statements is correct? (GATE CS 2001)

a) d(r, u) < d (r, v)
b) d(r, u) > d(r, v)
c) d(r, u) <= d (r, v)
d) None of the above
Answer (c)
d(r, u) and d(r, v) will be equal when u and v are at same level, otherwise d(r, u) will be less than d(r, v)

5. How many undirected graphs (not necessarily connected) can be constructed out of a given set V= {V 1, V 2,…V n} of n vertices ? (GATE CS 2001)

a) n(n-l)/2
b) 2^n
c) n!
d) 2^(n(n-1)/2)
Answer (d)
In an undirected graph, there can be maximum n(n-1)/2 edges. We can choose to have (or not have) any of the n(n-1)/2 edges. So, total number of undirected graphs with n vertices is 2^(n(n-1)/2).

1 In a heap with n elements with the smallest element at the root, the 7th smallest element can be found in time (GATE CS 2003)
a) \theta(n log n)
b) \theta(n)
c) \theta(log n)
d) \theta(1)
Answer(c)
Given a Min-heap, to get the 7th smallest element, we need to call Extract-Min 7 times which means \theta(7logn)( = \theta(logn)) operations

2. Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the in-order traversal sequence of the resultant tree? (GATE CS 2003)

a) 7 5 1 0 3 2 4 6 8 9
b) 0 2 4 3 1 6 5 9 8 7
c) 0 1 2 3 4 5 6 7 8 9
d) 9 8 6 4 2 3 0 1 5 7
Answer (c)
In-order traversal of a BST gives elements in increasing order. So answer c is correct without any doubt.

3. Let S be a stack of size n >= 1. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform n pop operations. Assume that Push and Pop operation take X seconds each, and Y seconds elapse between the end of one such stack operation and the start of the next operation. For m >= 1, define the stack-life of m as the time elapsed from the end of Push(m) to the start of the pop operation that removes m from S. The average stack-life of an element of this stack is (GATE CS 2003)

a) n(X+ Y)
b) 3Y + 2X
c) n(X + Y)-X
d) Y + 2X
Answer(c)
We can easily arrive at the result by taking few examples.

1. The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:
(A) 2^h -1
(B) 2^(h-1) – 1
(C) 2^(h+1) -1
(D) 2*(h+1)
Answer (C)
Maximum number of nodes will be there for a complete tree.
Number of nodes in a complete tree of height h = 1 + 2 + 2^2 + 2*3 + …. 2^h = 2^(h+1) – 1
2: The maximum number of binary trees that can be formed with three unlabeled nodes is:
(A) 1
(B) 5
(C) 4
(D) 3
Answer (B)
             O
          /     \
        O        O
           (i)

            O             
          /                             
       O                 
     /                      
   O                         
        (ii)

         O
       / 
     O
        \
          O
       (iii)

  O                      
     \                        
       O                     
          \                  
           O                                                         
    (iv)

       O
          \
            O
          /
       O               
    (v)
Note that nodes are unlabeled. If the nodes are labeled, we get more number of trees.
3. Which of the following sorting algorithms has the lowest worst-case complexity?
(A) Merge sort
(B) Bubble sort
(C) Quick sort
(D) Selection sort
Answer (A)
Worst case complexities for the above sorting algorithms are as follows:
Merge Sort — nLogn
Bubble Sort — n^2
Quick Sort — n^2
Selection Sort — n^2
4. The following postfix expression with single digit operands is evaluated using a stack:
              8 2 3 ^ / 2 3 * + 5 1 * - 
Note that ^ is the exponentiation operator. The top two elements of the stack after the first * is evaluated are:
(A) 6, 1
(B) 5, 7
(C) 3, 2
(D) 1, 5
Answer (A)
The algorithm for evaluating any postfix expression is fairly straightforward:
1. While there are input tokens left
    o Read the next token from input.
    o If the token is a value
       + Push it onto the stack.
    o Otherwise, the token is an operator 
      (operator here includes both operators, and functions).
       * It is known a priori that the operator takes n arguments.
       * If there are fewer than n values on the stack
        (Error) The user has not input sufficient values in the expression.
       * Else, Pop the top n values from the stack.
       * Evaluate the operator, with the values as arguments.
       * Push the returned results, if any, back onto the stack.
2. If there is only one value in the stack
    o That value is the result of the calculation.
3. If there are more values in the stack
    o (Error)  The user input has too many values.
Source for algorithm: http://en.wikipedia.org/wiki/Reverse_Polish_notation#The_postfix_algorithm
Let us run the above algorithm for the given expression.
First three tokens are values, so they are simply pushed. After pushing 8, 2 and 3, the stack is as follows
    8, 2, 3  
When ^ is read, top two are popped and power(2^3) is calculated
    8, 8 
When / is read, top two are popped and division(8/8) is performed
    1 
Next two tokens are values, so they are simply pushed. After pushing 2 and 3, the stack is as follows
    1, 2, 3
When * comes, top two are popped and multiplication is performed.
    1, 6

5. The inorder and preorder traversal of a binary tree are d b e a f c g and a b d e c f g, respectively. The postorder traversal of the binary tree is:

(A) d e b f g c a
(B) e d b g f c a
(C) e d b f g c a
(D) d e f g b c a
Answer (A)
Below is the given tree.
                              a 
                           /    \
                        /          \
                      b             c
                   /   \          /   \
                 /       \      /       \
               d         e    f          g 
 
1. Consider a hash table of size seven, with starting index 
zero, and a hash function (3x + 4)mod7. Assuming the hash table is 
initially empty, which of the following is the contents of the table 
when the sequence 1, 3, 8, 10 is inserted into the table using closed 
hashing? Note that ‘_’ denotes an empty location in the table.

(A) 8, _, _, _, _, _, 10

(B) 1, 8, 10, _, _, _, 3

(C) 1, _, _, _, _, _,3

(D) 1, 10, 8, _, _, _,  3
Answer (B)
Please see http://lcm.csa.iisc.ernet.in/dsa/node38.html for closed hashing and probing.
Let us put values 1, 3, 8, 10 in the hash of size 7.
Initially, hash table is empty
- - - - - - - 0 1 2 3 4 5 6 The value of function (3x + 4)mod 7 for 1 is 0, so let us put the value at 0
1 - - - - - - 0 1 2 3 4 5 6 The value of function (3x + 4)mod 7 for 3 is 6, so let us put the value at 6
1 - - - - - 3 0 1 2 3 4 5 6 The value of function (3x + 4)mod 7 for 8 is 0, but 0 is already occupied, let us put the value(8) at next available space(1)
1 8 - - - - 3 0 1 2 3 4 5 6 The value of function (3x + 4)mod 7 for 10 is 6, but 6 is already occupied, let us put the value(10) at next available space(2)
1 8 10 - - - 3 0 1 2 3 4 5 6


2. In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity by

(A) Dijkstra’s algorithm starting from S.
(B) Warshall’s algorithm
(C) Performing a DFS starting from S.
(D) Performing a BFS starting from S.
Answer(D)
* Time Comlexity of the Dijkstra’s algorithm is O(|V|^2 + E) * Time Comlexity of the Warshall’s algorithm is O(|V|^3) * DFS cannot be used for finding shortest paths * BFS can be used for unweighted graphs. Time Complexity for BFS is O(|E| + |V|)

3. A complete n-ary tree is a tree in which each node has n children or no children. Let I be the number of internal nodes and L be the number of leaves in a complete n-ary tree. If L = 41, and I = 10, what is the value of n?
(A) 3
(B) 4
(C) 5
(D) 6
Answer (C)
For an n-ary tree where each node has n children or no children, following relation holds
L = (n-1)*I + 1 Where L is the number of leaf nodes and I is the number of internal nodes.
Let us find out the value of n for the given data.
L = 41 , I = 10 41 = 10*(n-1) + 1 (n-1) = 4 n = 5

4. In the following C function, let n >= m.
int gcd(n,m) { if (n%m ==0) return m; n = n%m; return gcd(m,n); } How many recursive calls are made by this function?
(A) \theta(logn)?
(B) \Omega(n)
(C) \theta(loglogn)
(D) \theta(sqrt(n))
Answer (A)
Above code is implementation of the Euclidean algorithm for finding Greatest Common Divisor (GCD).
Please see http://mathworld.wolfram.com/EuclideanAlgorithm.html for time complexity.


5. What is the time complexity of the following recursive function:
int DoSomething (int n) { if (n <= 2) return 1; else return (DoSomething (floor(sqrt(n))) + n); } (A) \theta(n)
(B) \theta(nlogn)
(C) \theta(logn)
(D) \theta(loglogn)
Answer (D)
Recursive relation for the DoSomething() is
T(n) = T( \sqrt{n}) + C1 if n > 2 We have ignored the floor() part as it doesn’t matter here if it’s a floor or ceiling.
Let n = 2^m, T(n) = T(2^m) Let T(2^m) = S(m) From the above two, T(n) = S(m) S(m) = S(m/2) + C1 /* This is simply binary search recursion*/ S(m) = O(logm) = O(loglogn) /* Since n = 2^m */ Now, let us go back to the original recursive function T(n) T(n) = S(m) = O(LogLogn)

1. Consider the following C program segment where CellNode represents a node in a binary tree:
struct CellNode
{
  struct CellNOde *leftChild;
  int element;
  struct CellNode *rightChild;
};
int GetValue(struct CellNode *ptr)
{
  int value = 0;
  if (ptr != NULL)
  {
   if ((ptr->leftChild == NULL) &&
        (ptr->rightChild == NULL))
      value = 1;
   else
      value = value + GetValue(ptr->leftChild)
                   + GetValue(ptr->rightChild);
  }
  return(value);
}
The value returned by GetValue() when a pointer to the root of a binary tree is passed as its argument is:
(A) the number of nodes in the tree
(B) the number of internal nodes in the tree
(C) the number of leaf nodes in the tree
(D) the height of the tree
Answer (C)

2. Consider the process of inserting an element into a Max Heap, where the Max Heap is represented by an array. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of comparisons performed is:
(A) \theta(logn)
(B) \theta(LogLogn )
(C) \theta(n)
(D) \theta(nLogn)
Answer (B)
The height of a Max Heap is \theta(logn). If we perform binary search for finding the correct position then we need to do \theta(LogLogn) comparisons.


3. Let w be the minimum weight among all edge weights in an undirected connected graph. Let e be a specific edge of weight w . Which of the following is FALSE?
(A) There is a minimum spanning tree containing e.
(B) If e is not in a minimum spanning tree T, then in the cycle formed by adding e to T, all edges have the same weight.
(C) Every minimum spanning tree has an edge of weight w .
(D) e is present in every minimum spanning tree.
Answer (D)
(A), (B) and (C) are correct.
(D) is incorrect as there may be many edges of wight w in the graph and e may not be picked up in some of the minimum spanning trees.


4. An array of n numbers is given, where n is an even number. The maximum as well as the minimum of these n numbers needs to be determined. Which of the following is TRUE about the number of comparisons needed?
(A) At least 2n – c comparisons, for some constant c, are needed.
(B) At most 1.5n – 2 comparisons are needed.
(C) At least nLog2n comparisons are needed.
(D) None of the above.
Answer (B)



5. Consider the following C code segment:
int IsPrime(n)
{
  int i,n;
  for(i=2;i<=sqrt(n);i++)
   if(n%i == 0)
     {printf(“Not Prime\n”); return 0;}
  return 1;
}
Let T(n) denotes the number of times the for loop is executed by the program on input n. Which of the following is TRUE?
(A) T(n) = O(sqrt(n)) and T(n) = \Omega(sqrt(n))
(B) T(n) = O(sqrt(n)) and T(n) = \Omega(1)
(C) T(n) = O(n) and T(n) = \Omega(sqrt(n))
(D) None of the above
Answer (B)
Big O notation describes the upper bound and Big Omega notation describes the lower bound for an algorithm.
The for loop in the question is run maximum sqrt(n) times and minimum 1 time. Therefore, T(n) = O(sqrt(n)) and T(n) = \Omega(1)

1. The number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children is:
a) n/2
b) (n-1)/3
c) (n-1)/2
d) (2n+1)/3
Answer(d)
Let L be the number of leaf nodes and I be the number of internal nodes, then following relation holds for above given tree
  L = (3-1)I + 1 = 2I + 1
Total number of nodes(n) is sum of leaf nodes and internal nodes
  n = L + I 
After solving above two, we get L = (2n+1)/3


2. The running time of the following algorithm
  Procedure A(n)  
  If n <= 2 return(1) else return A(\lceil \sqrt{n}  \rceil);
is best described by
a) O(n)
b) O(log n)
c) O(1og log n)
d) O(1)
Answer(c)


3. A weight-balanced tree is a binary tree in which for each node. The number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the farthest leaf) of such a tree on n nodes is best described by which of the following?
a) \log_2 n
b) \log_{4/3} n
c) \log_3 n
d) \log_{3/2} n
Answer(d)
Let the maximum possible height of a tree with n nodes is represented by H(n).
The maximum possible value of H(n) can be approximately written using following recursion
   H(n) = H(2n/3) + 1     
The solution of above recurrence is \log_{3/2} n. We can simply get it by drawing a recursion tree.

4. Consider the following algorithm for searching for a given number x in an unsorted – array A[1..n] having n distinct values:

1)	Choose an i uniformly at random from 1..n; 
2)	If A[i] = x then Stop else Goto 1; 
Assuming that x is present in A, what is the expected number of comparisons made by the algorithm before it terminates?
a) n
b) n-l
c) 2n
d) n/2
Answer(a)
If you remember the coin and dice questions, you can just guess the answer for the above.
Below is proof for the answer.
Let expected number of comparisons be E. Value of E is sum of following expression for all the possible cases.
number_of_comparisons_for_a_case * probability_for_the_case 
Case 1
  If A[i] is found in the first attempt 
  number of comparisons = 1
  probability of the case  = 1/n
Case 2
  If A[i] is found in the second attempt 
  number of comparisons = 2
  probability of the case  = (n-1)/n*1/n
Case 3
  If A[i] is found in the third attempt 
  number of comparisons = 2
  probability of the case  = (n-1)/n*(n-1)/n*1/n
There are actually infinite such cases. So, we have following infinite series for E.
E  = 1/n + [(n-1)/n]*[1/n]*2 + [(n-1)/n]*[(n-1)/n]*[1/n]*3 + ….  (1)
After multiplying equation (1) with (n-1)/n, we get
E (n-1)/n = [(n-1)/n]*[1/n] + [(n-1)/n]*[(n-1)/n]*[1/n]*2 + 
                                 [(n-1)/n]*[(n-1)/n]*[(n-1)/n]*[1/n]*3 ……….(2)
Subtracting (2) from (1), we get
E/n = 1/n + (n-1)/n*1/n + (n-1)/n*(n-1)/n*1/n + …………
The expression on right side is a GP with infinite elements. Let us apply the sum formula (a/(1-r))
  E/n = [1/n]/[1-(n-1)/n]  = 1
  E = n 
 
 
1. We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. The total time required for this is
(A) \theta(logn)
(B) \theta(n)
(C) \theta(nlogn)
(D) \theta(n^2)
Answer(C)
The worst case time complexity for insertion in a binary heap is O(Logn) (Refer Wiki). So inserting n elements in a heap of size n should take \theta(nlogn) time.


2. The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is

(A) MNOPQR
(B) NQMPOR
(C) QMNPRO
(D) QMNPOR
Answer (C)

3. Consider the following functions:

f(n) = 2^n g(n) = n! h(n) = n^logn Which of the following statements about the asymptotic behaviour of f(n), g(n), and h(n) is true?
(A) f(n) = O(g(n)); g(n) = O(h(n))
(B) f(n) = \Omega(g(n)); g(n) = O(h(n))
(C) g(n) = O(f(n)); h(n) = O(f(n))
(D) h(n) = O(f(n)); g(n) = \Omega(f(n))
Answer (D)
According to order of growth: h(n) < f(n) < g(n) (g(n) is asymptotically greater than f(n) and f(n) is asymptotically greater than h(n) )
We can easily see above order by taking logs of the given 3 functions
lognlogn < n < log(n!) (logs of the given f(n), g(n) and h(n)). Note that log(n!) = \theta(nlogn)

4. The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is

(A) \theta(n)
(B) \theta(logn)
(C) \theta(log*n)
(D) \theta(n)
Answer (B)

1. The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity.
(A) \theta(n)
(B) \theta(m)
(C) \theta(m + n)
(D) \theta(mn)
Answer (C)
Connected components can be found in O(m + n) using Tarjan’s algorithm. Once we have connected components, we can count them.

2. Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then

(A) T(n) <= 2T(n/5) + n
(B) T(n) <= T(n/5) + T(4n/5) + n
(C) T(n) <= 2T(4n/5) + n
(D) T(n) <= 2T(n/2) + n
Answer (B)
For the case where n/5 elements are in one subset, T(n/5) comparisons are needed for the first subset with n/5 elements, T(4n/5) is for the rest 4n/5 elements, and n is for finding the pivot.
If there are more than n/5 elements in one set then other set will have less than 4n/5 elements and time complexity will be less than T(n/5) + T(4n/5) + n because recursion tree will be more balanced.

3 Dijkstra’s single source shortest path algorithm when run from vertex a in the below graph, computes the correct shortest path distance to


(A) only vertex a
(B) only vertices a, e, f, g, h
(C) only vertices a, b, c, d
(D) all the vertices
Answer (D)
Dijkstra’s single source shortest path is not guaranteed to work for graphs with negative weight edges, but it works for the given graph.
Let us see…
Let us run the 1st pass
b 1
b is minimum, so shortest distance to b is 1.
After 1st pass, distances are
c 3, e -2.
e is minimum, so shortest distance to e is -2
After 2nd pass, distances are
c 3, f 0.
f is minimum, so shortest distance to f is 0
After 3rd pass, distances are
c 3, g 3.
Both are same, let us take g. so shortest distance to g is 3.
After 4th pass, distances are
c 3, h 5
c is minimum, so shortest distance to c is 3
After 5th pass, distances are
h -2
h is minimum, so shortest distance to h is -2
4. The following C function takes a single-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers 1, 2, 3, 4, 5, 6, 7 in the given order. What will be the contents of the list after the function completes execution?

struct node
{
  int value;
  struct node *next;
};
void rearrange(struct node *list)
{
  struct node *p, * q;
  int temp;
  if ((!list) || !list->next)
      return;
  p = list;
  q = list->next;
  while(q)
  {
     temp = p->value;
     p->value = q->value;
     q->value = temp;
     p = q->next;
     q = p?p->next:0;
  }
}
(A) 1,2,3,4,5,6,7
(B) 2,1,4,3,6,5,7
(C) 1,3,2,5,4,7,6
(D) 2,3,4,5,6,7,1
Answer (B)
The function rearrange() exchanges data of every node with its next node. It starts exchanging data from the first node itself.

1. Consider a binary max-heap implemented using an array. Which one of the following array represents a binary max-heap?

(A) 25,12,16,13,10,8,14
(B) 25,14,13,16,10,8,12
(C) 25,14,16,13,10,8,12
(D) 25,14,12,13,10,8,16
Answer (C)
A tree is max-heap if data at every node in the tree is greater than or equal to it’s children’ s data.
In array representation of heap tree,  a node at index i has its left child at index 2i + 1 and right child at index 2i + 2.
           25
        /      \
      /          \
    14            16
   /  \           /  \
 /      \       /     \
13     10      8       12
2. What is the content of the array after two delete operations on the correct answer to the previous question?

(A) 14,13,12,10,8
(B) 14,12,13,8,10
(C) 14,13,8,12,10
(D) 14,13,12,8,10
Answer(D)
For Heap trees, deletion of a node includes following two operations.
1) Replace the root with last element on the last level.
2) Starting from root, heapify the complete tree from top to bottom..
Let us delete the two nodes one by one:
1) Deletion of 25:
Replace 25 with 12
          12
        /    \
      /       \
    14        16
   / \         /
 /     \      /
13     10    8
Since heap property is violated for root (16 is greater than 12), make 16 as root of the tree.
           16
        /     \
      /        \
    14         12
   / \         /
  /   \       /
13     10    8
2) Deletion of 16:
Replace 16 with 8
           8
        /    \
       /      \
    14         12
   / \
  /   \
 13     10
Heapify from root to bottom.
           14
         /    \
       /       \
     8         12
    / \
   /   \
 13     10
            14
         /     \
        /       \
     13         12
    / \
   /   \
  8    10
3. In quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?

(A) \theta(n)
(B) \theta(nLogn)
(C) \theta(n^2)
(D) \theta(n^2 log n)
Answer(B)
The recursion expression becomes:
T(n) = T(n/4) + T(3n/4) + cn
After solving the above recursion, we get \theta(nLogn).

4. What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.

(A) 2
(B) 3
(C) 4
(D) 5
Answer(B)
AVL trees are binary trees with the following restrictions.
1) the height difference of the children is at most 1.
2) both children are AVL trees
                 a
               /   \
             /      \
            b        c
          /  \      /
         /    \    /
        d     e   g
       /
      /
     h
References:
http://en.wikipedia.org/wiki/AVL_tree

1. An implementation of a queue Q, using two stacks S1 and S2, is given below:
void insert(Q, x) {
   push (S1, x);
}

void delete(Q){
   if(stack-empty(S2)) then 
      if(stack-empty(S1)) then {
          print(“Q is empty”);
          return;
      }
      else while (!(stack-empty(S1))){
          x=pop(S1);
          push(S2,x);
      }
   x=pop(S2);
}
Let n insert and m (<=n) delete operations be performed in an arbitrary order on an empty queue Q. Let x and y be the number of push and pop operations performed respectively in the process. Which one of the following is true for all m and n?
(A) n+m <= x < 2n and 2m <= y <= n+m
(B) n+m <= x < 2n and 2m<= y <= 2n
(C) 2m <= x < 2n and 2m <= y <= n+m
(D) 2m <= x <2n and 2m <= y <= 2n
Answer(A)
The order in which insert and delete operations are performed matters here.
The best case: Insert and delete operations are performed alternatively. In every delete operation, 2 pop and 1 push operations are performed. So, total m+ n push (n push for insert() and m push for delete()) operations and 2m pop operations are performed.

The worst case:
First n elements are inserted and then m elements are deleted. In first delete operation, n + 1 pop operations and n push operation are performed. Other than first, in all delete operations, 1 pop operation is performed. So, total m + n pop operations and 2n push operations are performed (n push for insert() and m push for delete())
2. Consider the following graph:

Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal’s algorithm?
(A) (a—b),(d—f),(b—f),(d—c),(d—e)
(B) (a—b),(d—f),(d—c),(b—f),(d—e)
(C) (d—f),(a—b),(d—c),(b—f),(d—e)
(D) (d—f),(a—b),(b—f),(d—e),(d—c)
Answer (D)
The edge (d-e) cannot be considered before (d-c) in Kruskal’s minimum spanning tree algorithm because Kruskal’s algorithm picks the edge with minimum weight from the current set of edges at each step.
3. The median of n elements can be found in O(n)time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot?
(A) \theta(n)
(B) \theta(nlogn)
(C) \theta(n^2)
(D) \theta(n^3)
Answer (B)
If median is always used as pivot, then recursion remains T(n) = 2T(n/2) + cn for all the cases where cn is combined time for median finding and partition. So, worst case time complexity of this quick sort becomes \theta(nlogn). In practical implementations, however, this variant is considerably slower on average (see http://en.wikipedia.org/wiki/Quicksort#Selection-based_pivoting)

1. Consider the polynomial p(x) = a0 + a1x + a2x^2 +a3x^3, where ai != 0, for all i. The minimum number of multiplications needed to evaluate p on an input x is:
(A) 3
(B) 4
(C) 6
(D) 9
Answer (A)
Multiplications can be minimized using following order for evaluation of the given expression.
p(x) = a0 + x(a1 + x(a2 + a3x))
2. To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:
(A) Queue
(B) Stack
(C) Heap
(D) B-Tree
Answer(A)
The shortest path in an un-weighted graph means the smallest number of edges that must be traversed in order to reach the destination in the graph. This is the same problem as solving the weighted version where all the weights happen to be 1. If we use Queue (FIFO) instead of Priority Queue (Min Heap), we get the shortest path in linear time O(|V| + |E|). Basically we do BFS traversal of the graph to get the shortest paths.
3.  A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4] location onward. An item x can be inserted into a 3-ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property.
Which one of the following is a valid sequence of elements in an array representing 3-ary max heap?
(A) 1, 3, 5, 6, 8, 9
(B) 9, 6, 3, 1, 8, 5
(C) 9, 3, 6, 8, 5, 1
(D) 9, 5, 6, 8, 3, 1
Answer (D)
                                      9
                                   /  |   \
                                /     |     \
                              5       6      8
                           /  |
                         /    |
                       3      1
4.  Suppose the elements 7, 2, 10 and 4 are inserted, in that order, into the valid 3- ary max heap found in the above question, Which one of the following is the sequence of items in the array representing the resultant heap?
(A) 10, 7, 9, 8, 3, 1, 5, 2, 6, 4
(B) 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
(C) 10, 9, 4, 5, 7, 6, 8, 2, 1, 3
(D) 10, 8, 6, 9, 7, 2, 3, 4, 1, 5
Answer(A)
After insertion of 7
                                          9
                                      /   |   \
                                    /     |     \
                                  7       6       8
                               / | \
                             /   |  \
                            3    1    5    
After insertion of 2
                                           9
                                      /    |   \
                                    /      |     \
                                  7        6       8
                               / | \       /
                             /   |  \     /
                            3    1    5  2
After insertion of 10
                                 10
                             /    |   \
                           /      |     \
                        7         9       8
                    / | \       / |
                  /   |  \     /  |
                3    1    5  2    6
After insertion of 4
                                 10
                             /   |   \
                           /     |     \
                         7        9       8
                      / | \      / | \
                    /   |  \    /  |   \
                  3    1    5  2   6    4 
 
1. Let X be a problem that belongs to the class NP. Then which one of the following is TRUE?
(A) There is no polynomial time algorithm for X.
(B) If X can be solved deterministically in polynomial time, then P = NP.
(C) If X is NP-hard, then it is NP-complete.
(D) X may be undecidable.
Answer (C)
(A) is incorrect because set NP includes both P(Polynomial time solvable) and NP-Complete .
(B) is incorrect because X may belong to P (same reason as (A))
(C) is correct because NP-Complete set is intersection of NP and NP-Hard sets.
(D) is incorrect because all NP problems are decidable in finite set of operations.
2. What is the number of swaps required to sort n elements using selection sort, in the worst case?
(A) \theta(n)
(B) \theta(n log n)
(C) \theta(n^2 )
(D) \theta(n^2 log n)
Answer (A)
Here is Selection Sort algorithm for sorting in ascending order.
1. Find the minimum value in the list 2. Swap it with the value in the first position 3. Repeat the steps above for the remainder of the list (starting at the second position and advancing each time) As we can see from the algorithm, selection sort performs swap only after finding the appropriate position of the current picked element. So there are O(n) swaps performed in selection sort.
Because swaps require writing to the array, selection sort is preferable if writing to memory is significantly more expensive than reading. This is generally the case if the items are huge but the keys are small. Another example where writing times are crucial is an array stored in EEPROM or Flash. There is no other algorithm with less data movement.
References:
http://en.wikipedia.org/wiki/Selection_sort
3. The running time of an algorithm is represented by the following recurrence relation:
if n <= 3 then T(n) = n else T(n) = T(n/3) + cn Which one of the following represents the time complexity of the algorithm?
(A) \theta(n)
(B) \theta(n log n)
(C) \theta(n^2)
(D) \theta(n^2log n)
Answer(A)
T(n) = cn + T(n/3) = cn + cn/3 + T(n/9) = cn + cn/3 + cn/9 + T(n/27) Taking the sum of infinite GP series. The value of T(n) will be less than this sum. T(n) <= cn(1/(1-1/3)) <= 3cn/2 or we can say cn <= T(n) <= 3cn/2 Therefore T(n) = \theta(n) This can also be solved using Master Theorem for solving recurrences. The given expression lies in Case 3 of the theorem.
4. The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k) = k mod 10 and linear probing. What is the resultant hash table?

Answer (C)
To get the idea of open addressing concept, you can go through below lines from Wikipedia
.
Open addressing, or closed hashing, is a method of collision resolution in hash tables. With this method a hash collision is resolved by probing, or searching through alternate locations in the array (the probe sequence) until either the target record is found, or an unused array slot is found, which indicates that there is no such key in the table. Well known probe sequences include:
linear probing in which the interval between probes is fixed–often at 1.
quadratic probing in which the interval between probes increases linearly (hence, the indices are described by a quadratic function).
double hashing in which the interval between probes is fixed for each record but is computed by another hash function.

1. Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?
(A) R is NP-complete
(B) R is NP-hard
(C) Q is NP-complete
(D) Q is NP-hard
Answer (B)
(A) Incorrect because R is not in NP. A NP Complete problem has to be in both NP and NP-hard.
(B) Correct because a NP Complete problem S is polynomial time educable to R.
(C) Incorrect because Q is not in NP.
(D) Incorrect because there is no NP-complete problem that is polynomial time Turing-reducible to Q.


2) A set X can be represented by an array x[n] as follows:

Consider the following algorithm in which x,y and z are Boolean arrays of size n:
algorithm zzz(x[] , y[], z [])
{
   int i;
   for (i=O; i<n; ++i)
     z[i] = (x[i] ^ ~y[i]) V (~x[i] ^ y[i])
}
The set Z computed by the algorithm is:
(A) (X Intersection Y)
(B) (X Union Y)
(C) (X-Y) Intersection (Y-X)
(D) (X-Y) Union (Y-X)
Answer (D)
The expression x[i] ^ ~y[i]) results the only 1s in x where corresponding entry in y is 0. An array with these set bits represents set X – Y
The expression ~x[i] ^ y[i]) results the only 1s in y where corresponding entry in x is 0. An array with these set bits represents set Y – X.
The operator “V” results in Union of the above two sets.


3. Consider the following recurrence:

Which one of the following is true?
(A) T(n) = \theta(loglogn)
(B) T(n) = \theta(logn)
(C) T(n) = \theta(sqrt(n))
(D) T(n) = \theta(n)
Answer (B)
  Let n = 2^m
  T(2^m) = T(2^(m/2)) + 1
  Let T(2^m) =  S(m)
  S(m)  = 2S(m/2) + 1  
Above expression is a binary tree traversal recursion whose time complexity is \theta(m). You can also prove using Master theorem.
S(m)  = \theta(m)  
      = \theta(logn)  /* Since n = 2^m */
Now, let us go back to the original recursive function T(n)
  T(n)  = T(2^m) = S(m)
                 = \theta(Logn) 
 
1. The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a1 ,a2 ,a3 ,…,an} and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2-dimensional Boolean array X, with n rows and W+1 columns. X[i, j],1 <= i <= n, 0 <= j <= W, is TRUE if and only if there is a subset of {a1 ,a2 ,...,ai} whose elements sum to j. Which of the following is valid for 2 <= i <= n and ai <= j <= W?
(A) X[i, j] = X[i - 1, j] V X[i, j -ai]
(B) X[i, j] = X[i - 1, j] V X[i - 1, j - ai]
(C) X[i, j] = X[i - 1, j] V X[i, j - ai]
(D) X[i, j] = X[i - 1, j] V X[i -1, j - ai]
Answer (B)
X[I, j] (2 <= i <= n and ai <= j <= W), is true if any of the following is true
1) Sum of weights excluding ai is equal to j, i.e., if X[i-1, j] is true.
2) Sum of weights including ai is equal to j, i.e., if X[i-1, j-ai] is true so that we get (j – ai) + ai as j.
2. In question 1, which entry of the array X, if TRUE, implies that there is a subset whose elements sum to W?
(A) X[1, W]
(B) X[n ,0]
(C) X[n, W]
(D) X[n -1, n]
Answer (C)
If we get the entry X[n, W] as true then there is a subset of {a1, a2, .. an} that has sum as W.
Reference: http://en.wikipedia.org/wiki/Subset_sum_problem
3. Consider the following C program that attempts to locate an element x in an array Y[] using binary search. The program is erroneous.
1.   f(int Y[10], int x) {
2.     int i, j, k;
3.     i = 0; j = 9;
4.     do {
5.             k =  (i + j) /2;
6.             if( Y[k] < x)  i = k; else j = k;
7.         } while(Y[k] != x && i < j);
8.     if(Y[k] == x) printf ("x is in the array ") ;
9.     else printf (" x is not in the array ") ;
10. }
On which of the following contents of Y and x does the program fail?
(A) Y is [1 2 3 4 5 6 7 8 9 10] and x < 10
(B) Y is [1 3 5 7 9 11 13 15 17 19] and x < 1
(C) Y is [2 2 2 2 2 2 2 2 2 2] and x > 2
(D) Y is [2 4 6 8 10 12 14 16 18 20] and 2 < x < 20 and x is even
Answer (C)
The above program doesn’t work for the cases where element to be searched is the last element of Y[] or greater than the last element (or maximum element) in Y[]. For such cases, program goes in an infinite loop because i is assigned value as k in all iterations, and i never becomes equal to or greater than j. So while condition never becomes false.

4. In question 3, the correction needed in the program to make it work properly is

(A) Change line 6 to: if (Y[k] < x) i = k + 1; else j = k-1;
(B) Change line 6 to: if (Y[k] < x) i = k - 1; else j = k+1;
(C) Change line 6 to: if (Y[k] <= x) i = k; else j = k;
(D) Change line 7 to: } while ((Y[k] == x) && (i < j));
Answer (A)
Below is the corrected function
f(int Y[10], int x) {
   int i, j, k;
   i = 0; j = 9;
   do {
           k =  (i + j) /2;
           if( Y[k] < x)  i = k + 1; else j = k – 1;
       } while(Y[k] != x && i < j);
   if(Y[k] == x) printf ("x is in the array ") ;
   else printf (" x is not in the array ") ;
}
Reference: http://en.wikipedia.org/wiki/Binary_search_algorithm#Implementations

1) A program P reads in 500 integers in the range [0..100] exepresenting the scores of 500 students. It then prints the frequency of each score above 50. What would be the best way for P to store the frequencies?
(a) An array of 50 numbers
(b) An array of 100 numbers
(c) An array of 500 numbers
(d) A dynamically allocated array of 550 numbers
Answer (a)
An array of size 50 looks the best option to store number of students for each score. We need to store frequencies of scores above 50. We can ignore scores below 50 and to index the scores above 50, we can subtract 50 from the score value/

2) An undirected graph G has n nodes. Its adjacency matrix is given by an n × n square matrix whose (i) diagonal elements are 0‘s and (ii) non-diagonal elements are 1‘s. which one of the following is TRUE?

(a) Graph G has no minimum spanning tree (MST)
(b) Graph G has a unique MST of cost n-1
(c) Graph G has multiple distinct MSTs, each of cost n-1
(d) Graph G has multiple spanning trees of different costs
Answer (c)
If all non diagonal elements are 1, then every vertex is connected to every other vertex in the graph with an edge of weight 1. Such a graph has multiple distinct MSTs with cost n-1. See the below example.
The connected graph:

Below are three Minimum Spanning trees each of cost 2.0.
Minimum Spanning Tree 1

Minimum Spanning Tree 2

Minimum Spanning Tree 3

3) The time complexity of computing the transitive closure of a binary relation on a set of n elements is known to be:
a) O(n)
b) O(nLogn)
c) O(n^(3/2))
d) O(n^3)
Answer (d)
In mathematics, the transitive closure of a binary relation R on a set X is the smallest transitive relation on X that contains R. If the original relation is transitive, the transitive closure will be that same relation; otherwise, the transitive closure will be a different relation.
In computer science the concept of transitive closure can be thought of as constructing a data structure that makes it possible to answer reachability questions. That is, can one get from node a to node other node b in one or more hops? A binary relation tells you only that node a is connected to node b, and that node b is connected to node c, etc. After the transitive closure is constructed in an O(1) operation one may determine that node c is reachable from node a.
Warshall’s algorithm can be used to construct the Transitive closure of directed graphs (). In Warshall’s original formulation of the algorithm, the graph is unweighted and represented by a Boolean adjacency matrix. Then the addition operation is replaced by logical conjunction (AND) and the minimum operation by logical disjunction (OR).
References:
http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
http://en.wikipedia.org/wiki/Transitive_closure
4. A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is given below:
10, 8, 5, 3, 2
Two new elements ”1‘ and ”7‘ are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the elements is:

(a) 10, 8, 7, 5, 3, 2, 1
(b) 10, 8, 7, 2, 3, 1, 5
(c) 10, 8, 7, 1, 2, 3, 5
(d) 10, 8, 7, 3, 2, 1, 5
Answer (D)
Original Max-Heap is:
        10
       /  \
      8    5
     / \
    3   2
After Insertion of 1.
         10
       /    \
      8      5
     / \    /
    3   2 1 
After Insertion of 7.
         10
       /   \
      8     7
    / \    / \ 
   3   2  1   5 
 
1. Which one of the following is a key factor for preferring B-trees to binary search trees for indexing database relations?
(a) Database relations have a large number of records
(b) Database relations are sorted on the primary key
(c) B-trees require less memory than binary search trees
(d) Data transfer form disks is in blocks.
Answer (d)
A disk block contains fairly large number of keys. Unlike BST where each node contains only one key, B-Tree is designed to contain large number of keys so that tree height is small.
2. How many distinct binary search trees can be created out of 4 distinct keys?
(a) 5
(b) 14
(c) 24
(d) 42
Answer (b)
Here is a systematic way to enumerate these BSTs. Consider all possible binary search trees with each element at the root. If there are n nodes, then for each choice of root node, there are n – 1 non-root nodes and these non-root nodes must be partitioned into those that are less than a chosen root and those that are greater than the chosen root.
Let’s say node i is chosen to be the root. Then there are i – 1 nodes smaller than i and n – i nodes bigger than i. For each of these two sets of nodes, there is a certain number of possible subtrees.
Let t(n) be the total number of BSTs with n nodes. The total number of BSTs with i at the root is t(i – 1) t(n – i). The two terms are multiplied together because the arrangements in the left and right subtrees are independent. That is, for each arrangement in the left tree and for each arrangement in the right tree, you get one BST with i at the root.
Summing over i gives the total number of binary search trees with n nodes.

The base case is t(0) = 1 and t(1) = 1, i.e. there is one empty BST and there is one BST with one node.

3. In a complete k-ary tree, every internal node has exactly k children. The number of leaves in such a tree with n internal nodes is:
(a) nk
(b) (n – 1) k+ 1
(c) n( k – 1) + 1
(d) n(k – 1)
Answer (c)
4) Suppose T(n) = 2T(n/2) + n, T(0) = T(1) = 1
Which one of the following is false.

a) T(n) = O(n^2)
b) T(n) = \theta(nLogn)
c) T(n) = \Omega(n^2)
d) T(n) = O(nLogn)
Answer (c)
The given recurrence relation can be solved using Master Theorem. It lies in case 2 of Master Theorem. Or, if you remember recurrence relation of Merge Sort or best case Quick Sort, you can guess the value of T(n).
T(n) = \theta(nLogn)
By definition of Big O notation, we can say.
\theta(nLogn) = O(nLogn) = O(n^2)
\theta(nLogn) ca be equal to \Omega(n) or \Omega(nLogn), but not \Omega(n^2)

1. The following C function takes a simply-linked list as input argument. It modifies the list by moving the last element to the front of the list and returns the modified list. Some part of the code is left blank.
typedef struct node 
{
  int value;
  struct node *next;
}Node;

Node *move_to_front(Node *head) 
{
  Node *p, *q;
  if ((head == NULL: || (head->next == NULL)) 
    return head;
  q = NULL; p = head;
  while (p-> next !=NULL) 
  {
    q = p;
    p = p->next;
  }
  _______________________________
  return head;
}
Choose the correct alternative to replace the blank line.
(A) q = NULL; p->next = head; head = p;
(B) q->next = NULL; head = p; p->next = head;
(C) head = p; p->next = q; q->next = NULL;
(D) q->next = NULL; p->next = head; head = p;
Answer(D)
When the while loop ends, q contains address of second last node and p contains address of last node. So we need to do following things after while loop.
i) Set next of q as NULL (q->next = NULL).
ii) Set next of p as head (p->next = head).
iii) Make head as p ( head = p)
Step (ii) must be performed before step (iii). If we change head first, then we lose track of head node in the original linked list.


2. A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below.

Which one of the following choices gives a possible order in which the key values could have been inserted in the table?
(A) 46, 42, 34, 52, 23, 33
(B) 34, 42, 23, 52, 33, 46
(C) 46, 34, 42, 23, 52, 33
(D) 42, 46, 33, 23, 34, 52
Answer (C)
The sequence (A) doesn’t create the hash table as the element 52 appears before 23 in this sequence.
The sequence (B) doesn’t create the hash table as the element 33 appears before 46 in this sequence.
The sequence (C) creates the hash table as 42, 23 and 34 appear before 52 and 33, and 46 appears before 33.
The sequence (D) doesn’t create the hash table as the element 33 appears before 23 in this sequence.
3. How many different insertion sequences of the key values using the same hash function and linear probing will result in the hash table shown above?
(A) 10
(B) 20
(C) 30
(D) 40
Answer (C)
In a valid insertion sequence, the elements 42, 23 and 34 must appear before 52 and 33, and 46 must appear before 33.
Total number of different sequences = 3! x 5 = 30
In the above expression, 3! is for elements 42, 23 and 34 as they can appear in any order, and 5 is for element 46 as it can appear at 5 different places.

1 Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry Wij in the matrix W below is the weight of the edge {i, j}.
What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in the tree T?

(A) 7
(B) 8
(C) 9
(D) 10
Answer (D)
To get the minimum spanning tree with vertex 0 as leaf, first remove 0th row and 0th column and then get the minimum spanning tree (MST) of the remaining graph. Once we have MST of the remaining graph, connect the MST to vertex 0 with the edge with minimum weight (we have two options as there are two 1s in 0th row).

2. In the graph given in question 1, what is the minimum possible weight of a path P from vertex 1 to vertex 2 in this graph such that P contains at most 3 edges?

(A) 7
(B) 8
(C) 9
(D) 10
Answer (B)
Path: 1 -> 0 -> 4 -> 2
Weight: 1 + 4 + 3
3. The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree sequence of any graph?
I. 7, 6, 5, 4, 4, 3, 2, 1
II. 6, 6, 6, 6, 3, 3, 2, 2
III. 7, 6, 6, 4, 4, 3, 2, 2
IV. 8, 7, 7, 6, 4, 2, 1, 1
(A) I and II
(B) III and IV
(C) IV only
(D) II and IV
Answer (D)
In sequence IV, we have a vertex with degree 8 which is not possible in a simple graph (no self loops and no multiple edges) with total vertex count as 8. Maximum possible degree in such a graph is 7.
In sequence II, four vertices are connected to 6 other vertices, but remaining 4 vertices have degrees as 3, 3, 2 and 2 which are not possible in a simple graph (no self loops and no multiple edges).
4. Consider a B+-tree in which the maximum number of keys in a node is 5. What is the minimum number of keys in any non-root node?
(A) 1
(B) 2
(C) 3
(D) 4
Answer (B)
Since the maximum number of keys is 5, maximum number of children a node can have is 6. By definition of B Tree, minimum children that a node can have would be 6/2 = 3. Therefore, minimum number of keys that a node can have becomes 2 (3-1).

1) A max-heap is a heap where the value of each parent is greater than or equal to the values of its children. Which of the following is a max-heap?

Answer: (B)
A binary tree is max-heap if it is a complete binary tree (A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible) and it follows the max-heap property (value of each parent is greater than or equal to the values of its children).
A) is not a max-heap because it is not a complete binary tree
B) is a max-heap because it is complete binary tree and follows max-heap property.
C) is not a max-heap because 8 is a chile of 5 in this tree, so violates the max-heap property.
D) is not a max-heap because 8 is a chile of 5 in this tree, so violates the max-heap property. There are many other nodes in this tree which violate max-heap property in this tree.
2) Four matrices M1, M2, M3 and M4 of dimensions pxq, qxr, rxs and sxt respectively can be multiplied is several ways with different number of total scalar multiplications. For example, when multiplied as ((M1 X M2) X (M3 X M4)), the total number of multiplications is pqr + rst + prt. When multiplied as (((M1 X M2) X M3) X M4), the total number of scalar multiplications is pqr + prs + pst.
If p = 10, q = 100, r = 20, s = 5 and t = 80, then the number of scalar multiplications needed is
A) 248000
B) 44000
C) 19000
D) 25000
Answer (C)
We get minimum number of multiplications using ((M1 X (M2 X M3)) X M4).
Total number of multiplications = 100x20x5 (for M2 x M3) + 10x100x5 + 10x5x80 = 19000.

3) Which of the given options provides the increasing order of asymptotic complexity of functions f1, f2, f3 and f4?

f1(n) = 2^n
f2(n) = n^(3/2)
f3(n) = nLogn
f4(n) = n^(Logn)
A) f3, f2, f4, f1
B) f3, f2, f1, f4
C) f2, f3, f1, f4
D) f2, f3, f4, f1
Answer (A)

4) We are given a set of n distinct elements and an unlabeled binary tree with n nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree?

A) 0
B) 1
C) n!
D) (1/(n+1)).2nCn
Answer (B)
See this explanation from PeddaBoku.
5) An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array A[0 :n-1] is given below.
Let Li denote the length of the longest monotonically increasing sequence starting at index i in the array



Which of the following statements is TRUE?

(A) The algorithm uses dynamic programming paradigm
(B) The algorithm has a linear complexity and uses branch and bound paradigm
(C) The algorithm has a non-linear polynomial complexity and uses branch and bound paradigm
(D) The algorithm uses divide and conquer paradigm.
Answer: (A)

1) An undirected graph G(V, E) contains n ( n > 2 ) nodes named v1 , v2 ,….vn. Two nodes vi , vj are connected if and only if 0 < |i – j| <= 2. Each edge (vi, vj ) is assigned a weight i + j. A sample graph with n = 4 is shown below.

What will be the cost of the minimum spanning tree (MST) of such a graph with n nodes?
(A) 1/12(11n^2 – 5n)
(B) n^2 – n + 1
(C) 6n – 11
(D) 2n + 1
Answer: (B)
Minimum spanning tree for 2 nodes would be
 (v1) _ (v2) 
Total weight 3
Minimum spanning tree for 3 nodes would be
 (v1) _ (v2) 
    |
 (v3)
Total weight= 3 + 4 = 7
Minimum spanning tree for 4 nodes would be
 (v1) _ (v2) _ (v4) 
    |
 (v3)
Total weight= 3 + 4 + 6 = 13
Minimum spanning tree for 5 nodes would be
 (v1) _ (v2) _ (v4) 
    |
 (v3)
    |
 (v5)
Total weight= 3 + 4 + 6 + 8 = 21
Minimum spanning tree for 6 nodes would be
 (v1) _ (v2) _ (v4) _ (v6)
    |
 (v3)
    |
 (v5)
Total weight= 3 + 4 + 6 + 8 + 10 = 31
We can observe from above examples that when we add kth node, the weight of spanning tree increases by 2k-2. Let T(n) be the weight of minimum spanning tree. T(n) can be written as
T(n) = T(n-1) + (2n-2) for n > 2
T(1) = 0, T(2) = 0 and T(2) = 3
The recurrence can be written as sum of series (2n – 2) + (2n-4) + (2n-6) + (2n-8) + …. 3 and solution of this recurrence is n^2 – n + 1.

2) The length of the path from v5 to v6 in the MST of previous question with n = 10 is

(A) 11
(B) 25
(C) 31
(D) 41
Answer: (C)
Any MST which has more than 5 nodes will have the same distance between v5 and v6 as the basic structure of all MSTs (with more than 5 nodes) would be following.
 (v1) _ (v2) _ (v4) _  (v6) _ .  . (more even numbered nodes)
    |
 (v3)
    |
 (v5)
    |
    .
    .
(more odd numbered nodes)
Distance between v5 and v6 = 3 + 4 + 6 + 8 + 10 = 31
3) Consider two binary operators '\uparrow ' and '\downarrow' with the precedence of operator \downarrow being lower than that of the \uparrow operator. Operator \uparrow is right associative while operator \downarrow is left associative. Which one of the following represents the parse tree for expression (7 \downarrow 3 ­\uparrow 4 ­\uparrow 3 \downarrow 2)?

Answer: (B)
Let us consider the given expression (7 \downarrow 3 \uparrow 4 \uparrow 3 \downarrow 2).
Since the precedence of \uparrow is higher, the sub-expression (3 \uparrow 4 \uparrow 3) will be evaluated first. In this sub-expression, 4 \uparrow 3 would be evaluated first because \uparrow is right to left associative. So the expression is evaluated as ((7 \downarrow (3 \uparrow (4 \uparrow 3))) \downarrow 2). Also, note that among the two \downarrow operators, first one is evaluated before the second one because the associativity of \downarrow is left to right.

1) Let w(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. which of the following is ALWAYS TRUE?
(A) A(n) = \Omega(W(n))
(B) A(n) = \Theta(W(n))
(C) A(n) = O(W(n))
(D) A(n) = o(W(n))
Answer (C)
The worst case time complexity is always greater than or same as the average case time complexity.


2) The worst case running time to search for an element in a balanced in a binary search tree with n2^n elements is
(A) \Theta(n log n)
(B) \Theta (n2^n)
(C) \Theta (n)
(D) \Theta (log n)
Answer (C)
Time taken to search an element is \Theta (h) where h is the height of Binary Search Tree (BST). The growth of height of a balanced BST is logerthimic in terms of number of nodes. So the worst case time to search an element would be \Theta (Log(n*2^n)) which is \Theta (Log(n) + Log(2^n)) Which is \Theta (Log(n) + n) which can be written as \Theta (n) .


3) Assuming P != NP, which of the following is true ?
(A) NP-complete = NP
(B) NP-complete \cap P = \Phi
(C) NP-hard = NP
(D) P = NP-complete
Answer (B)
The answer is B (no NP-Complete problem can be solved in polynomial time). Because, if one NP-Complete problem can be solved in polynomial time, then all NP problems can solved in polynomial time. If that is the case, then NP and P set become same which contradicts the given condition.


4) The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudocode below is invoked as height (root) to compute the height of a binary tree rooted at the tree pointer root.

The appropriate expression for the two boxes B1 and B2 are
(A) B1 : (1 + height(n->right)), B2 : (1 + max(h1,h2))
(B) B1 : (height(n->right)), B2 : (1 + max(h1,h2))
(C) B1 : height(n->right), B2 : max(h1,h2)
(D) B1 : (1 + height(n->right)), B2 : max(h1,h2)
Answer (A)
The box B1 gets exected when left subtree of n is NULL and right sbtree is not NULL. In this case, height of n will be height of right subtree plus one.
The box B2 gets executed when both left and right sbtrees of n are not NULL. In this case, height of n will be max of heights of left and right sbtrees of n plus 1.


5) A list of n string, each of length n, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is
(A) O (n log n
(B) O (n^2 log n)
(C) O (n^2 + log n)
(D) O (n^2)
Answer (B)
The recurrence tree for merge sort will have height n. And O(n^2) work will be done at each level of the recurrence tree (Each level involves n comparisons and a comparison takes O(n) time in worst case). So time complexity of this Merge Sort will be O (n^2 log n) .

1) The recurrence relation capturing the optimal time of the Tower of Hanoi problem with n discs is
(A) T(n) = 2T(n – 2) + 2
(B) T(n) = 2T(n – 1) + n
(C) T(n) = 2T(n/2) + 1
(D) T(n) = 2T(n – 1) + 1
Answer (D)
Following are the steps to follow to solve Tower of Hanoi problem recursively.
Let the three pegs be A, B and C. The goal is to move n pegs from A to C.
To move n discs from peg A to peg C:
    move n-1 discs from A to B. This leaves disc n alone on peg A
    move disc n from A to C
    move n?1 discs from B to C so they sit on disc n
The recurrence function T(n) for time complexity of the above recursive solution can be written as following.
T(n) = 2T(n-1) + 1
2) Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices S and T. Which one will be reported by Dijstra?s shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex v is updated only when a strictly shorter path to v is discovered.


(A) SDT
(B) SBDT
(C) SACDT
(D) SACET
Answer (D)
3) Suppose a circular queue of capacity (n – 1) elements is implemented with an array of n elements. Assume that the insertion and deletion operation are carried out using REAR and FRONT as array index variables, respectively. Initially, REAR = FRONT = 0. The conditions to detect queue full and queue empty are
(A) Full: (REAR+1) mod n == FRONT, empty: REAR == FRONT
(B) Full: (REAR+1) mod n == FRONT, empty: (FRONT+1) mod n == REAR
(C) Full: REAR == FRONT, empty: (REAR+1) mod n == FRONT
(D) Full: (FRONT+1) mod n == REAR, empty: REAR == FRONT
Answer (A)

1) Which of the following statements is/are TRUE for an undirected graph?
P: Number of odd degree vertices is even
Q: Sum of degrees of all vertices is even

A) P Only
B) Q Only
C) Both P and Q
D) Neither P nor Q
Answer (C)
Q is true: Since the graph is undirected, every edge increases the sum of degrees by 2.
P is true: If we consider sum of degrees and subtract all even degrees, we get an even number (because Q is true). So total number of odd degree vertices must be even.


2) Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is 1/2. What is the expected number of unordered cycles of length three?
(A) 1/8
(B) 1
(C) 7
(D) 8
Answer (C)
A cycle of length 3 can be formed with 3 vertices. There can be total 8C3 ways to pick 3 vertices from 8. The probability that there is an edge between two vertices is 1/2. So expected number of unordered cycles of length 3 = (8C3)*(1/2)^3 = 7


3) What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?
(A) \Theta(n^2)
(B) \Theta(n^2 Logn)
(C) \Theta(n^3)
(D) \Theta(n^3 Logn)
Answer (C).
Time complexity of Bellman-Ford algorithm is \Theta(VE) where V is number of vertices and E is number edges (See this). If the graph is complete, the value of E becomes \Theta(V^2). So overall time complexity becomes \Theta(V^3)


4) Which of the following statements are TRUE?
(1) The problem of determining whether there exists a cycle in an undirected graph is in P.
(2) The problem of determining whether there exists a cycle in an undirected graph is in NP.
(3) If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A.

(A) 1,2 and 3
(B) 1 and 2 only
(C) 2 and 3 only
(D) 1 and 3 only
Answer (A)
1 is true because cycle detection can be done in polynomial time using DFS (See this).
2 is true because P is a subset of NP.
3 is true because NP complete is also a subset of NP and NP means Non-deterministic Polynomial time solution exists. (See this)


5) Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of n nodes?
(A) O(1)
(B) O(log n)
(C) O(n)
(D) O(n log n)
Answer (C)
The worst case occurs for a skewed tree. In a skewed tree, when a new node is inserted as a child of bottommost node, the time for insertion requires traversal of all node. For example, consider the following tree and the case when something smaller than 70 is inserted.
             100
            /
           90
          /
        80
       /
     70   


6) Which one of the following is the tightest upper bound that represents the number of swaps required to sort n numbers using selection sort?
(A) O(log n)
(B) O(n)
(C) O(n log n)
(D) O(n^2)
Answer (B)
Selection sort requires only O(n) swaps. See this for details.


7) Consider the following operation along with Enqueue and Dequeue operations on
queues, where k is a global parameter

MultiDequeue(Q){
   m = k
   while (Q is not empty and m  > 0) {
      Dequeue(Q)
      m = m - 1
   }
}
What is the worst case time complexity of a sequence of n MultiDequeue() operations on an initially empty queue?
(A) \Theta(n)
(B) \Theta(n + k)
(C) \Theta(nk)
(D) \Theta(n^2)
Answer (A)
Since the queue is empty initially, the condition of while loop never becomes true. So the time complexity is


\Theta(n)

1) What is the return value of f(p, p) if the value of p is initialized to 5 before the call? Note that the first parameter is passed by reference, whereas the second parameter is passed by value.
int f(int &x, int c) {
   c  = c - 1;
   if (c == 0) return 1;
   x = x + 1;
   return f(x, c) * x;
} 
(A) 3024
(B) 6561
(C) 55440
(D) 161051
Answer (B)
Since c is passed by value and x is passed by reference, all functions will have same copy of x, but different copies of c.
f(5, 5) = f(x, 4)*x = f(x, 3)*x*x = f(x, 2)*x*x*x = f(x, 1)*x*x*x*x = 1*x*x*x*x = x^4
Since x is incremented in every function call, it becomes 9 after f(x, 2) call. So the value of expression x^4 becomes 9^4 which is 6561.
#include <stdio.h>

int f(int &x, int c)
{
    c  = c - 1;
    if (c == 0) return 1;
    x = x + 1;
    return f(x, c) * x;
}
int main()
{
    int p = 5;
    printf("%d", f(p, p));
}


1) 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 postorder 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
Ans (D)
The following is the constructed tree
            30
         /      \
        20       39 
       /  \     /  \
     10    25  35  42  
      \   /
      15 23


3) Consider the following function
 int unknown(int n) {
    int i, j, k = 0;
    for (i  = n/2; i <= n; i++)
        for (j = 2; j <= n; j = j * 2)
            k = k + n/2;
    return k;
 }
What is the returned value of the above function?
(A) \Theta(n^2)
(B) \Theta(n^2Logn)
(C) \Theta(n^3)
(D) \Theta(n^3Logn)
Answer (B)
The outer loop runs n/2 or \Theta(n) times. The inner loop runs \Theta(Logn) times (Note that j is divide by 2 in every iteration). So the statement "k = k + n/2;" runs \Theta(nLogn) times. The statement increases value of k by n/2. So the value of k becomes n/2*\Theta(nLogn) which is \Theta(n^2Logn)


4) The number of elements that can be sorted in \Theta(logn) time using heap sort is
(A) \Theta(1)
(B) \Theta(\sqrt{logn})
(C) \Theta(Log n/(Log Log n))
(d) \Theta(Log n)
Answer (C)
Time complexity of Heap Sort is \Theta(mLogm) for m input elements. For m = \Theta(Log n/(Log Log n)), the value of \Theta(m * Logm) will be \Theta( [Log n/(Log Log n)] * [Log (Log n/(Log Log n))] ) which will be \Theta( [Log n/(Log Log n)] * [ Log Log n - Log Log Log n] ) which is \Theta(Log n)


5) The procedure given below is required to find and replace certain characters inside an input character string supplied in array A. The characters to be replaced are supplied in array oldc, while their respective replacement characters are supplied in array newc. Array A has a fixed length of five characters, while arrays oldc and newc contain three characters each. However, the procedure is flawed
void find_and_replace(char *A, char *oldc, char *newc) {
    for (int i = 0; i < 5; i++)
       for (int j = 0; j < 3; j++)
           if (A[i] == oldc[j]) A[i] = newc[j];
}
The procedure is tested with the following four test cases
(1) oldc = "abc", newc = "dab"
(2) oldc = "cde", newc = "bcd"
(3) oldc = "bca", newc = "cda"
(4) oldc = "abc", newc = "bac"
The tester now tests the program on all input strings of length five consisting of characters ‘a’, ‘b’, ‘c’, ‘d’ and ‘e’ with duplicates allowed. If the tester carries out this testing with the four test cases given above, how many test cases will be able to capture the flaw?

(A) Only one
(B) Only two
(C) Only three
(D) All four
Answer (B)
The test cases 3 and 4 are the only cases that capture the flaw. The code doesn't work properly when an old character is replaced by a new character and the new character is again replaced by another new character. This doesn't happen in test cases (1) and (2), it happens only in cases (3) and (4).
6) If array A is made to hold the string “abcde”, which of the above four test cases will be successful in exposing the flaw in this procedure?
(A) None
(B) 2 only
(C) 3 and 4 only
(D) 4 only
Answer (C)
#include <stdio.h>
#include <string.h>

void find_and_replace(char *A, char *oldc, char *newc) {
    for (int i = 0; i < 5; i++)
       for (int j = 0; j < 3; j++)
           if (A[i] == oldc[j]) A[i] = newc[j];
}

int main()
{
    char *oldc1 = "abc", *newc1 = "dab";
    char *oldc2 = "cde", *newc2 = "bcd";
    char *oldc3 = "bca", *newc3 = "cda";
    char *oldc4 = "abc", *newc4 = "bac";

    char test[] =  "abcde";

    printf("Test 2\n");
    printf("%s\n", test);
    find_and_replace(test, oldc2, newc2);
    printf ("%s\n", test);

    printf("\nTest 3\n");
    strcpy(test, "abcde");
    printf("%s\n", test);
    find_and_replace(test, oldc3, newc3);
    printf ("%s\n", test);

    printf("\nTest 4\n");
    strcpy(test, "abcde");
    printf("%s\n", test);
    find_and_replace(test, oldc4, newc4);
    printf ("%s\n", test);
}
Output:
Test 2
abcde
abbcd

Test 3
abcde
addde

Test 4
abcde
aacde
 
 
(courtesy : www.geekforgeeks.com)