Unlock hundreds more features
Save your Quiz to the Dashboard
View and Export Results
Use AI to Create Quizzes and Analyse Results

OR
Sign inSign in with Facebook
Sign inSign in with Google
Quizzes > Computers & IT

Computer Science Trivia: Theory of Computation

Quick, free theory of computation quiz to test your knowledge. Instant results.

Editorial: Review CompletedCreated By: Ashley RoseUpdated Aug 23, 2025
Difficulty: Moderate
2-5mins
Learning OutcomesCheat Sheet
Paper art illustration for computational theory quiz on a sky blue background

This quiz helps you check your grasp of the theory of computation, including automata, formal languages, and Turing machines. In minutes, try our discrete math quiz, explore a big o notation quiz to sharpen complexity skills, or review broad computer science practice questions for extra drills.

What is the time complexity of binary search on a sorted array?
O(n)
O(n log n)
O(1)
O(log n)
Binary search divides the search interval in half at each step, resulting in logarithmic time complexity. This makes it much faster than a linear search for large datasets. The worst-case and average-case time complexity is O(log n). .
What does HTTP stand for?
HyperText Transport Procedure
Hyper Transmission Transfer Protocol
High Text Transfer Procedure
HyperText Transfer Protocol
HTTP is the foundation of data communication for the World Wide Web, defining how messages are formatted and transmitted. It stands for HyperText Transfer Protocol and operates at the application layer. HTTP requests and responses are used by clients and servers to exchange resources. .
Which of the following is a mutable data type in Python?
tuple
int
string
list
In Python, mutable types can have their content changed after creation. Lists are mutable, allowing operations like append, pop, or assignment to elements. Tuples and strings are immutable, while integers are also immutable. .
In SQL, which command removes all rows from a table without deleting the table itself?
CLEAR
DELETE
DROP
TRUNCATE
The TRUNCATE command removes all rows from a table quickly by deallocating the data pages, but it retains the table structure for future use. DELETE removes rows one at a time and can be rolled back if within a transaction, while DROP deletes the entire table. TRUNCATE cannot be rolled back in many databases. .
What is the maximum number of states in a DFA equivalent to an NFA with n states?
n!
n^2
2^n
n
The subset construction method for converting an NFA to a DFA can yield up to 2^n states in the worst case, as each DFA state corresponds to a subset of NFA states. This exponential growth illustrates the potential state explosion. However, many practical NFAs convert to much smaller DFAs. .
Which of the following sorting algorithms is stable?
QuickSort
MergeSort
SelectionSort
HeapSort
A stable sorting algorithm preserves the relative order of records with equal keys. MergeSort is stable because it merges sorted sublists by taking equal elements from the left sublist first. QuickSort, HeapSort, and SelectionSort are not stable in their typical implementations. .
Which CPU scheduling algorithm can lead to starvation of long processes?
First-Come First-Served
Shortest Job Next
Priority Scheduling
Round Robin
Priority scheduling selects processes based on priority and can cause starvation if low-priority processes never get CPU time because higher-priority tasks keep arriving. Techniques like aging can mitigate this. Round Robin and FCFS do not inherently starve processes, and Shortest Job Next may delay longer jobs but is not based on priority. .
In the OSI model, which layer is responsible for logical addressing and path determination?
Data Link Layer
Transport Layer
Session Layer
Network Layer
The Network Layer provides logical addressing (such as IP addresses) and determines the best path for data packets across interconnected networks. It handles routing, packet forwarding, and congestion control. The Data Link Layer deals with physical addressing, while the Transport Layer ensures reliable data transfer. .
Which problem is in NP but is not known to be NP-Complete (unless P=NP)?
Graph Isomorphism
Hamiltonian Cycle
Subset Sum
Traveling Salesman Problem
Graph Isomorphism asks whether two graphs are structurally identical and is in NP, but it is not known to be NP-Complete unless P=NP. Subset Sum, TSP, and Hamiltonian Cycle are classic NP-Complete problems. GI's complexity status remains unsettled. .
In real-time operating systems, which issue is addressed by the priority inheritance protocol?
Thrashing
Deadlock
Priority Inversion
Starvation
Priority inversion occurs when a lower-priority task holds a resource needed by a higher-priority task, causing the latter to wait indefinitely. The priority inheritance protocol temporarily raises the priority of the lower-priority task to that of the higher one, preventing inversion. This ensures time-critical tasks meet deadlines. .
In a B-tree of order m, what is the minimum number of children each non-root internal node must have?
m - 1
ceil(m/2)
floor(m/2)
m/2
A B-tree of order m requires that each non-root internal node has at least ceil(m/2) children to maintain balance and efficient operations. This lower bound ensures that the tree does not become too sparse. The upper bound is m children per node. .
Kleene's Recursion Theorem in computability theory demonstrates the existence of what?
Fixed points
NP-hard functions
Primitive recursive functions
Halting sets
Kleene's Recursion Theorem guarantees that for any computable function mapping program indices to program indices, there exists a program index e that is a fixed point of that mapping. In other words, the program can obtain its own description and produce equivalent behavior. This is a cornerstone of self-referential constructions in computability. .
0
{"name":"What is the time complexity of binary search on a sorted array?", "url":"https://www.quiz-maker.com/QPREVIEW","txt":"What is the time complexity of binary search on a sorted array?, What does HTTP stand for?, Which of the following is a mutable data type in Python?","img":"https://www.quiz-maker.com/3012/images/ogquiz.png"}

Study Outcomes

  1. Understand Core Automata Concepts -

    Distinguish between deterministic and nondeterministic automata and explain how finite-state machines process input strings in computational theory.

  2. Classify Formal Languages -

    Categorize languages within the Chomsky hierarchy and recognize the differences between regular, context-free, context-sensitive, and recursively enumerable languages.

  3. Analyze Decidability -

    Assess decision problems for decidability and identify classic undecidable problems such as the Halting Problem and Post's Correspondence Problem.

  4. Apply the Pumping Lemma -

    Use the pumping lemma for regular and context-free languages to prove whether a language belongs to a given class.

  5. Evaluate Complexity Classes -

    Differentiate common complexity classes like P, NP, and PSPACE and gauge the computational resources required to solve various problems.

  6. Identify Knowledge Gaps -

    Pinpoint areas for further study by reviewing your scores on CS trivia questions and targeting challenging computational theory topics.

Cheat Sheet

  1. Finite Automata & Regular Languages -

    Deterministic and nondeterministic finite automata (DFA/NFA) form the backbone of regular language theory by processing input symbols in 5-tuple structures (Sipser, 2006). For example, the language 0*1* - which matches any number of 0s followed by 1s - can be recognized by a two-state DFA. Remember "SALT" as a mnemonic for DFA components: States, Alphabet, δ (transition), Start, and Accept.

  2. Pumping Lemma for Regular Languages -

    The pumping lemma provides a proof technique to show certain languages aren't regular by demonstrating that all sufficiently long strings can be "pumped" inside a decomposed segment (Hopcroft & Ullman, 1979). In practice, you assume a pumping length p, split the string xyz with |xy| ≤ p and |y| > 0, and derive a contradiction by showing xyiz ∉ L for some i. Visualize "stretching" the y segment like a rubber band to recall how the lemma works!

  3. Context-Free Grammars & Pushdown Automata -

    Context-free grammars (CFGs) generate languages recognized by pushdown automata (PDA) via production rules like S → (S)S | ε for balanced parentheses (Sipser, 2006). PDAs use a stack to handle nested structures: push on "(" and pop on ")", accepting when the stack empties. A handy mnemonic is "PUSH then POP for proper pairing!"

  4. Turing Machines & Decidability -

    Turing machines extend finite automata with an infinite tape and bidirectional head, formalizing what it means to compute any algorithm (Turing, 1936). The Halting Problem proves there's no general algorithm to decide whether an arbitrary TM halts on a given input, showcasing an undecidable problem (Rice's Theorem). Picture the head spinning endlessly - no stopping criterion - to remember undecidability!

  5. Complexity Classes P vs NP -

    Class P contains problems solvable in polynomial time by a deterministic TM, while NP houses those verifiable in polynomial time by a nondeterministic TM (Cook, 1971). The P vs NP question - "Is P = NP?" - remains one of the seven Millennium Prize Problems and drives much of complexity theory. Think "verifier vs solver" to recall NP's nature of easy checking but potentially hard finding!

Make a Quiz (FREE) Copy & Edit This Quiz Create a Quiz with AI

Computers & IT Quizzes

Powered by: Quiz Maker