On the first question:
FAA Advisory Circular 25-7C Flight Test Guide For Certification Of Transport Category Airplanes states:
(g) In accordance with § 25.21(c), stalls must be demonstrated up to the maximum approved operating altitude to determine if there are any adverse compressibility effects on stall characteristics. These tests should be flown with gear and flaps up at the most adverse c.g. Power or thrust may be set, as required, to maintain approximately level flight and a 1 knot/second deceleration. A slight descent rate is permissible as long as the stall occurs at approximately the maximum approved altitude. Characteristics should be checked during a wings level stall and in a 30-degree banked turn.
On the second question: Yes, compressibility definitely affects stall speed and stalling characteristics at high altitudes.