信息学奥赛比赛练习题

如下：牌面计算方法牌面计算方法22点J11点33点Q12点..K13点1010点A1点要求从一付扑克牌中任取4张，通过+,—,X,F的运算而得到24点（每张牌能使用一次）。例如：有牌3,5,6,8,则可通过：3X（6—5）X8=24计算出24点，但也存在计算不出的情况，如：A，A，A，2等。将一个表达式如：（a+b）*c+e+d/f*（a+k）使用栈化为前缀与后缀来表示。设有数2，3，5，7，13，运算符号＋，—，*且运算符无优先级之分。如:2+3*5=253*5+2=17现给出任意一个整数N,要求用以上的数和运算符，以最少的运算次数产生出N。例如：N=7,>7=7即0次运算N=93,>93=13*7+2即2次运算已知三元素的字母表('A','B',‘C')。生成一个该字母表上的含N个(NV50)个字符的序列,要求生成的序更中没有两个相邻的子序更相同。例如：N=5时'ABCBA'是可接受的；而'ABCBC'是不可接受的。用1..这N个自然数顺序组合成一个多位数，现要求从中删除数字(MVN),使得剩下的数为最大。求某一个三位数ABC,要求满足下列条件：(1)A>B>C>0⑵交换A,C位置得到新的数比原数少495；(3)对ABC作全排列而得到的六个三位数之和为2886。输入两个正整数X,Y,将X,Y化为二进制数，然后将这两个二进制数作二进制加法运算,再将结果化为十进制输出。将十进制数N,转换成P进制数Mo一个整型变量只能用来贮较小的N!的值，当N较大时，可将阶乘值中的每一个数字存放在一个一维数组的一个元素中。使用这种方法,打印：N!的值；N!—M!(M>N)；N!+M!随机产生50个1..500的自然数。对每次产生的数,若是奇数,则加入队列,若是偶数则从队首取出一个数据输出,要求显示队列变化情况。利用两个栈S1,S2模拟一个队列，写出用栈的运算来现队列的插入与删除运算的算法和程序。编程完成以下的高精度计算：多位数乘以一位数；多位数除以一位数；多位数乘以多位数(要求用尽可能少的存储单元)；多位数除以多位数(要求用尽可能少的存储单元)；N!,要求精确到P位(0VPV1000)。B类综合练习题1.合并链表：已知两个链表{an}={a1,a2,……an},{bm}={b1,b2,……bm},将其合并成一个链表{cn}={a1,b1,a2,b2,}分解链表：已知一个由整数组成的线性表,存储在链表中。试将链表中各结点的数据除以3,分别得到余数0,1,2,按此三种不同情况,将原来的链表分解成三个不同的链表。算术表达式求值：输入一个由数字、+,—,*,／与括号组成的算述表达式,求其值。设有数列a1-=0,a2-=1,a3=a1+a2-,an=an-2+(n-1)an-1求出其前40项，并用尽可能少的字节表示结果编程求解两个高精度正实数的除法,要求精确到小数点20位,若20位内有循环节,请标出。求输入的实数算术表达式的值，结果精确到小数点后第N位(0VNV=30)。其中：表达式中出现的运算符为：*，／，－，操作数不多于5个不出现括号，但必须考虑运算优先级顺序。7．算述表达式：组成表达式的有｛0，1，2，3，4，5，6，7，8，9，＋，－，*，／，()｝这15个元素，求有n个元素组成的所有表达式。8．对于次数很高，但项目很少的多项式，可用链表来表示。例如：X100－76X78＋3X3－7可表示为1000*-7678*33-70NIL在此方式下，编程完成两个多项式的加法与乘法。9．一元多项式加法：实现两个整系数一元多项式的加法。如：有多项式5X6+4X3—7X4+1与多项式50X2+4X+0X3结果为：5X6－7X4＋4X3＋50X2＋4X＋1程序要求：键盘输入式项式的各项系数及指数，每项系数及指数为一组数据(系数及指数之一可为零)，以'0,0’结束一个多项式的输入，结果按降幕排列，同类项要合并(指数最大不超过30)。上列第一式的输入为：5，64，3—7，41，00，0上例输出结果表示如下：5X6—7X4+4X3+50X2+4X+110．编程序计算两个多项式除法的商与余数。例如:F(X)=X4+4X3+6X2+7X+9G(X)=X3+3X2+3X+1贝y：F(X)/G(X)=X+1......3X+811.多项式排列问题:多项式P：：=|｛±项｝项：：=Laibjck其中：L：整数i，j,k：包括0以内的任意整数例如：P=3a2-2ab2c+bc2-7多项式的输入方式：(a1,a2,a3,a4)其中：a1：系数，可正，负a2,a3,a4:表示i,j,k程序要求：按降序a—b—c方式排列输出。12．最小生成树：求出一个图的最小生成树，即该图的所有生成树中，树权最小的那棵生树。13．求出一个二叉树的深度与最大宽度。14．给出一个字符表达式，首先进行语法检查，然后表示成一个树的形式输出。15．以下方法称为最小代价的字母树：给定一个正整数的序列，例如：4，1，2，3不改变数的位置把他们相加，并且用括号来标记每一次加法所得到的和。例如：（（4+1）+（2+3））=（（5）+（5））=10除去原数4，1，2，3之外，其余都为中间结果，如：5，5，10将中间结果相加，得到：5＋5＋10=20数20称为此数列的一个代价。若得到另一种算法：（4＋（（1＋2）＋3）=（4＋（（3）＋3）=（4＋（6））=10数列的另一个代价为：3＋6＋10=19若给出N个数，可加N—1对括号，求出此数列的最小代价。（给出过程）16．对一个图进行拓扑排序，方法如下：（1）在有向图中选一个没有前趋的结点且输出之；（2）从图中删去该结点和所有与之相连的边。重复以上过程，直到全部结点均已输出或者图中没有无前趋的结点为止，后一种情况则说明有向图中存在环，无法进行须扑排序。设有N门课程（10V=NV20）,课程名字用a,b,c……英文字母来表示，学生学习某门课程的条件是：不需要任何条件；必须学习完某些课程之后，才能学习此课程。程序要求：（输入以0，0为结束符）输入课程数N,及每门课程的名字，并进行语法检查；输入学习课程之间的关系：输入形式：（a,b），表示a在b的前面学习，要学习b必须先学完a；若学生一次只学一门课程，给出一种学习的顺序，表示形式如下：a—b—c—d若学生一次可学习任意多门课程，表示形式如下：（a,b）—（c,e,d）—（g）问：一个学习至少要几次学习才能学完全部课程。正方形矩阵染色：有nXn的正方形矩阵，划分为nXn个边长为1的正方形，用黑、白两种颜色对这些小正方形涂色，求所有涂色方案（不包括旋转后重复的方案）。19．换钱币：给出一组兑换钱币的公式。例=如：（4，1）=5（4个1分可换1个5分）（2，2），（2，5）=20（2个2加上2个5分可换1个20分）该任务可以一直进行到不能兑换为止。例如根据以上公式，某人有：（6，1），（8，2），（3，5），（0，0）则可以用4个1分换成1个5分，此时，有（2，1）（8，2），（4，5）再用4个2分，4个5分换成2个20分；此时，有（2，1），（4，2），（0，5），（2，20），此时已不再换，共有钱币2+8+40=50分问题：给出一组兑换公式，输入方式：（A1,B1）,（A2,B2）,……（An,Bn）=r（分面值）（0，0）（结束）同时给出某人开始时所有的钱币：（X1,Y1）,（X2,Y2）,……（0,0）（结束）用不兑换方法,使此人具有最大的面值。20．用下列方式建立形成一个等价关系组：先输入若干组等价关系时,如（a,b）表示a,b等价；若有（a,b）,（b,c）,（c,d）则表示a,b,c,d等价，用（一1,－1）表示输入结束。当关系组建立后，再输入K个元素对，编程判断它们属于哪些关系类。例如：当初始状态时建立了如下四组关系对：3139184617313918546177391856177134一二三四一二三四一二三四（初始状态）（状态一）（状态二）当K=1时的元素对为（5,7）时,则有状态一；当K=2时的元素对为（7,13）时,则有状态二；当K=3时的元素对为（20,2）时,则应属于状态二的第四类21．建立二叉树的链表存储结构后：写出计算二叉树中叶子结点数目的递归算法；编写复制这棵二叉树的非递归程序。22．设有一个字符串，长度小于100，且全部以英文字母组成。对字串中的每个字母可用0，1，2三个数字进行编码，且数字可以重复使用。程序要求：输入字符串，并能判断输入是否有错；输出对应的编码表及码长，要求字串的编码长度为最短；根据上述编码表，给出一些编码，然后求出其原字符串。例如：输入的字符ABCBAAADDEF其对应的编码表为：A：2S：10C：11D：12E：00F：01对应的编码为：210111022212120001码长为：18根据该编码，给出编码：010001121110222则输出字串：FEFDCBAAA某些密码由N个英文字母组成（N<26=，每字母的平均使用率为：Wl,W2，W3，……Wn,要求编程完成下列任务：键入英文字母及个数；键入N个英文字母的使用频率；用二进制数对该N个英文字母进行编码（最短，无二义性）；键入字母短文（单词用空格区分），输出相应编码；键入二进制编码短文，输出译文。最长连线：设有一个NXN的方格图形，且N为3倍数。要求在图形中存放0或1,相邻的l可以连成一条连线，连接的方法可以是行，也可以是列；同时约定一条连线只能有一个起点和一个终点，图形上的点最多只能访问一次。例如N=6时，有下图：111101012345211011134510001101001100011061111006在该图中，包含有如下的一些连线1—111—1111—11\f\1—1—111f;1—1—1等等。但如下形状不是一条连线：1—1]1]11—1—1—1在以上的连线中，最长的连线为：表示方法：最长连线长度：LMAX=91连线：(1,6)—(2,6)—1—11(3,6)—(4,6)—f/(4,5)—(4,4)—11(3,4)—(2,4)—f/(2,5)—1—1连线的表示不是唯一的，仅给出一种即可。数据输入：首先输入N然后输入N组，每组N/3个8进制数，一个8个进制、数相当于3个2进制数。如上例的输入过程：N=6717056704程序要求：读入N,并检查合法性(NV=15)；读入N组8进制数(不含检查合法性)；求出最长连线长度量衡LMAX，及连线。键盘输入一个仅由小写字母组成的字符串，输出以该串中任取M个字母的所有排列及排列总数。输入M,N,R。表示从ASCII字符集的所有英文大写字母中的第M个字符开始，共顺序取出N个字母，然后打印所有满足R个字符的组合。例如：当M=3,N=4,R=2时，则有组合：（C，D）（C，E）（C，F）（D，E）（D，F）（E，F）当M=24,N=4,R=2时，则有：（X，Y）（X，Z）（Y，Z）有一个有N个元素组成的序列，有0，1两种元素，要求在任一位前1的个数不得超过0的个数，求出所有这样的序列。设有N个不同的数，从中取出两组来，要求第一组数中的最小的数比第二组中最大的数大，问共有一多少种取法？例：设有数1，2，3，4，5，第一组可取2个，第二组可取1个满足条件的取法有：1，2，3；1，3，41，2，4；1，3，51，2，5；1，4，52，3，4；2，3，53，4，5；又：若第一组取2个数，第二组取3个数满足条件的取法：1，2；2，4，5仅一种用逐步求精方法求出1，2,3，……6的全部排列。用回溯的方法求出从1，2,……N元素集合中，任取出r个全部组合。在nXm的方格中的A点，可以沿着x,y增加的方向到达B点，问：共有多少种走法？在NXM的方各中的A点，，可以沿着X，Y的正方向前进，但是必须绕过一个rXr的正方形，问共有多少种走法（当n,m=V5时需输出具体路径=?从整数值1，2，……100之中，任出两个数，使他们的差为7,问有多少种选法？使它们的差小于7，又共有多少种选法？有红球4个，白球8个，黄球3个排成一排，共有多少种排法？从一个8*8的棋盘中，选出两个相邻的方格，共有多少种选法？相邻的意义如下：//或//求一个给定图中的每两对结点之间的最短路径。有面值为M..N的邮票各一枚，求共能拼出多少不同的面额。有一幢大楼，共有N层。为了便利乘坐电梯，规定每架电梯除停顶层和底层外，还可停K层，试求至少需要多少架电梯才能使每两层之间有真达电梯。有一个四阶方阵，随机产生1..16这16个自然数(不重复)，依次填入每个方格中。要求用最的对调整次数，使每一行、每一列以及对角线上的四个数之和均相等。打印每一次对调的过程。例如；随机产生得如下数字方阵：16281351510379612144111对调过程表现为：step1：16231351510879612144111step2：有一白色矩形平板，另有若干涂有不同颜色的小矩形零件，每一种零件只涂一种颜色，可以为白色。将这些零件逐一叠放在平板上，每个零件的边都与平板的边平行，且都在平板的边界之内。最后，从平板的上方俯视，则平板被划分为不同颜色的区域。若任意两个区域存在有重合部分的边，则其颜色不同。编程输出每个区域的面积，并指明其颜色。输入格式：首先输入平板边长a,b,其中a,b小于100的自然数；输入矩形的个数N(0<=N<=30)输入每个零件的左上角和右下角坐标，及该矩形的颜色代码。零件的坐标是以平板左下角为坐标原点而得到的，可为小数；颜色以1－64间的自然数表示，1为白色。例：平板尺寸：20，12零件个数：5X1Y1X2Y2颜色35714591532688441251341213111771一个旅行者有最多能装M公斤的背包，现有N件物品，它们的重量分别为Wl,W2,W3,...Wn,它们的价值分别为C1,C2,C3...Cn。求旅行者应选哪几种物品装入背包，使包内物品的总价值最大。其中N和Wi,Ci由键盘输入。1、编程打印下面的图案（必须使用循环语句，否则不给分）**A**AAA**A*2、编程实现以下功能：由键盘任意输入20个整数，统计其中正数、负数和零的个数。3、编程实现经下功能：从键盘任意输入一个自然数B,由计算机判断B是不是大于100小于1000的奇数，如果不是，则打印“N”,并要求重新输入；如果是则打印“Y”,并输出1+2+3+・・・+B的值。4、由键盘任意输入25个整数，先把这25个整数按输入顺序打印一遍，然后把它们从大到小排序，输出排序后的第10个数。5、在10000以内验证下面的规律的正确性：任意一个大于9的整数减去它的各位数字之和的差，一定能被9整除。合肥市庐阳区首届中小学生信息学竞赛小学组试题学校姓名参赛号（考试时间：120分钟，满分100分）2003年3月一、填空题（每空1分，共计15分）1．“位”习惯上用英文字母⑴表示，“字节”习惯上用英文字母⑵表示。2．汉字国际码共收录了7445个汉字和图形符号，包括按⑶顺序排列的一级汉字3755个，按⑷顺序排列的二级汉字3008个以及图形符号682个。3．按入侵途径可以将病毒分为源码病毒、入侵病毒、操作系统病毒、⑸病毒四类。4．在计算机中，一个字节是由⑹个二进制位组成的5．Windows98中，欲选定当前文件夹中的全部文件和文件夹对象，可使用的组合键是⑺6．在计算机网络中，实现数字信号和模拟信号之间转换的设备是⑻。7．一台计算机必须具备的输入设备是⑼。8．在Windows98中，剪贴板是程序和文件间用来传递信息的临时存储区，此存储区是⑽的一部分。Windows98中"磁盘碎片整理程序"的主要作用是（11）。Internet实现了分布在世界各地的各类网络的互联，其通信协议是（12）。典型的电子邮件地址一般由（13）和主机域名组成。TOC\o"1-5"\h\z执行“PRINT9.4\3.7,9.4MOD3.7”后的运行结果是（⑷。四个字符串”ABC"、”abc"、"about”及”abacus"中的最大者为（15）。二、选择一个正确答案代码（A/B/C/D）,填入每题的括号内（每题1分，多选无分，共15分）1•字符的ASCII编码在计算机中的表示方法的准确描述为⑴。A.使用7位二进制代码B.使用8位二进制代码，最左一位为0C.使用输入码D.使用8位二进制代码，最左一位为1提出电子计算机“程序存储”结构思想的是⑵。A.比尔•盖茨B.艾兰•图灵3.4.5.6.C.帕斯卡计算机能直接执行的程序是A.高级语言编写的程序C.Pascal语言编写的程序中央处理器每执行一个⑷A.语言B.C.程序D.D.冯•诺依曼机器语言编写的程序汇编语言编写的程序，就可完成一次基本运算或判断指令软件B.D.系统软件与应用软件的相互关系是⑸。A.前者以后者为基础B.后者以前者为基础C.相互没有关系D•相互支持显示器的垂直刷新率必须最少超过⑹，眼睛才感觉不到显示器屏幕的闪烁，这样才能更有效地保护眼睛。A.55HZB.75HZC.95HZD.115HZTOC\o"1-5"\h\z用键盘退出Windows98操作系统，可按⑺键。A.ESCB.Alt+F4C.Alt+ESCD.F10Windows98“控制面板”中的⑻可以创建启动盘。A.系统B.添加/删除程序C.添加新硬件D.辅助选项在一个字节中，可存放⑼。A.—个汉字B.0-255之间的整数C.一个全角英文单词D.—个全角标点符号Windows98操作系统的“桌面”指的是⑽。A.整个屏幕B.全部窗口C.活动窗口D.某个窗口11•内存储器的每一个存储单元，都被赋予一个唯一的序号，作为它的（ID。A.内容B.标号C.容量D.地址计算机系统工作的优劣程度在软件上主要取决于（12）。A•应用软件B•实用程序C•操作系统D•编译软件13.在使用E-MAIL前,需要对OUTLOOK进行设置，其中ISP接收电子邮件的服务器称为服务器。（13）A．POP3B．SMTPC．DNSD．FTP衡量网络上数据传输速率的单位是BPS,其含义是（⑷。A.信号每秒传输多少公里B.信号每秒传输多少千公里C.每秒传送多少个二进制位D.每秒传送多少个数据INTERNET的主管机构的英文简称为（15），是非赢利性组织，其总部设在美国弗吉尼亚州的雷斯顿市（RESTON）。A.ISOCB.ARPAC.NSFD.ISO9001三、阅读程序，写出正确的程序运行结果(3+3+4+4+5+5+6=30分)1、READa,b,c,d:X=b+dRESTORE120READa,b,c,dy=b+dRESTOREREADa,a,a,aREADa,a,a,aX=x+y+aPRINTxDATA1,2,3120DATA4,5,6DATA7,8,9END运行结果是⑴2、CLSA=INT(RND(1)*12)+50B=INT(RND(1)*20+42)FORI=1TO2STEP2IFA=BTHENPRINT“*****”;ELSEPRINT“$$$$$”NEXTIEND运行结果是⑵3、FORI=1TO3IFI<=1THENA=3IFI<=2THENA=2IFI<=3THENA=1PRINTA;NEXTIPRINTIEND运行结果是⑶4、A$=”ABCD”N=LEN(A$):B$=””FORI=1TONB$=MID$(A$,I,1)+B$NEXTIPRINTB$END运行结果是⑷5、DIMA(10)FORI=1TO10A(I)=2*IS=A(I)NEXTIPRINTA(A(2))+SEND运行结果是⑸6、FORJ=1TO3FORK=1TO3arr(J,K)=(J-1)*3+KNEXTKNEXTJFORJ=2TO3FORK=2TO3PRINTarr(K,J);NEXTKPRINTNEXTJEND运行结果是⑹7、DIMB(10)INPUTL，NIFN<=LTHEN50S=L:K=1:T=L10IFS>=NTHEN20K=K+1:T=T*L:S=S+TGOTO1020S=S-T:N=N-S-1FORI=1TO10:B(I)=0:NEXTIJ=1130IFN<=0THEN40J=J-1:B(J)=NMODL:N=INT(N/L)GOTO3040FORI=10-K+1TO10PRINTCHR$(65+B(I));NEXTIPRINTGOTO10050PRINTCHR$(65+N-1)100END输入：5，199运行结果是⑺四、完善程序(每空2分共32分)1、下面程序的作用是利用随机函数产生10个100—200之间(包含100、200)的随机整数，打印其中7的倍数的数并求出它们的总和。请根据程序的需要在空白处填上正确的内容。RANDOMIZETIMERFORI=1TO10A=INT(RND*⑴)IF⑵THENPRINTA；:S=⑶NEXTIPRINTPRINT“S=”；SEND2、求1000!后有多少个零。CLSKKK=0FORI=5TO1000STEP5J=⑷DOKKK=KKK+1J=⑸LOOP⑹NEXTIPRINT"KKK=";KKKEND3、数组A中有100个整数，下标从1到100,下面的程序采用比较交换法把A中所有的数按照升序排列，请在空处填入适当的内容将程序补充完整。DIMA(100),B(100)FORI=1TO100A(I)=INT(1000*RND):PRINTA(I);NEXTIPRINTFORI=1TO99FORJ=⑺IFA(I)>A(J)THENSWAP⑻NEXTJNEXTIPRINT"DATAAFTERSORTING:"FORI=1TO100PRINTA(I)NEXTIEND4、下面程序的功能是打印如下图形，请把程序补充完整.^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx*1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1*^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx*1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1*^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx*1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1*^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^Tx^TxFORI=1TO4FORK=1TO4:PRINTTAB⑼;FORJ=1TO⑽PRINT"*";NEXTJPRINT"";FORJ=1TO(11)PRINT"*";NEXTJPRINT"";NEXTKPRINTNEXTIEND5、把0-9十个数字分别组成一个一位数，一个二位数，一个三位数和一个四位数，使它们都是完全平方数(每个数字只能用一次)。FORA=1TO3:A1=A*AFORB=4TO9:B1=B*BFORC=13TO31:C1=C*CFORD=32TO99:D1=D*DX$=(12)FORI=2TO10FORJ=1TOI-1IF(13)THEN110NEXTJ,IPRINTA1,B1,C1,D1110NEXTD,C,B,A6、在一个划分为10行15列的区域内，随机地埋上30枚地雷，要求地雷不能在同地点重复埋设。下图是其中一个地雷分布示意图，*代表地雷。OOO*OOO*OOOOOOO*OO*OOOO*OO*OOOO*OOOO*OOOO*O*OOOO*OOO*OOOO*OOOO*OO*OOOOOOOOOOOOOOO*OOO*OO*OOO*OOOOO*OOOOOOOOO*OO*OOOO*OOOOO*OOO*OOOO*OO*OOOOO*OO*OOO*OORANDOMIZECLSDIMN$(10,15)FORK=1TO30DOI=(⑷J=(15)LOOPWHILEN$(I,J)<>""(16)NEXTKFORI=1TO10FORJ=1TO15IFN$(I,J)<>""THENPRINTN$(I,J);ELSEPRINT"O";NEXTJPRINTNEXTIEND五、编程（8分）设计一个程序，把一个真分数表示为埃及分数之和的形式。所谓埃及分数，是指分子为1的形式古代埃及有一个非常奇怪的习惯，他们喜欢把一个分数表示为若干个分子为1的分数之和的形式如，7/8=1/2+1/3+1/24。