How many queries does it take to find the best flight?
There are problem parameters where you need $2^k$ queries in the worst case.  I'll prove this by giving an explicit example of an instance where you need $2^k$ queries.

Suppose $X = \{0,1\}^k$ and $A_i = \{x \in X : x_i = 1\}$ (this is without loss of generality in any case).  Suppose $\alpha_i = 1/2^i$.  Pick a single value $x^* \in X$, and define

$$f(x) = 1 - g(x) - 2^{-k-1} [x = x^*].$$

To any query set $X'$ we can associate a single element $m(X') = \arg \max_{x \in X'} g(x)$.  Notice that the results of the query $X'$ depends only on $m(X')$, and there are $2^k$ possible values for $m(X')$.  Thus we can identify each query with the value of $m(X')$, so effectively there are only $2^k$ different queries (where I consider two queries different if their value of $m(\cdot)$ differs; formally, consider the equivalence relation induced by $m(\cdot)$, choose one canonical representative for each equivalence class, and from here on we will assume that each query is one of these $2^k$ canonical representatives).  Now I claim that out of these $2^k$ possible queries, there is only a single one that gives you any useful information about $x^*$.  In particular, the only thing you learn about $x^*$, when you query on the set $X'$, is whether $x^* = m(X')$ or not.  Why?  If $x^* = m(X')$, then the oracle will return $x^*$, and you can recognize that this has happened by looking at the value of $f$.  However, if $x^* \ne m(X')$, then the oracle will return $m(X')$ as well as the value of $f$ on that element, and that is something you could have computed on your own using your knowledge of $g$, so you have learned nothing about $x^*$ other than that it is different from $m(X')$.  Moreover, there is only a single (canonical) set $X'$ where $x^* = m(X')$.

So, you have a search space of size $2^k$, and each query only lets you test a single candidate for $x^*$.  It's like playing a game where I think of a secret number, and you can ask me questions like "is your number 17?" where you replace 17 with any number of your choice.  It's easy to see that this game will require $2^k$ guesses in the worst case, and $2^{k-1}$ guesses on average.

So for that setting of weights, you can't do any better than $2^k$ queries.

(As a generalization, for your Question 2, this will require ${k \choose k'}$ queries in the worst case.)



In contrast, there also exist choices of weights where this allows an efficient solution.  Consider the case where $\alpha_1=\cdots=\alpha_k=1$.  Then you can query on the subsets $X'_0 = \{x \in X : g(x) = 0\}$, $X'_1 = \{x \in X : g(x)=1\}$, .., $X'_k= \{x \in X : g(x)=k\}$.  Then, take the best of those results -- the one that has the smallest value of $f(x)+g(x)$.  After doing $k+1$ queries, this is guaranteed to find you the optimal solution to the problem.  As a generalization, if the set of sums $\{\sum_i c_i \alpha_i : c \in \{0,1\}^k\}$ has cardinality Q, then Q queries suffice to obtain the exact answer.



So, ultimately, the number of queries needed to the oracle depends on the weights.  There are some choices where this might require many queries, and other choices where very few queries suffice.

One nice thing is that you can approximate the optimal value to within an additive error of $\delta$ using $(\sum_i \alpha_i)/\delta$ queries.  In particular, query the subset $X' = \{x \in X : g(x) \le t\}$ for $t:=\delta,2\delta,3\delta,\dots,\sum_i \alpha_i$.  Take the best solution found over all of those queries, and that will be at most $\delta$ worse than the optimum.