1、程序员-数据结构与算法(五)及答案解析(总分：100.00，做题时间：90 分钟)一、试题一(总题数：1，分数：20.00)阅读以下说明和流程图，填补流程图中的空缺。说明平面上一个封闭区域内稳定的温度函数是一个调和函数，如果区域边界上各点的温度是已知的(非常数)，那么就可以用数值方法近似地计算出区域内各点的温度(非负数)。假设封闭区域是矩形，可将整个矩形用许多横竖线切分成比较细小的网格，并以最简单的方式建立坐标系统，从而可以将问题描述为：已知调和函数 u(i,j)在矩形 0im;0jn)四边上的值，求函数 u 在矩形内部各个网格点 i=1,m-1;j=1,n-1 上的近似值。根据调和函数的特点
2、可以推导出近似算式：该矩形内任一网格点上的函数值等于其上下左右四个相邻网格点上函数值的算术平均值。这样，我们就可以用迭代法来进行数值计算了。首先将该矩形内各网格点上的函数值设置为一个常数，例如 u(0,0)；然后通过该迭代式计算矩形内个网格点上的新值。这样反复进行迭代计算，若某次迭代后所有的新值与原值之差别都小于预定的要求(例如 0.01)，则结束求解过程。流程图（分数：20.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_二、试题二(总题数：1，分数：20.00)阅读以下说明和 C 程序，填充程序中的空缺。说明埃拉托斯特尼筛法求不超过自然数 N 的所有素数的做法是
3、：先把 N 个自然数按次序排列起来，1 不是素数，也不是合数，要划去；2 是素数，取出 2(输出)，然后将 2 的倍数都划去；剩下的数中最小者为 3，3 是素数，取出 3(输出)，再把 3 的倍数都划去；剩下的数中最小者为 5，5 是素数(输出)，再把 5 的倍数都划去。这样一直做下去，就会把不超过 N 的全部合数都筛掉，每次从序列中取出的最小数构成的序列就是不超过 N 的全部质数。下面的程序实现埃拉托斯特尼筛法求素数，其中，数组元素 sievei(u0)的下标 i 对应自然数i，sievei的值为 1/0 分别表示 i 在/不在序列中，也就是将 i 划去(去掉)时，就将 sievei设置为
4、0。C 程序#include stdio.h#define N 10000int main()char sieveN+1=(0);int i=0,k;/*初始时 2N 都放入 sieve 数组*/for(i=2;_;i+)sievei=1;for(k=2;)/*找出剩下的数中最小者并用 K 表示*/for(;kN+1sievek=0;_);if(_)break;print(“%d/t“,k); /*输出素数*/*从 Sieve 中去掉 k 及其倍数*/for(i=k;iN+1;i=_)_;return 0;/*end of main*/（分数：20.00）填空项 1:_填空项 1:_填空项 1
5、:_填空项 1:_填空项 1:_三、试题三(总题数：1，分数：20.00)阅读以下说明和 C 程序，填充函数中的空缺。说明N 个游戏者围成一圈，从 1N 顺序编号，游戏方式如下；从第一个人开始报数(从 1 到 3 报数)，凡报到3 的人退出圈子，直到剩余一个游戏者为止，该游戏者即为获胜者。下面的函数 playing(Linklist head)模拟上述游戏过程并返回获胜者的编号。其中，N 个人围成的圈用一个包含 N 个结点的单循环链表来表示，如图 1 所示，游戏者的编号放在结点的数据域中。在函数中，以删除结点来模拟游戏者退出圈子的处理。整型变量 c(初值为 1)用于计数，指针变量 p 的初始值
6、为。head(如图 1 所示)。游戏时，从 p 所指向的结点开始计数，p 沿链表中的指针方向遍历结点，c的值随 p 的移动相应地递增。当 c 计数到 2 时，就删除 p 所指结点的下一个结点(因下一个结点就表示报数到 3 的游戏者)，如图 2 所示，然后将 c 设置为 0 后继续游戏过程。（分数：20.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_四、试题四(总题数：1，分数：20.00)阅读以下说明和流程图，回答下面问题。说明图 1 所示的流程图中有两个判断条件 A0 和 B0。这些判断条件的各种组合情况如图 2 所示。表中 Y 表示相应的条件成立，N 表示相应
7、的条件不成立。每一列表示一种条件组合，并在列首用相应的序号来表示。（分数：20.00）(1).当遇到哪几种条件组合时，流程图能执行“1i”?(写出相应的序号即可)（分数：5.00）_(2).当遇到哪几种条件组合时，流程图能执行“2j”?(写出相应的序号即可)（分数：5.00）_(3).当遇到哪几种条件组合时，流程图能执行“3k”?(写出相应的序号即可)（分数：5.00）_(4).该流程图共有多少条实际执行路径?流程图*（分数：5.00）_五、试题五(总题数：1，分数：20.00)阅读以下说明和流程图，将应填入_处的字句写在对应栏内。说明下面的流程图旨在统计指定关键词在某一篇文章中出现的次数。设
8、这篇文章由字符 A(0),A(n-1)依次组成，指定关键词由字符 B(0),B(m-1)依次组成，其中nm1。注意，关键词的各次出现不允许有交叉重叠。例如，在“aaaa”中只出现两次“aa”。该流程图采用的算法是：在字符串 A 中，从左到右寻找与字符串 B 相匹配的并且没有交叉重叠的所有子串。流程图中，i 为字符串 A 中当前正在进行比较的动态子串首字符的下标，j 为字符串 B 的下标，k 为指定关键词出现的次数。流程图（分数：20.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_程序员-数据结构与算法(五)答案解析(总分：100.00，做题时间：90 分钟)一、试
9、题一(总题数：1，分数：20.00)阅读以下说明和流程图，填补流程图中的空缺。说明平面上一个封闭区域内稳定的温度函数是一个调和函数，如果区域边界上各点的温度是已知的(非常数)，那么就可以用数值方法近似地计算出区域内各点的温度(非负数)。假设封闭区域是矩形，可将整个矩形用许多横竖线切分成比较细小的网格，并以最简单的方式建立坐标系统，从而可以将问题描述为：已知调和函数 u(i,j)在矩形 0im;0jn)四边上的值，求函数 u 在矩形内部各个网格点 i=1,m-1;j=1,n-1 上的近似值。根据调和函数的特点可以推导出近似算式：该矩形内任一网格点上的函数值等于其上下左右四个相邻网格点上函数值的算
10、术平均值。这样，我们就可以用迭代法来进行数值计算了。首先将该矩形内各网格点上的函数值设置为一个常数，例如 u(0,0)；然后通过该迭代式计算矩形内个网格点上的新值。这样反复进行迭代计算，若某次迭代后所有的新值与原值之差别都小于预定的要求(例如 0.01)，则结束求解过程。流程图（分数：20.00）填空项 1:_ （正确答案：0 或任意一个负数）解析：填空项 1:_ （正确答案：(u(i,j+1)+u(i,j-1)+u(i-1,j)+u(i+1,j)/4）解析：填空项 1:_ （正确答案：max）解析：填空项 1:_ （正确答案：new 或(u(i,j+1)+u(i,j-1)+u(i-1,j)+
11、u(i+1,j)/4 或等价表示）解析：填空项 1:_ （正确答案：max）解析：本题是要完成一个算法的流程。(1)是给 max 赋初始值，由于本题所涉及到的数据都是非零数，故可以给 max 赋值为 0 或者为任意一个负数。(2)循环开始后，本题要算的是该矩形内任一网格点上的函数值 new，该值等于其上下左右 4 个相邻网格点上函数值的算术平均，所以 new 为(u(i,j+1)+u(i,j-1)+u(i-1,j)+u(i+1,j)/4。(3)循环继续进行，如果u(i,j)-newmax，则将u(i,j)-new的值赋值给 max，所以填 max，(4)若u(i,j)-newmax 不成立，则
12、将 new 或者(u(i,j+1)+u(i,j-1)+u(i-1,j)+u(i+1,j)/4 赋值给 u(i,j)。(5)循环结束，判断 max 是否小于 0.01，故填 max。如果成立，则迭代算法结束，若不成立，则继续迭代算法。二、试题二(总题数：1，分数：20.00)阅读以下说明和 C 程序，填充程序中的空缺。说明埃拉托斯特尼筛法求不超过自然数 N 的所有素数的做法是：先把 N 个自然数按次序排列起来，1 不是素数，也不是合数，要划去；2 是素数，取出 2(输出)，然后将 2 的倍数都划去；剩下的数中最小者为 3，3 是素数，取出 3(输出)，再把 3 的倍数都划去；剩下的数中最小者为
13、5，5 是素数(输出)，再把 5 的倍数都划去。这样一直做下去，就会把不超过 N 的全部合数都筛掉，每次从序列中取出的最小数构成的序列就是不超过 N 的全部质数。下面的程序实现埃拉托斯特尼筛法求素数，其中，数组元素 sievei(u0)的下标 i 对应自然数i，sievei的值为 1/0 分别表示 i 在/不在序列中，也就是将 i 划去(去掉)时，就将 sievei设置为 0。C 程序#include stdio.h#define N 10000int main()char sieveN+1=(0);int i=0,k;/*初始时 2N 都放入 sieve 数组*/for(i=2;_;i+)s
14、ievei=1;for(k=2;)/*找出剩下的数中最小者并用 K 表示*/for(;kN+1sievek=0;_);if(_)break;print(“%d/t“,k); /*输出素数*/*从 Sieve 中去掉 k 及其倍数*/for(i=k;iN+1;i=_)_;return 0;/*end of main*/（分数：20.00）填空项 1:_ （正确答案：iN+1 或其等价形式）解析：填空项 1:_ （正确答案：k+或+k 或其等价形式）解析：填空项 1:_ （正确答案：kN 或 k=N+1 或其等价形式）解析：填空项 1:_ （正确答案：i+k 或其等价形式）解析：填空项 1:_ （
15、正确答案：sievei=0 或其等价形式）解析：本题要求是完成程序，该程序的功能是找到不超过自然数 N 的所有素数。首先在初始时 2N 都放入 sieve 数组中，所以 i 的取值范围为 2N，包含 N，所以第一空应该填 i 的最大取值为 N，所以第一空填 iN+1 或者 i=N，并赋值 sievei=1，表示所有的数，无论是否为素数都放入数组中，接下来找出剩下的数中最小者并用 K 表示，在 for 循环中，每执行一次循环就 k 值就要加 1，所以第二空应该填 k+或+k 或其等价形式，当循环执行到 kN 或 k=N+1 时，即 k 值超过了 N 值时，该循环结束用 break 跳出里面的循环
16、语句，故第三空应该填 kN 或 k=N+1 或其等价形式，接下来输出素数，再删除素数的倍数，这也是一个循环语句，此时变量 i 是从 i 开始到 i+k 结束，所以第四空应填 i+k 或其等价形式，找到是素数的倍数后，再将该素数的倍数赋值为 0，从 sievei数组中划去，所以第五空应填 sievei=0 或其等价形式。三、试题三(总题数：1，分数：20.00)阅读以下说明和 C 程序，填充函数中的空缺。说明N 个游戏者围成一圈，从 1N 顺序编号，游戏方式如下；从第一个人开始报数(从 1 到 3 报数)，凡报到3 的人退出圈子，直到剩余一个游戏者为止，该游戏者即为获胜者。下面的函数 playi
17、ng(Linklist head)模拟上述游戏过程并返回获胜者的编号。其中，N 个人围成的圈用一个包含 N 个结点的单循环链表来表示，如图 1 所示，游戏者的编号放在结点的数据域中。在函数中，以删除结点来模拟游戏者退出圈子的处理。整型变量 c(初值为 1)用于计数，指针变量 p 的初始值为。head(如图 1 所示)。游戏时，从 p 所指向的结点开始计数，p 沿链表中的指针方向遍历结点，c的值随 p 的移动相应地递增。当 c 计数到 2 时，就删除 p 所指结点的下一个结点(因下一个结点就表示报数到 3 的游戏者)，如图 2 所示，然后将 c 设置为 0 后继续游戏过程。（分数：20.00）填
18、空项 1:_ （正确答案：1）解析：填空项 1:_ （正确答案：q-next 或 p-next-next）解析：填空项 1:_ （正确答案：0）解析：填空项 1:_ （正确答案：p-next）解析：填空项 1:_ （正确答案：p-code）解析：本题要求完成程序，该程序的功能是删除报号为 3 的结点，直到剩下一个结点为止。while 语句中的 n 的取值范围从 1 到 N，又因为 while 语句先执行中括号里的语句在判断 n 值，所以第一空应填n1，while 语句中的 if 条件语句是判断 P 指向的下一结点是否该删除，若当 c 为 2 时，则 P 指向的当前结点报号为 2，p 指向的下一
19、个结点，即 p-next 的报号应为 3，该删除，这时应该将 p-next 的指向 C 为 3 的结点的下一个结点，即 p-next-next，再将 p-next 删除，所以第二空应该填 p-next-next，删除 p-next 之后将开始新一轮的报数，根据题意，将 c 值重新设置为 0 后继续，所以第三空对 C 重新赋值，应该填 0，此时，n 个数已经删去一个数，所以 n 的值相应的要减少，if 语句执行完后，跳出 if 语句，将 p 重新赋值，即第四空 p=p-next，当从 1 到 n 都执行一遍后，会有一个人留下，即为获胜者，第五空是给获胜者编号赋值所以应该填 p-code，最后返回
20、获胜者编号，该程序执行完毕。四、试题四(总题数：1，分数：20.00)阅读以下说明和流程图，回答下面问题。说明图 1 所示的流程图中有两个判断条件 A0 和 B0。这些判断条件的各种组合情况如图 2 所示。表中 Y 表示相应的条件成立，N 表示相应的条件不成立。每一列表示一种条件组合，并在列首用相应的序号来表示。（分数：20.00）(1).当遇到哪几种条件组合时，流程图能执行“1i”?(写出相应的序号即可)（分数：5.00）_正确答案：(1，2)解析：(2).当遇到哪几种条件组合时，流程图能执行“2j”?(写出相应的序号即可)（分数：5.00）_正确答案：(2，4)解析：(3).当遇到哪几种条
21、件组合时，流程图能执行“3k”?(写出相应的序号即可)（分数：5.00）_正确答案：(1，3，4)解析：(4).该流程图共有多少条实际执行路径?流程图*（分数：5.00）_正确答案：(4 条)解析：本题属于简单的流程图分析。问题 1，要求流程图执行“1i”步骤，从图上“1i”的方框上只有一个菱形并且该菱形为“N”的出口已经越过语句“1i”，所以它是语句“1i”执行的一个判断条件。满足 A0 的条件执行语句“1i”，即序号为 1，2。问题 2，要求流程图能执行“2j”。该方框之卜有两个菱形，两个菱形是串行，因此第一菱形的判断条件 A0?，对执行“2j”语句无限制。第二个菱形判读 B0?，一个出口
22、指向“2j”，一个出口越过“2j”，即是执行“2j”语句的判断条件。B0?为“N”时，执行“2j”，序号为 2，4。问题 3，要求流程图执行“3k”。该方框之上有三个菱形，其中下面两个菱形，由于第二个菱形的一个出口是第三个菱形的入口，它的另一个出口越过了第三个菱形，所以，这两个菱形构成了一个组合条件。而第一菱形与下面两个菱形构成的系统串行，因此，第一个菱形中的判断条件对执行“3k”语句无影响。执行“3k”，要求“B0”的判断为“Y”，或者“B0”的判断为“N”并且“A0”的判断为“N”。因此，满足条件的需要为 1，3，4。问题 4，因为本题的条件组合一共有 4 组。将每种组合执行一次看是否有执
23、行的路径重复。A0，B0，执行“1i”和“3k”语句。A0，B0，执行“1i”和“2j”语句。A0，B0，执行“3k”语句。A0，B0，执行“2j”和“3k”语句。没有重复，即实际执行路径为 4 条。五、试题五(总题数：1，分数：20.00)阅读以下说明和流程图，将应填入_处的字句写在对应栏内。说明下面的流程图旨在统计指定关键词在某一篇文章中出现的次数。设这篇文章由字符 A(0),A(n-1)依次组成，指定关键词由字符 B(0),B(m-1)依次组成，其中nm1。注意，关键词的各次出现不允许有交叉重叠。例如，在“aaaa”中只出现两次“aa”。该流程图采用的算法是：在字符串 A 中，从左到右寻
24、找与字符串 B 相匹配的并且没有交叉重叠的所有子串。流程图中，i 为字符串 A 中当前正在进行比较的动态子串首字符的下标，j 为字符串 B 的下标，k 为指定关键词出现的次数。流程图（分数：20.00）填空项 1:_ （正确答案：0k）解析：填空项 1:_ （正确答案：i+j）解析：填空项 1:_ （正确答案：i+m）解析：填空项 1:_ （正确答案：i+1）解析：填空项 1:_ （正确答案：i）解析：在文章中查找某关键词出现的次数是经常碰到的问题。流程图最终输出的计算结果 k 就是文章字符串 A 中出现关键字符串 B 的次数。显然，流程图开始时应将 k 赋值 0，以后每找到一处出现该关键词，
25、就执行增 1 操作 k=k+1。因此第一空处应填 0k。字符串 A 和字符串 B 的下标都是从 0 开始的。所以在流程图执行的开始处，需要给它们赋值 0，接下来执行的第一个小循环就是判断 A(i)，A(i+1)，A(i+j-1)是否完全等于 B(0)，B(1)，B(m-1)，其循环变量 j=0，1，m-1。只要发现其中对应的字符有一个不相等时，该小循环就结束，不必再继续执行该循环。因此，该循环中继续执行的判断条件应该是 A(i+j)=B(j)且 jm。只要遇到 A(i+j)B(j)或者 j=m(关键词各字符都已判断过)就不再继续执行该循环。因此流程图的第二空处应填 i+j。对于 j=m，已找到
26、一处关键词的情况，显然应该执行 k=k+1，对关键词出现次数的变量 k 进行增 1 计算。同时，为了继续进行以后的判断，应将字符串 A 的小标 i 右移 m(这是因为题中假设关键词的出现不允许重叠)。因此第三空处应填写 i+m，表示应该从已出现的关键词后面开始再继续进行判断。由于此时的j=m，书写 i+j 的答案也是正确的，但这不是程序员的好习惯，因为这不符合逻辑思维的顺势，在程序不断修改的过程中容易出错。不少考生在第三空处填写 i+1，这意味着下次判断关键词将从 A(i+1)开始，这就使关键词的出现有可能发生部分重需的现象。流程图中，对于 jm 的情况，表示刚才判断关键词时并非各个字符都完全
27、相同，也就是说，刚才的判断结沦是此处并没有出现关键词。即 A(i)开始的子串并不是关键词。因此，下次判断关键词应该以 A(i+1)开始，即第四空处应填 i+1。在下次判断关键词之前还应该判断是否全文已经判断完。最后一次小循环判断应该是对 A(n-m)，A(n-m+1)，A(n-1)的判断。下标 n-m 来自从 n-1 倒数 m 个数。可以先试验写出 A(n-m)，A(n-m+1)，A(n-1)，再判断其个数是否为 m。经检查，个数为(n-1)-(n-m)+1=m 个，所以这是正确的。也可以用例子来检查次数是否正确。检查次数是程序员的基本功，数目的计算很容易少一个或多一个。既然最后一次判断关键词应该是对 A(n-m)，A(n-m+1)，A(n-1)的判断，即对 i=n-m 进行小循环判断，所以当 in-m 时就应该停止大循环，停止在查找关键词了。
