【1】 假设有一个池塘，里面有无穷多的水。现有2个空水壶，容积分别为5升和6升。问题是如何只用这2个水壶从池塘里取得3升的水。
由满6向空5倒，剩1升，把这1升倒5里，然后6剩满，倒5里面，由于5里面有1升水，因此6只能向5倒4升水，然后将6剩余的2升，倒入空的5里面，再灌满6向5里倒3升，剩余3升。
【2】 周雯的妈妈是豫林水泥厂的化验员。一天，周雯来到化验室做作业。做完后做稿想出去玩。"等等，妈妈还要考你一个题目，"她接着说，"你看这6只做化验用的玻璃杯，前面3只盛满了水，后面3只是空的。你能只移动1只玻璃杯，就便盛满水的杯子和空杯子间隔起来吗?"爱动脑筋的周雯，是学校里有名的"小机灵"，她只想了一会儿就做到了。请你想想看，"小机灵"是怎样做的?
设杯子编号为ABCDEF，ABC为满，DEF为空，把B中的水倒进E中即可。
【3】 三个小伙子同时爱上了一个姑娘，为了决定他们谁能娶这个姑娘，他们决定用手q进行一次决斗。小李的命中率是30%，小黄比他好些，命中率是50%，最出色的q手是小林，他从不失误，命中率是100%。由于这个显而易见的事实，为公平起见，他们决定按这样的顺序：小李先开q，小黄第二，小林最后。然后这样循环，直到他们只剩下一个人。
那么这三个人中谁活下来的机会最大呢?他们都应该采取什么样的策略?
小林在轮到自己且小黄没死的条件下必杀黄，再跟菜鸟李单挑。
所以黄在林没死的情况下必打林，否则自己必死。
小李经过计算比较(过程略)，会决定自己纯大孝先打小林。
于是经计算，小李有873/2600≈33.6%的生机
小黄有109/260≈41.9%的生机
小林有24.5%的生机。
哦，这样，那小李的第一q会朝天仿段开，以后当然是打敌人，谁活着打谁
小黄一如既往先打林，小林还是先干掉黄，冤家路窄啊!
最后李，黄，林存活率约38：27：35
菜鸟活下来抱得美人归的几率大。
李先放一空q(如果合伙干中林，自己最吃亏)黄会选林打一q(如不打林，自己肯定先玩完了)林会选黄打一q(毕竟它命中率高)李黄对决0.3:0.280.4可能性李林对决0.3:0.60.6可能性成功率0.73
李和黄打林李黄对决0.3:0.40.7 0.4可能性李林对决0.3:0.7 0.6 0.70.7 0.6可能性成功率0.64
【4】 一间囚房里关押着两个犯人。每天监狱都会为这间囚房提供一罐汤，让这两个犯人自己来分。起初，这两个人经常会发生争执，因为他们总是有人认为对方的汤比自己的多。后来他们找到了一个两全其美的办法：一个人分汤，让另一个人先选。于是争端就这么解决了。可是，现在这间囚房里又加进来一个新犯人，现在是三个人来分汤。必须寻找一个新的方法来维持他们之间的和平。该怎么办呢?按：心理问题，不是逻辑问题
是让甲分汤，分好后由乙和丙按任意顺序给自己挑汤，剩余一碗留给甲。这样乙和丙两人的总和肯定是他们两人可拿到的最大。然后将他们两人的汤混合之后再按两人的方法再次分汤。
【5】 在一张长方形的桌面上放了n个一样大小的圆形硬币。这些硬币中可能有一些不完全在桌面内，也可能有一些彼此重叠当再多放一个硬币而它的圆心在桌面内时，新放的硬币便必定与原先某些硬币重叠。请证明整个桌面可以用4n个硬币完全覆盖。
要想让新放的硬币不与原先的硬币重叠，两个硬币的圆心距必须大于直径。也就是说，对于桌面上任意一点，到最近的圆心的距离都小于2，所以，整个桌面可以用n个半径为2的硬币覆盖。
把桌面和硬币的尺度都缩小一倍，那么，长、宽各是原桌面一半的小桌面，就可以用n个半径为1的硬币覆盖。那么，把原来的桌子分割成相等的4块小桌子，那么每块小桌子都可以用n个半径为1的硬币覆盖，因此，整个桌面就可以用4n个半径为1的硬币覆盖。
【6】 一个球、一把长度大约是球的直径2/3长度的直尺.你怎样测出球的半径?方法很多，看看谁的比较巧妙
把球放在平面上,把直尺的一边卡在平面上,一边卡在球上,球与尺子的接触点到平面的距离就是球的半径.因为直尺长度约为直径的2/3>半径,所以能测量.
【7】 五个大小相同的一元人民币硬币。要求两两相接触，应该怎么摆?
底下放一个1，然后2 3放在1上面，另外的4 5竖起来放在1的上面。
【8】 猜牌问题S先生、P先生、Q先生他们知道桌子的抽屉里有16张扑克牌：红桃A、Q、4黑桃J、8、4、2、7、3草花K、Q、5、4、6方块A、5。约翰教授从这16张牌中挑出一张牌来，并把这张牌的点数告诉P先生，把这张牌的花色告诉Q先生。这时，约翰教授问P先生和Q先生：你们能从已知的点数或花色中推知这张牌是什么牌吗?于是，S先生听到如下的对话：P先生：我不知道这张牌。Q先生：我知道你不知道这张牌。P先生：现在我知道这张牌了。Q先生：我也知道了。听罢以上的对话，S先生想了一想之后，就正确地推出这张牌是什么牌。请问：这张牌是什么牌? 方块5
【9】 一个教授逻辑学的教授，有三个学生，而且三个学生均非常聪明!一天教授给他们出了一个题，教授在每个人脑门上贴了一张纸条并告诉他们，每个人的纸条上都写了一个正整数，且某两个数的和等于第三个!(每个人可以看见另两个数，但看不见自己的)教授问第一个学生：你能猜出自己的数吗?回答：不能，问第二个，不能，第三个，不能，再问第一个，不能，第二个，不能，第三个：我猜出来了，是144!教授很满意的笑了。请问您能猜出另外两个人的数吗?
经过第一轮，说明任何两个数都是不同的。第二轮，前两个人没有猜出，说明任何一个数都不是其它数的两倍。现在有了以下几个条件：1.每个数大于02.两两不等3.任意一个数不是其他数的两倍。每个数字可能是另两个之和或之差，第三个人能猜出144，必然根据前面三个条件排除了其中的一种可能。假设：是两个数之差，即x-y=144。这时1(x，y>0)和2(x!=y)都满足，所以要否定x+y必然要使3不满足，即x+y=2y，解得x=y，不成立(不然第一轮就可猜出)，所以不是两数之差。因此是两数之和，即x+y=144。同理，这时1，2都满足，必然要使3不满足，即x-y=2y，两方程联立，可得x=108，y=36。
这两轮猜的顺序其实分别为这样：第一轮(一号，二号)，第二轮(三号，一号，二号)。这样分大家在每轮结束时获得的信息是相同的(即前面的三个条件)。
那么就假设我们是C，来看看C是怎么做出来的：C看到的是A的36和B的108，因为条件，两个数的和是第三个，那么自己要么是72要么是144(猜到这个是因为72的话，108就是36和72的和，144的话就是108和36的和。这样子这句话看不懂的举手):
假设自己(C)是72的话，那么B在第二回合的时候就可以看出来，下面是如果C是72，B的思路：这种情况下，B看到的就是A的36和C的72，那么他就可以猜自己，是36或者是108(猜到这个是因为36的话，36加36等于72，108的话就是36和108的和)：
如果假设自己(B)头上是36，那么，C在第一回合的时候就可以看出来，下面是如果B是36，C的思路：这种情况下，C看到的就是A的36和B的36，那么他就可以猜自己，是72或者是0(这个不再解释了)：
如果假设自己(C)头上是0，那么，A在第一回合的时候就可以看出来，下面是如果C是0，A的思路：这种情况下，A看到的就是B的36和C的0，那么他就可以猜自己，是36或者是36(这个不再解释了)，那他可以一口报出自己头上的36。(然后是逆推逆推逆推)，现在A在第一回合没报出自己的36，C(在B的想象中)就可以知道自己头上不是0，如果其他和B的想法一样(指B头上是36)，那么C在第一回合就可以报出自己的72。现在C在第一回合没报出自己的36，B(在C的想象中)就可以知道自己头上不是36，如果其他和C的想法一样(指C头上是72)，那么B在第二回合就可以报出自己的108。现在B在第二回合没报出自己的108，C就可以知道自己头上不是72，那么C头上的唯一可能就是144了。
史上最雷人的应聘者
【10】 某城市发生了一起汽车撞人逃跑事件，该城市只有两种颜色的车,蓝15%绿85%，事发时有一个人在现场看见了，他指证是蓝车，但是根据专家在现场分析,当时那种条件能看正确的可能性是80%那么,肇事的车是蓝车的概率到底是多少?
15% 80%/(85%×20%+15% 80%)
【11】 有一人有240公斤水，他想运往干旱地区赚钱。他每次最多携带60公斤，并且每前进一公里须耗水1公斤(均匀耗水)。假设水的价格在出发地为0，以后，与运输路程成正比，(即在10公里处为10元/公斤，在20公里处为20元/公斤......)，又假设他必须安全返回，请问，他最多可赚多少钱?
f(x)=(60-2x)*x,当x=15时，有最大值450。
450×4
【12】 现在共有100匹马跟100块石头，马分3种，大型马中型马跟小型马。其中一匹大马一次可以驮3块石头，中型马可以驮2块，而小型马2头可以驮一块石头。问需要多少匹大马，中型马跟小型马?(问题的关键是刚好必须是用完100匹马) 6种结果
【13】 1=5，2=15，3=215，4=2145那么5=?
因为1=5，所以5=1.
【14】 有2n个人排队进电影院，票价是50美分。在这2n个人当中，其中n个人只有50美分，另外n个人有1美元(纸票子)。愚蠢的电影院开始卖票时1分钱也没有。问：有多少种排队方法使得每当一个拥有1美元买票时，电影院都有50美分找钱
注：1美元=100美分拥有1美元的人，拥有的是纸币，没法破成2个50美分
本题可用递归算法，但时间复杂度为2的n次方，也可以用动态规划法，时间复杂度为n的平方，实现起来相对要简单得多，但最方便的就是直接运用公式：排队的种数=(2n)!/[n!(n+1)!]。
如果不考虑电影院能否找钱，那么一共有(2n)!/[n!n!]种排队方法(即从2n个人中取出n个人的组合数)，对于每一种排队方法，如果他会导致电影院无法找钱，则称为不合格的，这种的排队方法有(2n)!/ (n-1)!(n+1)! 种，所以合格的排队种数就是(2n)!/[n!n!]- (2n)!/[(n-1)!(n+1)!] =(2n)!/[n!(n+1)!]。至于为什么不合格数是(2n)!/[(n-1)!(n+1)!]，说起来太复杂，这里就不讲了。
【15】 一个人花8块钱买了一只鸡，9块钱卖掉了，然后他觉得不划算，花10块钱又买回来了，11块卖给另外一个人。问他赚了多少?
2元
【16】 有一种体育竞赛共含M个项目，有运动员A，B，C参加，在每一项目中，第一,第二,第三名分别的X，Y，Z分，其中X,Y,Z为正整数且X>Y>Z。最后A得22分，B与C均得9分，B在百米赛中取得第一。求M的值，并问在跳高中谁得第二名。
因为ABC三人得分共40分,三名得分都为正整数且不等,所以前三名得分最少为6分,40=5 8=4 10=2 20=1 20,不难得出项目数只能是5.即M=5.
A得分为22分,共5项,所以每项第一名得分只能是5,故A应得4个一名一个二名.22=5*4+2,第二名得1分,又B百米得第一,所以A只能得这个第二.
B的5项共9分,其中百米第一5分,其它4项全是1分,9=5+1=1+1+1.即B除百米第一外全是第三,跳高第二必定是C所得.
【17】 前提：
1 有五栋五种颜色的房子
2 每一位房子的主人国籍都不同
3 这五个人每人只喝一种饮料，只抽一种牌子的香烟，只养一种宠物
4 没有人有相同的宠物，抽相同牌子的香烟，喝相同的饮料
提示：1 英国人住在红房子里
2 瑞典人养了一条狗
3 丹麦人喝茶
4 绿房子在白房子左边
5 绿房子主人喝咖啡
6 抽PALL MALL烟的人养了一只鸟
7 黄房子主人抽DUNHILL烟
8 住在中间那间房子的人喝牛奶
9 挪威人住第一间房子
10 抽混合烟的人住在养猫人的旁边
11 养马人住在抽DUNHILL烟的人旁边
12 抽BLUE MASTER烟的人喝啤酒
13 德国人抽PRINCE烟
14 挪威人住在蓝房子旁边
15 抽混合烟的人的邻居喝矿泉水
问题是：谁养鱼???
第一间是黄房子，挪威人住，喝矿泉水，抽DUNHILL香烟，养猫! f/ [% a: \6 L! J. Q9 x第二间是蓝房子，丹麦人住，喝茶，抽混合烟，养马+ o8 _0 S) L8 i' E' u第三间是红房子，英国人住，喝牛奶，抽PALL MALL烟，养鸟/ N9 o/ n2 M# U" c第四间是绿房子，德国人住，喝咖啡，抽PRINCE烟，养猫、马、鸟、狗以外的宠物7 P5 l) G, G, |C, {7 V第五间是白房子，瑞典人住，喝啤酒，抽BLUE MASTER烟，养狗。
【18】 5个人来自不同地方，住不同房子，养不同动物，吸不同牌子香烟，喝不同饮料，喜欢不同食物。根据以下线索确定谁是养猫的人。
10.养鱼的人住在最右边的房子里。
11.吸万宝路香烟的人住在吸希尔顿香烟的人和吸“555”香烟的人的中间(紧邻)
12.红房子的人爱喝茶。
13.爱喝葡萄酒的人住在爱吃豆腐的人的右边隔壁。
14.吸红塔山香烟的人既不住在吸健牌香烟的人的隔壁，也不与来自上海的人相邻。
15.来自上海的人住在左数第二间房子里。
16.爱喝矿泉水的人住在最中间的房子里。
17.爱吃面条的人也爱喝葡萄酒。
18.吸“555”香烟的人比吸希尔顿香烟的人住的靠右
第一间是兰房子，住北京人，养马，抽健牌香烟，喝茅台，吃豆腐2 G7 x% z0 vC第二间是绿房子，住上海人，养狗，抽希尔顿，喝葡萄酒，吃面条% C2 k4 o8 t" p6 L* x第三间是黄房子，住香港人，养蛇，抽万宝路，喝矿泉水，吃牛肉&N" S% x# o3 ag第四间是红房子，住天津人，抽555，喝茶，吃比萨7 \5 s. J# d, Q/ N% N' O# ]第五间是白房子，住成都人，养鱼，抽红塔山，喝啤酒，吃鸡。
【19】 斗地主附残局
地主手中牌2、K、Q、J、10、9、8、8、6、6、5、5、3、3、3、3、7、7、7、7
长工甲手中牌大王、小王、2、A、K、Q、J、10、Q、J、10、9、8、5、5、4、4
长工乙手中牌2、2、A、A、A、K、K、Q、J、10、9、9、8、6、6、4、4
三家都是明手，互知底牌。要求是：在三家都不打错牌的情况下，地主必须要么输要么赢。问：哪方会赢?
无解地主怎么出都会输
【20】 一楼到十楼的每层电梯门口都放着一颗钻石，钻石大小不一。你乘坐电梯从一楼到十楼，每层楼电梯门都会打开一次，只能拿一次钻石，问怎样才能拿到最大的一颗?
先拿下第一楼的钻石，然后在每一楼把手中的钻石与那一楼的钻石相比较，如果那一楼的钻石比手中的钻石大的话那就把手中的钻石换成那一层的钻石。
信息学竞赛普及组初赛模拟试题(五)信息学竞赛普及组初赛模拟试题(五)
一、选择题：（每题1.5分，共计30分。每题有5个选项，前10题为单选题，后10题为不定项选择题，全部选对才得分）。
1. 二进制数11011011的十进制值是（ ）
A. 202 B. 219C. 193 D. 209
2. 我国研制的银河Ⅲ型的超级计算机通过基准程序的测试，其峰值速度是（ ）
A. 80亿次 B. 100亿次 C. 130亿次 D. 150亿次
3. 程序段如下：
FOR I:=1 TO 5 DO
FOR J:=2 TO I DO
Writeln(‘*’)
输出’*’的个数是（ ）
A. 5 B. 10 C. 15 D. 25 E. 30
4. 设待排序的记录为（49，38，65，97，76， 13，27 , 49, 55, 4），经过下过程将序列排序
第一趟：13, 27, 49, 55, 4, 49, 38, 65, 97, 76
第二趟：13, 4, 49, 38, 27, 49, 55, 65, 97, 76
第三趟：4, 13, 27, 38, 49, 49, 55, 65, 76, 97
问它所用的方法是：(
A. 冒泡排序 B. 直接选择排序 C. 直接插入排序 D. 希尔排序
5. 设无向树T有7片树叶，其余顶点度均为3，则T中3度顶点有多少个（ ）
A. 5B. 7 C. 9 D. 4 E. 8
6. 设连通图G的顶点数和边数与一立方体相同，即有8个顶点和12条边。任意一棵G的生成树的总边数为（ ）
A．7 B. 8 C. 9D. 10 E. 11
7. 设有两个散列函数h1(k)=k mod 13 和 h2(k)=k mod 11 +1，散列表为T[0…12]，用二次散列法解决冲突。函数h1用来计算散列地址，当发生冲突时，h2作为计算下一个探测地址的地址增量。假定某一时刻散列表的状态为：
0 1 2 3 4 5 6 7 8 9 10 11 12
80 44 35
下一个被插入的关键码为57，其搭码插入的位置为( 。
A. 4B. 5C. 6D. 7E. 8
请根据下面是一段PASCAL程序,判断第8、9题。
for h :=1 to n-1 do begin
x :=A[h+1]
k :=h
while (k>=1) and (A[k]>x) do begin
A[k+1] :=A[k]
k:=k–1
end
A[k+1] :=x
end
8. 假设在程序开始执行时，数组A[1…n]是一组随机整数。下列答案中，哪一个最知此哪好的描述了最差情况下的程序排序的时间复杂度？（ ）
A. O(n log2 n) B. O(n) C. O(log2n)D. O(n2)E. O(2n)
9. 假设在程序开始执行时，扒郑数组A[1…n]是按关键字非递减有序排列时，下列答案中，哪一个最好的描述了最好情况下的程序排序的时间复杂度？（ ）
A. O(n log2 n) B. O(n) C. O(log2n)D. O(n2)E. O(2n)
10.对下列四个序列用快速排序方法进行排序，以序列的第一个元素为划分的基准，在第一趟划分过程中，元素的移动数最多的是哪一个序列（ ）
A. 70 , 65 , 34 , 82 , 53 , 25 , 90
B. 82 , 53 , 25 , 70 , 65 , 34 , 90
C. 34 , 25 , 53 , 65 , 90 , 82 , 70
D. 53 , 25 , 65 , 70 , 34 , 90 , 82
E. 65 , 34 , 82 , 70 , 25 , 53 , 90
11.在计算机运行时，把程序和数据一样存放在内存中，这是1946年由_______所领导的研究小组正式提出并论证的。（ ）
A. 图灵
B. 冯·诺依曼
C. 布尔
D. 赫夫曼
E. 哈希
12.下面关于计算机的说法正确的是（ ）
A. 微机内存容量的基本计量单位是字节
B. 二进制数中右起第10位上的1相当于210
C. CPU每执行一个指令，就完成一步基本运算或判断
D. 1T=1024MB
E. 32位的计算机中的“32”指的是字长
13.为什么说PASCAL是“高级语言”，是因为它（ ）
A. 必须在性能较高的机器上运行
B. 必须经过良好培训的高水平的程序员使用
C. 离机器的硬件较远
D. 开发的时间较长
E. 程序的性能较好
14.以下数据结构中，哪一个是线性结构？（ ）
A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 E. 队列
15.在下面关于计算机系统硬件的说法中不正确的是(
A. 没有外部设备的计算机称为裸机
B. 当关闭计算机电源后，RAM中的程序和数据就消失了
C. 软盘和硬盘上的数据均可由 CPU直接存取
D. 软盘和硬盘驱动器既属于输入设备又属于输出设备
E. CPU主要由运算器、控制器和寄存器组成
16. 下面关于算法的正确说法是（ ）
A. 算法必须有输出
B. 算法必须在计算机上用某种语言实现
C. 算法不一定有输入
D. 算法必须在有限步执行后能结束
E. 算法是程序的灵魂
17.以下关于结构化程序的说法中，正确的是（ ）
A. 结构化程序是由单入口，单出口和循环三种结构组成
B. 结构化程序是出顺序、单入中和单出口三种结构组成
C. 结构化程序是由顺序、循环和GOTO语句结构组成
D. 结构化程序是由顺序、循环和分支三种结构组成
E. “自顶向下，逐步求精”是结构化程序设计方法的特点
18.栈S最多能容纳4个元素。现有6个元素按1，2，3，4，5，6的顺序进栈，问下列哪一个序列是可能的出栈序列？（ ）
A. 5，4，3，2，1，6
B. 3, 2, 5, 4, 1, 6
C. 2, 3, 5, 6, 1, 4
D. 1, 4, 6, 5, 2, 3
E. 4，5，3，6，2，1
19.下列排序算法中，哪些排序是不稳定的（ ）
A．快速排序 B. 基数排序 C. 希尔排序 D. 冒泡排序 E.选择排序
20.下列说法正确的是（ ）
A. 解释程序是接受参数，按照某一样板产生机器语言的计算机程序
B. BASIC语言程序通常需解释执行
C. 连接程序可以把经编译程序产生的目标程序变成可执行的机器语言程序
D. 就执行速度而言，编译程序比解释程序快
E. PASCAL通常是先编译后执行
二、问题求解题（每题5分，共计10分）
1. 由四个结点可以构造多少种不同的二叉树 .
2. 下图是一个设想有11项活动的活动网。其中有9个事件V1，V2，… V9,每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。V1表示整个工程的开始，V9表示结束，与每个活动相联系的数ax(x=1…11)是执行该活动所需的时间（单位：天）。问完成整项工程至少需要天，影响工程进度的关键活动有哪些：。
V2 V7
V1 V5V9
V3V8
V4 V6
三、程序阅读理解题 （每题8分，共计32分）
1．program ex11_8
var
n,i,j,k,p:longint
begin
write('N=12')
i:=2j:=0k:=1
repeat
inc(i)p:=j+kj:=kk:=p
until i=12
writeln('F(',12,')=',p)
end.
运行结果为：
2．program example
var
n:byte
a:array[1..100] of longint
function f(n:byte):longint
var i:longint
begin
if a[n-1]>0 then i:=a[n-1]
else i:=f(n-1)
if a[n-2]>0 then i:=i+a[n-2]
else i:=i+f(n-2)
a[n]:=if:=i
end
begin
fillchar(a,sizeof(a),0)
a[1]:=1a[2]:=1
writeln('F(',8,')=',f(8))
end.
运行结果为:
3．program example3
begin
a[1]:=1t:=0
for i:=2 to 6 do
begin
s:=0
for j:=1 to i-1 do
s:=s+a[j]
a[i]:=s+1
end
for i:=1 to 6 do
t:=t+a[i]
writeln(‘t=’,t)
end.
运行结果为：
4．program example4
var i,s,max:integer
begin
for i:=1 to 10 do read(a[i])
max:=a[1]s:=a[1]
for i:=2 to 10 do
begin
if s<0 then s:=0
s:=s+a[i]
if s>max then max:=s
end
writeln(‘max=’,max)
end.
输入：8 9 –1 24 6 5 11 15 –28 9
运行结果为：
四、程序完善题 (每题14分，共计28分)
1.n×n方阵的每行每列都是自然数1..n的一个全排列，每行（列）无重复数字。
例：
n＝5时，
1 4 3 2 5
5 3 2 1 4
4 2 1 5 3
3 1 5 4 2
2 5 4 3 1
输入 n（>＝2）和第一行数字（不检查错误）
输出 一个满足要求的方阵
因为只是要求每行（列）无重复数字，对第一行的每个数字，都四十五度斜向下写，写到行尽头就从行开头开始。这样就不会重复。
对于经过第y行，第x列的直线，斜率k=1
设：y=x+b
代入坐标，得出：b=y-x
令y=1，取首行的数：x=y-b
x从1开始，到n,如果x为0或负数，则x=x+n，取出第一行的数。
程序只用一维数组，存第一行的数字。
program example2
constmaxn=10000
var
a:array[1..maxn] of integer
x,y,n:integer
function f(x,y:integer):integer
var
b:integer
begin
(1)
(2)
if x<=0 then (3)
f:=a[x]
end
begin
write('Enter n:') readln(n)
if (n<2) or (n>maxn) then exit
write('Enter first line:')
for x:=1 to n do read(a[x])
writeln('Output:')
for x:=1 to n do write(a[x]:4)
writeln
for y:=2 to n do
begin
for x:=1 to n do write( (4) :4)
writeln
end
end.
2．[程序说明] 设有n个人依次围成一圈，从第1个人开始报数，数到第m个人出列，然后从出列的下一个人开始报数，数到第m个人又出列，…，如此反复到所有的人全部出列为止。设n个人的编号分别为1，2，…，n，打印出出列的顺序。
本题用数组建立标志位等方法求解,用数组实现链式结构。 数组a[i]作为"指针"变量来使用，a[i]存放下一个结点的位置。设立指针j指向当前结点，则移动结点过程为j:=a[j]，当数到m时，m结点出链，则a[j]:=a[a[j]]。
[程序]
program example
const n=14m=4
var a:array[1..n] of integer
i,j,k,p:integer
begin
for i:=1 to n-1 do a[i]:=i+1
a[n]:=1
(1)
k:=1
p:=0
repeat
(2)
k:=k+1
if k=m then
begin
write(a[j]:4)
p:=p+1
(3)
(4)
end
until p=n
end.
参考答案
一、选择题：（每题1.5分，共计30分。每题有5个选项，前10题为单选题，后10题为不定项选择题，全部选对才得分）。
题号 1 2 3 4 5 6 7 8 9 10
答案 B C B D A A E D B E
题号 11 12 13 14 15 16 17 18 19 20
答案 B ACE C DE AC ABCDE DE BE AC BCDE
二、问题求解题（每题5分，共计10分））
1、 14
2、 19 ,（2分） a1,a4,a7,a10 （3分）
三、程序阅读理解题 （每题8分，共计32分）
1、F（12）=89
2、F（8）=21
3、 t=63
4、max=77
四、程序完善题 (每题14分，共计28分)
1、
①b:=y-x
②x:=1-b
③x:=x+n
④f(x,y)
2、
①j:=n
②j:=a[j]
③a[j]:=a[a[j]]
④k:=1
grundfos 发表于 >2004-10-18 10:16:57 [全文] [评论] [引用] [推荐] [档案] [推给好友] [收藏到网摘]
2004-10-18
信息学竞赛普及组初赛模拟试题(四)
信息学竞赛普及组初赛模拟试题(四)
一、 选择题：（选出每题正确的答案代码，填在括号里，1—10题为单选题，每小题只有一个正确答案，11—20题为不定项选择题，每小题有一个或一个以上的正确答案，共20题，每题1.5，共30分）
1、二进制数01100100转换成十六进制数是（ ）。
A．32 B．64 C．128 D．100 E．256
2、 *** 作系统是一类重要的系统软件，下面几个软件中，不属于系统软件的是（ ）。
A．Java B．MS-DOS C．Linux D．Windows2000 E．Unix
3、计算机病毒的传染是以计算机运行和（ ）为基础的，没有这两个条件，病毒是不会传染的。
A．编辑文稿 B．读写磁盘 C．编程序 D．扫描图画 E．打印
4、因特网不属于任何个人，也不属于任何组织。其中在网络知识这一块中有一个英文简写ISP，它的中文意思是（ ）。
A．因特网连接 B．因特网使用 C．因特网设计 D．因特网服务提供者 E．信息传输
5、Internet给我们提供了资源共享、浏览、检索信息和远程登录等多种服务，下面几个选项中用于远程登录的是（ ）。
A．WWW B．TCP/IP C．Telnet D．E-mail E．FTP
6、IE是目前流行的浏览器软件，它的工作基础是解释执行用（ ）语言书写的文件。
A．VC B．HTML C．BASIC D．HTTP E．VB
7、给出3种排序：插入排序、冒泡排序、选择排序。这3种排序的时间代价分别是（ ）。
A．O(n)、O(n2)、O(logn)B．O(logn) 、O(n)、O(n2)C．O(n2)、O(n)、O(logn)
D．O(n2)、O(n)、O(n) E．O(n2)、O(n2)、O(n2)
8、一棵完全二叉树的结点总数为18，其叶结点数为（ ）。
A．7个 B．8个 C．9个 D．10个 E．11个
9、在流程图的符号中，菱形框一般作为（ ）。
A．起始框 B．判断框 C．输入输出框 D．处理工作框 E．结速框
10、在解决计算机主机与打印机之间速度不匹配时通常设置一个打印数据缓冲区，主要将要输出打印的数据依次写入该缓冲区，而打印机从该缓冲区中取出数据打印。该缓冲区应该是一个（ ）结构。
A．堆栈 B．数组 C．线性表 D．队列 E．链表
11、多媒体技术中的“多媒体”的含义主要是指如（ ）等多种表达信息的形式。
A．磁盘B．音箱 C．显示器D．声音E．图像
12、下面有关计算机知识说明，正确的是（ ）。
A． 在WINDOWS98 *** 作系统下，删除磁盘中的文件时都先存放在回收站中
B． FOXMAIL是用于收发电子邮件的工具
C． 文件夹组织是一个有层次的树状结构，其中最顶层的是桌面
D．存储器具有记忆能力，其中的信息任何时候都不会丢失
E． 为了提高软件的测试效率，应该选择发现错误的可能性大的测试数据
13、对按关键字排序好的线性表进行二分查找，该线性表适合的存储结构为（ ）。
A．链接存储 B．索引存储 C．散列存储 D．顺序存储 E．循环存取
14、一个栈的输入顺序为1、2、3、4、5，下列序列中可能是栈的输出序列的是（ ）。
A．54312 B．24135 C．21543 D．12534 E．12345
15、评价一个算法的好坏有多种指标，下列是算法评价指标的是（ ）。
A． 正确性 B．运行时间 C．占用空间 D．迭代次数 E．简单性
16、下面描述用多维数组表示的数据结构的语句中，正确的是（）。
A． 多维数组存放的都是同一种类型的数据
B． 多维数组各维的下标范围必须一样
C． 多维数组在内存中的地址是连续的
D． 多维数组中的下标不能是表达式
E． 多维数组是随机存取的数据结构
17、若已知一个栈的入栈顺序1，2，3，…，n，其输出序列为P1，P2，P3，…，Pn（它是输入序列的一个排列），则在输出序列中可能出现的情况是（ ）。
A．Pj<Pk<Pi，其中i<j<k
B．Pk<Pj<Pi，其中i<j<k
C．Pj<Pi<Pk，其中i<j<k
D．Pi<Pk<Pj，其中i<j<k
E．以上都不可能出现
18、线性表具有如下的结构特点：（ ）
A．均匀性 B．单一性 C．简单性 D．无序性 E．有序性
19、下列关于数据结构的叙述中正确的是（）。
A．数据结构是带有结构的数据元素的集合
B．线性表的线性存储结构优于链式存储结构
C．队列是限定仅在一端进行插入，在另一端进行删除的线性表
D．二维数组是其数据元素为线性表的线性表
E．图是一种非线性数据结构
20、任意一棵树均可惟一地转换成与它对应的二叉树。由树转换成的二叉树中，顶点N的左右子女分别是N在原树里对应顶点的（ ）。
A． 最左子顶点/最邻近的右兄弟
B． 最右子顶点/最右的兄弟
C．最邻近的右兄弟/最左的兄弟
D．最邻近的左兄弟/最邻近的右兄弟
F． 最邻近的右兄弟/最右的兄弟
二、 问题解答：（共2题，每题5分，共10分）
1、 光明中学开设数学、英语和信息学三个兴趣学习小组，其中数学小组30人，英语小组15人，信息学小组18人，参加三个小组总人数为50人，其中有3人同时参加3个小组，那么同时只参加两个小组的同学有多少人？
2、 给出一组顶点（顶点值用A，B，C，D，E，F表示），其对应权值分别为2，3，1，7，8，4。请以A，B，C，D，E，F为叶子顶点构造一棵哈夫曼树，并求出它的最小带权路径长度WPL的值。
三、 写出程序的运行结果（共4题，每题8分，共32分）
第1题：
program test1；
var n：integer；
function count(n：integer)：integer；
begin
if n=1 then count：=0
else
if n mod 2=0 then count：=count(n div 2)+1
else count：=count(n*3+1)+1；
end；
begin
readln(n)；
writeln(count(n))；
end.
输入：99
输出：
第2题：
program test2(input,output)
var
i,j,k,s:integer
begin
s:=0
for i:=3 downto 1 do
begin
for j:=1 to 3 do
begin
k:=0
repeat
k:=k+1s:=s+k
until k=j
end
s:=s-(k+1)
end
write(‘s=’,s)
end.
输出：
第3题：
program test3
var a,b,n:longint
begin
readln(n)
a:=0b:=0
repeat
a:=a+1b:=b+a
until b>=n
writeln(a)
end.
输入：415377
输出：
program test4
var m,n,i,p,k：integer
r:array[1…200] of integer
b:Boolean
begin
m:=6n:=2
for I:=1 to m-1 do r[i]:=i+1
r[m]:=1i:=0p:=1b:=true
while b do
begin
i:=i+1k:=pp:=r[p]
if k=p then
begin writeln(p)b:=false end
else if i=n+1 then
begin
write(p,‘ ’)i:=0p:=r[p]r[k]:=p
end
end
end.
输出：
四、完善程序（共2题，每题14分，共28分）
第1题（7分）
【问题描述】
设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为XK，今从n种物品中选取若干件（同一种物品可以多次选取），使其重量的和小于等于XK，而价值的和为最大。
【程序清单】
Program package
const maxxk=400maxn=20
type tlist=array[1…maxn] of byte
tmake=array[0…maxn,0…maxxk] of integer
var n,xk:integer
w,u:tlist
f:tmake
procedure init
var i:byte
begin
fillchar(w,sizeof(w),0)
fillchar(u,sizeof(u),0)
readln(n,xk)
for i:=1 to n do
①
end
procedure make
var i,j:byte
begin
for i:=1 to n do
begin
for j:=1 to w[i]-1 do
f[i,j]:=f[i-1,j]
for j:=w[i] to xk do
if f[i-1,j]>f[i,j-w[i]]+u[i] then ②
else ③
end
end
procedure print
var get:tlist
i,j:byte
begin
fillchar(get,sizeof(get),0)
i:= ④ j:= ⑤
while i>0 do
if f[i,j]=f[i-1,j] then dec(i)
else begin
dec(j,w[i])
⑥
end
writeln(‘n=’,n, ‘,’, ‘xk=’,xk)
writeln(‘max worth=’,⑦
for i:=1 to n do
writeln(‘no.’,i‘, weight:’,w[i]:2, ‘worth:’,u[i]:2, ‘get’,get[i]:2)
end
begin
init
make
end.
第2题（7分）
【问题描述】
给定一个01串，请你找出长度介于a,b之间，重复出现次数最多的01串。
输入：a,b(0<a<=b<=12)
由0，1组合的数列，由‘.’结尾。
输出：要求的串。
提示：本程序中将01序列转换为2进制数存取。
【程序清单】
program shuchuan
var i,j,s,k,a,b,max:integer
m:array[1…8192] of integer
two,v:array[1…20] of integer
c:char
begin
for i:=1 to 13 do
①
readln(a,b)
read(c)
s:=1k:=1
while c<>‘.’do begin
s:=s shl 1+ord(c)-48
if②then
s:=((s-two[b+1]) mod two[b])+two[b]
inc(m[s])
if k<b then
for i:=a to k-1 do
③
inc(k)
read(c)
end
for i:=two[b] to two[b+1] do
if m[i]>0 then
for j:=a to b-1 do
m[(i mod two[j])+two[j]]:= ④
max:=0
for i:=two[a] to two[b+1] do
if m[i]>max then⑤
for i:=two[a] to two[b+1] do
if m[i]=max then begin
j:=0k:=I
repeat
inc(j)v[j]:=k mod 2⑥
until ⑦
while j>0 do begin write(v[j])dec(j) end
writeln
end
end.
信息学命题(四)参考答案
一、 选择题：（选出每题正确的答案代码，填在括号里，1—10题为单选题，每小题只有一个正确答案，11—20题为不定项选择题，每小题有一个或一个以上的正确答案，共20题，每题1.5，共30分）
题号 1 2 3 4 5 6 7 8 9 10
答案 B A B D C B E C B D
题号 11 12 13 14 15 16 17 18 19 20
答案 DE BCE D CE ABCE ACE BCD AE ACDE A
二、问题解答：（共2题，每题5分，共10分）
第1题：
7
第2题：
61
三、写出程序的运行结果：（共4题，每题8分，共32分）
第1题：
25 第2题：
s=18
第3题：
911 第4题：
4 2 1 3 6 5
四、完善程序（共2题，每题14分，共28分）
第1题：
①read(w[i],u[i])
②f[i,j]:=f[i-1,j]
③f[i,j]:=f[i,j-w[i]]+u[i]
④i:=n
⑤j:=xk
⑥inc(get[i])
⑦f[n,xk]
第2题：
①two[i]:=1 shl i；
②s>=two[b+1](或k>b)
③inc（m[(s mod two[i])+two[i]]）
④m[(i mod two[j])+two[j]]+m[i]
⑤max:=m[i]
⑥k:=k div 2
⑦k=1
grundfos 发表于 >2004-10-18 8:36:45 [全文] [评论] [引用] [推荐] [档案] [推给好友] [收藏到网摘]
2004-10-18
信息学竞赛普及组初赛模拟试题(三)
信息学竞赛普及组初赛模拟试题(三)
〔 作者：教研室转贴自：教研室点击数：15更新时间：2004-10-3文章录入：admin 〕
一、选择一个正确答案代码（A/B/C/D），填入每题的括号内（每题1.5分，多选无分，共30分）
1、MAN英文缩写的含义是（ ）
A.局域网 B.城域网C.广域网 D.增值网
2、小张用十六进制，八进制和十进制写了如下一个等式：64－13=33
式中三个数是各不相同进位制的数，试问64，13，33，分别为________。
A．八进制，十进制，十六进制 B．十进制，十六进制，八进制
C．八进制，十六进制，十进制 D．十进制，八进制，十六进制
3、表达式(4 MOD (－3))与(－4 MOD 3)的值为：_______。
A．－1，－1 B．1，－1 C．－1，1D．1，1
4、试指出：下列if语句中，当x=80时, 运行的结果为______。
begin
y:=0
readln(x)
if x<0 then y:=5
else
if x<10 then begin
y:=10
if x<100 then y:=100
end
else y:=200
write('y=',y)
end.
A．y=9 B．y=200C．y=10 D．y=100
5、设栈S的初始状态为空，现有5个元素组成的序列{1，2，3，4，5}，对该序列在S栈上依次进行如下 *** 作(从序列中的1开始，出栈后不再进栈)：进栈，进栈，进栈，出栈，进栈，出栈，进栈，试问出栈的元素序列是________。
A．{5，4，3，2，1}B．{2，1}C．{2，3} D．{3，4}
6、ASCII码是（ ）。
A．国标码B．二进制编码 C．十进制编码 D．美国标准信息交换码
7、一台计算机的字长是4个字节，这意味着（ ）。
A．能处理的数值最大为4位十进制数9999
B．能处理的字符串最多由4个英文字母组成
C．在CPU中能够同时处理32位二进制数据
D．在CPU中运算的最大结果为2的32次方
8、假设一台计算机的地址总线为16，那么中央处理器CPU能访问的最大存储器容量为(
A． 2 * 16 KB B．16KB C．216B D．16*1024*8 B
9、计算机最终处理的信息形式是（ ）
A．ASCII码 B．BCD码 C．二进制 D．十六进制
10、与十六进制数6F等值的八进制数是（）
A．166B．139 C．157 D．183
11、以下属非法用户自定义标识符的是()。
A．date B．dir C．list D．type
12、设X和Y是同一种枚举类型变量，则下列语句中合法的是()。
A．X:=ORD(Y) B．X:=Y C．READ(X,Y) D．WRITE(T,Y)
13、计算机能够直接识别和处理的程序是_______程序
A．汇
哎 我应聘了N家公司 给你一些题好了华为的
第一部分:选择题
QUESTION NO: 1
1、public class Test {
历消public static void changeStr(String str){
str="welcome"
}
public static void main(String[] args) {
String str="1234"
changeStr(str)
System.out.println(str)
}
}
Please write the output result :
QUESTION NO:2
1. public class Test {
2. static boolean foo(char c) {
3. System.out.print(c)
4. return true
5. }
6. public static void main( String[] argv ) {
7. int i =0
8. for ( foo('A'派烂高)foo('B')&&(i<2)foo('C')){
9. i++
10. foo('D')
12. }
13. }
14. }
What is the result?
A. ABDCBDCB
B. ABCDABCD
C. Compilation fails.
D. An exception is thrown at runtime.
QUESTION NO: 3
1. class A {
2. protected int method1(int a, int b) { return 0}
3. }
Which two are valid in a class that extends class A? (Choose two)
A. public int method1(int a, int b) { return 0}
B. private int method1(int a, int b) { return 0}
C. private int method1(int a, long b) { return 0}
D. public short method1(int a, int b) { return 0}
E. static protected int method1(int a, int b) { return 0}
尘尺QUESTION NO: 4
1. public class Outer{
2. public void someOuterMethod() {
3. // Line 3
4. }
5. public class Inner{}
6. public static void main( String[]argv ) {
7. Outer o = new Outer()
8. // Line 8
9. }
10. }
Which instantiates an instance of Inner?
A. new Inner()// At line 3
B. new Inner()// At line 8
C. new o.Inner()// At line 8
D. new Outer.Inner()// At line 8//new Outer().new Inner()
QUESTION NO: 5
Which method is used by a servlet to place its session ID in a URL that is written to the servlet’s response output stream?
A. The encodeURL method of the HttpServletRequest interface.
B. The encodeURL method of the HttpServletResponse interface.
C. The rewriteURL method of the HttpServletRequest interface.
D. The rewriteURL method of the HttpServletResponse interface.
QUESTION NO: 6
Which two are equivalent? (Choose two)
A. <%= YoshiBean.size%>
B. <%= YoshiBean.getSize()%>
C. <%= YoshiBean.getProperty("size")%>
D.
E.
F.
G.
QUESTION NO: 7
Which of the following statements regarding the lifecycle of a session bean are correct?
1. java.lang.IllegalStateException is thrown if SessionContext.getEJBObject() is invoked when a stateful session bean instance is passivated.
2. SessionContext.getRollbackOnly() does not throw an exception when a session bean with bean-managed transaction demarcation is activated.
3. An exception is not thrown when SessionContext.getUserTransaction() is called in the afterBegin method of a bean with container-managed transactions.
4. JNDI access to java:comp/env is permitted in all the SessionSynchronization methods of a stateful session bean with container-managed transaction demarcation.
5. Accessing resource managers in the SessionSynchronization.afterBegin method of a stateful session bean with bean-managed transaction does not throw an exception.
第二部分:概念题
1. 描述Struts体系结构?对应各个部分的开发工作主要包括哪些?
3. JSP有哪些内置对象和动作?它们的作用分别是什么?
4、SQL问答题
SELECT * FROM TABLE
和
SELECT * FROM TABLE
WHERE NAME LIKE '%%' AND ADDR LIKE '%%'
AND (1_ADDR LIKE '%%' OR 2_ADDR LIKE '%%'
OR 3_ADDR LIKE '%%' OR 4_ADDR LIKE '%%' )
的检索结果为何不同?
5、SQL问答题
表结构:
1、 表名:g_cardapply
字段(字段名/类型/长度):
g_applyno varchar 8//申请单号(关键字)
g_applydate bigint 8//申请日期
g_state varchar 2//申请状态
2、 表名:g_cardapplydetail
字段(字段名/类型/长度):
g_applyno varchar 8//申请单号(关键字)
g_name varchar 30//申请人姓名
g_idcard varchar 18//申请人身份z号
g_state varchar 2//申请状态
其中，两个表的关联字段为申请单号。
题目:
1、 查询身份z号码为440401430103082的申请日期
2、 查询同一个身份z号码有两条以上记录的身份z号码及记录个数
3、 将身份z号码为440401430103082的记录在两个表中的申请状态均改为07
4、 删除g_cardapplydetail表中所有姓李的记录
")
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）