1200CST308122401

SET 1 Answer
Total Pages: 5
Scheme
Reg No.: _______________ Name: _____________________________________

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY

B.Tech Degree S6 (S, FE) / S6 (PT) (S, FE) Examination December 2024 (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.
(5) Calculators are not permitted

1. The prerequisite of the binary search algorithm is

a) Array should be b) Array should be c) Array should be d) None of these
sorted in randomly arranged sorted in
descending order ascending order
2. In a binary heap, what is the time complexity of deleting the maximum element?

a) O(1) b) O(log n) c) O(n) d) O(n log n)

3. How many edges does a complete graph with n vertices have?
a) n(n-1) b) n(n-1)/2 c) n^2 d) n^2 - n
4. The data structure used in breadth first search algorithm is
a) queue b) stack c) heap d) Hash table
5. What is the amortized time complexity of operations in a dynamic array?

a) O(1) b) O(log n) c) O(n) d) O(n^2)

6. In a max-heap with n elements, where are the leaf nodes stored?
a) Levels 0 to log n - 1 b) Last level only c) Levels log n to n d) Randomly
7. A hash table is
a) A structure used to b) A structure used for c) A structure that d) A structure that
implement stack storage maps values to maps keys to
and queue keys values
8. In a circular queue implemented with an array, how do you determine if the queue is full?
a) (rear == front) b) (rear + 1) % size == c) (rear - front) == d) (front + size) %
front size rear == 1
9. Which of the following traversal algorithms ensures elements are visited in sorted order for a binary
search tree?

Page 1 of 6
1200CST308122401

a) Pre-order b) Post-order c) In-order d) Level-order

10. What is the maximum number of nodes in a binary tree of height h?
a) 2^h - 1 b) 2^(h-1) - 1 c) 2^(h+1) - 1 d) 2^h
11 In a multithreaded environment, which of the following is used to avoid race conditions?
a) Thread Pooling b) Mutex c) paging d) Deadlock
12 In a two-level directory structure, which of the following is true?
a) Files in different b) Files in the same c) Directories d) Each user can only
directories can directory can have cannot have have one file
have the same the same name subdirectories
name

13 A system is said to be in a deadlock state when:

a) All processes are b) Processes c) CPU utilization is d) Processes are in

blocked are waiting 0% ready state
for resources
held by each other

14 In a multithreaded program, a thread takes 100 ms for computation and 10 ms for I/O. If there are 5
such threads, what is the CPU utilization?

a) 33.3% b) 50% c) 90.9% d) 100%

15 A paging system has a 3-level page table. If the first, second, and third levels occupy 1 KB each, what is
the minimum memory needed to store the page tables for a process with 2 MB of virtual memory and 4
KB page size?

a) 2 KB b) 4 KB c) 6 KB d) 8 KB
16 In a system with multiple processes, which synchronization mechanism ensures mutual exclusion?

a) Semaphore b) Paging c) Spooling d) deadlock

17 A system has 5 processes and 3 resource types with the following allocation and request matrices:
Allocation: [1, 0, 2], [0, 1, 0], [1, 3, 5], [1, 0, 0], [0, 0, 1]
Need: [0, 0, 0], [1, 0, 2], [1, 1, 0], [0, 0, 2], [1, 0, 0]
Available: [1, 1, 1]
What is the state of the system?

a) Safe b) Unsafe c) Deadlocked d) Indeterminate

18 Consider a paging system with a page size of 4 KB. How many bits are used for the offset in a 32-bit
address?
a) 10 bits b) 12 bits c) 14 bits d) 16 bits
19 What is the primary purpose of an operating system?
a) To enable direct b) To manage system c) To compile d) To act as a
hardware control resources programs debugger

Page 2 of 6
1200CST308122401

20 Which of the following is an example of a process scheduling algorithm?

a) Round Robin b) Bubble sort c) DFS d) Quick sort

21 A CPU has a clock cycle time of 2 ns and executes a program with 1 billion instructions. The CPI of the
processor is 1.5. What is the total execution time?

a) 3s b) 1s c) 2s d) 0.5 s
22 In a 4-way set associative cache, the total cache size is 64 KB and block size is 16 bytes. What is the
number of sets in the cache?

a) 256 b) 1024 c) 2048 d) 512

23 Which of the following addressing modes is used in the instruction MOV AX, [BX]?

a) Register b) Direct Addressing c) Register Indirect d) Immediate

Addressing Addressing Addressing
24 A computer has 16 GB of RAM and a 32-bit virtual address space. If the page size is 4 KB, what is the size
of the page table?

a) 8 MB b) 16 MB c) 4 MB d) 32 MB
25 In a pipelined processor, the instruction throughput increases because
a) Each instruction b) Multiple c) The clock cycle d) The instruction set
uses fewer instructions are time is reduced is simplified
resources executed
simultaneously

26 If a CPU has 4 registers and 32 instructions, how many bits are required for the opcode?
a) 4 b) 5 c) 3 d) 6
27 A system has a 32 KB 2-way set associative cache and a block size of 16 bytes. How many cache lines are
in one set?
a) 1024 b) 2048 c) 4096 d) 8192
28 A system uses a direct-mapped cache with 512 blocks and a block size of 32 bytes. What is the size of
the tag field for a 32-bit memory address?
a) 19 bits b) 18 bits c) 17 bits d) 16 bits
29 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

(RAM) memory (Hard
Disk)

30 Which of the following techniques is used to handle branch hazards?

a) Instruction b) Branch Prediction c) Delayed Branch d) Both b and c

Prefetch
31 Which of the following is a key feature of a relational database?

Page 3 of 6
1200CST308122401

a) Data is stored as b) Data is stored in c) Data is stored in d) Data is stored as

objects the form of tables XML format scripts
32 Given a relation R(A, B, C) with functional dependencies {A → B, B → C}, which of the following is a
superkey?
a) A b) B c) C d) AB
33 Consider the following SQL query:

sql
Copy code
SELECT COUNT(*)
FROM Employees
WHERE Salary > (SELECT AVG(Salary) FROM Employees);

What does this query compute?

a) The total salary of b)

The number of c) The average d) The count of
all employees employees earning salary of all employees with
above the average employees the lowest salary
salary
34 Which SQL command is used to remove a table from a database?
a) DELETE b) REMOVE c) DROP d) ERASE
35 Which of the following properties ensures that a database transaction is completed or entirely rolled
back?
a) Consistency b) Durability c) Atomicity d) Isolation
36 What is the role of the primary key in a database?
a) To uniquely b) To store large data c) To index the table d) To allow duplicate
identify a record records
in a table
37 A schedule is said to be conflict serializable if:
a) It can be b) It allows concurrent c) It maintains the d) It ensures no
transformed into execution of all ACID properties deadlocks occur
a serial schedule transactions of transactions
by swapping non-
conflicting
operations
38 For a relation R(A, B, C, D) with candidate keys {A, BC}, which normal form does it violate if A → B and B
→ C exist?
a) INF b) 2NF c) 3NF d) BCNF
39 Given the following relational algebra query:

scss
Copy code
π_name(σ_age > 30(Employees))

Page 4 of 6
1200CST308122401

What does this query return?

a) All employee b)
Names of c) Ages of all d) Names and ages
names employees older employees of employees
than 30
40 Consider a B+ tree with order 4. What is the maximum number of keys that can be stored in a node?
a) 2 b) 3 c) 4 d) 5
41 The language accepted by Linear Bounded Automaton:

a) Recursive b) Context free c) Context Sensitive d) All of the

Language language Language mentioned

42 The Chomsky hierarchy classifies formal languages into how many levels?
a) 2 b) 3 c) 4 d) 5
43 Finite automata requires minimum _______ number of stacks.
a) 1 b) 0 c) 2 d) None of the
mentioned
44 Regular expression for all strings starts with ab and ends with bba is.
a) aba*b*bba b) ab(ab)*bba c) ab(a+b)*bba d) All of the
mentioned
45 The Grammar can be defined as: G=(V, ∑, p, S). In the given definition, what does S represents?
a) Accepting State b) Starting Variable c) Sensitive d) None of these
Grammar
46 The closure property of context free grammar includes :
a) Kleene b) Concatenation c) Union d) All of the
mentioned
47 A multitape turing machine is ________ powerful than a single tape turing machine.
a) more b) less c) equal d) none of the
mentioned
48 A turing machine that is able to simulate other turing machines:
a) Nested Turing b) Universal Turing c) Counter machine d) None of the
machines machine mentioned
49 Which of the following statements are false?
a) Every recursive b) Recursively c) Recursive d) None of the
language is enumerable languages may mentioned
recursively language may not not be
enumerable be recursive recursively
enumerable
50 If L is a recursive language, L’ is:
a) Recursive b) Recursively c) Recursive and d) None of the
Enumerable Recursively mentioned
Enumerable

Page 5 of 6
1200CST308122401

Page 6 of 6