信息学奥赛CSP-J模拟阅读程序1（链表）

题目：给定一个程序，请根据给定的程序回答下列判断题与选择题

#include<bits/stdc++.h>
using namespace std;
struct node {int d;node *nxt;
};
int isPrime(int x) {if(x==1)	return 0;for(int i=2;i<x;i++) if(x%i==0)return 0;return 1;
}
int main()
{int n;cin >> n;node *h = new node;node *q = h;for(int i=1;i<=n;i++) {node *p = new node;p->d = i;p->nxt = NULL;q->nxt = p;q = p;}q = h->nxt;node *p = h;while(q!=NULL) {if(isPrime(q->d)) {p->nxt = q->nxt;q = q->nxt;}else  {p = p->nxt;q = q->nxt;}}for(q=h->nxt;q!=NULL;q=q->nxt)cout << q->d << " ";cout << endl;return 0;
}

一、判断题

1、本程序用到了双向链表的技术。（    ）

2、将第10行i<x改为i*i<=x，程序运行输出结果不会改变。（    ）

3、将第24行p->nxt=NULL，改为p->nxt=NIL，程序运行输出结果不会改变。（    ）

4、将第31行if(isPrime(q->d))改为if(!isPrime(q->d))，程序运行输出结果会改为打印1到n之间的所有质数。（    ）

二、选择题

1、若输入10，则输出（    ）

A. 1 4 6 8 9 10

B. 2 3 5 7

C. 4 6 8 9 10

D. 1 2 3 5 7

2、若输入2024，则输出的数字总数为（    ）

A. 1716

B. 1717

C. 1718

D. 1719

---

三、程序解读        

在这里，我将把代码分片，重点讲述每一片代码块的功能，最后将其串联起来阐述整个程序所实现的功能与注意事项。

struct node {int d;node *nxt;
};

        定义一个结构体，包含两个成员变量，分别为整型数字d和结构体指针nxt，d用来存储当前该节点的数字，而nxt用来存储当前节点下一个节点的地址，用来指向当前节点的下一个节点。 

int isPrime(int x) {if(x==1)	return 0;for(int i=2;i<x;i++) if(x%i==0)return 0;return 1;
}

         判断x是否为质数，如果是，该函数返回1，否则返回0。注意，此处判断质数的方法是最原始、最暴力的方法，直接从2判断到x-1，因为质数的定义是：只能被1和本身整除的数称为质数，那么就意味着，2~x-1但凡有某个数能够把x整除，那么x就不是质数。

int n;
cin >> n;
node *h = new node;
node *q = h;
for(int i=1;i<=n;i++) {node *p = new node;p->d = i;p->nxt = NULL;q->nxt = p;q = p;
}
q = h->nxt;
node *p = h;

         n代表链表的具有n个节点，其中一开始的时候，h指向头节点，q也指向头节点。接下来使用一个for循环构造单链表，例如当n=6时，链表情况如下图所示，其中绿色代表头节点，蓝色代表真正的数据节点。

        当for循环结束后，让q指向第1个节点，p指向头节点，如下图所示。 

while(q!=NULL) {if(isPrime(q->d)) {p->nxt = q->nxt;q = q->nxt;}else  {p = p->nxt;q = q->nxt;}
}

         我们重点来解析一下这段代码，可以代入具体的例子 n = 6。

        第一轮循环：q指向第1个节点，即q!=NULL，执行while循环，首先判断q指向的节点数据是否为质数，此时q指向第1个节点，第1个节点的数据值为1，发现不是质数，执行else代码块语句，让p指针指向原来p指针所指向节点的下一个节点，让q指针指向原来q指针所指向节点的下一个节点，即p指向第1个节点，q指向第2个节点，如下图所示

        第二轮循环，q指向第2个节点，即q!=NULL，执行while循环，首先判断q指向的节点数据是否为质数，此时q指向第2个节点，第2个节点的数据值为2，发现是质数，执行if代码块中的语句，让原来p指向的节点的指针域存储原来q指向节点的下一个节点的地址，紧接着让q本身指向自己指向的下一个节点。然后让q指针指向原来q指针指向的节点的下一个节点。如下图所示：

        第三轮循环，q指向第3个节点，即q!=NULL，执行while循环，首先判断q指向的节点数据是否为质数，此时q指向第3个节点，第3个节点的数据值为3，发现是质数， 指向if代码块中的语句，根据上一轮循环的讲解，此时p、q指针的指向情况如下图所示：

        第四轮循环，q指向第4个节点，即q!=NULL，执行while循环，首先判断q指向的节点数据是否为质数，此时q指向第4个节点，第4个节点的数据值为4，发现不是质数，执行else代码块中的语句， 根据第一轮循环的讲解，此时p、q指针的指向情况如下图所示：

        第五轮循环，q指向第5个节点，即q!=NULL，执行while循环，首先判断q指向的节点数据是否为质数，此时q指向第5个节点，第5个节点的数据值为5，发现是质数，执行if代码块中的语句，同理，此时p、q指针的指向情况如下图所示： 

        第六轮循环，q指向第6个节点，即q!=NULL，执行while循环，首先判断q指向的节点数据是否为质数，此时q指向第6个节点，第6个节点的数据值为6，发现不是质数， 执行else代码块中的语句，同理，此时p、q指针的指向情况如下图所示：

        此时q==NULL，while条件成立，退出循环！ 

for(q=h->nxt;q!=NULL;q=q->nxt)cout << q->d << " ";

         当while循环结束后，链表的整体情况如下图所示：

        只要q不等于NULL，那么就一直输出每个节点的数据，因此输出结果为1 4 6。 

        将程序放入编译器中编译并且运行，得到验证结果如下图所示：

        相信大家听完上述的讲解之后，能够大概猜测出此此程序的用处 — 没错，它的作用就是使用链表来筛选出所有非质数数据。如上所述的这种数据结构为们称之为单链表，它属于线性数据结构，其中每个节点包含指向下一个节点的指针，如果要进行数据的查找，只能从第1个节点开始从头往后查找，效率较低。

---

四、答案解读

判断题：

1、本程序用到了双向链表的技术。（    ）

答案：错误

解析：该题考察单链表和双链表的概念，我们先来看一幅图，你就能够从宏观上看出单链表和双链表的区别。

        根据观察，我们发现 ，双链表的每一个节点都有两个指针，一个指向前面的节点（前驱节点），另一个指向后面的节点（后继节点）。且双链表既可以从表头（第一个节点）向后遍历，也可以从表尾（最后一个节点）向前遍历，对于双链表来说，它在进行插入和删除操作时可以更方面地定位节点，因此我们可以给出双链表的准确定义：双链表是一种线性数据结构，它是单链表的扩展。与单链表不同，双链表中的每个节点不仅包含指向下一个节点的指针（后继指针），还包含指向前一个节点的指针（前驱指针）。这种双向链接的特性使得双链表在某些操作上比单链表更灵活。

2、将第10行i<x改为i*i<=x，程序运行输出结果不会改变。（    ）

答案：正确

解析：我们知道，对于任意一个正整数都可以表示为：n = p*q，假设p<=q，且p、q两个数据当中，其中p是小于等于根号n的，而q是大于等于根号n的。

        这样子讲好像很抽象对不对，那我们来举例子，例如，对于36，36可以表示为两个数字相乘的式子有如下那么几个：

36 = 1 * 36

36 = 2 * 18

36 = 3 * 12

36 = 4 *  9

36 = 6 * 6 

        在此处，p的取值有1、2、3、5、6，q的取值为36、18、12、9、6。我们会发现p的取值都是小于等于根号36=6的，而q的取值都是大于等于根号36=6的，那意味着什么呢？ — 若在2~根号n范围内没有n的因数，那么n必然是质数，若在这个范围内存在因数，那么n就不是质数。例如对于n=36，在2~根号36=6之间存在36的因数，那么36不是质数，而对于17而言，在2~根号17=4之间没有17的因数，那么17一定是一个质数。因此在进行范围判断的时候，可以不必从2判断到n-1，而是从2判断到根号n即可，因为如果n有因数，那么必然有因数是小于或等于根号n的，这样子可以提高程序的效率。

        因此可以将i<x修改为i*i<=x。此时i不必增加到n-1了，只需要让其增加到根号n即可，此时i*i<=x等价于i<=根号x。

3、将第24行p->nxt=NULL，改为p->nxt=NIL，程序运行输出结果不会改变。（    ）

答案：错误

解析：送分题啊，你不要做成送命题了。在C++中，NULL等价于0，同时如果将其赋值给指针变量，那么代表当前指针不指向任何地址空间。若改成NIL，会出现编译错误，C++根本不认识这个单词的含义。

4、将第31行if(isPrime(q->d))改为if(!isPrime(q->d))，程序运行输出结果会改为打印1到n之间的所有质数。（    ）

答案：正确

解析：if(isPrime(q->d))当该条件成立（是质数），那么就跳过当前的质数节点，如果对其结果进行取反，那么就是当该条件不成立（不是质数），整体条件成立，跳过当前非质数节点。因此此时会筛选出所有的非质数节点，程序验证结果如下图所示：

选择题：

1、若输入10，则输出（    ）

A. 1 4 6 8 9 10

B. 2 3 5 7

C. 4 6 8 9 10

D. 1 2 3 5 7

答案：A

解析：本程序的作用是使用链表筛选出1~n所有的非质数节点，且输出每一个节点的值。因此当输入10，输出的结果为1、4、6、8、9、10。

2、若输入2024，则输出的数字总数为（    ）

A. 1716

B. 1717

C. 1718

D. 1719

答案：C

解析：题目实际上问的是1~2024，有多少个非质数，那我们转换一下思路，用总的数字，减去1~2024的质数个数，得到的就是1~2024的非质数总数。问题来了，1~2024的质数个数怎么计算呢？暴力算需要很长的时间，1~2024共有306个质数，那么非质数个数有2024-306=1718个。这题我是用程序验证的，因为觉得很费时，没有手动从头算，不然就只能靠平时的积累了，比如平时有背过1~2000的质数个数，那这个时候就会轻松一些。