Impact on the order of elements on the cost of searching in a linked list
I'm assuming costs are strictly positive. Otherwise it doesn't make much sense to consider the quantity $P_i/C_i$.

Regarding 1: Consider any order, and suppose that for some $i$, $P_i/C_i &lt; P_{i+1}/C_{i+1}$. Suppose that we switch the elements $i$ and $i+1$. Say that we switched between $\ldots,A,B,\ldots$ and $\ldots,B,A\ldots$. Let $\Delta$ be the difference in average search cost (new cost minus old cost). When looking for $A$, which happens with probability $P_i$, we have to pay $C_{i+1}$ more. When looking for $B$, which happens with probability $P_{i+1}$, we have to pay $C_i$ less. So
$$ \Delta = P_i C_{i+1} - P_{i+1} C_i = (P_i/C_i - P_{i+1}/C_{i+1}) C_i C_{i+1} &lt; 0. $$
In other words, the switch was beneficial. We conclude that the optimal arrangement is to store the elements in non-increasing order.

How I found this proof: I tried to construct a counterexample by trying a few examples on two elements, but I didn't work. So I decided to write the inequalities enjoyed by such a counterexample, and solve them in order to find one. The solution showed that in fact no counterexample is possible. 

Regarding 2: This is quite easy to construct, especially in view of part 1, which gives a condition for optimality in case there are only two elements. I'm sure you can handle this part yourself.