算法应用综合测试（二）
（作答时间：3小时）
说明:1、作题前先在D盘新建一个文件夹，以自已的“学校+姓名”命名
2、各程序的源文件名、输入输出文件见题目
第一题杨辉三角（yh.pas）
【问题描述】
输出杨辉三角第n行。
【输入数据】
一个整数n，表示要输出杨辉三角的第n行。
【输出数据】
一行，杨辉三角的第n行，两个数之间用空格隔开。
【数据范围】
对于30%数据，0 对于100%数据，0 第二题亲和数(amicable.pas) 【问题描述】 某一天，tenshi看了一本趣味数学书，上面提到了亲和数：定义数对 (x,y) 为亲和数对当且仅仅当x、y为不同正整数，且x、y各自的所有非自身正因子之和等于另一个数。例如 (220,284) 和 (280,224) 都是亲和数对，因为： 220的所有非自身正因子之和为：1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284 284的所有非自身正因子之和为：1 + 2 + 4 + 71 + 142 = 220 数对 (x,y ) 跟 (y,x) 被认为是同一数对，所以我们只考虑 x 【输入格式】 输入文件名:Amicable.in,从文件的第一行分别读入正整数A和B，其中A、B满足 1 ≤ A ≤ B ≤108 【输出格式】 输出文件名:Amicable.out,输出文件只有一行，就是[A,B]内亲和数对的数量 【样例输入】 200 1200 【样例输出】 2 注：[200,1200] 内的数对只有两个，分别是(220,284)和(1184 1210) 【数据规模】 对于60%的数据，2<=A、B 对于100%的数据，2<=A、B< longint； B-A<100000。 第三题数的查找（seek.pas） 【问题描述】 对于给定的N个元素表，要求从中找出第K小的元素. 输入: 第一行是总数N和K, 以下若干行共N个的元素,每行最多20个元素. 输出: 第K小的数. 【输入文件】 输入文件名为：seek.in,第一行有两个数N、K（2 以下若干行为N个元素表；(每行最多30个元素) 【输出文件】 输出文件名为：seek.out,一行，为在元素表中找的到第K小素. 【样例输入1】 5 3 23 8 91 56 4 【样例输出1】 23 【样例输入2】 5 3 23 4 1 56 4 【样例输出2】 4 【数据规模】 对于40%的数据，2<=N、K 对于100%的数据，2<=N、K 第四题两只塔姆沃斯牛 【问题描述】 两只牛在森林里故意走丢了。农民John开始用他的专家技术追捕这两头牛。你的任务是模拟他们的行为(牛和John)。 追击在10x10的平面网格内进行。一个格子可以是： ?一个障碍物, ?两头牛(它们总在一起), 或者 ?农民John. 两头牛和农民John可以在同一个格子内(当他们相遇时)，但是他们都不能进入有障碍的格子。 一个格子可以是： ?. 空地 ?* 障碍物 ? C 两头牛 ? F 农民John 这里有一个地图的例子:: *...*..... ......*... ...*...*.. .......... ...*.F.... *.....*... ...*...... ..C......* ...*.*.... .*.*...... 牛在地图里以固定的方式游荡。每分钟，它们可以向前移动或是转弯。如果前方无障碍且不会离开地图，它们会按照原来的方向前进一步。否则它们会用这一分钟顺时针转90度。 农民John, 深知牛的移动方法，他也这么移动。 每次(每分钟)农民John和两头牛的移动是同时的。如果他们在移动的时候穿过对方，但是没有在同一格相遇，我们不认为他们相遇了。当他们在某分钟末在某格子相遇，那么追捕结束。开始时，John和牛都面向北方。 【输入文件】 文件名: ttwo.in，共10行，每行10个字符，如上文描述的地图。 【样例输入】 *...*..... ......*... ...*...*.. .......... ...*.F.... *.....*... ...*...... ..C......* ...*.*.... .*.*...... 【输出文件】 文件名：ttwo.out，输出一个数字，表示John需要多少时间才能抓住牛们。输出0，如果John无法抓住牛。 【样例输出】 49 一、初识Pascal语言 一、Pascal 语言概述 Pascal 语言是一种算法语言，它是瑞士苏黎世联邦工业大学的Niklaus Wirth教授于1968年设计完成的，1971年正式发表。1975年对Pascal 语言进行了修改，作为“标准PASCAL语言”。 Pascal 语言是一种结构化的程序设计语言，可以用来编写应用程序。它又是一种系统程序设计语言，可以用来编写顺序型的系统软件（如编译程序）。它的功能强、编译程序简单。 二、Pascal 语言的特点 Pascal语言有以下几个主要的特点： ⒈它是结构化的语言。Pascal语言提供了直接实现三种基本结构的语句以及定义“过程”和“函数”的功能。可以方便地书写出结构化程序。在编写程序时可以完全不使用GOTO语句和标号。这就易于保证程序的正确性和易读性。Pascal语言强调的是可靠性、易于验证性、概念的清晰性和实现的简化。在结构化这一点上，比其它（如 BASIC,FORTRAN77）更好一些。 ⒉有丰富的数据类型。Pascal提供了整数、实型、字符型、布尔型、枚举型、子界型、数组类型、集合类型、记录类型、和文件类型和指针类型。⒊能适用于数值运算和非数值运算领域。PASCAL的功能较强，能广泛应用于各种领域。PASCAL语言还可以用于辅助设计，实现计算机绘图功能。 ⒋ PASCAL程序的书写格式比较自由。PASCAL允许一行写多个语句，一个语句可以分写在多行上，这样就可以使PASCAL程序写得格式优美，便于阅读。 三、Pascal语言程序的基本结构 程序设计语言都有着一组自己的记号和规则。PASCAL语言必须采用其本身所规定的记号和规则来编写程序。下面我们首先来了解Pascal语言的程序基本结构。 Pascal语言的程序结构为: 程序首部 标号说明语句 常量定义语句 类型定义语句程序的说明部分 变量说明语句 函数和过程说明语句分程序 程序体程序的执行部分 先看一个简单的PASCAL程序： program exam1(input,output); var r,s,c:real; begin readln(r); c:=3.14*2*r; s:=3.14*r*r; writeln(c,s) end. 高中信息技术《算法与程序设计》试题 一、单选题（每小题3分，20小题，共60分） 1、用计算机解决问题时，首先应该确定程序“做什么？”，然后再确定程序“如何做？”请问“如何做？”是属于用计算机解决问题的哪一个步骤？（） A、分析问题 B、设计算法 C、编写程序 D、调试程序 2、在调试程序过程中，下列哪一种错误是计算机检查不出来的？（） A、编译错误 B、执行错误 C、逻辑错误 D、任何错误计算机都能检查出来 3、下列关于算法的叙述中，错误的是（） A、一个算法至少有一个输入和一个输出 B、算法的每一个步骤必须确切地定义 C、一个算法在执行有穷步之后必须结束 D、算法中有待执行的运算和操作必须是相当基本的。 4、流程图中表示判断的是（）。 Ａ、矩形框Ｂ、菱形框Ｃ、圆形框Ｄ、椭圆形框 5、任何复杂的算法都可以用三种基本结构组成，下列不属于基本结构的是（） A、顺序结构 B、选择结构 C、层次结构 D、循环结构 6、能够被计算机直接识别的语言是（） A、伪代码 B、高级语言 C、机器语言 D、汇编语言 7、在VB语言中，下列数据中合法的长整型常量是（） A、08A B、2380836E C、88.12345 D、1.2345E6 8、求Mid(“ABCDEFG”,3,2)的结果是（） A、“ABC” B、“CD” C、“ABCDEF” D、“BCD” 9、表达式 A+B+C 第十二课过程与函数 前面我们曾经学习了程序设计中的三种基本控制结构（顺序、分支、循环）。用它们可以组成任何程序。但在应用中，还经常用到子程序结构。 通常，在程序设计中，我们会发现一些程序段在程序的不同地方反复出现，此时可以将这些程序段作为相对独立的整体，用一个标识符给它起一个名字，凡是程序中出现该程序段的地方，只要简单地写上其标识符即可。这样的程序段，我们称之为子程序。 子程序的使用不仅缩短了程序，节省了内存空间及减少了程序的编译时间，而且有利于结构化程序设计。因为一个复杂的问题总可将其分解成若干个子问题来解决，如果子问题依然很复杂，还可以将它继续分解，直到每个子问题都是一个具有独立任务的模块。这样编制的程序结构清晰，逻辑关系明确，无论是编写、阅读、调试还是修改，都会带来极大的好处。在一个程序中可以只有主程序而没有子程序(本章以前都是如此)，但不能没有主程序，也就是说不能单独执行子程序。pascal中子程序有两种形式：函数和过程。 一、函数 在此之前，我们曾经介绍并使用了pascal提供的各种标准函数，如ABS,SUCC等等，这些函数为我们编写程序提供了很大的方便。但这些函数只是常用的基本函数，编程时经常需要自定义一些函数。 （一）函数的说明 在pascal中，函数也遵循先说明后使用的规则，在程序中，函数的说明放在调用该函数的程序（主程序或其它子程序）的说明部分。函数的结构主程序的结构很相似。 函数定义的一般格式: function <函数名> (<形式参数表>):<类型>; {函数首部} 说明: ①函数由首部与函数体两部分组成。 ②函数首部以关键字function开头。 ③函数名是用户自定义的标识符。 ④函数的类型也就是函数值的类型，所求得的函数值通过函数名传回调用它的程序。可见，函数的作用一般是为了求得一个值。 ⑤形式参数简称形参，形参即函数的自变量。自变量的初值来源于函数调用。在函数中，形参一般格式如下： 变量名表1：类型标识符1；变量名表2：类型标识符2；…;变量名表n：类型标识符n 可见形参表相当于变量说明，对函数自变量进行说明，但应特别注意：此处只能使用类型标识符，而不能直接使用类型。 ⑥当缺省形参表（当然要同时省去一对括号）时，称为无参函数。 ⑦函数体与程序体基本相似，由说明部分和执行部分组成。 ⑧函数体中的说明部分用来对本函数使用的标号、常量、类型、变量、子程序加以说明，这些量只在本函数内有效。 ⑨函数体的执行部分由begin开头，end结束，中间有若干用分号隔开的语句，只是end后应跟分号,不能像程序那样用句号"."。 ⑩在函数体的执行部分，至少应该给函数名赋一次值，以使在函数执行结束后把函数值带回调用程序。 （二）函数的调用 高二信息技术（算法与程序设计）试题卷 一、单项选择题（每小题2.5分共50分将正确答案填到答题卷相应题号下） 1、一同学想通过程序设计解决“鸡兔同笼”的问题，他制定的如下工作过程中，更恰当的是（）。 A、提出问题、设计算法、编写程序、得到答案 B、提出问题、编写程序、运行程序、得到答案 C、编写程序、设计算法、调试程序、得到答案 D、设计程序、提出问题、编写程序、运行程序 2、下列常量说明中，符合语法的是（）。 A、CONST color=red B、CONST const=10*5 C、CONST xl：=3.9； D、CONST color=”abcd” 3、下列代数式的Visual Basic表达式是( )。 A、(x^5-cos(29*3.14))/(sqr(exp(x)+log(y))) B、(x^5-cos(29))/(sqr(exp(x)+ln(y))+5) C、(x^5-cos(29*3.14/)/(sqr(exp(x)+ln(y))+5) D、(x^5-cos(0.506))/(sqr(exp(x)+log(y))+5) 4、下列变量名写法错误的是（）。 A、abc B、abc123 C、abc_123 D、123abc 5、visual basic程序设计语言是一种（）。 A、高级语言 B、汇编语言 C、机器语言 D、数据库语言 6、下列给出的赋值语句中正确的是（）。 A、4 = M B、-M =M C、B=A－3 D、x + y = 0 7、下列Visual Basic中，下列（）的表达式的值不等于4。 A、int(4.1) B、fix(4.9) C、Abs(int(-3.9)) D、Abs(int(-4.5)) 8、下面程序运行后的输出S结果为（）。 i=1 do WHILE i<8 i=i+2:s=2*i+3 loop PRINT s A、17 B、19 C、21 D、23 9、下列Visual Basic中，下列（）类型属于字符串型。 A、Integer B、Single C、String D、Boolean 10、在VB中表达式11\3+11 mod 3 的运算结果值是（）。 A、3 B、4 C、5 D、6 11、下列程序执行后，整型变量n的值为( )。 n=0: for I=1 to 100: if I mod 4=0 then n=n+1: next I A、5050 B、25 C、26 D、33 12、以下选项中，不是Visual Basic控件的是( )。 A、文本框 B、定时器 C、窗体 D、命令按钮 13、使用Visual Basic编程,我们把工具箱在的工具称为( )。 A、事件 B、工具 C、控件 D、窗体 14、结构化程序设计由三种基本结构组成，下面哪个不属于这三种基本结构（）。 A、顺序结构 B、输入、输出结构 C、选择结构 D、循环结构 15、语句if 3*4>=10 then a=1 else a=2 执行后，a的值为（）。 A、12 B、10 C、1 D、2 16、下列结果为True的逻辑表达式是( )。 A、Not (3<8) B、(3<9) And (5>10) C、(3<8) And (5<10) D、(3>8) Or (5>10) 17、要交换变量X和Y之值，应使用的语句组是( )。 A、X=Y；Y=Z；Z=X B、C=X；X=Y；Y=C C、X=Y；Y=X D、Z=Y；Y=X；Y=Z 18、以下程序中的循环体执行的次数是（）。 end if A 25 B 26 C 10 D 5 25、以下程序段运行后，整型变量s的值是（）。 s=1 For i=1 To 10 Step 3 s=s*i Next i Print s A 55 B 3640 C 28 D 280 25、以下程序段执行后，输出结果为（）。 m=29 If m Mod 3 <> 0 Then Print m & “不能被3整除” Else Print m & “能被3整除” End If A n能被3整除 B n不能被3整除 C 29不能被3整除 D 29能被3整除 26.以下程序段语句执行后，y的值是（） X=16 If x<0 then Y=abs(x) Else Y=sqr(x) End if A 其他三项答案都不对 B 256 C 4 D 16 24.如图所示，三个文本框自上而下的顺序是Text1，text2, text3，在文本框text1中输入3，在文本框text2中输入4。单击命令按钮“计算”后，文本框text3中显示的内容是（） “计算”按钮事件过程代码： Private sub command1_click() Dim a as integer Dim b as integer A=val(text1.text) B=val(text2.text) Text3.text=2*(a+b) End sub A 14 B 24 C 7 D 12 25.下列程序段执行后，变量s的值是（）。 S=0 For i=1 To 10 s=s+i Next I A 10 B 0 C 1 D 55 24.下列程序段运行后，输出“*”的个数是（） For I =2 to 10 Print “ * ” Next i 算法应用综合测试（二） （作答时间：3小时） 说明:1、作题前先在D盘新建一个文件夹，以自已的“学校+姓名”命名 2、各程序的源文件名、输入输出文件见题目 第一题杨辉三角（yh.pas） 【问题描述】 输出杨辉三角第n行。 【输入数据】 一个整数n，表示要输出杨辉三角的第n行。 【输出数据】 一行，杨辉三角的第n行，两个数之间用空格隔开。 【数据范围】 对于30%数据，0 某一天，tenshi看了一本趣味数学书，上面提到了亲和数：定义数对 (x,y) 为亲和数对当且仅仅当x、y为不同正整数，且x、y各自的所有非自身正因子之和等于另一个数。例如 (220,284) 和 (280,224) 都是亲和数对，因为： 220的所有非自身正因子之和为：1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284 284的所有非自身正因子之和为：1 + 2 + 4 + 71 + 142 = 220 数对 (x,y ) 跟 (y,x) 被认为是同一数对，所以我们只考虑 x 算法与程序设计模块(选择题) 1.用流程图描述算法中表示“条件判断”的图形符号是 A. B. C. D. 答案：A 2.以下为求0到1000以内所有奇数和的算法，从中选出描述正确的算法 A. ①s=0； ②i=1； ③s=s+i； ④i=i+2； ⑤如果i≤1000，则返回③； ⑥结束 B. ①s=0； ②i=1； ③i=i+2； ④s=s+i； ⑤如果i≤1000，则返回③； ⑥结束 C. ①s=1； ②i=1； ③s=s+i； ④i=i+2； ⑤如果i≤1000，则返回③； ⑥结束 D. ①s=1； ②i=1； ③i=i+2； ④s=s+i； ⑤如果i≤1000，则返回③； ⑥结束 答案：A 3.在VB语言中，下列数据中合法的长整型常量是 A. 123456 B. 1234.56 C. 12345A D. A12345 答案：A 4.在VB语言中可以作为变量名的是 A. Print B. ab=cd C. 123abc D. abc_123 答案：D 5.设置TextBox的字体时，应改变TextBox的 A. Text属性 B. Font属性 C. ForeColor属性 D. Name属性 答案：B 7.代数式a ac b 24 2 对应的VB表达式是 A. sqr(b*b－4*a*c)/2*a B. sqr(b*b－4*a*c)/2/a C. sqr(b*b－4*a*c)/(2/a) D. sqr(b*b－4*a*c)/2a 答案：B 8.在VB语言中，下列正确的赋值语句是 A. I=I+1 B. I+1=I C. I*3=I D. 2I=I+1 答案：A 9.下列计算机程序设计语言中不属于高级语言的是 A. C++ B. Visual Basic C.机器语言 D. Java 答案：C 计算机程序设计语言:机器语言010*******汇编语言高级语言10.在VB语言中，下列逻辑表达式的值为"假"的是 A. #1/11/2009# > #11/15/2008# B. #1/11/2009# < #11/15/2008# C. 5 > 3 and 6 < 9 D. 5 > 3 or 6 > 9 答案：B 11.用流程图描述算法中表示“开始/结束”的图形符号是 A. B. C. D. 答案：B 一、选择题 1、流程图是描述（）的常用方式。 A、程序 B、算法 C、数据结构 D、计算规则 2、下面不属于算法描述方式的是（）。 A、自然语言 B、伪代码 C、流程图 D、机器语言 3、以下运算符中运算优先级最高的是（）。 A、+ B、^ C、>= D、* 4、某程序中三个连续语句如下： a=1 b=2 c=b+a 它属于（） A、顺序结构 B、选择结构 C、循环结构 D、以上三种都不是 5、穷举法的适用范围是（） A、一切问题 B、解的个数极多的问题 C、解的个数有限且可一一列举 D、不适合设计算法 6、在现实生活中，人工解题的过程一般分为（） A、理解分析问题→寻找解题方法→用工具计算→验证结果 B、寻找解题方法→理解分析问题→用工具计算→验证结果 C、用工具计算→验证结果→寻找解题方法→理解分析问题 D、用工具计算→验证结果→理解分析问题→寻找解题方法 7、下列关于算法的特征描述不正确的是（） A、有穷性：算法必须在有限步之内结束 B、确定性：算法的每一步必须确切的定义 C、输入：算法必须至少有一个输入 D、输出：算法必须至少有一个输出 8、下列哪一个不是用于程序设计的软件（） A、BASIC B、C语言 C、Word D、Pascal 9、下列可以作为合作变量名的是（） A、a7 B、7a C、a-3 D、8 10、编程求1+2+3+........+1000的和，该题设计最适合使用的控制结构为（）。 A、顺序结构 B、分支结构 C、循环结构 D、选择结构 11、下列步骤不属于软件开发过程的是（） A、任务分析与系统设计 B、软件的销售 C、代码编写与测试 D、软件测试与维护12．以下程序段运行时，语句k=k+1 执行的次数为（）次。 基本算法模块 对于NOIP，基础是相当重要的，在3个小时之内做完4道题，那么就要求我们有相当快的速度。特别是对于一些简单的、常用的算法模块，一定要要熟练掌握并灵活运用。由于NOIP是一个比较基础的比赛，因此基本算法的掌握尤为重要，所以要求能够把这些基本的模块快速、准确的移植到不同的程序中，才能在稳中取胜。 基本算法模块中最重要的是基本程序框架，也就是说，要养成适合于自己的程序风格，这样对于程序编写的速度与程序的准确度都有较大的提高。 模块目录 一、排序 1．选择排序 2．插入排序 3．冒泡排序 4．快速排序 5．堆排序 6．归并排序 7．线性时间排序二、高精度 1．高精度比较 2．高精度加法 3．高精度减法 4．单精度乘法 5．高精度乘法 6．单精度除法 7．高精度除法 8．进制转换 三、数论 1．欧几里德算法 2．扩展欧几里德 3．求最小公倍数 4．求解线形同余方程 5．素数的判断 6．素数的生成 四、排列组合 1．排列生成算法 2．组合生成算法 3．排列按序生成法 4．排列字典序生成法五、图论 1．图的读入 2．深度优先搜索 3．广度优先搜索 4．强连同分量 5．拓扑排序 6．最小生成树 7．最短路径 六、背包问题 1．装满背包 2．一维价值最大背包 3．二位价值最大背包 一、排序算法 var a:array[1..maxn]of longint;——排序对象 1．选择排序——Select_sort procedure select_sort; begin for i:=1to n-1do for j:=i+1to n do if a[i]>a[j]then begin temp:=a[i];a[i]:=a[j];a[j]:=temp;end; end; 2．插入排序——Insert_sort procedure insert_sort; begin for i:=2to n do begin key:=a[i];j:=i-1; while(key 2014山东省信息技术学考算法与程序设计试题答案附后讲解 山东省学考算法与程序设计试题 选择题 1、下列VB表达式中： ⑴Sqr(x) ⑵Text1.text ⑶Command1.caption ⑷"45"+"34" ⑸45+34值为字符串类型的是（） A⑴⑵⑶ B⑵⑶⑷ C ⑴⑶⑸ D⑵⑷⑸ 2、如果给出三条线段的长分别为a、b、c，且已知a≤b≤c，要问这三条线段能否构成三角形，仅需下列选项中的哪个判定条件即可？（） A 其他选项都不对 B a+c>b C a+b>c D b+c>a 3、VB程序中“Dim n As Integer”这条语句的作用是（） A 定义一个事件过程 B 定义一个数据输入方法 C 定义一个变量 D 定义一个数据处理方法 4、关于算法的描述，下列选项中正确的是（） A 算法的每一步骤必须有确切的含义 B 算法必须有输入 C 算法的步骤可以是无穷的 D 算法本身就是一种程序设计语言 5、关于算法的描述，正确的是（） A同一种算法只能用一种程序语言实现 B算法就是数值计算的方法 C描述算法的方法只有流程图 D算法是描述解决问题的方法和步骤 6、算法的描述方法有多种，下列选项中不适合描述算法的是（） A机器语言 B自然语言 C流程图 D伪代码 7、长度分别为a、b、c的三条线段，能够组成三角形的条件是（） A a+b>c Or a+c>b Or b+c>a B a+b>c or a+c>b And b+c>a C a+b>c Or a+c>b And b+c>a D a+b>c And a+c>b And b+c>a 8、已知海伦公式：()()() p p a p b p c ---p=1 2 （a+b+c），a、b、c分别为三角形的三条 边长。利用海伦公式求三角形面积的算法属于（） A 排序法 B 解析法 C 穷举法 D 查找法 9、以下程序段中循环体执行的次数是（） s=0 i=0 Do While s<10 i=i+1 s=s+i*i Loop A 1 B 3 C 2 D 4 10、下列VB表达式中，能正确表达不等式方程|x|>1的解的是（） A x>-1 and x<1 B x>-1 or x<1 C x<-1 and x>1 D x<-1 or x>1 11、一元二次方程ax2+bx+c=0(a≠0)的两个实数根分别为： x 1 24 b b ac -+- 2 24 b b ac ---下列表达式正确的是（） A x 2=-b-sqr(b^2-4*a*c)/(2*a) B x 1 =(-b+sqr(b^2-4ac))/(2*a) Tarjan算法Pascal语言描述 Tarjan算法Pascal语言描述 TonyShaw 那天做了个2-sat题，里面牵扯到求有向图的强连通分量，我这么弱，显然不会，于是从网上找求有向图的强连通分量的方法，有一个是DFS两遍，同时建原图与补图，算法名字是B？？？忘掉了，反正当时同时看见了Tarjan算法。鉴于我对于Tarjan的略微崇拜，于是想先学一下Tarjan。写这篇文章的原因在于，我在网上没有找到Pascal语言描述的程序，同时一些关于这个算法的解释不是很清楚，所以我想写一下，算是我对该算法理解的总结，也算是为其他要学习该算法的人提供点无用的参照吧。 算法思想：从一个点开始，进行深度优先遍历，同时记录到达该点的时间（dfn记录到达i 点的时间），和该点能直接或间接到达的点中的最早的时间（low记录这个值，其中low的 初始值等于dfn）。（如图。假设我们从1开始DFS，那么到达1的时间为1，到达2的时间为2，到达3的时间为3。同时，点1能直接或间接到达的点中，最小时间为1，点2能通过3间接到达点1，所以点2可到达最早的点时间为1，点3可以直接到达点1，故点3到达的最早的点的时间为1。）。对于每一个没有被遍历到的点A，如果从当前点有一条到未遍历点A的有向边，则遍历到A，同时将点A入栈，时间戳+1并用dfn[a]记录到达点A的时间，枚举从A发出的每一条边，如果该边指向的点没有被访问过，那么继续dfs，回溯后low[a]:=min(low[a],low[j])(其中j为A可以到达的点。)如果该点已经访问过并且该点仍在栈里，那么low[a]=min(low[a],dfn[j])。 解释：若点j没有被访问过，那么回溯后low[j]就是j能到达最早点，a能到达的最早点当然就是a本身能到达的最早点，或者a通过j间接到达的最早点。若点j已经被访问过，那么low[j]必然没有被回溯所更新。所以low[a]就等于a目前能到达的最小点或a直接到达点j 时点j的访问时间。注意：两个句子中的“或”其实指的是两者的最小值。那么如果我们回溯 《算法与程序设计》模块会考复习题 一.单选题 1. java方法重载时参数不可能出现的情况是____D______。P67 A．参数的个数不同 B．参数的个数相同而参数的类型不同 C．参数不完全对应相同D．参数完全对应相同 2. 运行Java程序需要的工具软件所在的目录是___A_______。P16 A．JDK的bin目录B．JDK的demo目录 C．JDK的lib目录D．JDK的jre目录 3. J_HelloWorld.java 的文件内容如下： class J_HelloWorld { public static void Main(String args[]) M不应大写 { System.out.println(" Hello World "); } } 下面说法正确的是____B______。 A．J_HelloWorld.java无法通过编译，因为main方法的声明方式不对 B．J_HelloWorld.java可以通过编译，但程序运行时出现“程序中没main方法”的异常C．J_HelloWorld.java可以通过编译，但无法运行，因为该文件没有public类 D．J_HelloWorld.java可以通过编译并正常运行，结果输出字符串“Hello World” 4. 逻辑表达式!(3/2==1.5)&& 9<3|| 9>3的运算结果为_____A_______。 P9 A．true Ｂ．false Ｃ．表达式有错Ｄ．条件不足 5. 下列可以将变量x和y的值互换的语句是___B______。P35 A．x=y；y=x； B．z=x；x=y；y=z； C．x=z；z=y；y=x； D. x=（x+y）/2；y=（x-y）/2； 6. 执行完下面程序片段之后，下面结论正确的是___B_____。 P43 int a,b,c; a=1;b=2; c=(a+b)>3 ? a++:b++; A．a的值是2，b的值是3 Ｂ．a的值是1，b的值是3 C．a的值是1，b的值是2 Ｄ．c的值是false。 7. 下面程序片段输出的是___C_______。应使用关系运算符== int a=3,b=1; 新课标高中信息技术《算法与程序设计模块》练习题 一、单选题（每题2分，共40分） 1、四川汶川地震过后，要对各个单位捐款救灾情况进行分组制表，并进行积分排序，一般使用的专业电子处理软件是（） A、powerpoing B、Excel C、Word D、Visual Basic 2、一位爱好程序设计的同学，想通过程序设计解决“韩信点兵”的问题，他制定的如下工作过程中，更恰当的是（） A、设计算法，编写程序，提出问题，运行程序，得到答案 B、分析问题，编写程序，设计算法，运行程序，得到答案 C、分析问题，设计算法，编写程序，运行程序，得到答案 D、设计算法，提出问题，编写程序，运行程序，得到答案 3、交通警察到达案发现场，一般按照下列哪种思路开展工作（） ①观察、分析现场②收集必要的信息③进行判断、推理④按一定的方法和步骤解决 A、②①③④ B、①③②④ C、③①②④ D、①②③④ 4、下面说法正确的是（） A、算法+数据结构=程序 B、算法就是程序 C、数据结构就是程序 D、算法包括数据结构 5、下列常量说明中，符合语法的是（） A、CONST color=red B、CONST const=10*5 C、CONST xl：=3.9； D、CONST color=”abcd” 6、VB中将两个字符串连接起来的运算符有：+和&，那么“123” +45结果是（） A、168 B、12345 C、”123” D、45 7、字符串”ABCD”和字符串”DCBA”进行比较，如果让比较的结果为真，应选用关系运算符（） A、> B、< C、= D、>= 8、设a，b，c，d，e均为整型变量，且a=13，b=2，c=10，d=3，e=2，则表达式“a-b*c \ d MOD e”的值是( ) A、13 B、-7 C、ll D、0 9、已知A，B，C，D是简单变量，且都已有互不相同的值，执行语句B=8；A=C；D=A；D=B；后，其值相等的变量是（） A、A，D B、A，C C、C，B D、B，A 10、结构化程序设计由三种基本结构组成，下面哪个不属于这三种基本结构（） A、顺序结构 B、输入、输出结构 C、选择结构 D、循环结构 11、下列结果为真的关系表达式是（） A、”A”<100 B、23.5<20 C、23<45 AND 72>8 D、5 12、以下运算符中运算优先级最高的是（） A、+ B、OR C、> D、\ 13、整除运算时，若运算量为实数，则先取整，后相除，结果为整型或长整型。下列哪种是整除运算符（） A、+ B、Mod C、/ D、\ 14、VB结束程序的运行可以单击程序窗体的“关闭”按钮，或 我是在高一接触pascal语言，因为参加NOI的需要，顺理成章的要使用Turbo Pascal来写程序了。半年后，我开始想着如何编写Windows程序，又理所当然的找上Delphi。初见Delphi，除了begin，end 让我觉得倍感亲切外，Object Pascal里的增加的面向对象的语法却让我很是吃惊，当时的我可根本不懂什么叫面向过程，面向对象；最可恶的是，国内那些教育家们，除了会拿着清华的那本精简的不能再精简的pascal教材照本宣科外，似乎再也没有什么实质性的工作了，传说中的《Turbo Pascal大全》更是无处可寻，所以关于unit，interface这些Delphi里随处可见的关键字我也很不明白。所幸，其后不久，我得到一本名为《计算机反病毒技术》的书，里面统统都是用Turbo Pascal编写的源代码，通过它我迅速明白了早已存在于Turbo Pascal中unit，interface等关键字的含义和用法，又以Delphi中的Help文档为扶手，开始蹒跚学步了。 印象中，国内Delphi作家似乎更偏爱编写应用实例类的技术书籍，至于语法这种东西，没有几个人愿意多去涉及，即使书中必须谈及，也是寥寥数笔，匆匆带过，或者干脆与某本书类似。对Object Pascal语法讲解最好，最权威的恐怕就算《Delphi5开发人员指南》了，这本书至今也是备受推崇的。但与如今泛滥的C++书籍相比，Delphi仍然逊色许多，也难怪很多新手特别是从来没有接触过pascal语言的新手，在学习Object Pascal时会遇到不少困难。自己的感觉是：在从Turbo Pascal向Delphi过渡的过程中，由于没有正确的指引，走了很多弯路；由于没有正确的桥梁，必须要一步实现大跨越。所以，在这里，我提出自己曾经遇见的沟壑，路标性给出我自己的认识和总结，希望给入门的同学们一些帮助。我不打算详细介绍语法知识，并假设你已经有一点pascal语言和面向对象概念的基础。要想学习相关详细知识，我推荐各位一定要阅读《Delphi开发人员指南》和Delphi Help文档中的相关章节。 ●记录体和类 习惯了在一个Program模块内写完所有面向过程代码的我，有几天的时间一直未能彻底明白在非Unit模块中，非继承的自定义类的框架，语法是如何的，VCL源代码虽然经典，却过于繁杂，不能让我迅速掌握根本，我需要一个最简单又最能说明问题，完整的可运行的代码，苦于无处寻求答案，只好亲自动手，探索对应关系，终成其下两段代码。 program TP;{本代码在Turbo Pascal7.0下编译通过} type MyRecord=record {...} end; var MR:MyRecord; procedure Procedure1; begin {Procedure1Code} end; {===========main===========} begin {以这个begin为标志，主程序开始，其作用相当于C/C++中的main函数} Procedure1; end. 高中信息技术算法与程序设计（VB ）练习题2004 年8月20日作者：洪鼎文化中心浏览选项：大中小--> 颜色Black Red Yellow Pink Green Orange Purple Blue Beige Brown Teal Navy Maroon LimeGreen 本一、选择题： 1. 下列各组控件都具有Caption 属性的是 A. 窗体、文本框 B.标签、定时器 C.窗体、标签 D.文本框、定时器 2. 下列各组控件具有相同默认事件的是 A. 窗体、文本框 B.标签、按钮 C.窗体、标签 D.文本框、按钮 3. 下列每个控件都具有的属性是 A. Name B.Caption C.Font D.Interval 4. 下列运算结果中，值最大的是 A.34 B.3/4 C.4 mod 3 D.3 mod 4 〖/表示除，表示整除，mod表示求余数〗 5. 以下哪个是合法的变量名 A．Len B ．Test@qw C．6cost_1 D．count2s 6. 在Visual Basic 代码中，将多个语句合并在一行上的并行符是 A. 撇号（'） B. 冒号（：） C. 感叹号（！） D. 问号（?） 7. 如果要求设置定时器时间间隔为0.5秒钟，那么它的Interval 属性值应该是 A ．5000 B．500 C．50 D．5 8．下列控件中可设置滚动条是 A.计时器B .标签C.文本框D.按钮 9．下面程序执行的结果是 Private Sub Form_Click（） A = "123": B = "456" C = Val（A） + Val（B）〖val 是把字符转化为数值的函数〗 Print C 100 End Sub A.123 B.3 C.5 D.579 10. 若要求从文本框中输入密码时在文本框中只显示#号，则应当在此文本框的属性窗口中设置 A. Text 属性值为"#" B . Caption 属性值为"#" C . password 属性值为空"#" D . Passwordchar 属性值为"#" 11. 下列逻辑运算结果为"true" 的是 A.flase or not true B.flase and not true C. true or not true D.true and not true 12. 下列控件中可用于接受用户输入文本，又可用于显示文本的是 A. Label 控件 B. TextBox 控件 C. Timer 控件 D. CommandButton 控件 13. 以下程序段执行后，整型变量n 的值为 year=2001 n=year4+year400-year100 A. 495 B. 505 C. 500 D. 485 算法与程序设计综合评价练习题 一、利用计算机解决问题的基本过程 判断题： 1、一个算法有一个或多个输出，但可以没有输入。（）参考答案：正确。 2、我们常说的程序设计语言就是程序设计。（）参考答案：错误。 3、一个算法可以用多种程序设计语言来实现。（）参考答案：正确。 4、用计算机解决问题要经过分析问题——设计算法——编写程序——调试程序等基本过程。（）参考答案：正确。单选题： 5、在日常生活中，我们常常会碰到许多需要解决的问题，以下描述中最适合用计算机编程来处理的是（）。 A、确定放学回家的路线 B、计算某个同学期中考试各科成绩总分 C、计算10000以内的奇数的平方和 D、在因特网上查找自己喜欢的歌曲参考答案：C 6、以下不属于算法基本特征的是（）。 A、可执行性 B、确定性 C、有穷性 D、无限性参考答案：D 7、生活中有许多工作可以通过编程来解决，但以下描述中，不宜使用编程来处理的是（）。 A、编辑调查报告 B、机器人灭火比赛 C、导弹自动防御系统设置 D、山西省高中生学籍管理系统参考答案：A 8、一位爱好程序设计的同学，想通过程序设计解决“韩信点兵”的问题，他制定的如下工作过程中，最恰当的是（）。 A、设计算法，编写程序，提出问题，运行程序，得到答案 B、分析问题，编写程序，设计算法，运行程序，得到答案 C、分析问题，设计算法，编写程序，运行程序，得到答案 D、设计算法，提出问题，编写程序，运行程序，得到答案参考答案：C 9、以下说法正确的是（）。 A、算法+ 数据结构= 程序设计 B、算法就是程序 C、数据结构就是程序 D、算法包括数据结构 提示：程序=数据结构+算法是由N.Wirth(沃斯)提出来的。数据结构指的是数据与数据之间的逻辑关系，算法指的是解决特定问题的步骤和方法。参考答案：A 10、下列关于算法的描述错误的是（）。 A、算法必须在有限步之内结束 B、算法的第一步必须有确切的含义 C、算法必须至少有一个输入 D、算法必须至少有一个输出参考答案：C 11、流程图是描述（）的常用方式。 A、程序 B、算法 C、数据结构 D、计算规则参考答案：B 12、算法描述可以有多种表达方法，下面不属于算法描述的是（）。 A、自然语言 B、流程图 C、伪代码 D、机器语言参考答案：D 13、在使用流程图描述算法时，表示变量的计算与赋值应使用的符号框为（）。 A、矩形框 B、菱形框 C、平行四边形框 D、椭圆形框参考答案：A 第一套 1.有如下程序段： x=5 y=6 p=Not(x+y=11) 该程序段运行后，P的值是 (1)False或0 。 2. 有如下程序段： x=5 y=10 z=12 if x+y<=z Or y+z<=x Or x+z<=y then a=" False" else a=" True" 该程序段运行后，a 的值为(1)True 。 3. 有如下程序段： s=0 for i=1 to 5 s=s+i*i next i 该程序段运行后，s的值为(1) 55 。 4. 程序填空 随机产生10个0～100之间的整数，按从小到大的次序排序并输出。为了实现这一目标，完善下面 的VB程序，在划线处填入合适的语句或表达式，完成程序设计（流程图参见图12-3）。 图12-3 sub command1_click() const n=10 dim i,j,t as integer dim a(1 to 10) as integer for i=1 to 10 ______(1)__a(i)=int(Rnd*101)________ next i For i = 1 To n - 1 For j = i+1 To n If ______(2)_a(i)>a(j)_____ Then k = a(i): a(i) = a(j): a(j) = k End If Next j Next i For i = 1 To n List1.AddItem Str(a(i)) Next i 第二套 1.有如下程序段： x=5 y=6 t=x x=y y=t 该程序段运行后，y的值为 (1)5 。 2. 有如下程序段： x=5 y=-20 if not x>0 then x=y-3 else y=x+3 该程序段运行后，x 的值为 (1) 5 。 3. 有如下程序段： e=0:f=1 for i=1 to 3 e=e+f f=f+e next i 该程序段运行后，f的值为 (1) 13 。 4. 程序填空 有30个人，其中有男人、女人和小孩。他们在一家饭馆里花去500元。已知，每个男人花30元，每个女人花20元，每个小孩花10元。问男人、女人、小孩各为多少人？ 为了实现这一目标，完善下面的VB程序，在划线处填入合适的语句或表达式，完成程序设计。 sub command1_click() dim man,woman,child,s as integer for man =1 to 15 for woman =1 to 23 child = _______(1)_30-woman-man_ s=30* man+20* woman+ 10*child if ___ (2) s=500 and child>0 then list1.additem str(man)+" "+str(woman)+" "+ str(child) end if 选修：算法与程序设计选择题 [日期：2010-04-28] 来源：作者：[字体：大中小] 1. 结构化程序设计由三种基本结构组成，下面哪个不属于这三种基本结构之一（B） A.顺序结构 B.并列结构 C.选择结构 D.循环结构 2．下面不合法的运算符是（D） A. + B. - C.* D.% 3.下列表示中不是字符串常量的是（D）。 A.“ab” B.“你好” C."2006" D. 1235 4．下列哪一个不是用于程序设计的（C） A. BASIC B. C语言 C.WORD D.Pasical 5.下列可以作为合法变量的是（A） A.a7 B.7a C.a-3 D.8 6. 下面不合法的运算符是（D） A. + B. - C.* D.& 7．结构化程序设计由三种基本结构组成，下面哪个不属于这三种基本结构之一（B） A.顺序结构 B.环形结构 C.选择结构 D.循环结构 8.二进制数1101转化为十进制数是（B）。 A、11 B、13 C、10 D、14 9．下列表示中是字符串常量的是（B）。 A.ab B.“你好” C.2006 D.1235 10.下列可以作为合法变量的是（A） A.a1 B.7a C.a-3 D.8 11.下列不属于算法结构的是（C） A.输入数据 B.处理数据 C.存储数据 D.输出结果 12.警察到达案发现场，一般按照下列哪种思路开展工作（D） ①观察、分析现场②收集必要的信息③进行判断、推理④按一定的方法和步骤解决 A.②①③④ B.①③②④ C.③①②④ D.①②③④ 13.结构化程序设计由三种基本结构组成，下面哪三种结构是正确的。（A） ①顺序结构②输入、输出结构③分支结构④循环结构 A. ①③④ B. ①③② C. ①②④ D. ①②③ 14.下列可以作为合法变量名的是：（B） A.15b B.a1 C.else D.for 15.下列表示中不是常量的是（D）。 A.month B.not C."2006" D.abc 16.学校要举行运动会，请你设计一个能够对运动员分数自动排序的软件，如果要设计此软件，以下最好的方法和步骤是（C） A.分析问题，编写程序，设计算法，调试程序 B.设计算法，编写程序，提出问题，调试程序 C.提出问题，设计算法，编写程序，调试程序 Ｄ.设计算法，提出问题，编写程序，调试程序Pascal基础知识
高中信息技术《算法与程序设计》试题
pascal 过程与函数教程
高二算法与程序设计试题及答案
算法与程序设计真题2017级整理版-选择题
pascal算法题
算法与程序设计模块(选择题)汇总
历年算法与程序设计学业水平考试真题带答案
pascal 基本算法
2014山东省信息技术学考算法与程序设计试题答案附后讲解
Tarjan算法 Pascal语言描述
算法与程序设计会考复习题答案
高中信息技术《算法与程序设计模块》练习题
PASCAL语法解释
高中信息技术算法与程序设计练习题
算法与程序设计综合评价练习题
算法与程序设计填空题10套
算法与程序设计选择题
相关主题
文本预览