📄 历届试题 - 一九九八年度高级程序员级 下午试卷.htm
字号:
<BR><BR> 1．考虑元素d[i]被包含在新的部分元素序列中的可能性。如果在当前部分元素序列之后接上d[i]，新序列的元素和不超过total，则函数将d[i]包含在当前部分元素序列中。如果新的部分元素序列的元素和等于total时，新的部分元素序列就是一个解答，函数将其输出；否则，若继续考虑后面的元素还有可能找到解答时，函数就递归去考虑后面的元素，寻找解答。最后，函烽就恢复原来部分元素序列中不包含d[i]的状态。
<BR><BR> 2．考虑元素d[i]不被包含在新的部分元素序列中的可能性。如果继续向d[i]之后考虑还是有希望能得到和为total的部分元素序列时，函数将新序列不包含d[i]也作为一种可能的选择，并递归去考虑后面的元素，寻找解答。<BR><BR>＃include
〈stdio.h〉 <BR><BR>＃define N 100 <BR><BR>int a[N]； <BR><BR>int
flg[N]； <BR><BR>sum (int i，int total，int sigma，int rear，int d[]，int
t) <BR><BR>{int j； <BR><BR> /*考虑元素d[i]被包含在新的部分元素序列中的可能性 */
<BR><BR> if(sigma＋d[i] total/*如果d[i]与当前序列的和不超过total*/
<BR><BR> ｛flg[i]＝1；/*d[i]被考虑在被部分元素序列中 */ <BR><BR> if(_(1)_＝＝total)
<BR><BR> {/*输出解*/ <BR><BR> for (j＝0；flg[j]＝＝0；j＋＋)；
<BR><BR> printf("％4d＝％d"，total，d[j])； <BR><BR> for(j＋＋；＜＝i；j＋＋)
<BR><BR> if (flg[j]) <BR><BR> printf("＋％d",d[j])；
<BR><BR> printf("\")； <BR><BR> } <BR><BR> else
/*并且继续考虑后面的元素有可能找到解答时 */ <BR><BR> if(i＜n－1
&&rear－d[i]＋sigma＞＝total)
<BR><BR> sum(i＋1，total，_(2)_，rear－d[i]，d，n); <BR><BR> _(3)_；
<BR><BR> /*考虑元素d[i]不被包含在新的部分元素序列中的可能性。*/ <BR><BR> if
(i＜n－1&&rear－d[i]＋tigma＞＝total)
<BR><BR> sum(i＋1，total，_(4)，rear－d[i]，d，n)； <BR><BR>}
<BR><BR>main() <BR><BR>{int i，j，n，total，s，d；
<BR><BR> printf("输入total！/n")；scanf("％d",&total)；
<BR><BR> printf("输入n！/n")； scanf("％d",&n)； <BR><BR> for
(s＝i＝0；i＜n；) <BR><BR> {printf ("输入第％d个元素＞0且＜＝％d)\n"，i＋1，total)；
<BR><BR> scanf ("％d"，&d)； <BR><BR> if( d＜1||d＞total)
<BR><BR> {printf("出错，请重新输入！\n")； <BR><BR> contnue；
<BR><BR> } <BR><BR> s＋＝a[i＋＋]＝d； <BR><BR> }
<BR><BR> sum(0，total，0,_(5)_，a，n)； <BR><BR> printf ("\n\n")；
<BR><BR>} <BR><BR><BR>试题八
<BR><BR> 阅读以下程序说明和FORTRAN程序，将应填入_(n)_处的字句，写在答卷的对应栏内。 <BR><BR>[程序说明]
<BR><BR> 本程序用以查找给定数组A的第K小元素。程序执行后，第K小元素存放在数组元素A(K)中。
<BR><BR> 设给定的数组中各元素A(i)＝(i＝1，2…N)互为不相等。它的第K(1≤k≤N)小元素是指这样的元素；它大于N个元素中的K－1个元素，而小于其余的N－K个元素。假如，假设N=8，数组A为：<BR><BR>44
94 12 50 55 6 18 67 <BR><BR>它的第5小元素(即K＝5)是50。 <BR><BR> 本程序的处理过程如下：
<BR><BR> 将A(K)的值(此例为A(5)，此时值为55)存入X，从左向右扫描，直至遇以第一个不小于X的元素(此时为94)，再从右向左扫描，直到遇见第一个不大于X的元素(此时为18)，然后交换这两个元素，数且A成为：<BR><BR>44
18 12 50 55 6 94 67
<BR><BR>继续这一“扫描与交换”的过程，直到两个方向的扫描在数组中间的某处汇合。此时数组被分成两段，汇合点左边的元素均小于汇合点右边的元素。然后选取存在第K小元素的一段，重复上述扫描、交换和调整扫描范围的处理过程。程序中采用L、R来表示扫描的范围的左右边界。开始时L为1，R为N，以后逐次调整。当变成为L值不小于R值时，A[K]即是第K小元素。<BR><BR> SUBROUTINT
FIND(A，N，K) <BR> INTEGET A(N)，R，X，W <BR><BR> L＝1 <BR><BR> R＝N
<BR><BR>20 IF (L，LT，R)THEN <BR><BR> X＝A(K) <BR><BR> I＝L
<BR><BR> J＝R <BR><BR>30 IF(A(1)，LT，X)THEN <BR><BR> I＝I＋1
<BR><BR> GOTO 30 <BR><BR> ENDIF
<BR><BR>40 IF(___(1)___)THEN <BR><BR> ___(2)___
<BR><BR> GOTO 40 <BR><BR> ENDIF <BR><BR> IF(I,LE,J)THEN
<BR><BR> W＝A(I) <BR><BR> ___(3)___ <BR><BR> I＝I＋1
<BR><BR> ___(4)___ <BR><BR> IF(I，LE，J)___(5)___
<BR><BR> ENDIF <BR><BR> IF(J，LT，K)L＝I
<BR><BR> IF(___(6)___) R＝___(7)___ <BR><BR> GOTO 20
<BR><BR> ENDIF <BR><BR> RETURN <BR><BR> END
<BR><BR></TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE>
<TABLE cellSpacing=0 cellPadding=0 width=755 align=center bgColor=#ffffff
border=0>
<TBODY>
<TR vAlign=top>
<TD>
<TABLE cellSpacing=0 cellPadding=0 width="98%" align=center border=0>
<TBODY>
<TR>
<TD>
<HR noShade SIZE=1>
<TABLE cellSpacing=0 cellPadding=1 width="60%" align=center
border=0>
<FORM name=reviewform action=/admin/addreview.php method=post>
<TBODY>
<TR bgColor=#eeeeee>
<TD colSpan=2><B>发表你的评论>></B></TD></TR>
<TR>
<TD vAlign=top width=213>您的名字:</TD>
<TD vAlign=top width=542><INPUT size=32 name=mf_name> </TD></TR>
<TR>
<TD vAlign=top width=213>E-mail:</TD>
<TD vAlign=top width=542><INPUT size=32 name=mf_email> </TD></TR>
<TR>
<TD vAlign=top width=213>评论内容:</TD>
<TD vAlign=top width=542><TEXTAREA name=mf_reviewtxt rows=4 cols=32></TEXTAREA>
</TD></TR>
<TR>
<TD> </TD>
<TD><INPUT class=inputclass style="WIDTH: 35px" type=submit value=发表! name=Submit>
<BR> </TD></TR><INPUT type=hidden value=47 name=mf_pageid>
<INPUT type=hidden value=submitted name=mf_action>
</FORM></TBODY></TABLE>
<TABLE cellSpacing=0 cellPadding=0 width="60%" align=center
border=0>
<TBODY>
<TR bgColor=#eeeeee>
<TD width="50%"><B>关于本文的评论:</B></TD>
<TD><A href="http://www.xiaohui.com/admin/dispallreview.php"
target=_blank>点此查看所有评论>></A></TD></TR>
<TR>
<TD
colSpan=2>目前暂无任何评论</TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE></TD></TR>
<TR>
<TD> </TD></TR></TBODY></TABLE><!-- #EndEditable -->
<TABLE cellSpacing=0 cellPadding=0 width=755 align=center bgColor=#ffffff
border=0>
<TBODY>
<TR bgColor=#dddddd height=1>
<TD></TD></TR>
<TR align=middle bgColor=#efefef>
<TD><A href="http://www.xiaohui.com/about/contact.htm">联系我</A> | <A
href="http://www.xiaohui.com/webmap.htm">站内导航</A> | <A
href="http://www.xiaohui.com/about/maillist.htm" target=_self>订阅邮件</A> |
<SPAN id=add_bookmark style="CURSOR: hand"
onclick="window.external.addFavorite('http://www.XiaoHui.com','小辉程序员之路')">加入书签</SPAN>
| <A class=text2
onclick="this.style.behavior='url(#default#homepage)';this.setHomePage('http://www.XiaoHui.com');"
href="http://www.xiaohui.com/dev/exam/st/98x.htm#" target=_self>设为首页</A>
</TD></TR>
<TR bgColor=#dddddd height=1>
<TD></TD></TR></TBODY></TABLE>
<TABLE borderColor=#000000 height=80 cellSpacing=0 cellPadding=0 width=755
align=center bgColor=#ffffff border=0>
<TBODY>
<TR align=middle borderColor=#ffffff>
<TD><A href="http://www.xiaohui.com/">小辉程序员之路</A>(<A
href="http://www.chinaithero.com/">中国镜像</A>|<A
href="http://www.xiaohui.com/" target=_self>美国镜像</A>) ◇
做一名最好的开发者是我不变的理想……<BR>Copyright(C) 1998-2004 XiaoHui.com &
ChinaITHero.com All rights reserved<BR><FONT
color=#ff0000>声明：站内所有原创文字，未经许可，不得转载、复制。</FONT></TD></TR></TBODY></TABLE><BR><!-- #EndTemplate --></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -