F Pages: 6

1100CST308052302

Reg No.:_______________ Name:__________________________

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
B.Tech Degree S6 (R, S) / S6 (PT) (R) Examination June 2023 (2019 Scheme)

Course Code: CST 308

Course name: COMPREHENSIVE COURSE WORK
Max. Marks: 50 Duration: 1Hour

Instructions: (1) Each question carries one mark. No negative marks for wrong answers
(2) Total number of questions: 50
(3) All questions are to be answered. Each question will be followed by 4 possible answers of
which only ONE is correct.
(4) If more than one option is chosen, it will not be considered for valuation.

1. The worst case complexity of quick sort is ..............

a) O(n) b) O(log n) c) O(n2 ) d) O(n log n)
2. What is the output of following function for start pointing to first node of following linked
list? 1->2->3->4->5->6
void fun(struct node* start)
{
if(start == NULL)
return;
printf("%d ", start->data);
if(start->next != NULL )
fun(start->next->next);
printf("%d ", start->data);
}

a) 1 4 6 6 4 1 b) 1 3 5 1 3 5 c) 1 2 3 5 d) 1 3 5 5 3 1
3. The prefix form of A-B/ (C * D ⋀ E) is?
a) -/*⋀ACBDE b) -ABCD*⋀DE c) -A/B*C⋀DE d) -A/BC*⋀DE
4. Suppose we are sorting an array of eight integers using quicksort, and we have just finished
the first partitioning with the array looking like this:
2 5 1 7 9 12 11 10
Which statement is correct?
a) The pivot could b) The pivot could c) The pivot is d) Neither the 7
be either the 7 be the 7, but it is not the 7, but nor the 9 is the
or the 9. not the 9 it could be pivot.
the 9
5. In a complete k-ary tree, every internal node has exactly k children or no child. The

Page 1 of 6
 1100CST308052302

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)
6. If a node in a Binary search tree has two children, then its inorder predecessor has .........
a) No child b) No left child c) No right d) Two children
child
7. Using Bubble sort, the number of interchanges required to sort 5, 1, 6, 2 and 4 in ascending
order is...........
a) 7 b) 5 c) 8 d) 6
8. Which one of the following is a sequence container?
a) stack b) dequeue c) queue d) set
9. Minimum number of queues needed to implement the priority queue is ...........
a) 1 b) 2 c) 3 d) 4
10. The data structure used in breadth first search algorithm is ...........
a) queue b) stack c) heap d) hash table
11 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
12 Which of the following are NOT shared by the threads of the same process?
a) Stack
b) Registers
c) Address space
d) Message queue
a) a and d b) b and c c) a and b d) a, b and c
13 The problem of indefinite blockage of low priority jobs in general priority scheduling
algorithm can be solved using
a) Swapping b) Dirty Bit c) Aging d) Compaction
14 Which of the following are the advantage of Multiprogramming?
a) High and b) CPU scheduling is c) memory d) All of the above
efficient CPU not required management
utilization is good
15 A memory management system has 64 pages with 512 bytes page size. Physical memory
consists of 32 page frames Number of bits required in logical and physical address are
respectively:
a) 14 and 15 b) 14 and 29 c) 15 and 14 d) 16 and 32
16 Consider the reference string:
012301401234
If FIFO page replacement algorithm is used, then the number of page faults
with three page frames and four page frames are ____ and ___ respectively.
a) 10, 9 b) 9, 9 c) 10, 10 d) 9, 10
17 Consider a disk queue with I/O requests on the following cylinders in their arriving order:
6,10,12,54,97,73,128,15,44,110,34,45. The disk head is assumed to be at cylinder 23 and
moving in the direction of decreasing number of cylinders. Total number of cylinders in the
Page 2 of 6
 1100CST308052302

disk is 150. The disk head movement using SCAN –scheduling algorithm is:
a) 172 b) 173 c) 151 d) 161
18 At a particular time of computation, the value of a counting semaphore is 10. Then 12 P
operations and "x" V operations were performed on this semaphore. If the final value of
semaphore is 7, x will be
a) 8 b) 9 c) 10 d) 11
19 In the ..... algorithm, the disk head moves from one end to the other, servicing requests
along the way. When the head reaches the other end, it immediately returns to the
beginning of the disk without servicing any requests on the return trip.
a) LOOK b) SCAN c) C-SCAN d) C-LOOK
20 Paging suffers from .............. fragmentation
a) External b) Internal c) Physical d) All of the abve
21 The main virtue for using single Bus structure is ____________
a) Fast data b) Cost effective c) Cost d) None of the
transfers connectivity and effective mentioned
speed connectivity
and ease of
attaching
peripheral
devices
22 Memory Buffer Register (MBR) is connected to ___.
a) Control Bus b) Address Bus c) Data Bus d) System Bus
23 The basic component of arithmetic circuit is________.
a) parallel b) parallel adder. c) half adder. d) full adder.
subtractor.
24 When we use auto increment or auto decrements, which of the following is/are true?
1) In both, the address is used to retrieve the operand and then the address gets altered
2) In auto increment, the operand is retrieved first and then the address altered
3) Both of them can be used on general purpose registers as well as memory locations
a) 1, 2, 3 b) 2 c) 1, 3 d) 2, 3
25 When we perform subtraction on -7 and -5 the answer in 2’s complement form is ....
a) 11110 b) 1110 c) 1010 d) 0010
26 The instruction -> Add LOCA, R0 does _______
a) Adds the value b) Adds the value of c) Adds the d) Adds the value
of LOCA to R0 R0 to the address values of of LOCA with a
and stores in the of LOCA both LOCA value in
temp register and R0 and accumulator and
stores it in stores it in R0
R0
27 Suppose, after analyzing a new cache design, you discover that the cache has far too many
conflict misses, and this needs to be resolved. You know that you must increase
associativity in order to decrease the number of cache misses. What are the implications of
increasing associativity?

Page 3 of 6
 1100CST308052302

a) Slower cache b) Increase index c) Increase d) All of these

access time bits block size
28 In a k-way set associative cache, the cache is divided into v sets, each of which consists of
k lines. The lines of a set are placed in sequence one after another. The lines in set s are
sequenced before the lines in set (s+1). The main memory blocks are numbered 0 onwards.
The main memory block numbered j must be mapped to any one of the cache lines from.
AA
a) (j mod v) * k to (j mod v) * k + (k-1)
b) (j mod v) to (j mod v) + (k-1)
c) (j mod k) to (j mod k) + (v-1)
d)
(j mod k) * v to (j mod k) * v + (v-1)

29 Highly encoded schemes that use compact codes to specify a small number of functions in
each micro instruction is ________
a) Horizontal b) Vertical c) Diagonal d) None of the
organisation organisation organisation mentioned

30 DMA interface unit eliminates the need to use CPU registers to transfers data from
a) MAR to MBR b) MBR to MAR c) I/O units to d) Memory to I/O
memory units
31 Let E1 and E2 be two entities in an E/Rdiagram with simple single-valued attributes. R1
and R2 are two relationships between E1 and E2, where R1 is one-to-many and R2 is
many-to-many. R1 and R2 do not have any attributes of their own. What is the minimum
number of tables required to represent this situation in the relational model?

a) 2 b) 3 c) 4 d) 5
32 Consider the join of a relation R with relation S. If R has m tuples and S has n tuples,then
the maximum size of join is............

a) mn b) m+n c) (m+n)/2 d) 2(m+n)

33 An index record appears for every search key value in the file
a) Dense index b) Sparse index c) Hash index d) Single-key
index
34 If a relatin is in BCNF Then it is in:
a) 2 NF b) 3 NF c) 1 NF d) 1 NF and 2 NF
35 Which of the following is a DDL command?
a) Select b) Create c) Insert d) Delete
36 The number of attributes in a relation is called its
a) cardinality b) size c) schema d) degree
37 Consider a database implemented using B+ tree for file indexing and installed on a disk
drive with block size of 4 KB. The size of search key is 12 bytes and the size of tree/disk
pointer is 8 bytes. Assume that the database has one million records. Also assume that no

Page 4 of 6
 1100CST308052302

node of the B+ tree and no records are present initially in main memory. Consider that each
record fits into one disk block. The minimum number of disk accesses required to retrieve
any record in the database is _______

a) 1 b) 2 c) 3 d) 4
38 Consider the relation R(A,B,C,D,E) and the set F={AB->CE, E->AB, C->D}.What is the
highest normal form of this relation?
a) 1 NF b) 2 NF c) 3 NF d) BCNF
39 What is the Lost Update Problem also known as?

a) W-W b) W-R c) R-R d) None

Conflict Conflict Confli
ct
40 Consider the following transactions with data items P and Q initialized to zero:

T1: read (P) ;

read (Q) ;
if P = 0 then Q : = Q + 1 ;
write (Q) ;
T2: read (Q) ;
read (P) ;
if Q = 0 then P : = P + 1 ;
write (P) ;

Any non-serial interleaving of T1 and T2 for concurrent execution leads to

a) A serializable b) A schedule that is c) A conflict d) A schedule for
schedule not conflict serializable which a
serializable schedule precedence
graph cannot be
drawn
41 The non- Kleene Star operation accepts the following string of finite length
over set A = {(0,1) | where string s contains even number of 0 and 1}

a) 01, 0011, b) 0011, 11001100 c) ε, 0011, d) ε, 0011,

010101 11001100 11001100
42 Which of the following is a not a part of 5-tuple finite automata:
a) Input alphabet b) Transition c) Initial State d) Output Alphabet
function
43 Which of the following conversion is not possible (algorithmically)?
a) Regular b) Non Deterministic c) Non d) Non
grammar to FA to Deterministic Deterministic
CFG Deterministic FA PDA to TM to
Deterministic Deterministic
PDA TM
44 Regular expression for all strings starts with ab and ends with bba is...........

Page 5 of 6
 1100CST308052302

a) aba^*b^*bba
b) ab(ab)^*bba
c) ab(a+b)^*bba
d) All of the mentioned
45 Pumping lemma is generally used for proving that
a) Given grammar b) Given grammar is c) Whether two d) None of these
is regular not regular given regular
expressions
are
equivalent or
not
46 ∗
Consider the regular language L= (111+11111) . The minimum number of states in any
DFA accepting this language is ...................
a) 3 b) 5 c) 8 d) 9
47 Suppose a regular language L is closed under the operation halving, then the result would
be ...................
a) 1/4 L will be b) 1/2 L will be c) 1/8 L will be d) All of the
regular regular regular mentioned
48 Which among the following cannot be accepted by a regular grammar?
a) L is a set of b) L is a set of binary c) L is a set of d) L is a set of
numbers complement string with 0n1 n
divisible by 2 odd number
of 0
49 If L1 and L2 are context free languages, which of the following is context free?
a) L1* b) L2UL1 c) L1.L2 d) All of the
mentioned
50 Consider a grammar with the following productions
S--> aab | bac | aB
S --> aS |
S --> abb | ab
S a --> bdb
The above grammar is
a) Context free b) Regular c) Context d) Type 0
sensitive
*****

Page 6 of 6