2013上半年程序员考试真题及答案-下午卷.doc-资料库

第1页 / 共18页

第2页 / 共18页

第3页 / 共18页

第4页 / 共18页

第5页 / 共18页

第6页 / 共18页

第7页 / 共18页

第8页 / 共18页

2013 上半年程序员考试真题及答案-下午卷试题一平面上一个封闭区域内稳定的温度函数是一个调和函数。如果区域边界上各点的温度是已知的（非常数），那么就可以用数值方法近似地计算出区域内各点的温度。假设封闭区域是矩形，可将整个矩形用许多横竖线切分成比较细小的网格，并以最简单的方式建立坐标系统，从而可以将问题描述为：已知调和函数 u(i,j)在矩形{0≤i≤m；0≤ j≤n}四边上的值，求函数 u 在矩形内部各个网格点{(i,j)|i=1，…，m-1；j=1，…，n-1} 上的近似值。根据调和函数的特点可以推导出近似算式：该矩形内任一网格点上的函数值等于其上下左右四个相邻网格点上函数值的算术平均值。这样，我们就可以用迭代法来进行数值计算了。首先将该矩形内部所有网格点上的函数值设置为一个常数，例如 u(0,0);然后通过该迭代式计算矩形内各网格点上的新值。这样反复进行迭代计算，若某次迭代后所有的新值与原值之差别都小于预定的要求（如 0.01),则结束求解过程。阅读以上说明和流程图，填补流程图中的空缺（1)〜（5)，将解答填入答题纸的对应栏内。

(1) 0 或任意一个负数 (2) (u(ij+1)+u(ij-1)+u(i-1j)+u(i+1j))/4 或等价表示 (3) max (4) new 或（(u(i,j+l)+u(i，j-l)+u(i-lj)+u(i+l，j))/4 或等价表示 (5) max 试题二（共 15 分）本题考查算法（数值计算）流程的描述。封闭区域内稳定（没有奇异点）的温度场、磁场等都是调和函数。已知边界上的值，就可以近似计算区域内各点的值。对于网格化后的矩形区域{0≤i≤m；0≤j≤n},其边界点为 {(0，j)丨 j=0，..，n}、{((i，0)丨 i=0，..，m}、{(m，j)丨 j=0,..,n}、{((i,n)|i=0,..,m}，其内点为{(i，j)|i=1，•.•m-l;j=1，...，n-l}。本题采用迭代法进行近似计算。初始时，设矩形每个内点处的 u(ij)均等于常数 u(0,0)。每次迭代需要再计算出所有内点处的 u(ij)新值。为了检查迭代能否结束，需要算出所有内点处函数 u 的新值与旧值之差的绝对值是否都小于 0.01(或判断其最大值是否小于 0.01)。为此，每次算出的新值需要先暂存于一个临时变量 new。它应是点(ij 上下左右四个点处 u 值的算术平均值，因此（2)处应填(u(i，j+1)+u(i，j-1)+u(i-1，j)+u(i+1，j))/4。为了计算本次迭代中新老值之差的绝对值|u(ij)-new|的最大值 max,需要先对 max 赋一个不可能再低的值（由于绝对值总是非负，所以 max 常先存 0)。因此（1)处可以填 0(填任何一个负数也是可以的）。当某个内点处新老 u 值之差的绝对值超过 max 时，就需要将该值赋给 max。因此，(3) 处应填 max。不管是否更新了 max，此后新值就可以替代老值了。因此（4)处应填 newo (5)处应填本次迭代求出的最大值 max,以判断它是否小于 0.01，是否达到了近似要求。如果已经达到误差要求，则计算结束，所有的 u(ij)就是计算结果。否则，还需要继续进行迭代。

试题二函数 GetDateId(DATEdate)的功能是计算并返回指定合法日期 date 是其所在年份的第几天。例如，date 表示 2008 年 1 月 25 日时，函数的返回值为 25，date 表示 2008 年 3 月 3 日时，函数返回值为 63。函数 Kday — Date(inttheyear,intk) 的功能是计算并返回指定合法年份 theyear(theyear≥1900)的第 k 天（1≤k≤365)所对应的日期。例如，2008 年的第 60 天是 2008 年 2 月 29 日，2009 年的第 60 天是 2009 年 3 月 1 日。函数 isLeapYear(inty)的功能是判断 y 代表的年份是否为闰年，是则返回 1，否则返回 0。 DATE 类型定义如下：填充函数中的空缺，将解答填入答题纸的对应栏内。（1)date.month

(2) date.month>2 或其等价形式 (3) DATE (4) theyear (5) days_month[i-1]或其等价形式本题考查 c 程序的基本语法和运算逻辑。函数 GetDateId(DATE date)的功能是计算并返回指定合法日期 date 是其所在年份的第几天。处理思路是：先将 1 月~date.month-l 月的天数累加起来，然后加上 date.month 的天数 date.day 即可。若 date.month>2，则需要考虑特殊情况 2 月份，在闰年为 29 天而不是 28 天。因此，空（1)处应填入 date.month，空（2)处应填入 date.month>2。函数 Kday_Date(int theyear,int k) 的功能是计算并返回指定合法年份 theyear (theyear≥1900)的第 k 天（1≤k≤365)所对应的日期。根据说明，显然空（3)应填入“DATE”。当 k<32 时，计算出的日期一定在 1 月份；当 k 大于 31 而小于 60(闰年时为 61)时，计算出的日期一定在 2 月份；以此类推。函数中的处理思路是：先将 k 的值减去 1 月份的天数，若仍大于 0,则继续减去 2 月份的天数，以此类推，直到 k 的值小于或等于 0。此时将多减去的最后 1 个月的天数加上即可。因此，空（4)应填入“theyear”，空(5)应填入“days_month[i]”。

试题三埃拉托斯特尼筛法求不超过自然数 N 的所有素数的做法是:先把 N 个自然数按次序排列起来，1 不是素数，也不是合数，要划去；2 是素数，取出 2(输出），然后将 2 的倍数都划去；剩下的数中最小者为 3,3 是素数，取出 3(输出），再把 3 的倍数都划去；剩下的数中最小者为 5,5 是素数，再把 5 的倍数都划去。这样一直做下去，就会把不超过 N 的全部合数都筛掉，每次从序列中取出的最小数所构成的序列就是不超过 N 的全部质数。下面的程序实现埃拉托斯特尼筛法求素数，其中，数组元素 sieve[i](i>0)的下标 i 对应自然数 i，sieve[i]的值为 1/0 分别表示 i 在/不在序列中，也就是将 i 划去（去掉）时，就将 sieve[i]设置为 0。阅读以上说明和 C 程序，填充程序中的空缺，将解答填入答题纸的对应栏内。

(1) iN 或 k>N+1 或其等价形式 (4) i+k 或其等价形式 C5)sieve[i]=0 或其等价形式本题考査 c 程序的运算逻辑，应用案例是埃拉托斯特尼筛法求素数。显然，空⑴所在的 for 语句用于设置 Sieve[]的初始值，根据题目描述，一开始 1〜N 范围内的自然数 i 都在序列中，因此对应的数组元素 sieve[i]都要设置为丨。因此，空（1) 处应填入“iN”或其等价形式，表示要找的最小素数己经大于 N，应结束处理。空（4)和（5)所在 for 语句用于将刚找出的素数 k 及其倍数从序列中去掉，用 i 表示 k 的倍数（包括 k 自己）时，i 的取值为 k，2k,3k 在 i 的初值己设置为 k 的情况下，i 的迭代方式为 i=i+k，因此空（4)处应填入“i+k”，空（5)处应填入“sieve[i]=0”

试题四 N 个游戏者围成一圈，从 1〜N 顺序编号，游戏方式如下：从第一个人开始报数（从 1 到 3 报数)，凡报到 3 的人退出圈子，直到剩余一个游戏者为止，该游戏者即为获胜者。下面的函数 playing(LinkList head)模拟上述游戏过程并返回获胜者的编号。其中，N 个人围成的圈用一个包含 N 个结点的单循环链表来表示，如图 4-1 所示，游戏者的编号放在结点的数据域中。在函数中，以删除结点来模拟游戏者退出圈子的处理。整型变量 c(初值为 1)用于计数，指针变量 p 的初始值为 head(如图 4-1 所示)。游戏时，从 p 所指向的结点开始计数，p 沿链表中的指针方向遍历结点，c 的值随 p 的移动相应地递增。当 c 计数到 2 时，就删除 P 所指结点的下一个结点（因下一个结点就表示报数到 3 的游戏者），如图 4-2 所示，然后将 c 设置为 0 后继续游戏过程。

阅读以上说明和 C 程序，填充函数中的空缺，将解答填入答题纸的对应栏内。 (1) 1 (2) q->next 或 p->next->next (3) 0 (4) p->next (5) p->code 本题考查数据结构的应用和 C 程序的运算逻辑，主要涉及指针和链表。由于游戏最后剩一人时结束，因此空（1)处应填入“1”，表示 N>1 时游戏过程要继续。当 c 等于 2 时，p 所指结点的后继表示为 q(q=p->next)，q 所指结点即为要删除的结点，即如下图所示。

资料库

2013上半年程序员考试真题及答案-下午卷.doc

相关推荐

程序员考试

热门标签

最新资料