F 1100CST308052301 Pages: 6

Reg No.:_______________ Name:__________________________

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
Sixth Semester B.Tech Degree Supplementary Examination May 2023 (2019 Scheme)

Course Code: CST308

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. Which data structure is used to store the undo history in a web browser?
a) Stack b) Queue c) Linked List d) Hash table

2. When a pop() operation is called on an empty queue, what is the condition called?
a) Overflow b) Underflow c) Syntax Error d) Garbage Value

3. Given a binary tree with the following elements: 50, 25, 75, 10, 30, 60, 90. Which traversal
technique will produce the following sequence? 10, 30, 25, 60, 90, 75, 50.
a) Pre-order b) In-order c) Post-order d) Level order

4. Which sorting algorithm has a time complexity of O(n log n) in the average and worst case?
a) Bubble sort b) Insertion sort c) Quick sort d) Selection sort

5. Which of the following statements about a linked list is true?

a) It has a fixed b) Elements stored c) It allows for d) It consists of nodes
size. contiguously in efficient random linked by pointers
memory access
6. Which type of linked list has its last node pointing to the first node?
a) Singly linked b) Doubly linked c) Circular linked d) Sparse linked list.
list list. list.

7. Travelling salesman problem is an example of

a) Dynamic b) Greedy c) Recursive d) Divide & Conquer
Algorithm Algorithm Approach

Page 1 of 6
 1100CST308052301

8. Time complexity of Depth First Traversal of is

a) Θ(|V|+|E|) b) Θ(|V|) c) Θ(|E|) d) Θ(|V|*|E|)

9. Visiting root node after visiting left and right sub-trees is called
a) In-order b) Pre-order c) Post- d) Level order
Traversal Traversal order Traversal
10. How is the 2nd element in an array accessed based on pointer notation?
a) *a + 2 b) *(*a + 2) c) &(a + 2) d) *(a + 2)

11 Which of the following is NOT a primary function of an operating system?

a) Memory b) Device c) File management d) Database
management management management
12 The Banker's algorithm grants resource requests if:
a) The requested b) The requested c) The requested d) All of the above
resources are resources do not resources do not
immediately exceed the exceed the total
available. maximum claim of resources
the process. available in the
system
13 The Banker's algorithm is applicable to which type of resource allocation problem?
a) Preemptive b) Non-preemptive c) Dynamic d) Distributed resource
resource resource resource allocation.
allocation. allocation. allocation.
14 The Dining Philosophers problem can lead to a deadlock if:
a) All the b) All the c) All the d) All the philosophers
philosophers pick philosophers pick philosophers try are hungry at the
up their left up their right to pick up both same time.
chopstick first. chopstick first. chopsticks
simultaneously.
15 In the Dining Philosophers problem, the maximum number of philosophers who can eat simultaneously
without deadlock is:
Answer: d) N-1, where N is the total number of philosophers.
a) 1 b) 2 c) 3 d) N-1, where N is the
total number of
philosophers.

16 Which memory management technique allows for efficient utilization of memory by allocating memory
in variable-sized blocks?
a) Paging b) Segmentation c) Swapping d) Fragmentation

17 A deadlock in an operating system occurs when:

a) A process is b) ) A process gets c) A process d) A process encounters
unable to access stuck in an infinite exceeds its an error during
a required loop. allocated execution.
resource memory limit.
indefinitely.

Page 2 of 6
 1100CST308052301

18 Consider a system with four processes: P1, P2, P3, and P4. The arrival times and burst times for each
process are given in the table below:
Process Arrival Time Burst Time
P1 0 4
P2 2 6
P3 4 8
P4 6 2
Assuming the scheduling algorithm is First-Come, First-Served (FCFS), what is the average waiting time
for these processes?
a) 6.5 b) 8.25 c) 9.75 d) 10.5
19 Consider a system with three resource types (A, B, and C) and four processes (P1, P2, P3, and P4). The
maximum resource allocation needs for each process are as follows:
Process Max Allocation (A, B, C)
P1 3, 1, 2
P2 2, 2, 3
P3 1, 3, 1
P4 4, 2, 1
The current resource allocation and the maximum available resources in the system are as follows:
Process Allocation (A, B, C) Available (A, B, C)
P1 1, 1, 0 2, 1, 1
P2 1, 0, 2
P3 1, 2, 1
P4 0, 1, 1
Using the Banker's algorithm, is the system in a safe safe?
a) Yes b) No c) Cannot d) None of these
Determine
20 Consider a system with five processes: P1, P2, P3, P4, and P5. The burst times for each process are given
in the table below:
Process Burst Time
P1 8
P2 4
P3 9
P4 5
P5 2
Assuming the scheduling algorithm is Round Robin with a time quantum of 3, what is the turnaround
time for process P3?
a) 10 b) 11 c) 12 d) 13
21 A processor has an instruction cache with a hit rate of 90% and an access time of 1 ns. If the cache miss
penalty is 20 ns, what is the average memory access time?
a) 1.1 ns b) 2 ns c) 2.2 ns d) 3 ns

22 A computer system uses a direct-mapped cache with a cache size of 8 KB and a block size of 32 bytes.
How many bits are needed for the cache index?
a) 5 bits b) 7 bits c) 9 bits d) 11 bits
23 Which memory type is the closest to the CPU and provides fast access to frequently used data?
a) Cache memory b) Main memory c) Virtual memory d) Secondary memory
(RAM) (Hard Disk)

Page 3 of 6
 1100CST308052301

24 Which addressing mode uses a base register plus an offset to calculate the memory address?
a) Immediate b) Direct addressing c) Indirect d) Indexed addressing
addressing mode mode addressing mode mode
25 A computer system uses a 32-bit virtual address and a 4 KB page size. How many entries are there in the
page table?
a) 256 entries b) 512 entries c) 1024 entries d) 2048 entries

26 In a pipelined processor, which hazard occurs when the current instruction depends on the result of a
previous instruction that has not yet completed?
a) Data hazard b) Control hazard c) Structural hazard d) Pipeline hazard
27 Which cache mapping technique provides the fastest access time but has limited capacity?
a) Direct mapping b) Associative c) Set-associative d) Fully associative
mapping mapping mapping
28 Which technique is used to reduce the effect of memory latency in a pipelined processor?
a) Branch b) Instruction-level c) Out-of-order d) Loop unrolling
prediction parallelism execution
29 Which technique is used to minimize the impact of control hazards in a pipelined processor?
a) Branch b) Data forwarding c) Loop unrolling d) Out-of-order
prediction execution
30 Example of immediate addressing mode is:
a) MOV A, B b) ADD A, [B] c) SUB A, #10 d) JMP LABEL
31 Which of the following is NOT a component of a formal language?
a) Alphabet b) Syntax c) Semantics d) Compiler
32 Which type of automaton recognizes regular languages?
a) Pushdown b) Finite automaton c) Turing machine d) Linear-bounded
automaton (PDA) (FA) (TM) automaton (LBA)

33 The Chomsky hierarchy classifies formal languages into how many levels?
a) 2 b) 3 c) 4 d) 5
34 Which type of automaton has both a finite control unit and an unbounded tape?
a) Finite automaton b) Pushdown c) Turing machine d) Mealy machine
(FA) automaton (PDA) (TM)

35 The language accepted by a Turing machine with a halting state is known as:
a) Regular language b) Context-free c) Context-sensitive d) Recursive
language language enumerable language

36 Which of the following is a non-deterministic automaton?

a) Finite automaton b) Pushdown c) Turing machine d) Mealy machine
(FA) automaton (PDA) (TM)

Page 4 of 6
 1100CST308052301

37 Which of the following is true about regular languages?

a) They can be b) They can be c) They can be d) They can be
recognized by a recognized by a recognized by a recognized by a finite
Turing machine. pushdown linear-bounded automaton.
automaton. automaton

38 The Chomsky normal form (CNF) is a way to represent a context-free grammar (CFG) where:

a) All the b) The start symbol is c) There are no ε- d) All the production
production rules on the left-hand productions in rules have at most
are in the form A side of the the grammar two non-terminals on
-> Ab. production rules. the right-hand side

39 Which of the following is a regular expression for the language of all strings over {a, b} that contain at
least one “a”?
a) ab b) (ab)* c) (a+b)* d) (a+b)a(a+b)
40 Which type of automaton is used in lexical analysis for tokenizing source code?
a) Finite automaton b) Pushdown c) Turing machine ™ d) Linear-bounded
(FA) automaton (PDA) automaton (LBA)

41 Typically, a database administrator (DBA) is responsible for:

a) Schema b) Schema c) Granting of d) All of the above
definition modification authorization for
data access

42 Which of the following queries will retrieve students whose name has ‘p’ as the second letter ?
a) SELECT rollNo b) SELECT rollNo c) SELECT rollNo d) SELECT rollNo FROM
FROM student FROM student FROM student student
where name = where name LIKE where name LIKE where name IN ‘_p%’;
‘_p’; ‘_p’; ‘_p%’;

43 Consider a relation R(A, B, C, D, E) and a set of all FDs that hold on R as given below:
{A → BC, CD → E, B → D, E → A}
Choose the correct option:
a) R is in 1NF, not in b) R is in 2NF, not in c) R is in 3NF, not in d) R is in BCNF
2NF 3NF BCNF

44 Consider the following two sets of functional dependencies:

F = {A → C, AC → D, E → AD, E → H}
G = {A → CD, E → AH}
Choose the correct option:
a) only F covers G b) only G covers F c) F and G are d) None of the above
equivalent
45 Consider the following schedule S.
S: R1(X); W1(X); R2(X); W2(X); R1(Y); R2(Y);
Which of the following is a non-conflicting pair of operations in the schedule S?
a) R1(X); W1(X); b) W1(X); R2(X); c) W1(X); W2(X); d) R1(X); W2(X);

Page 5 of 6
 1100CST308052301

46 To be conflict serializable, all transactions should follow _______

a) Binary locking b) Two phase locking c) Binary Locking d) None of the above
with wait-for
graph
47 Which of the following is NOT a type of database model?
a) Relational model b) Network model c) Hierarchical d) Object-oriented
model model
48 Which of the following database models represents data as a collection of key-value pairs?
a) Relational model b) Hierarchical model c) Network model d) NoSQL model
49 Which SQL function is used to calculate the total number of records in a table?
a) COUNT b) SUM c) AVG d) MAX
50 Consider the statements given below:
S1: Data abstraction is the DBMS characteristic that allows program-data independence.
S2: Data models allow representation of a database at different levels of detail.
Choose the correct option:
a) S1: True; S2: True b) S1: True; S2: False c) S1: False; S2: d) S1:False; S2: False
True
*****

Page 6 of 6