first test bruh · guest · Algorithmics (HESS)

01 Binary search uses \(\lfloor(low+high)/2\rfloor\) on the sorted integers 1…63. How many values are inspected when searching for 63?

A 4 Does not fit this requirement.

B 6 The midpoint trace reaches 63 after 6 inspection(s).

C 8 Does not fit this requirement.

D 1 Does not fit this requirement.

Written for icaijy.com · U4 AOS2 · Binary search · answered at 4909 ms

02 Which term remains true before and after every loop iteration?

A input size Does not fit this requirement.

B postcondition Does not fit this requirement.

C loop invariant This describes a loop invariant.

D base case Does not fit this requirement.

Written for icaijy.com · U3 AOS2 · Correctness and modularity · answered at 11321 ms

03 A* uses f(n) = g(n) + h(n). Which frontier node should it expand next?

A Node A: g = 1, h = 12, f = 13 f = 13; another node has a smaller f.

B Node B: g = 3, h = 9, f = 12 f = 12; another node has a smaller f.

C Node C: g = 5, h = 5, f = 10 f = 10; another node has a smaller f.

D Node D: g = 7, h = 2, f = 9 f = 9; this is minimal.

Written for icaijy.com · U4 AOS2 · A* search · answered at 18648 ms

04 If A* uses h(n) = 0 for every node with non-negative edge weights, it behaves like

A depth-first search Does not fit this requirement.

B Dijkstra’s algorithm Then priority is cost-so-far only.

C Prim's algorithm Does not fit this requirement.

D PageRank Does not fit this requirement.

Written for icaijy.com · U4 AOS2 · Advanced design · answered at 23119 ms

05 A school system must represent cities and the roads joining them. Which ADT is most suitable?

A stack Does not fit this requirement.

B graph A graph models entities and relationships.

C dictionary Does not fit this requirement.

D set Does not fit this requirement.

Written for icaijy.com · U3 AOS1 · ADTs · answered at 29047 ms

06 To show new problem X is NP-Hard using known NP-Hard problem Y, the required polynomial reduction direction is

A P → Y Does not fit this requirement.

B Y → X Solving X would then solve Y.

C X → Y Does not fit this requirement.

D X → P Does not fit this requirement.

Written for icaijy.com · U4 AOS1 · Complexity limits · answered at 37657 ms

07 Use the supplied Master Theorem. What is T(n) if \(T(n)=4T(n/2)+O(n^1)\)?

A \(O(\log n)\) Does not fit this requirement.

B \(O(n^2)\) Compare \(a=4\) with \(b^c=2\).

C \(O(n)\) Does not fit this requirement.

D \(O(n^3)\) Does not fit this requirement.

Written for icaijy.com · U4 AOS1 · Recurrence relations · answered at 47375 ms

08 Binary search uses \(\lfloor(low+high)/2\rfloor\) on the sorted integers 1…63. How many values are inspected when searching for 31?

A 4 Does not fit this requirement.

B 3 Does not fit this requirement.

C 5 Does not fit this requirement.

D 6 The midpoint trace reaches 31 after 6 inspection(s).

Written for icaijy.com · U4 AOS2 · Binary search · answered at 50943 ms

09 A basic hill-climbing search may stop before the global optimum because of

A the Master Theorem Does not fit this requirement.

B a local optimum No improving neighbour may exist at a non-global optimum.

C a guaranteed negative cycle Does not fit this requirement.

D a queue overflow by definition Does not fit this requirement.

Written for icaijy.com · U4 AOS2 · Advanced design · answered at 57564 ms

10 How many edges are in an undirected complete graph with 7 vertices?

A 42 Does not fit this requirement.

B 21 There is one edge for each unordered pair: 7×6/2 = 21.

C 6 Does not fit this requirement.

D 49 Does not fit this requirement.

Written for icaijy.com · U3 AOS1 · Graph modelling · answered at 59963 ms