高端豪宅别墅 国外奢华别墅高清图片案例.doc

清北学堂信息学竞赛辅导班测试题
时间:3小时 2004年7月
学校:______ 姓名:______
注意:最大公约数用(a,b)表示,a除以b的余数用a mod b表示,计算题要算出最后结果。
一、(8分) 编码
在书写以下语句时,要注意可能出现哪些错误?如果不会出错,写“无”
:______
:______
:______
:______
:______
:______
:______
:______
二、(8分) 算法分析
分析以下程序段的时间复杂度。其中n为输入规模,为正整数。上限应该尽量紧
:O(__)
a := n * n; a = n*n;
:O(__)
for i:=1 to n do j := j + n; for(i=1;i<=n;i++)j+=n;
:O(__)
for i:=n downto 1 do for(i=n;i>=1;i--)
for j:=1 to n do for(j=1;j<=n;j++)
k := i * j; k=i*j;
:O(__)
for i:=1 to n do for(i=1;i<=n;i++)
for j:=i to n do for(j=i;j<=n;j++)
k := 1; k=1;
:O(__)
i := n; i=n;
while i>0 do i := i div 2; while(i>0)i/=2;
(1)的时间复杂度为:O(__)
function test(a:integer):integer; int test(int a){ if (a>n) return test(a+1)+test(a+1); }
begin
if(a<n) test:=test(a+1)+test(a+1);
end;
(n)的时间复杂度为:O(__)
function test(a:integer):integer; int test(int a){
var i:integer; for(int i=1;i<=a;i++)c++;
begin if (a>1) return test(a+1)+test(a+1); }
for i:=1 to a do c := c + 1;
if(a>1) test:=test(a div 2)+test(a div 2);
end;
:O(__)
j:=1; j=1;
for i:=1 to n do for(i=1;i<=n;i++){ while(j<=n&&a[j]<k)j++;j++; }
begin
while (j<=n) and (a[j]<k) do j++;
j++;
end;
三、(6分) 调试与测试
测试某一段程序A
经测试,n扩大10倍,运行时间扩大约100倍,则算法的时间复杂度最有可能是____
a. O(n) b. O(n2) c. O(nlogn)
这个程序通常可以支持n<=____的规模
a. 3000 b. 10 c. 100,000
对于同样的规模,另一个程序B比它快2秒,能说明A比B的渐进时间复杂度高吗?
a. 可以 b. 不可以
程序中有这样一条语句:if ok(a) and ok(b) and ok(c) then funA(b) else funB(c);
用白箱测试法让它覆盖完所有条件,需要至少取几组a,b,c?
a. 2组 b. 8组 c. 6组
跟踪调试发现,语句a[i]:=2; 执行完后b[3]突然变成2了,问题的原因是______;
a. 算术运算溢出 b. I/O错误 c. 下标越界
接上题,如果要让Pascal编译器通知此事,应打开编译开关______。
a. 范围检查开关 b. 算术溢出检查开关 c. I/O错误开关
接上题,什么时候应该关闭此开关________
接上题,和此开关同时打开和关闭的一般还有____________开关
四、(8分) 排序
对于常见的算法,平均情况的时间复杂度为:
:____ :_____ :______ :______
四个算法中(只填字母代号。,,,