I85PREP
⌘ K
OSAT Computer Science (OK181) study materials
OSAT Computer Science (OK181) study resources

OSAT Computer Science (OK181) practice questions

One question at a time. Build your OSAT Computer Science (OK181) understanding.

First 50 of 200 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 1Computer Science Foundations and Computational Thinking

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

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

Explanation

An inorder traversal visits the left subtree, then the node, then the right subtree, so the BST ordering property yields keys in sorted ascending order. The other traversals place the root before or after its subtrees and therefore do not produce sorted output.

Question 2Computer Science Foundations and Computational Thinking

A stack is used to evaluate a postfix expression. Which sequence of operations correctly evaluates the input "6 2 3 * -", and what is the result?

  1. Push 6, push 2, push 3; on * pop 3 and 2 push 5; on - pop 5 and 6 push 1
  2. Push 6, push 2, push 3; on * pop 2 and 3 push 6; on - pop 6 and 6 push 0
  3. Push 6, push 2, push 3; on * pop 3 and 2 push 6; on - pop 6 and 6 push 0 Correct answer.
  4. Push 6, push 2, push 3; on * pop 3 and 2 push 6; on - pop 6 and 6 push 12

Explanation

Postfix evaluation pushes operands and, at each operator, pops the two most recent values. Multiplying 2 by 3 gives 6, and the final subtraction computes 6 minus 6, which is 0.

Question 3Computer Science Foundations and Computational Thinking

A recursive function has no base case. What is the most accurate description of the resulting behavior at runtime?

  1. The compiler detects the missing base case and refuses to build the program
  2. The function returns the default value for its return type automatically
  3. Recursive calls continue until the call stack is exhausted, typically raising a stack overflow error Correct answer.
  4. The recursion terminates on its own once local variables are reused

Explanation

Each recursive call consumes a stack frame, and without a terminating condition the frames accumulate until memory for the call stack is exhausted. Compilers generally cannot decide this in advance because termination may depend on runtime values.

Question 4Computer Science Foundations and Computational Thinking

A student claims that a linear search on sorted data is asymptotically as efficient as binary search in the worst case. Which statement correctly evaluates the claim?

  1. The claim is true because sorting the data makes linear search constant time
  2. The claim is false because binary search runs in O(n log n) while linear search runs in O(1)
  3. The claim is true because both algorithms must examine every element in the worst case
  4. The claim is false because binary search runs in O(log n) while linear search runs in O(n) in the worst case Correct answer.

Explanation

Binary search halves the remaining search interval at each step, giving logarithmic worst-case comparisons. Linear search may still inspect all n elements, so its worst case grows linearly.

Question 5Computer Science Foundations and Computational Thinking

Which Boolean expression is logically equivalent to the XOR of inputs A and B?

  1. (A OR B) AND (A NAND B) Correct answer.
  2. (A AND B) OR (A NOR B)
  3. A OR B
  4. A AND B

Explanation

XOR is true exactly when the inputs differ, which means at least one is true and they are not both true. The expression (A OR B) AND (A NAND B) captures precisely that condition.

Question 6Computer Science Foundations and Computational Thinking

In two's complement representation using 8 bits, what decimal value does the bit pattern 11110000 represent?

  1. 16
  2. -15
  3. 240
  4. -16 Correct answer.

Explanation

The leading bit is 1, so the value is negative. Inverting the bits gives 00001111 and adding one gives 00010000, which is 16, so the original pattern represents -16.

Question 7Computer Science Foundations and Computational Thinking

A relational table has a candidate key consisting of two attributes together, and neither attribute alone is unique. Which normal form does the table violate if a non-key attribute depends on only one of those two attributes?

  1. First normal form
  2. Third normal form
  3. Fourth normal form
  4. Second normal form Correct answer.

Explanation

Second normal form forbids partial dependencies, where a non-key attribute depends on part of a composite candidate key. First normal form concerns atomic values, and third normal form concerns transitive dependencies.

Question 8Computer Science Foundations and Computational Thinking

Which of the following best describes the role of the operating system's scheduler?

  1. It translates virtual memory addresses into physical addresses
  2. It maps file names to blocks on a storage device
  3. It selects which ready process or thread receives CPU time next Correct answer.
  4. It converts source code into machine instructions

Explanation

The scheduler decides the order in which runnable processes or threads are dispatched to the CPU. Address translation belongs to the memory management unit, file mapping to the file system, and compilation to a compiler.

Question 9Computer Science Foundations and Computational Thinking

A process needs to read a file from disk. Which sequence of process states is most typical in a preemptive multitasking operating system?

  1. Waiting, then running, then ready, then waiting
  2. Running, then ready, then waiting, then terminated
  3. Ready, then running, then terminated, then waiting
  4. Running, then waiting, then ready, then running Correct answer.

Explanation

When a running process issues a blocking I/O request it moves to the waiting state, and once the I/O completes it becomes ready before being scheduled to run again. Termination only occurs when the process finishes.

Question 10Computer Science Foundations and Computational Thinking

What does it mean for a programming language to use short-circuit evaluation of the Boolean operator AND?

  1. Both operands are always evaluated before the result is computed
  2. The right operand is evaluated before the left operand
  3. The right operand is evaluated only if the left operand evaluates to true Correct answer.
  4. The operator returns the integer value 1 instead of a Boolean

Explanation

With short-circuit AND, a false left operand already determines a false result, so the right operand is skipped. This matters when the right operand has side effects or could raise an error.

Question 11Computer Science Foundations and Computational Thinking

Consider the array [5, 3, 8, 1]. After one complete pass of bubble sort that moves the largest element to the end, what is the array?

  1. [5, 3, 1, 8]
  2. [3, 5, 1, 8] Correct answer.
  3. [1, 3, 5, 8]
  4. [3, 5, 8, 1]

Explanation

Bubble sort compares adjacent pairs and swaps when out of order: 5 and 3 swap, 5 and 8 stay, then 8 and 1 swap. The result is [3, 5, 1, 8] with the largest value 8 at the end.

Question 12Computer Science Foundations and Computational Thinking

A hash table uses separate chaining and a load factor of 0.75. What is the primary purpose of resizing the table when the load factor is exceeded?

  1. To sort the keys stored in each bucket
  2. To reduce the memory used by the table
  3. To guarantee that no two keys ever hash to the same bucket
  4. To keep the average number of elements per bucket small so lookups stay near constant time Correct answer.

Explanation

Resizing increases the number of buckets, which lowers the average chain length and keeps average lookup cost close to O(1). Collisions can still occur, and resizing increases rather than decreases memory use.

Question 13Computer Science Foundations and Computational Thinking

Which statement correctly distinguishes a compiler from an interpreter?

  1. A compiler performs type checking, while an interpreter never performs type checking
  2. A compiler translates the whole program before execution, while an interpreter executes statements directly Correct answer.
  3. A compiler produces bytecode, while an interpreter always produces native machine code
  4. A compiler runs on the target machine, while an interpreter runs only on the host machine

Explanation

The defining difference is when translation happens: compilers translate source into another form ahead of execution, whereas interpreters process and execute the program as it is read. Either tool may perform type checking, and either may target bytecode or native code.

Question 14Computer Science Foundations and Computational Thinking

A grammar contains the productions S -> aS | b. Which language does it generate?

  1. Strings of one or more a characters followed by a single b Correct answer.
  2. Strings containing exactly one a and one b in any order
  3. All strings of a and b with equal counts of each
  4. Strings of one or more b characters followed by a single a

Explanation

Each application of S -> aS prepends an a, and the recursion ends with S -> b, so every derived string is one or more a characters followed by b. The grammar produces a regular language.

Question 15Computer Science Foundations and Computational Thinking

In a finite automaton, what distinguishes a deterministic finite automaton from a nondeterministic finite automaton?

  1. A DFA has exactly one transition per state and input symbol, while an NFA may have several or none Correct answer.
  2. A DFA has no accepting states, while an NFA has at least one
  3. A DFA uses a stack, while an NFA uses a queue
  4. A DFA accepts only finite languages, while an NFA accepts infinite languages

Explanation

Determinism means a single next state for each state-symbol pair, whereas an NFA may branch among multiple states or have no transition. Both models recognize exactly the regular languages.

Question 16Computer Science Foundations and Computational Thinking

A programmer writes a loop that counts from 1 to n and, inside the loop, performs a nested loop that runs from 1 to n. What is the growth rate of the total number of iterations?

  1. Theta(2 to the n)
  2. Theta(n log n)
  3. Theta(n)
  4. Theta(n squared) Correct answer.

Explanation

The inner loop runs n times for each of the n outer iterations, so the total work is proportional to n times n. This yields quadratic growth, written as Theta(n squared).

Question 17Computer Science Foundations and Computational Thinking

A directed graph is represented by an adjacency matrix. What is the time complexity of checking whether a specific edge (u, v) exists?

  1. O(V)
  2. O(E)
  3. O(1) Correct answer.
  4. O(V squared)

Explanation

An adjacency matrix stores a cell for every ordered pair of vertices, so checking an edge is a single indexed lookup. Scanning adjacency lists would take time proportional to the out-degree instead.

Question 18Computer Science Foundations and Computational Thinking

Which data structure is most appropriate for implementing a breadth-first search frontier that must process vertices in the order they were discovered?

  1. Priority queue ordered by key
  2. Binary search tree
  3. Queue Correct answer.
  4. Stack

Explanation

Breadth-first search processes vertices in first-in, first-out order so that all vertices at one distance are handled before moving further out. A queue provides exactly that ordering.

Question 19Computer Science Foundations and Computational Thinking

A network uses the IPv4 address 192.168.10.130 with subnet mask 255.255.255.192. Which address is the network address of this subnet?

  1. 192.168.10.128 Correct answer.
  2. 192.168.10.0
  3. 192.168.10.130
  4. 192.168.10.192

Explanation

The mask 255.255.255.192 leaves 6 host bits and a block size of 64, so subnets begin at multiples of 64 in the last octet. The address 130 falls in the block 128 through 191, making 192.168.10.128 the network address.

Question 20Computer Science Foundations and Computational Thinking

Which statement best explains why public-key cryptography is often combined with symmetric encryption in network protocols?

  1. Symmetric keys eliminate the need for any key distribution
  2. Symmetric ciphers are used only to sign messages, while public-key ciphers encrypt all traffic
  3. Public-key ciphers are faster than symmetric ciphers for large data transfers
  4. Public-key methods help exchange a shared secret, while symmetric ciphers handle bulk data faster Correct answer.

Explanation

Asymmetric cryptography solves the key distribution problem but is computationally expensive, so protocols use it to establish a shared session key and then encrypt traffic with a fast symmetric cipher. Symmetric encryption alone still requires a secure way to share the key.

Question 21Computer Science Foundations and Computational Thinking

In an object-oriented program, a subclass overrides a method declared in its superclass. Which concept allows a variable declared with the superclass type to invoke the subclass version at runtime?

  1. Dynamic dispatch Correct answer.
  2. Encapsulation
  3. Method overloading
  4. Multiple inheritance

Explanation

Dynamic dispatch selects the method implementation based on the object's actual runtime type rather than the declared variable type. Encapsulation concerns hiding internal state, and overloading resolves methods by signature at compile time.

Question 22Computer Science Foundations and Computational Thinking

A binary tree has 15 nodes and is perfectly balanced with every level completely filled. What is its height if height is counted as the number of edges on the longest root-to-leaf path?

  1. 4
  2. 15
  3. 3 Correct answer.
  4. 7

Explanation

A perfect binary tree with height h has 2 to the (h+1) minus 1 nodes. Solving 2 to the (h+1) minus 1 equals 15 gives h+1 equal to 4, so the edge-counted height is 3.

Question 23Computer Science Foundations and Computational Thinking

A programmer uses a debugger to step through code and observes that a variable holds an unexpected value after a function call. Which category of tool behavior is the programmer relying on?

  1. Link-time symbol resolution
  2. Runtime inspection of program state Correct answer.
  3. Static analysis of source code
  4. Lexical analysis of tokens

Explanation

A debugger observes the program while it executes, letting the programmer inspect live variable values and control flow. Static analysis examines code without running it, and lexical analysis and linking occur during translation.

Question 24Computer Science Foundations and Computational Thinking

A function is defined recursively as f(0) = 1 and f(n) = n times f(n-1) for n greater than 0. A memoized implementation is compared with a naive recursive one. What is the main benefit of memoization here?

  1. It changes the mathematical definition of the function
  2. It converts the recursion into an iterative loop automatically
  3. It reduces the recursion depth to a constant
  4. It stores previously computed results so repeated subproblems are not recomputed Correct answer.

Explanation

Memoization caches results keyed by argument so that any subproblem already solved is returned from the cache. For this recurrence the naive version already solves each subproblem once, so the gain is limited, but the mechanism is caching rather than restructuring control flow.

Question 25Computer Science Foundations and Computational Thinking

Which of the following is an example of a problem that is decidable but generally considered computationally intractable for large inputs?

  1. The problem of determining whether a string belongs to a given regular language
  2. The traveling salesperson decision problem for a general graph Correct answer.
  3. The halting problem for arbitrary programs
  4. The problem of adding two integers

Explanation

The traveling salesperson decision problem is decidable because a brute-force search over tours always terminates, but no polynomial-time algorithm is known, so it is treated as intractable. Regular language membership is solvable in linear time, and the halting problem is undecidable.

Question 26Computer Science Foundations and Computational Thinking

A programmer wants to express the algorithm for finding the largest value in a list of n numbers using pseudocode. Which characteristic most clearly distinguishes pseudocode from a program written in a formal programming language?

  1. Pseudocode uses natural-language phrases mixed with control structures and is not bound to the syntax rules of any executable language. Correct answer.
  2. Pseudocode can only represent sequence and selection, never iteration.
  3. Pseudocode requires every variable to be declared with an explicit data type before use.
  4. Pseudocode must be translated by a compiler before a computer can interpret its meaning.

Explanation

Pseudocode is a design and communication tool that borrows control structures such as loops and conditionals while using readable natural-language statements, so it is not tied to the grammar of a compilable language. Because it is not executable, it needs no compiler and imposes no strict declaration or typing rules.

Question 27Computer Science Foundations and Computational Thinking

A student evaluates the Boolean expression (x > 0) OR (y / x > 2) where the OR operator uses short-circuit evaluation. If x equals 0, what is the result of evaluating the expression?

  1. The whole expression evaluates to true without evaluating the division. Correct answer.
  2. The whole expression evaluates to false because the second operand is skipped.
  3. The expression raises a division-by-zero error because the second operand is always evaluated.
  4. The expression cannot be evaluated because the operands have mismatched types.

Explanation

With short-circuit OR, if the left operand is true the right operand is never evaluated, and the overall result is true. Since x > 0 is true when x is 0? No: x > 0 is false when x is 0, so the right operand would be evaluated and a division by zero would occur.

Question 28Computer Science Foundations and Computational Thinking

A software team models a campus map as an undirected weighted graph where vertices are buildings and edge weights are walking times in minutes. They need the fastest route from the library to the gym. Which algorithm and data structure combination is most appropriate?

  1. Dijkstra's algorithm using a priority queue, because it accounts for nonnegative edge weights. Correct answer.
  2. Depth-first search using a stack, because it explores each building exactly once.
  3. A topological sort using indegree counts, because the map has no cycles.
  4. Breadth-first search using a queue, because it minimizes the number of buildings visited.

Explanation

Walking times are nonnegative weights, so Dijkstra's algorithm with a priority queue finds the minimum total-weight path from a source vertex. Unweighted searches such as BFS or DFS optimize hop count or exploration order, not weighted travel time.

Question 29Computer Science Foundations and Computational Thinking

A database designer places a table in third normal form (3NF). Which condition must hold in addition to the table already being in second normal form?

  1. No non-prime attribute is transitively dependent on a candidate key. Correct answer.
  2. Every attribute in the table must be part of some candidate key.
  3. Every non-prime attribute depends on the whole primary key rather than on part of it.
  4. The table must contain no multivalued dependencies of any kind.

Explanation

Third normal form extends second normal form by eliminating transitive dependencies, meaning no non-key attribute may depend on another non-key attribute. Removing partial dependencies is the job of 2NF, and eliminating multivalued dependencies belongs to 4NF.

Question 30Computer Science Foundations and Computational Thinking

A recursive function computes the nth Fibonacci number using the definition F(0)=0, F(1)=1, and F(n)=F(n-1)+F(n-2). Without memoization, the number of calls grows exponentially, while a memoized version runs in linear time. Which statement best explains this improvement?

  1. Memoization sorts the subproblems by size, so the recursion depth becomes logarithmic.
  2. Memoization reduces the size of each subproblem, so fewer arithmetic operations are needed per call.
  3. Memoization converts the recursion into iteration, so the call stack is eliminated entirely.
  4. Memoization caches each distinct subproblem result, so overlapping subproblems are computed once instead of repeatedly. Correct answer.

Explanation

The naive recursion recomputes the same Fibonacci values many times because subproblems overlap. Memoization stores each result the first time it is computed and reuses it, reducing the work to one computation per distinct subproblem, which yields linear time.

Question 31Programming Fundamentals and Algorithm Design

In a binary search tree with no duplicate keys, which property must hold for every node?

  1. All keys in its left subtree are smaller and all keys in its right subtree are larger. Correct answer.
  2. All keys in its left subtree are larger and all keys in its right subtree are smaller.
  3. Its left child is always a leaf node and its right child is always an internal node.
  4. Every key in both subtrees is either larger or smaller depending on insertion order.

Explanation

A binary search tree orders keys so that everything reachable through the left child is less than the node key and everything through the right child is greater. This ordering is what makes search, insertion, and deletion follow a single root-to-leaf path.

Question 32Programming Fundamentals and Algorithm Design

A procedure calls itself with a smaller input on every invocation and stops when the input reaches a base case. Which characteristic does this describe?

  1. Recursion with a terminating condition Correct answer.
  2. Iteration using a loop counter
  3. Dynamic programming with memoization
  4. Parallel execution across threads

Explanation

Recursion occurs when a routine invokes itself, and it must make progress toward a base case so the call stack eventually unwinds. Without a reachable base case the calls continue until stack space is exhausted.

Question 33Programming Fundamentals and Algorithm Design

Which pair correctly matches a data structure with its defining access behavior?

  1. Stack: first-in, first-out retrieval
  2. Queue: last-in, first-out retrieval
  3. Heap: first-in, first-out retrieval
  4. Stack: last-in, first-out retrieval Correct answer.

Explanation

A stack pushes and pops at the same end, so the most recently added element is the first removed. A queue instead removes from the opposite end from which elements are added.

Question 34Programming Fundamentals and Algorithm Design

What is the average-case time complexity of searching for a key in a hash table with good hash distribution and low load factor?

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

Explanation

With uniform hashing and a bounded load factor, the expected number of probes per lookup stays constant, giving O(1) average time. Worst-case behavior degrades to O(n) when many keys collide.

Question 35Programming Fundamentals and Algorithm Design

Which sorting algorithm repeatedly selects the smallest remaining element and swaps it into the next position of the sorted prefix?

  1. Selection sort Correct answer.
  2. Insertion sort
  3. Quick sort
  4. Merge sort

Explanation

Selection sort scans the unsorted suffix for its minimum and exchanges it with the first unsorted position, growing a sorted prefix. It performs O(n^2) comparisons regardless of input order.

Question 36Programming Fundamentals and Algorithm Design

In most programming languages, which parameter-passing mechanism gives the called function a copy of the argument value?

  1. Pass by reference
  2. Pass by result
  3. Pass by name
  4. Pass by value Correct answer.

Explanation

Pass by value copies the argument into the parameter, so assignments inside the function do not affect the caller's variable. Pass by reference instead lets the function modify the caller's storage directly.

Question 37Programming Fundamentals and Algorithm Design

Which Boolean expression is logically equivalent to NOT (A AND B)?

  1. (NOT A) OR (NOT B) Correct answer.
  2. (NOT A) AND (NOT B)
  3. A AND B
  4. A OR B

Explanation

De Morgan's law states that the negation of a conjunction equals the disjunction of the negations. Applying it gives (NOT A) OR (NOT B).

Question 38Programming Fundamentals and Algorithm Design

A loop is written as: for i from 1 to n, for j from 1 to n, execute one constant-time statement. How many times does the statement execute?

  1. n
  2. n squared Correct answer.
  3. 2n
  4. n log n

Explanation

The outer loop runs n times and the inner loop runs n times for each outer iteration, so the statement executes n times n, which is n squared. Each execution is constant time, giving quadratic total work.

Question 39Programming Fundamentals and Algorithm Design

A queue is implemented with an array and two indices, front and rear, where rear marks the next free slot. After several enqueue and dequeue operations, rear reaches the end of the array while free slots remain at the beginning. What is the standard remedy?

  1. Double the size of the array every time rear reaches the end
  2. Reset front and rear to zero and discard the remaining elements
  3. Use a circular buffer so rear wraps around to index zero Correct answer.
  4. Switch to storing elements in a linked list sorted by value

Explanation

A circular buffer treats the array as a ring, so the rear index wraps to the start once it passes the last slot. This reuses freed space without moving elements or discarding data.

Question 40Programming Fundamentals and Algorithm Design

A singly linked list stores its head pointer only. Which operation requires time proportional to the list length?

  1. Inserting a new node at the head
  2. Reading the value stored in the head node
  3. Deleting the head node
  4. Appending a new node at the tail Correct answer.

Explanation

Without a tail pointer, appending requires traversing every node to find the last one, which costs O(n). Head insertion, head deletion, and reading the head value all take constant time.

Question 41Programming Fundamentals and Algorithm Design

A recursive function computes fib(n) as fib(n-1) + fib(n-2) with base cases fib(0)=0 and fib(1)=1, with no caching. What is the time complexity?

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

Explanation

Each call spawns two recursive calls, producing a call tree whose size grows exponentially with n. Memoizing previously computed values would reduce the cost to linear time.

Question 42Programming Fundamentals and Algorithm Design

An array contains the values 5, 3, 8, 1, and the algorithm performs insertion sort in ascending order. What does the array look like after the third element (8) has been processed?

  1. 3, 5, 8, 1 Correct answer.
  2. 5, 3, 8, 1
  3. 1, 3, 5, 8
  4. 3, 5, 1, 8

Explanation

Insertion sort keeps a sorted prefix. After processing 5 the prefix is 5; after 3 it becomes 3, 5; after 8 the prefix is 3, 5, 8 with 1 still unsorted.

Question 43Programming Fundamentals and Algorithm Design

A binary search on a sorted array of 1,000 elements compares the target with the middle element and discards half the remaining range each step. Approximately how many comparisons are needed in the worst case?

  1. 100
  2. 32
  3. 500
  4. 10 Correct answer.

Explanation

Binary search performs about log base 2 of n comparisons, and 2 to the tenth power is 1,024, so 10 comparisons suffice for 1,000 elements. Each comparison eliminates half of the remaining candidates.

Question 44Programming Fundamentals and Algorithm Design

Which statement about a min-heap stored in an array is correct?

  1. Each parent key is less than or equal to its children's keys Correct answer.
  2. Sibling keys must appear in sorted order
  3. The largest key is always stored at index zero
  4. The array is fully sorted in ascending order

Explanation

The heap property requires every parent to be no greater than its children in a min-heap, which places the minimum at the root. The rest of the array is only partially ordered, not sorted.

Question 45Programming Fundamentals and Algorithm Design

A program uses a stack to check whether parentheses in an expression are balanced. Which action should occur when a closing parenthesis is read?

  1. Ignore it and continue scanning
  2. Push it onto the stack
  3. Pop the stack and verify the top was the matching opening parenthesis Correct answer.
  4. Clear the entire stack

Explanation

Opening symbols are pushed and each closing symbol must match the most recent unmatched opener, so the top is popped and compared. A mismatch or an empty stack at that point signals unbalanced input.

Question 46Programming Fundamentals and Algorithm Design

A hash table uses open addressing with linear probing. Which situation most directly causes primary clustering?

  1. Keys are stored in sorted order within each bucket
  2. The hash function returns values uniformly across the table
  3. Two keys that hash to the same index probe adjacent slots, forming long runs Correct answer.
  4. The table is resized before it becomes full

Explanation

Linear probing places colliding keys in consecutive slots, so occupied runs grow and attract further collisions, lengthening probe sequences. This effect is called primary clustering.

Question 47Programming Fundamentals and Algorithm Design

A function is defined as f(0) = 2 and f(n) = 3 * f(n-1) for n greater than zero. What is f(3)?

  1. 54 Correct answer.
  2. 24
  3. 162
  4. 18

Explanation

Applying the recurrence gives f(1) = 6, f(2) = 18, and f(3) = 54. Each step multiplies the previous value by three.

Question 48Programming Fundamentals and Algorithm Design

Which algorithm design strategy does merge sort use?

  1. Greedy choice at each step
  2. Backtracking with pruning
  3. Divide and conquer Correct answer.
  4. Dynamic programming over a table

Explanation

Merge sort divides the array into halves, sorts each recursively, and merges the results, which is the divide-and-conquer pattern. The merge step combines sorted subproblems into a sorted whole.

Question 49Programming Fundamentals and Algorithm Design

A programmer writes a loop that compares adjacent elements and swaps them when out of order, repeating passes until no swaps occur. Which algorithm is this?

  1. Heap sort
  2. Radix sort
  3. Bubble sort Correct answer.
  4. Quick sort

Explanation

Bubble sort repeatedly compares adjacent pairs and swaps inversions, stopping early when a pass makes no swaps. This early exit makes the best case linear on already sorted input.

Question 50Programming Fundamentals and Algorithm Design

In a language with short-circuit evaluation, the expression (p != null) AND (p.value > 0) is evaluated. Why does this ordering matter?

  1. It prevents dereferencing a null pointer when p is null Correct answer.
  2. It forces both operands to be evaluated in parallel
  3. It guarantees the second operand is always evaluated
  4. It converts the expression into a bitwise operation

Explanation

Short-circuit AND skips the right operand when the left operand is false, so the null check guards the dereference. Reversing the order would evaluate p.value even when p is null.