21. Which of the following is true for computation time in insertion, deletion and finding maximum and minimum element in a sorted array?
(1) Insertion-O(1), Deletion-O(1), Maximum-O(1), Minimum-O(1)
(2) Insertion-O(1), Deletion-O(1), Maximum-O(n), Minimum-O(n)
(3) Insertion-O(n), Deletion-O(n), Maximum-O(1), Minimum-O(1)
(4) Insertion-O(n), Deletion-O(n), Maximum-O(n), Minimum-O(n)
22. The seven elements A, B, C, D, E, F and G are pushed onto a stack in reverse order, i.e., starting from G. The stack is popped five times and each element is inserted into a queue. Two elements are deleted from the queue and pushed back onto the stack. Now, one element is popped from the stack. The popped item is ……………….
23. Which of the following is a valid heap?
24. If h is chosen from a universal collection of hash functions and is used to hash n keys into a table of size m, where n≤m, the expected number of collisions involving a particular key x is less than ……………….
25. Which of the following statements is false?
(A) Optimal binary search tree construction can be performed efficiently using dynamic programming.
(B) Breadth-first search cannot be used to find connected components of a graph.
(C) Given the prefix and postfix walks of a binary tree, the tree cannot be re-constructed uniquely.
(D) Depth-first-search can be used to find the components of a graph.
26. Match the following Layers and Protocols for a user browsing with SSL:
a. Application of layer i. TCP
b. Transport layer ii. IP
c. Network layer iii. PPP
d. Datalink layer iv. HTTP
a b c d
(1) iv i ii iii
(2) iii ii i iv
(3) ii iii iv i
(4) iii i iv ii
27. The maximum size of the data that the application layer can pass on to the TCP layer below is ………
(1) 216 bytes
(2) 216 bytes + TCP header length
(3) 216 bytes – TCP header length
(4) 215 bytes
28. A packet whose destination is outside the local TCP/IP network segment is sent to …………..
(1) File server
(2) DNS server
(3) DHCP server
(4) Default gateway
29. Distance vector routing algorithm is a dynamic routing algorithm. The routing tables in distance vector routing algorithm are updated ………..
(2) by server
(3) by exchanging information with neighbour nodes.
(4) with back up database
30. In link state routing algorithm after construction of link state packets, new routes are computed using:
(1) DES algorithm
(2) Dijkstra’s algorithm
(3) RSA algorithm
31. Which of the following strings would match the regular expression: p+[3-5]*[xyz]?
(1) I, III and Vl only
(2) IV, V and VI only
(3) II, IV and V only
(4) I, IV and V only
32. Consider the following assembly language instructions:
mov al, 15
mov ah, 15
xor al, al
mov cl, 3
shr ax, cl
add al, 90H
adc ah, 0
What is the value in ax register after execution of above instructions?
33. Consider the following statements related to compiler construction:
I. Lexical Analysis is specified by context-free grammars and implemented by pushdown automata.
II. Syntax Analysis is specified by regular expressions and implemented by finite-state machine.
Which of the above statement(s) is/are correct?
(1) Only l
(2) Only ll
(3) Both I and II
(4) Neither I nor Il
34. The contents of Register (BL) and Register (AL) of 8085 microprocessor are 49H and 3AH respectively. The contents of AL, the status of carry flag (CF) and sign flag (SF) after executing ‘SUB AL, BL’ assembly language instruction, are
(1) AL=0FH; CF=1; SF=1
(2) AL=F0H; CF=0; SF=0
(3) AL=F1H; CF=1; SF=1
(4) AL=1FH; CF=1; SF=1
35. Which of the following statement(s) regarding a linker software is/are true?
I. A function of a linker is to combine several object modules into a single load module.
II. A function of a linker is to replace absolute references in an object module by symbolic references to locations in other modules.
(1) Only I
(2) Only II
(3) Both I and II
(4) Neither I nor Il
36. There are three processes P1, P2 and P3 sharing a semaphore for synchronizing a variable. Initial value of semaphore is one. Assume that negative value of semaphore tells us how many processes are waiting in queue. Processes access the semaphore in following order:
(a) P2 needs to access
(b) P1 needs to access
(c) P3 needs to access
(d) P2 exits critical section
(e) Pi exits critical section
The final value of semaphore will be:
37. In a paging system, it takes 30 ns to search translation Look-aside Buffer (TLB) and 90 ns to access the main memory. If the TLB hit ratio is 70%, the effective memory access time is:
(1) 48 ns
(2) 147 ns
(3) 120 ns
(4) 84 ns
38. Match the following w.r.t. Input/Output management:
a. Device controller i. Extracts information from the controller register and store it in data buffer
b. Device driver ii. I/O scheduling
c. Interrupt handler iii. Performs data transfer
d. Kernel I/O subsystem iv. Processing of I/O request
a b c d
(1) iii iv i ii
(2) ii i iv iii
(3) iv i ii iii
(4) i iii iv ii
39. Which of the following scheduling algorithms may cause starvation?
b. Round Robin
d. Shortest process next
e. Shortest remaining time first
(1) a, c and e
(2) c, d and e
(3) b, d and e
(4) b, c and d
40. Distributed operating systems consist of:
(1) Loosely coupled O.S. software on a loosely coupled hardware
(2) Loosely coupled O.S. software on a tightly coupled hardware
(3) Tightly coupled O.S. software on a loosely coupled hardware
(4) Tightly coupled O.S. software on a tightly coupled hardware