Computer Science

Operating System • Main functions of operating systems: Processes, threads, interprocess

communication. • Concurrency, synchronization, deadlock, CPU scheduling, I/O scheduling,
resource scheduling. • Deadlock and scheduling algorithms, Banker’s algorithm for deadlock
handling. • Memory management, virtual memory. • File systems, I/O systems. • Operating
systems: DOS, UNIX, and Windows.

Data Structures • Arrays and their applications. • Sparse matrices, stacks, queues, priority queues,
linked lists. • Trees: Forests, binary trees, threaded binary trees, binary search trees, AVL trees, B
Syllabus
trees, B+ trees, B* trees. • Data structure for sets, graphs. • Sorting and searching algorithms,
hashing. • Functions, recursion, parameter passing. • Definition of data structures.

Digital Fundamentals • Data Types • Number Systems and Conversion • Complements • Fixed Point
Representation • Floating Point Representation • Error Detection Codes Computer Arithmetic •
Addition • Subtraction • Multiplication • Division Algorithms Digital Computers • Logic Gates •
Boolean Algebra • Map Simplifications • Combinational Circuits Sequential Circuits • Flip-Flops •
Integrated Circuits Other Components • Decoders • Multiplexers • Registers and Counters •
Memory Unit

Consider implementation of database. Among the following options, choose the most appropriate
data struc ture for this
Q.1
(1) B+ tree (2) Linked list (3) Queue (4) Stack

Match List – I with List – II

List – I
A. Asynchronous
B. Trigger
C. J–K Flip–flop
D. D flip flop

List – II
Q.2 I. A pulse that cause a logic device to be activated or change state
II. The operation is not executed in step with the clock
III. Flip flop and atleast set, reset toggle and hold modes of operation
IV. Flip flop with atleast set and rest modes of operations.

Choose the correct answer from the options given below:

(1) [(A – I); (B – II); (C – III); (D – IV)] (3) [(A – III); (B – IV); (C – II); (D – I)]
(2) [(A – II); (B – I); (C – III); (D – IV)] (4) [(A – I); (B – II); (C – IV); (D – III)]

Consider a system with 1K pages and 512 frames and each page is of size 2 KB. How many bits are
required to represent the virtual address space memory:
Q.3
(1) 20 bits (2) 21 bits (3) 11 bits (4) 16 bit

Each node is having a successor node in ________________:

(1) Singly linked list (2) Singly Circular Linked list
Q.4
(3) Double Linked list (4) Not possible in any linked list
How does the number of page frames affect and number of page faults for a given memory access
pattern in FIFO page replacement algorithm?
(1) Increasing the number of page frames decreases the number of page faults.
(2) Increasing the number of page frames may increase or decrease the number of page faults
Q.5
depending on the memory access pattern.
(3) Increasing the number of page frames always increases the number of page faults.
(4) Increasing the number of page frames has no effect on the number of page faults.

Arrange the following in increasing order of their per unit cost.

(A) DRAM (B) Magnetic disk (C) Optical disk (D) SRAM (E) Magnetic tape
Q.6 Choose the correct answer from the options given below:
(1) E, C, B, A, D (2) E, C, B, D, A (3) C, B, E, D, A (4) C, B, D, E, A

Match List – I with List – II

List – I
(A) Flash memory
(B) PMOS
(C) NMOS
(D) CMOS

List – II
Q.7 (I) Oldest and Slowest
(II) Used in large scale integration (LSI)
(III) Least power consumption
(IV) Non volatile RAM which is powered continuously

Choose the correct answer from the options given below:

(1) [(A – I); (B – IV); (C – III); (D – II)] (2) [(A – I); (B – IV); (C – II); (D – III)]
(3) [(A – IV); (B – I); (C – III); (D – II)] (4) [(A – IV); (B – I); (C – II); (D – III)]

Consider a completely skewed (left / right) binary search tree with n elements. What is the worst
case time complexity of searching an element in this tree?
Q.8
(1) O(n) (2) O(1) (3) O(lo g) (4) O(n log n)

If we want to find last node of a singly linked list then the correct coding is

(1) if (temp  link! = NULL) temp = temp  link

(2) if (temp  data = = Num) temp = temp  link
Q.9
(3) While (temp  link! = NULL) temp = temp  link
(4) While (temp  link! = data) temp = temp  link

Q.10 The function represented by the k-map given below is

k – map
C/AB 00 01 11 10
0 0 1 1 1
1 0 0 1 0
(1)BC+AB+AC' (2)BC'+AB+AC' (3)(B⊕C)' (4)A.BC

Choose the correct answer from the options given below:

(1) (A), (B) and (D) only (2) (A) and (D) only
(3) (A), (B) , (C) and (D) (4) (B) and (D) only

A logic circuit, that can odd two 1-bit numbers and produce output for sum and carry but cannot
handle carry, input, is called ____________.
Q.11
(1) Half adder (2) Full adder (3) Multiplexer (4)Encoder

On a system using simple segmentation, following is the segment table:

Segment Limit Base
0 500 1000
1 200 2000
Q.12 2 300 2500
3 100 1700
What is the physical address for the logical address 2, 212?
(1)2712 (2)512 (3)2212 (4)2800

Arrange the following in the increasing order of their asympotic complexities:

(A) Insertion sort (best case) (C) Binary Search (worst case)
(B) Bubble sort (worst case) (D) Merge sort (worst case)
Q.13
(1) A, C, B, D (2) D, A, C, B (3) A, B, C, D (4) C, A, D, B

Decreasing the RAM of a computer typically leads to which of the following outcomes?
(1) Virtual memory increases
(3) Page faults decreases
Q.14
(2) Page faults increses
(4) Segmentation faults occurs.

We can say that a schedule is conflict serializable?

(1) If a schedule T can be transformed into a serial schedule U by a series of swaps of conflicting
operations.
(2) If a schedule T can be transformed into a serial schedule U by a series of swaps of
Q.15 nonconflicting operations.
(3) If a schedule T can be transformed into a nonserial schedule U by a series of swaps of conflicting
operations.
(4) If a schedule T can be transformed into a nonserial schedule U by a series of swaps of
nonconflicting operations.
The following integers are needed to be stored in ascending order using bubble sort.
5, 8, 22, 18, 1
Following are the results of various passes during the sorting process.
Q.16
(1) 5, 1, 8, 18, 22 (2) 1, 5, 8, 18, 22 (3) 5, 8, 18, 1, 22 (4) 5, 8, 1, 18, 22

Q.17 The range of integers that can be represented by a 2’s complements number system is ________.
where is n is number of bits in number.

1. -2n-1 to 2n-1 – 1
2. –(2n-1 - 1) to (2n-1 - 1)
3. -2n-1 to 2n-2
4. –(2n-1 + 1) to (2n-1 – 1)

Given √(224)r = (13)r where r is the radix. The value of r is ______.

Q.18
(1) 10 (2) 8 (3) 5 (4) 6

What are the ways to implement a priority Queue?

(A) Arrays (B) Fibonacci tree (C) Heap Data Structure (D) Linked List

Q.19 Choose the correct answer from the options given below:
(1) (A), (B) and (D) only (3) (A), (B), (C) and (D)
(2) (B), (C) and (D) only (4) (A), (C) and (D) only

An operating system cotains 4 user processor each requiring 5 units of resource R. The minimum
number of required units of R such that no deadlock will every occur is
Q.20
(1) 20 (2) 4 (3) 17 (4) 15

The current allocation and Maximum requirement of different types of resources for four
processes are given below:
Process Max Allocation Available
R1 R2 R3 R1 R2 R3 R1 R2 R3
P1 8 6 4 1 2 1 4 4 5
P2 4 3 3 3 1 1
P3 10 1 3 4 1 3
P4 3 3 3 3 2 2

Consider the following four statements.

Q.21 (A) P2 P4 P1 P3 is a safe sequence
(B) (B) P4 P2 P1 P3 is a safe sequence
(C) (C) P4 P2 P2 P1 is a safe sequence
(D) (D) P1 P4 P2 P3 is a safe sequence

Identify correct statements from the given options.

(1) (A), (B) and (D) only
(2) (A), (B) and (C) only
(3) (B), (C) and (D) only
(4) A, (B), (C), (D)

Q.22 Match List – I with List – II

List – I (Algorithms)
A. Bellman - Ford algorithm (with adjacencylist representation)
B. Dijkstra Algorithm
C. Prim’s Algorithm
D. Topological sorting (with adjacency list representation)

List – II (Complexity)
I. O(|V|2)
II. O((V+E)logV)
III. O(nm)
IV. O(n + m)

Choose the correct answer from the options given below:

(1) [(A – III); (B – I); (C – II); (D – IV)]
(2) [(A – II); (B – IV); (C – III); (D – I)]
(3) [(A – III); (B – IV); (C – I); (D – II)]
(4) [(A – II); (B – I); (C – III); (D – IV)]
Consider the following statements
(A) RAM is a combinational circuit
(B) RAM is sequential circuit
(C) PLA is a combinational circuit
(D) PLA is a sequential circuit
Q.23
Which of the above statements are true

(1) (A) and (D) only

(2) (B) and (C) only
(3) (B) and (D) only
(4) (A) and (C) only
The idea of cache memory is based on the which of the following?
(1) Principle of locality reference.
Q.24 (2) Based on the fact that large portion of a program is referenced relatively.
(3) Principle of 10 – 90 rule
(4) Non volatile storage
Which of the following is not an applicaiton of Stack?
Q.25
(1) Tower of Hanoi (2) Recursion (3) Voter polling station(4) Parantheses Matching
How many child processes will be created by following fork() system call?
Q.26 fork(); fork(); fork(); fork();
(1) 4 (2) 16 (3) 15 (4) 3
68. Match List – I with List – II
List – I
(A) Critical Region
(B) Working Set
(C) Deadlock
(D) Wait/signal

List – II
Q.27
(I) Circular wait
(II) Condition variable
(III) Principle of locality
(IV) Mutual exclusion

Choose the correct answer from the options given below:

(1) [(A – IV); (B – III); (C – I); (D – II)] (2) [(A – IV); (B – III); (C – II); (D – I)]
(3) [(A – III); (B – IV); (C – II); (D – I)] (4) [(A – III); (B – IV); (C – I); (D – II)]
Consider the following tree. This is a / a _________________.
105
Q.28 /\
165 125
(1) AVL Search Tree (2) Binary Tree (3) Binary Search Tree (4) Fibonacci Tree
Let A’ represent complement of A. Which of the following boolean expressions is/are true?
(A) A +AB= A
(B) (A +B) '=A'B'
(C) ( A') ' =A
(D) (AB)' = A' B'
Q.29
Choose the correct answer from the options given below:
(1) (A), (B) and (D) only
(2) (A) and (D) only
(3) (A), (B) , (C) and
(D) (4) (B) and (D) only
In a computer if the page fault service time is 10 ms and average memory access time is 30 ns. If
one page fault is generated for every 106 memory accesses. What is the effective access time for
Q.30
the memory?
(1) 21 ns approximate (2) 25 ns approximate (3) 30 ns approximate (4) 40 ns approximate