国开电大《数据结构与算法》形考实验任务1答案

1．请用循环队列编写程序求解素数环问题。
【实验目的】练习循环队列的使用，包括循环队列如何插入数据元素、删除数据元素等。
【实验要求】将1~n的自然数排列成环形，使得相邻两数之和为素数，构成一个素数环。
【实验分析】任意两数和为素数，可以从1开始找，对2~n进行测试，如果它与环中最后那个数的和为素数，则将其加入环中；否则暂时放回，待下次进行判断。
【实验步骤】素数环可以用循环队列实现，存放2~n的数可以用另一个队列。
Step1：建立空的素数环队列A，插入1。
Step2：建立存放待排数的队列B，依次插入2~n。
Step3：从队列B中取队头，计算与队列A队尾之和，如和为素数，则插入队列A；否则将取下的该队头插入队列B队尾。
Step4：继续重复Step3，直至队列B空。
2.请用栈实现数值转换(十进制转换为八进制)。
【实验目的】练习栈的使用，包括栈的入栈、出栈、取栈顶等操作。
【实验要求】利用一个顺序栈、除法运算及模运算将十进制数N转换为八进制数。
【实验分析】其转换方法利用辗转相除法（N/r），每次将除法结果放入N中，将得到的余数依次放入栈中，当除法结果为0时，依次出栈所有数据，即得到转换后的数据。
【实验步骤】当N>0时，重复Step1，Step2。
Step1：若 N≠0，则将N % r压入栈s中，执行Step2; 若N=0，则将栈s的内容依次出栈，算法结束。
Step2：用N / r代替 N。