I85PREP
⌘ K
OAE Computer Science study materials
OAE Computer Science study resources

OAE Computer Science practice questions

One question at a time. Build your OAE Computer Science understanding.

First 50 of 198 questions. Each one lists the choices, the correct answer, and an explanation. The checker at the top of this page saves progress in this browser when it is available.

Continue in the practice tool above to load more questions, 50 at a time.

Question 1Fundamentals of Computer Science and Algorithms

In a binary search tree with no duplicate keys, which traversal visits the nodes in ascending key order?

  1. Preorder traversal
  2. Inorder traversal Correct answer.
  3. Level-order traversal
  4. Postorder traversal

Explanation

An inorder traversal processes the left subtree, then the node, then the right subtree, so the BST ordering property guarantees nondecreasing key order. The other traversals visit nodes in structural orders that do not respect key ordering.

Question 2Fundamentals of Computer Science and Algorithms

A stack data structure follows which access discipline, and which operation removes an element?

  1. Last-in first-out; pop removes an element Correct answer.
  2. First-in first-out; dequeue removes an element
  3. Random access by index; delete removes an element
  4. Priority-ordered; extract-min removes an element

Explanation

A stack is last-in first-out: the most recently pushed element is the first removed, and that removal is the pop operation. Push adds to the same end, so the structure is managed entirely at the top.

Question 3Fundamentals of Computer Science and Algorithms

What is the average-case time complexity of searching for a key in a well-distributed hash table with n entries?

  1. O(log n)
  2. O(n)
  3. O(n log n)
  4. O(1) Correct answer.

Explanation

With a good hash function and controlled load factor, keys spread evenly across buckets, so a lookup examines a constant expected number of entries. The worst case degrades to O(n) when every key collides into one bucket.

Question 4Fundamentals of Computer Science and Algorithms

Which statement correctly describes the relationship between a class and an object in object-oriented programming?

  1. A class and an object are the same construct with different names
  2. An object is the blueprint and a class is an instance created from it
  3. An object stores only methods, while a class stores only fields
  4. A class defines structure and behavior, and an object is an instance of that class Correct answer.

Explanation

A class is the definition that declares fields and methods, while an object is a runtime instance allocated from that definition with its own state. Many distinct objects can be created from one class.

Question 5Fundamentals of Computer Science and Algorithms

A decimal value is stored in an 8-bit unsigned register. What is the largest value it can represent?

  1. 127
  2. 128
  3. 255 Correct answer.
  4. 256

Explanation

An 8-bit unsigned register has 2^8 = 256 distinct patterns, ranging from 0 through 255, so the maximum is 255. The value 256 would require a ninth bit.

Question 6Fundamentals of Computer Science and Algorithms

Which of the following is the binary representation of the decimal number 13?

  1. 1011
  2. 1101 Correct answer.
  3. 1001
  4. 1110

Explanation

Thirteen equals 8 + 4 + 1, which corresponds to bits set in the 8s, 4s, and 1s places, giving 1101. Reading the bits as 8+4+0+1 confirms the value.

Question 7Fundamentals of Computer Science and Algorithms

In asymptotic analysis, what does it mean to say that an algorithm is O(n^2)?

  1. The algorithm runs in quadratic time only on sorted inputs
  2. The runtime grows no faster than a constant multiple of n^2 for large inputs Correct answer.
  3. The algorithm uses n^2 bytes of memory
  4. The algorithm always performs exactly n^2 operations

Explanation

Big-O gives an upper bound: beyond some input size, the growth is bounded by a constant times n^2. It describes growth rate, not an exact operation count or a memory figure.

Question 8Fundamentals of Computer Science and Algorithms

Which logic gate outputs 1 only when both of its inputs are 1?

  1. OR
  2. NOR
  3. XOR
  4. AND Correct answer.

Explanation

The AND gate produces a true output only for the input combination 1,1. Every other input combination yields 0.

Question 9Fundamentals of Computer Science and Algorithms

A recursive function computes fibonacci(n) by calling fibonacci(n-1) and fibonacci(n-2) with no memoization. Why is this inefficient?

  1. Recursion cannot express the Fibonacci recurrence
  2. The base cases are evaluated before the recursive calls
  3. The same subproblems are recomputed many times, giving exponential growth Correct answer.
  4. Each call allocates a new heap object

Explanation

Without memoization the recursion tree branches at every level, so subproblems such as fibonacci(n-3) are solved repeatedly, producing roughly exponential work. Caching results or using iteration reduces the cost to linear time.

Question 10Fundamentals of Computer Science and Algorithms

An array holds n unsorted integers, and a program must report whether any value appears more than once. Which approach gives O(n) expected time?

  1. Insert each value into a hash set and check for a prior insertion Correct answer.
  2. Compare every pair of elements
  3. Sort the array, then scan adjacent pairs
  4. Compute the sum and compare it to the expected sum

Explanation

A hash set supports expected O(1) insertion and membership tests, so one pass detects duplicates in expected O(n) time. Sorting works but costs O(n log n), and pairwise comparison is quadratic.

Question 11Fundamentals of Computer Science and Algorithms

A queue is implemented with a fixed-size circular array of capacity 8 using front and rear indices. After several enqueue and dequeue operations, front = 5 and rear = 2. How many elements are currently stored?

  1. 5 Correct answer.
  2. 3
  3. 6
  4. 7

Explanation

With a circular buffer the count is (rear - front + capacity) mod capacity, which gives (2 - 5 + 8) mod 8 = 5. The wrap-around is handled by the modular arithmetic rather than by simple subtraction.

Question 12Fundamentals of Computer Science and Algorithms

A binary search tree receives keys in the order 50, 40, 60, 35, 45, 55, 70. Which key is the inorder successor of 45?

  1. 50 Correct answer.
  2. 55
  3. 35
  4. 60

Explanation

Inorder traversal of this balanced BST yields 35, 40, 45, 50, 55, 60, 70, so the node visited immediately after 45 is 50. Since 45 has no right child, its successor is the lowest ancestor for which 45 lies in the left subtree, namely 50.

Question 13Fundamentals of Computer Science and Algorithms

Which sorting algorithm is stable and guarantees O(n log n) worst-case time while using O(n) auxiliary space?

  1. Merge sort Correct answer.
  2. Selection sort
  3. Heapsort
  4. Quicksort

Explanation

Merge sort divides the input, sorts halves recursively, and merges them while preserving the relative order of equal keys, giving stability and O(n log n) worst-case time at the cost of O(n) extra space. Quicksort and heapsort are not stable, and quicksort has O(n^2) worst-case time.

Question 14Fundamentals of Computer Science and Algorithms

A process uses 32-bit virtual addresses with 4 KB pages. How many bits of the virtual address form the page offset?

  1. 22
  2. 12 Correct answer.
  3. 20
  4. 10

Explanation

A 4 KB page contains 4096 bytes, and log2(4096) = 12, so the low 12 bits index within the page. The remaining 20 bits identify the virtual page number.

Question 15Fundamentals of Computer Science and Algorithms

Which statement best distinguishes a process from a thread?

  1. A process can run concurrently, but threads always execute sequentially
  2. Threads have separate address spaces, while processes share one
  3. Threads cannot access heap memory, while processes can
  4. A process has its own address space, while threads of one process share that address space Correct answer.

Explanation

A process owns an isolated virtual address space, whereas threads within a process share code, data, and heap while keeping separate stacks and registers. This sharing makes thread communication cheap but requires synchronization.

Question 16Fundamentals of Computer Science and Algorithms

A relation has a candidate key {A, B} and a functional dependency A -> C. Which normal form does the relation violate?

  1. Second normal form Correct answer.
  2. Boyce-Codd normal form
  3. First normal form
  4. Third normal form

Explanation

Second normal form requires that no non-prime attribute depend on part of a candidate key. Because C depends on A alone while the key is {A, B}, the relation violates 2NF.

Question 17Fundamentals of Computer Science and Algorithms

What does the halting problem demonstrate about computation?

  1. Compilers cannot detect infinite loops in any program
  2. Some programs cannot be written in high-level languages
  3. No algorithm can decide, for every program and input, whether the program halts Correct answer.
  4. Programs that halt always do so within a fixed time bound

Explanation

Turing proved that no general algorithm can decide halting for all program-input pairs; the problem is undecidable. This is a fundamental limit of computation, not a limitation of a particular language or compiler.

Question 18Fundamentals of Computer Science and Algorithms

Which of the following correctly converts the decimal fraction 0.375 to binary?

  1. 0.110
  2. 0.101
  3. 0.111
  4. 0.011 Correct answer.

Explanation

Repeatedly multiplying by two: 0.375 x 2 = 0.75 gives bit 0; 0.75 x 2 = 1.5 gives bit 1; 0.5 x 2 = 1.0 gives bit 1, yielding 0.011. Checking: 1/4 + 1/8 = 0.375.

Question 19Fundamentals of Computer Science and Algorithms

Which data structure is the most appropriate for implementing an efficient priority queue that repeatedly extracts the minimum key?

  1. Binary min-heap Correct answer.
  2. Hash table
  3. Unsorted singly linked list
  4. FIFO queue

Explanation

A binary min-heap keeps the minimum at the root, so extract-min costs O(log n) and insertion costs O(log n). An unsorted list makes extraction O(n), and hash tables and FIFO queues do not maintain key order.

Question 20Fundamentals of Computer Science and Algorithms

A program repeatedly performs binary search on a sorted array of 1,000,000 elements. Approximately how many comparisons does a single unsuccessful search require in the worst case?

  1. About 500,000
  2. About 20 Correct answer.
  3. About 1,000
  4. About 10

Explanation

Binary search halves the interval each step, so the worst case is about log2(1,000,000), which is roughly 20 comparisons. Linear probing would need up to a million comparisons.

Question 21Fundamentals of Computer Science and Algorithms

A cache has 16 blocks and uses direct mapping with 4-byte blocks. A memory address 0x2C is accessed. Which cache block does it map to?

  1. Block 11 Correct answer.
  2. Block 12
  3. Block 3
  4. Block 7

Explanation

The block number is 0x2C / 4 = 0x0B = 11, and with 16 cache blocks the index is 11 mod 16 = 11. Direct mapping therefore places the data in block 11.

Question 22Fundamentals of Computer Science and Algorithms

A relational table stores orders with columns (order_id, customer_id, order_date). A query groups rows by customer_id and keeps only groups with more than three orders. Which SQL clause performs the filtering?

  1. WHERE
  2. DISTINCT
  3. HAVING Correct answer.
  4. ORDER BY

Explanation

HAVING filters groups after aggregation, so conditions on aggregate results such as COUNT(*) > 3 belong there. WHERE filters individual rows before grouping and cannot reference aggregate functions.

Question 23Fundamentals of Computer Science and Algorithms

A deterministic finite automaton must accept exactly the strings over {a, b} that contain an even number of a's. What is the minimum number of states required?

  1. 2 Correct answer.
  2. 4
  3. 1
  4. 3

Explanation

The automaton only needs to track the parity of a's seen so far: one state for even parity and one for odd parity, with b-transitions looping in place. Two states therefore suffice, and one cannot distinguish the accepting from the rejecting condition.

Question 24Fundamentals of Computer Science and Algorithms

A directed graph has V vertices and E edges and may contain negative edge weights but no negative cycles. Which algorithm correctly computes single-source shortest paths?

  1. Dijkstra's algorithm with a binary heap
  2. Prim's algorithm
  3. Bellman-Ford algorithm Correct answer.
  4. Depth-first search from the source

Explanation

Bellman-Ford relaxes every edge V-1 times, which correctly handles negative weights and detects negative cycles. Dijkstra's greedy choice is invalid with negative edges, and the other two algorithms do not compute shortest paths.

Question 25Fundamentals of Computer Science and Algorithms

A dynamic programming solution fills an n-by-n table where each cell depends on its left and upper neighbors, and each cell takes constant time. What are the time and space complexities?

  1. O(n^2) time and O(n^2) space Correct answer.
  2. O(n log n) time and O(n) space
  3. O(n^2) time and O(n) space
  4. O(n) time and O(n) space

Explanation

Filling every cell of an n-by-n table once at constant cost per cell gives O(n^2) time, and storing the full table requires O(n^2) space. Space can sometimes be reduced to O(n) by keeping only the previous row, but the stated full table uses quadratic space.

Question 26Fundamentals of Computer Science and Algorithms

Which number base is used internally by nearly all modern general-purpose computers to represent integer values in memory?

  1. Base 16
  2. Base 2 Correct answer.
  3. Base 8
  4. Base 10

Explanation

Digital circuits distinguish two voltage levels, so stored values are naturally encoded as base-2 digits (bits). Octal and hexadecimal are only human-friendly shorthand groupings of those bits, not the physical representation.

Question 27Fundamentals of Computer Science and Algorithms

A Boolean expression is written as A AND (NOT B) OR C, with standard operator precedence. Which input assignment makes the expression true?

  1. A=1, B=0, C=1
  2. A=1, B=1, C=0
  3. A=0, B=0, C=0
  4. A=0, B=1, C=1 Correct answer.

Explanation

NOT binds tightest, then AND, then OR, so the expression is (A AND NOT B) OR C. With A=0, B=1, C=1 the first term is 0 and the second term is 1, giving a true result. Any assignment with C=1 is true regardless of A and B.

Question 28Fundamentals of Computer Science and Algorithms

In a two's complement system using 8 bits, what decimal value does the bit pattern 11110110 represent?

  1. -10 Correct answer.
  2. 246
  3. -11
  4. -9

Explanation

The leading bit is 1, so the value is negative. Inverting the bits gives 00001001 (9) and adding 1 gives 10, so the pattern represents -10. Equivalently, -128 + 64 + 32 + 16 + 4 + 2 = -10.

Question 29Fundamentals of Computer Science and Algorithms

Which statement describes the role of a compiler in the software development toolchain?

  1. It links object files and resolves external symbol references into a final executable.
  2. It executes source code one statement at a time while tracking variable values.
  3. It translates a high-level language program into machine-level or intermediate code before execution. Correct answer.
  4. It converts assembly mnemonics into machine instructions.

Explanation

A compiler performs translation of a whole high-level source program into a lower-level target form, such as assembly, object code, or bytecode, ahead of execution. Execution, linking, and assembly are separate stages handled by other tools.

Question 30Fundamentals of Computer Science and Algorithms

A stack is used to evaluate the postfix expression 5 3 + 4 *. What value results?

  1. 23
  2. 32 Correct answer.
  3. 35
  4. 17

Explanation

Scanning left to right: push 5, push 3, then + pops 3 and 5 and pushes 8. Push 4, then * pops 4 and 8 and pushes 32. The single remaining stack value, 32, is the result.

Question 31Fundamentals of Computer Science and Algorithms

A singly linked list stores n nodes and only a head reference is kept. Which operation has O(n) worst-case time?

  1. Reading the value stored in the head node
  2. Inserting a new node immediately after the head node
  3. Accessing the k-th element for an arbitrary k Correct answer.
  4. Deleting the head node

Explanation

A linked list has no index arithmetic, so reaching position k requires following k next references, which is O(n) in the worst case. Operations at the head only touch a constant number of references.

Question 32Fundamentals of Computer Science and Algorithms

A hash table uses separate chaining and its load factor grows well beyond 1. What is the primary consequence for performance?

  1. Average search time degrades toward linear in the number of entries. Correct answer.
  2. The table can no longer store any additional keys.
  3. Keys become impossible to compare for equality.
  4. Hash collisions are eliminated because chains absorb them.

Explanation

With separate chaining, each bucket holds a list whose expected length equals the load factor. As that factor grows, unsuccessful and successful searches scan longer chains, so expected cost approaches O(n) rather than O(1).

Question 33Fundamentals of Computer Science and Algorithms

Which traversal of a binary search tree visits keys in ascending sorted order?

  1. Postorder
  2. Level order
  3. Preorder
  4. Inorder Correct answer.

Explanation

An inorder traversal visits the left subtree, then the node, then the right subtree. Because every left descendant is smaller and every right descendant is larger, this produces keys in increasing order.

Question 34Fundamentals of Computer Science and Algorithms

A complete binary tree is stored in an array using 0-based indexing. For the node at index i, where is its right child located?

  1. 2i + 2 Correct answer.
  2. 2i
  3. 2i + 1
  4. i + 2

Explanation

In the standard 0-based array layout, the left child of index i sits at 2i + 1 and the right child at 2i + 2. This mapping lets a heap avoid explicit pointers while keeping parent and child relationships implicit.

Question 35Fundamentals of Computer Science and Algorithms

An algorithm's running time satisfies T(n) = 2T(n/2) + n for n > 1, with T(1) constant. What is its asymptotic complexity?

  1. O(log n)
  2. O(n)
  3. O(n log n) Correct answer.
  4. O(n^2)

Explanation

This recurrence matches the merge sort pattern: two subproblems of half size plus linear work to combine them. The master theorem's case with a = 2, b = 2, and f(n) = n gives Theta(n log n).

Question 36Fundamentals of Computer Science and Algorithms

Which algorithm design technique builds a solution by making the locally best choice at each step without backtracking?

  1. Divide and conquer
  2. Greedy method Correct answer.
  3. Dynamic programming
  4. Backtracking

Explanation

A greedy algorithm commits to the locally optimal option at each step and never revisits earlier decisions. Correctness then depends on proving a greedy-choice property and optimal substructure for the specific problem.

Question 37Fundamentals of Computer Science and Algorithms

Which problem is decidable by a deterministic algorithm in polynomial time?

  1. Determining whether an arbitrary first-order logic formula is valid
  2. Determining whether a given program halts on a given input
  3. Determining whether two arbitrary context-free grammars generate the same language
  4. Determining whether a string is accepted by a given deterministic finite automaton Correct answer.

Explanation

DFA acceptance is solvable by simulating the automaton on the input string, which takes time linear in the input length. The other listed problems are undecidable in their general forms.

Question 38Fundamentals of Computer Science and Algorithms

A language L is regular. Which statement must be true?

  1. L requires a Turing machine with unbounded tape.
  2. L must be infinite.
  3. L can be recognized by some finite automaton. Correct answer.
  4. L cannot be described by a regular expression.

Explanation

Regular languages are exactly those accepted by finite automata, and equivalently those described by regular expressions. The defining restriction is finite memory rather than an unbounded tape.

Question 39Fundamentals of Computer Science and Algorithms

In an 8-bit sign-magnitude representation, what is the range of integers that can be stored?

  1. -128 to +127
  2. -255 to +255
  3. 0 to 255
  4. -127 to +127 Correct answer.

Explanation

One bit is reserved for the sign and seven bits hold magnitude, giving magnitudes 0 through 127. Because both +0 and -0 exist, the representable range is -127 to +127.

Question 40Fundamentals of Computer Science and Algorithms

Which statement about a binary search over a sorted array of n elements is accurate?

  1. Its worst-case time is linear because it may scan every element.
  2. It works correctly on an unsorted array provided the target exists.
  3. It examines at most about log2(n) + 1 elements in the worst case. Correct answer.
  4. It requires the array to be sorted in descending order only.

Explanation

Each comparison halves the remaining search interval, so the number of probes is bounded by roughly log2(n) + 1. This logarithmic bound is why sorted order is a prerequisite.

Question 41Fundamentals of Computer Science and Algorithms

A program must repeatedly retrieve the minimum element from a collection that also receives new insertions. Which structure gives the best asymptotic performance for both operations?

  1. Hash table keyed by value
  2. Unsorted singly linked list
  3. Sorted array with linear insertion
  4. Min-heap Correct answer.

Explanation

A min-heap supports insertion and extraction of the minimum in O(log n) time, with the minimum itself visible in O(1). That combination outperforms structures where one of the two operations degrades to linear time.

Question 42Fundamentals of Computer Science and Algorithms

A graph with V vertices and E edges is stored as an adjacency matrix. What is the space complexity?

  1. O(V^2) Correct answer.
  2. O(E)
  3. O(log V)
  4. O(V + E)

Explanation

An adjacency matrix allocates one cell for every ordered pair of vertices, so it uses V^2 entries regardless of how many edges exist. This is wasteful for sparse graphs, where adjacency lists use O(V + E).

Question 43Fundamentals of Computer Science and Algorithms

A weighted undirected graph has nonnegative edge weights and a program must find the shortest path from one source to all vertices. Which algorithm is the standard choice?

  1. Kruskal's algorithm
  2. Depth-first search
  3. Topological sort
  4. Dijkstra's algorithm Correct answer.

Explanation

Dijkstra's algorithm greedily finalizes the nearest unfinalized vertex and relaxes its outgoing edges, which is correct when all edge weights are nonnegative. The restriction matters because a negative edge could invalidate a finalized distance.

Question 44Fundamentals of Computer Science and Algorithms

A spanning tree of a connected undirected graph with V vertices contains how many edges?

  1. V + 1
  2. 2V
  3. V - 1 Correct answer.
  4. V

Explanation

A spanning tree connects all V vertices with no cycles, which requires exactly V - 1 edges. Adding any further edge would create a cycle, and removing any edge would disconnect the graph.

Question 45Fundamentals of Computer Science and Algorithms

A sorting algorithm compares adjacent elements and swaps them whenever they are out of order, repeating passes until no swaps occur. Which statement about this algorithm is correct?

  1. It requires O(n) auxiliary arrays to merge runs.
  2. It guarantees O(n log n) worst-case time.
  3. It is stable and runs in O(n) time on already sorted input with an early-exit check. Correct answer.
  4. It is unstable because equal elements are swapped.

Explanation

Bubble sort only swaps strictly out-of-order neighbors, so equal elements keep their relative order and the sort is stable. With a flag that stops after a pass with no swaps, sorted input needs a single pass, giving O(n) best-case time.

Question 46Fundamentals of Computer Science and Algorithms

A recursive procedure lacks a base case. What is the most direct consequence at runtime?

  1. The procedure compiles but produces a syntax error.
  2. The compiler automatically inserts a default base case.
  3. The call stack keeps growing until a stack overflow occurs. Correct answer.
  4. The recursion terminates with an incorrect value.

Explanation

Without a terminating condition, each call makes another call and pushes a new stack frame. Stack space is finite, so the process eventually exhausts it and typically crashes with a stack overflow.

Question 47Fundamentals of Computer Science and Algorithms

A loop runs i from 1 to n, and inside it an inner loop runs j from 1 to i. How many times is the inner loop body executed in total?

  1. 2n
  2. n(n + 1)/2 Correct answer.
  3. n log n
  4. n^2

Explanation

The inner body runs 1 + 2 + ... + n times, and that arithmetic series sums to n(n + 1)/2. Asymptotically this is Theta(n^2), but the exact count is the triangular number.

Question 48Fundamentals of Computer Science and Algorithms

A binary tree has 31 nodes and is perfectly balanced, with every level completely filled. What is its height measured in edges from root to deepest leaf?

  1. 6
  2. 4 Correct answer.
  3. 5
  4. 15

Explanation

A perfect binary tree with height h has 2^(h+1) - 1 nodes. Setting 2^(h+1) - 1 = 31 gives 2^(h+1) = 32, so h + 1 = 5 and the height in edges is 4.

Question 49Fundamentals of Computer Science and Algorithms

An undirected graph is connected and contains exactly one cycle. What can be concluded about its edge count relative to V vertices?

  1. It has V edges. Correct answer.
  2. It has V + 1 edges.
  3. It has 2V - 2 edges.
  4. It has V - 1 edges.

Explanation

A connected graph on V vertices needs at least V - 1 edges to form a spanning tree, and each additional edge creates exactly one independent cycle. Exactly one cycle therefore means exactly V edges.

Question 50Fundamentals of Computer Science and Algorithms

A dynamic programming table is filled for the 0/1 knapsack problem with n items and capacity W, where each cell depends on the cell one row above and a cell in that row. What are the time and space complexities of the standard tabulation?

  1. O(2^n) time and O(n) space
  2. O(n log W) time and O(W) space
  3. O(n + W) time and O(W) space
  4. O(nW) time and O(nW) space Correct answer.

Explanation

The table has n rows and W + 1 columns, and each cell is computed in constant time from earlier entries, giving O(nW) time. Storing the full table also takes O(nW) space, although space can be reduced to O(W) by keeping only one row.