Subtopics in this chapter
- 7.1Introduction to data structure, list, linked lists and trees
- 7.2Sorting, searching, and graphs
- 7.3Introduction to data models, normalization, and SQL
- 7.4Transaction processing, concurrency control and crash recovery
- 7.5Introduction to Operating System and process management
- 7.6Memory management, file systems and system administration
What is usually tested
Data-structure questions cover complexity notation, stacks, queues, linked lists, trees and traversals, sorting and searching algorithms, hashing, and graph algorithms such as spanning trees and shortest paths. Database questions ask about the E-R model, keys, normal forms, SQL, relational algebra, transactions, ACID properties, locking and recovery. Operating-system questions cover processes and threads, scheduling, synchronisation, deadlock, paging, page replacement, file allocation and basic administration.
Sample questions with answers
Choose an answer to check it, or open "Show answer". These 12 are taken from the 219 questions for this chapter in the practice bank.
-
Which data structure follows LIFO order?
Show answer
Answer: A. Stack
Stack: Last In, First Out.
-
An abstract data type (ADT) specifies:
Show answer
Answer: A. A set of data and the operations on it, without saying how they are implemented
A stack ADT, for example, can be implemented with either an array or a linked list.
-
The worst-case time complexity of quicksort is:
Show answer
Answer: C. O(n²)
Poor pivot choices lead to O(n²) in the worst case.
-
External sorting is used when:
Show answer
Answer: B. The data is too large to fit in main memory
The data stays on disk and is sorted in pieces, usually with a merge-based method.
-
Which SQL command removes a table and its structure completely?
Show answer
Answer: C. DROP
DROP removes the table definition and data.
-
The three levels of data abstraction in a database system are:
Show answer
Answer: A. Physical, logical and view
The physical level describes how the data is stored, the logical level what is stored, and the view level what each user sees.
-
Which ACID property ensures a transaction is all-or-nothing?
Show answer
Answer: A. Atomicity
Atomicity: either all operations complete, or none do.
-
Which of the following is NOT a necessary condition for deadlock?
Show answer
Answer: D. Preemption
The condition is NO preemption; preemption actually prevents deadlock.
-
An operating system is best described as:
Show answer
Answer: A. A program that manages the hardware resources and provides services to other programs
It acts as an interface between the user and the computer hardware.
-
The main aim of multiprogramming is to:
Show answer
Answer: B. Keep the CPU busy by switching to another job when one job waits for I/O
Several jobs are kept in memory at the same time.
-
Belady's anomaly is associated with which page replacement algorithm?
Show answer
Answer: D. FIFO
In FIFO, more frames can sometimes cause more page faults.
-
The address generated by the CPU during the execution of a program is called a:
Show answer
Answer: D. Logical (virtual) address
The memory management unit translates it into a physical address.
Practise this chapter
The full mock tests mix 10 questions from this chapter with 10 from each of the other nine, under the real 2-hour limit. Chapter practice mode lets you work through this chapter alone, untimed, with the explanation shown after every question. Go to the mock tests