PDS/Phase 7 · Integration & Final Test

Answer key 7.4-key · Item 103 of 103

Final Test — Answer Key🛑Stop here until you have finished the 90-minute final test.🔑 Open the full answer keyQ1 Answer: (C)1 mark6 & 3 = 2, 6 | 3 = 7, 6 ^ 3 = 5; + binds tighter than <<: 1 << 4.Output2 7 5 16(A) is wrong: 1 << 4 is 16.(B) is wrong: Precedence: 3 + 1 is computed first.(D) is wrong: 110 & 011 = 010.Re-read: Lesson 1.1.2 — Operators: arithmetic, relational, logical with short-circuiting, bitwise, assignment, ++ and --; precedence and associativity; undefined behaviorQ2 Answer: 151 markn = 3, 6, 9, 12, 15; 15 % 5 = 0 ends the loop.Output15Re-read: Lesson 1.2.2 — for, while, do-while; break and continue; tracing loop output and counting iterationsQ3 Answer: (D)1 markmul(add(2, 3), 4).Output20(A) is wrong: That is 2 + 3 + 4.(B) is wrong: That is 2 · 3 + 4.(C) is wrong: That is 2 + 3 · 4.Re-read: Lesson 1.8 — Preprocessor macros and their expansion traps; function pointersQ4 Answer: (D)1 markPrinting after the call reverses the string.Outputetag(A) is wrong: Print comes after recursion.(B) is wrong: Every character prints.(C) is wrong: Every character prints.Re-read: Lesson 2.1.3 — Classic patterns: factorial, Fibonacci, GCD, power, Tower of Hanoi (2ⁿ−1 moves), digit/array recursionQ5 Answer: 631 mark2⁶ − 1.Output63Re-read: Lesson 2.1.3 — Classic patterns: factorial, Fibonacci, GCD, power, Tower of Hanoi (2ⁿ−1 moves), digit/array recursionQ6 Answer: (B)1 markThe parameter is a pointer.(A) is wrong: sizeof counts bytes.(C) is wrong: No such size.(D) is wrong: That is sizeof the array in the caller.Re-read: Lesson 1.5.1 — 1-D arrays; a[i] == *(a+i) == i[a]; arrays decaying to pointers; passing arrays to functions; the sizeof trapQ7 Answer: 13001 mark1000 + (7·10 + 5)·4.Re-read: Lesson 3.1 — Arrays as a data structure: the ADT idea; address calculation (row-major, column-major, non-zero lower bounds); cost of insert, delete and searchQ8 Answer: 141 markC(4).Re-read: Lesson 3.2.3 — Valid stack permutations; Catalan numbersQ9 Answer: (C)1 markEach element moves between the stacks once.(A) is wrong: Only a single refill can cost O(n).(B) is wrong: Far too large.(D) is wrong: No tree involved.Re-read: Lesson 3.3.3 — Deque; priority queue as a concept; queue from two stacks and stack from two queues (operation costs)Q10 Answer: (C)1 markThe previous node of the last must be found.(A) is wrong: O(1).(B) is wrong: O(1).(D) is wrong: O(1).Re-read: Lesson 3.4.1 — Singly linked list: node, head, traversal, search, insertion (head/tail/middle), deletionQ11 Answer: 631 mark2⁶ − 1.Re-read: Lesson 4.2.2 — Binary tree properties: nodes per level and height; n₀ = n₂ + 1; minimum and maximum heightQ12 Answer: (B)1 markLeft, node, right.(A) is wrong: Root last.(C) is wrong: Root first.(D) is wrong: By depth.Re-read: Lesson 4.5.1 — The BST property; search, minimum, maximum; inorder gives sorted orderQ13 Answer: 201 markN(5) = 12 + 7 + 1.Re-read: Lesson 4.6 — Balanced BSTs — AVL idea, balance factor, rotations, minimum nodes for a given heightQ14 Answer: (A)1 markSum of node heights.(B) is wrong: Every key is read.(C) is wrong: Too large.(D) is wrong: That is n insertions.Re-read: Lesson 5.3 — Build-heap in O(n) vs n insertions; heap sortQ15 Answer: 191 mark(30 + 8)/2.Re-read: Lesson 6.1 — Graph vocabularyQ16 Answer: (D)2 marks(*(p + 1))[1] is a[1][1]; *(*p + 4) is the 5th int from a[0][0].Output5 5(A) is wrong: Index 1 in row 1 is 5.(B) is wrong: p + 1 is row 1.(C) is wrong: *p + 4 is &a[0][4] = &a[1][1].Re-read: Lesson 1.5.2 — 2-D arrays; row-major layout; pointer to array vs array of pointers; reading complex declarationsQ17 Answer: (C)2 marksq is a[2]; (q − 1) is a[1] with y = 1; P holds two ints.Output2 1 8(A) is wrong: sizeof(P) is 8.(B) is wrong: q->x is 2.(D) is wrong: a[1].y = 1·1.Re-read: Lesson 1.7 — Dynamic memory: malloc, calloc, realloc, free; stack vs heap; dangling pointers, memory leaks, double freeQ18 Answer: (D)2 marksOnly 10…40 fit; pop 40 and 30, push 70 at index 2.Outputfull 70 2(A) is wrong: The fifth push prints full.(B) is wrong: 50 was never pushed.(C) is wrong: Two pops then one push: top is 2.Re-read: Lesson 3.2.1 — Stack ADT; push/pop/peek; array implementation; overflow and underflowQ19 Answer: 132 marksBottom-up: f(0) = f(1) = f(2) = 1; f(3) = f(2) + f(0) = 2; f(4) = 2 + 1 = 3; f(5) = 3 + 1 = 4; f(6) = 4 + 2 = 6; f(7) = 6 + 3 = 9; f(8) = f(7) + f(5) = 9 + 4 = 13.Re-read: Lesson 2.1.4 — Computing what a recursive function returns via its recurrence; static and global variables inside recursionQ20 Answer: (C)2 marksBoth loops run about log₂ n times.(A) is wrong: Neither loop is linear.(B) is wrong: The inner loop is logarithmic.(D) is wrong: Two nested logarithmic loops.Re-read: Lesson 2.2 — Counting work: a Big-O primerQ21 Answer: (A) (B) (C) (D)2 marksAt the "−" the stack holds a b c d.Re-read: Lesson 3.2.2 — Stack applications: parenthesis matching; infix → postfix/prefix conversion; postfix evaluationQ22 Answer: 22 marksrear moves 12 times: 12 % 10 = 2 (the queue holds 8 ≤ 9).Re-read: Lesson 3.3.2 — Circular queue: full/empty conditions and index arithmeticQ23 Answer: (D)2 marksBypass p from both sides, then free it.(A) is wrong: Neighbours still point to p.(B) is wrong: Changes only p’s own links.(C) is wrong: Uses p after free.Re-read: Lesson 3.4.3 — Doubly and circular linked lists; operation costs compared with arraysQ24 Answer: 22 marksPostorder 4 5 2 6 7 3 1.Re-read: Lesson 4.3.3 — Rebuilding a tree from two traversals; counting distinct binary trees (Catalan)Q25 Answer: 32 marksLongest path 15 → 10 → 8 → 6 (also 15 → 20 → 25 → 27).Re-read: Lesson 4.5.2 — BST insertion; building a BST from an insertion sequence; best- vs worst-case heightQ26 Answer: (A)2 marksLeft {1, 2}: C(2) = 2; right {4, 5, 6}: C(3) = 5; 2 × 5.(B) is wrong: That is only the right side.(C) is wrong: Not doubled again.(D) is wrong: C(4) is unrelated.Re-read: Lesson 4.5.4 — BST GATE drills: BST from a preorder/postorder sequence; number of BSTs; valid search paths; insertion orders giving the same BSTQ27 Answer: (A)2 marks5 moves to the root and sinks below 2.(B) is wrong: 2 is the smaller child.(C) is wrong: The last key goes to the root first.(D) is wrong: 4 does not move.Re-read: Lesson 5.2 — Heap insertion (sift-up) and deleting the root (sift-down)Q28 Answer: 82 marksC(4, 3)·2·1.Re-read: Lesson 5.4 — Heap GATE drills: k-th largest, number of heaps, comparisons, d-ary heapsQ29 Answer: (A) (C)2 marksLevels {A}, {B, C}, {D}, {E}, {F}.(B) is wrong: E (distance 3) cannot precede D.(D) is wrong: C (distance 1) must come before D (distance 2).Re-read: Lesson 6.3 — Graph traversals: BFS, DFS, connected componentsQ30 Answer: 362 marksK₉ plus one isolated vertex: (10 − 2)(10 − 1)/2.Re-read: Lesson 6.1 — Graph vocabulary

Read at your own pace. Try the questions before opening the answers.