Identify trees, lists, and array search costs

Give concise answers for each part and justify the time complexities involved.

a) A data model requires every node to have no more than two children and exactly one parent. Identify the structure and list the common fields stored in each node. When keys are kept to support ordered lookups, give the average and worst-case search times by key, along with the property that must hold for the average case to apply.

b) You need a collection in which each item references the following item and allows $O(1)$ insertion at the front. Name this structure. Explain how to check whether it has a cycle, and state the time and space complexity of your approach.

c) Given an unsorted array of $n$ integers, what is the worst-case time needed to decide whether a target value is present? If the array is sorted, which algorithm would you apply and what time complexity does it give? Yes or no: can binary search be used on an unsorted array? Justify in one sentence.

Overview: This question tests familiarity with basic data structures (tree hierarchies, linear list structures, and arrays), time and space complexity analysis, and cycle-detection ideas.