NPCBL — Executive Trainee (Software) — Exam: 2023প্রশ্ন ও সমাধান

Correct answer: (c) 0 or 1 or 2

A binary tree is a tree in which each node has at most two children. The question means "how many children can a node of a binary tree have": a leaf has 0, a node with only a left or only a right child has 1, and a node with both has 2.

Why the other options are wrong

• (a) 2: exactly two children for every non-leaf is a full binary tree, a special case; ordinary binary trees also allow one child.
• (b) 0: only leaves have no children; otherwise the tree would be a single node.
• (d) Any number of children: that describes a general (n-ary) tree, not a binary tree.

Tip: Binary = at most 2 children per node: 0, 1 or 2.

Source: Lecture 6: Binary Trees I - 6.006 Introduction to Algorithms, MIT OpenCourseWare (Spring 2020)

Correct answer: (a) Fibonacci Series

F(n) = F(n − 1) + F(n − 2), so plain recursion computes the same values again and again: fib(30) needs 2,692,537 calls. Dynamic programming stores each F(k) once, either memoized top-down or in a bottom-up table, so only 31 subproblems are solved and the time drops from exponential to O(n). The problem has both DP ingredients: optimal substructure and overlapping subproblems.

Why the other options are wrong

• (b) Tower of Hanoi: the classic example of plain recursion (decrease and conquer). It must output all 2ⁿ − 1 moves (1,023 for n = 10), so storing sub-results cannot make it faster.
• (c) Dijkstra Shortest Path: it is normally classified as greedy, because at every step it settles the unvisited vertex with the smallest tentative distance.
• (d) None of the above: wrong, because (a) is a DP example.

Tip: DP = optimal substructure + overlapping subproblems. Fibonacci is the first example almost every DP lecture uses.

Source: MIT 6.006 Introduction to Algorithms (Fall 2011), Lecture 19: Dynamic Programming I — Fibonacci, Shortest Paths; NIST DADS: greedy algorithm

Correct answer: (a) 1

In C a return statement has the form return expression;. The expression is evaluated, the function ends, and that one result becomes the value of the function call. So a function can hand back only one value at a time.

To get several results out, you still return one thing: pack them in a struct (one value with several members), or pass pointers so the function writes the extra results into the caller's variables.

Why the other options are wrong

• (b) 2: A return takes a single expression. return a, b; uses the comma operator and returns only b.
• (c) 0: A void function returns nothing, but the question asks how many values a function can return; a non-void function returns exactly one.
• (d) more than 2: Same reason as (b); returning a struct or array pointer is still one returned value.

Tip: One call → one return value; use a struct or pointer parameters for more.

Source: return statement - cppreference.com

Correct answer: (c) ORDER BY

ORDER BY sorts the rows of a query result, ascending (ASC) by default or descending with DESC. Without it, rows come back in whatever order the engine finds fastest, so no order is guaranteed.

SELECT name FROM employee ORDER BY name;        -- Anik, Riaz, Toha
SELECT name FROM employee ORDER BY name DESC;   -- Toha, Riaz, Anik

Why the other options are wrong

• (a) SORT BY: Not an SQL clause; SQLite rejected it with a syntax error near "BY".
• (b) ALIGN BY: Not an SQL clause either; also a syntax error.
• (d) GROUP BY: It collects rows with equal values into one row per group for aggregates such as COUNT or SUM. It does not guarantee any output order; add ORDER BY when order matters.

Tip: Sort → ORDER BY; summarise per group → GROUP BY.

Sources: Sorting Rows (ORDER BY) - PostgreSQL Documentation; SELECT - PostgreSQL Documentation

Correct answer: (d) Deadlock annihilation

Deadlocks are handled in a small number of recognised ways: prevention (guarantee that deadlocks can never occur in the first place), avoidance (detect potential deadlocks in advance and act so that deadlock will not occur) and detection with recovery (allow deadlocks to form, then find and break them). "Deadlock annihilation" is not one of them; it is not a recognised deadlock-handling technique.

Why the other options are wrong

• (a) Deadlock prevention: a standard strategy; the system is arranged so that deadlocks can never occur in the first place.
• (b) Timeout: a real, practical method: a transaction that cannot get a resource may wait only for a fixed time interval, and if the resource does not become available, the requesting or the holding transaction is aborted. Database systems use lock-wait timeouts too; PostgreSQL, for example, waits on a lock for a set time (deadlock_timeout) before checking for a deadlock.
• (c) Deadlock detection and recovery: a standard strategy; deadlocks are allowed to form and are then found and broken.

Exam note: A timeout is usually counted as part of one of the main strategies (waiting a fixed interval and then aborting a transaction, or using the wait to trigger a deadlock check), not as a separate strategy. It is still a valid way of handling deadlock, so only (d) is "not a strategy".

Tip: The classic answers are prevention, avoidance and detection + recovery; anything else on the list is the odd one out.

Source: A survey of distributed deadlock detection algorithms (SIGMOD Record 15(3), 1986)
Source: Lock Management: deadlock_timeout (PostgreSQL Documentation)