FPSC- Programmer (BS-17) - PMD High Yield - 2026 — Test 5

Correct Answer: B. When exactly 0 or 2 vertices have odd degree
Explanation: If 0 vertices have odd degree, the graph has an Euler circuit. If exactly 2 do, the path runs between those two vertices. ALSO KNOW (related points): • What is the maximum number of edges in a simple undirected graph with n vertices? → n(n - 1)/2

Correct Answer: C. A B + C *
Explanation: The parentheses force A + B to be evaluated first. A B C + * would mean A * (B + C). ALSO KNOW (related points): • What is the value of the postfix expression 2 3 4 * +? → 14

Correct Answer: B. + A * B C
Explanation: Multiplication has higher precedence, so B * C forms a subtree under +. A B C * + is the postfix form. ALSO KNOW (related points): • What problem does linear probing in hashing suffer from? → Primary clustering • Which data structure is best suited to prefix searches, such as autocomplete? → Trie

Correct Answer: D. (rear + 1) % n == front
Explanation: front == rear means the queue is empty. Checking rear == n - 1 ignores the wraparound. ALSO KNOW (related points): • Which algorithm detects a cycle in a singly linked list using O(1) extra space? → Floyd's tortoise-and-hare (fast and slow pointers) • How can a queue be implemented using two stacks, and what is the amortized cost per operation? → Use an inbox stack and an outbox stack; the amortized cost is O(1)

Correct Answer: C. O(n)
Explanation: Most nodes are near the bottom of the heap and need very little sift-down work. Inserting the elements one at a time would cost O(n log n). ALSO KNOW (related points): • What is the worst-case search time in an unbalanced binary search tree? → O(n) • What is the time complexity of inserting at the tail of a singly linked list that has no tail pointer? → O(n) • What is the time complexity of searching for a key in a balanced BST (such as an AVL or red-black tree)? → O(log n) • What is the time complexity of reversing a singly linked list in place? → O(n) time and O(1) extra space

Correct Answer: B. At 2i + 1 and 2i + 2
Explanation: 2i and 2i + 1 is the 1-indexed formula, a common mix-up. ALSO KNOW (related points): • Which balance factors are allowed for each node of an AVL tree? → -1, 0, or +1 • When deleting a BST node that has two children, what replaces it? → Its inorder successor (or inorder predecessor) • Which data structure is typically used to implement a priority queue efficiently? → A binary heap

Correct Answer: C. Inorder and preorder
Explanation: Preorder and postorder cannot tell left children from right children when a node has only one child. ALSO KNOW (related points): • Which traversal of a binary search tree visits the keys in sorted order? → Inorder • How many structurally distinct BSTs can be built from 3 distinct keys? → 5 • For a binary tree with root A, left child B, and right child C, what are the preorder and postorder traversals? → Preorder ABC; postorder BCA • In a complete binary tree with n nodes, what is the height (counting edges)? → floor(log₂ n)

Correct Answer: D. 31
Explanation: The minimum is 2^n - 1 moves. ALSO KNOW (related points): • What is the time complexity of the Sieve of Eratosthenes up to n? → O(n log log n) • How many multiplications does fast (binary) exponentiation need to compute xⁿ? → O(log n) • What is the time complexity of Euclid's GCD algorithm? → O(log min(a, b)) • Which of these problems is NP-complete? → Boolean satisfiability (SAT) • What is true of the Halting Problem? → It is undecidable: no algorithm can decide whether an arbitrary program halts on an arbitrary input • What is the recursion depth of merge sort on n elements? → O(log n)

Correct Answer: C. OSI has 7; TCP/IP has 4
Explanation: Some textbooks use a 5-layer hybrid model, but the original TCP/IP model has 4 layers: Link, Internet, Transport, and Application. ALSO KNOW (related points): • What is the range of TCP and UDP port numbers? → 0 to 65535

Correct Answer: A. Presentation (Layer 6)
Explanation: A common mistake is to assign encryption to the Application or Transport layer. ALSO KNOW (related points): • At which OSI layer does routing between different networks happen? → Layer 3 (Network) • Which OSI layer establishes, manages, and synchronizes dialogs, for example with checkpoints? → Session (Layer 5) • Which OSI layers does the TCP/IP Application layer correspond to? → Layers 5, 6, and 7 (Session, Presentation, Application)