On my many test worlds, the nether fortresses located in the valley of souls are spawned with basalt in the halls, and with halls interrupted by the world generation.

Postscript
It does not allow me to put images