《2013莱芜信息奥赛选拔》由会员分享,可在线阅读,更多相关《2013莱芜信息奥赛选拔(3页珍藏版)》请在金锄头文库上搜索。
1、莱芜一中54级信息奥赛选拔试题一、选择题1以A0作为起点,对下面的无向图进行深度优先搜索时(搜索的顺序与顶点字母的下标无关),最后一个搜索到的顶点可能是(CD)A.A1 B.A2 C.A3 D.A42.27个小朋友在放学后,在lis的带领下去吃巧克力,巧克力店搞促销,凭三个空袋子可以再换一包巧克力,他们最少买多少包巧克力才能保证一人一包?CA. 17 B.18 C.19 D.203. 如果变量可以简单形容为存放一个数的盒子,可以对这个盒子里的数进行加减乘除计算和重新赋值,那么请问这样一个给出k,x,b,且已知y=kx+b,求y的值的程序最少需要用多少个变量:AA1个 B.2个 C.3个 D.4
2、个4. 一篮子水果装有苹果、香蕉和橘子。为了保证篮子里要么至少有8个苹果要么至少有6个香蕉要么至少有9个橘子,则至少向篮子中放入多少个水果?CA10 B.23 C.21 D.19二、填空题6有A、B、C三个实习生采集到一块矿样,分别对它判断如下:A说:这种矿不是铁,也不是铜;B说:这种矿不是铁,是锡;C说:这种矿不是锡,是铁;经鉴定得知,该矿样是铜、铁、锡中的一种,且三人中,有一人两个判断都正确(2),另一人的两个判断都错(0),第三人的判断一对一错(1),指出是什么矿石,三人判断的对错情况。矿样名: 铁 A: 1 B: 0 C: 27现在有这样一个完全二叉树由我们对其进行标号,标号规则为:从
3、初始节点开始标号,从左到右标号,这样,给你一个标号为n 的节点,它的左子节点的标号为_2n_,右子节点的标号为_2n+1_。8从7开始数的第1999个数减去471再从这个数开始倒数133个数是_1402_。9 .将有序序列21, 63, 14, 42,17, 32, 75, 36中的元素按从小到大的顺序排列,每次可以交换任意两个元素,最少需要交换 _5_ 次。10. 75名儿童到游乐场去玩。他们可以骑旋转木马,坐滑行铁道,乘宇宙飞船,已知其中20人这三种东西都玩过,55人至少玩过其中的两种。若每样乘坐一次的费用是5元,游乐场总共收取700元,可计算出有_10_名儿童没玩过其中任何一种。三、简答
4、题11假设你是一个新来的狱警,你的犯人共有100个,编号从1到100.他们被关押在100间与其编号对应的牢房内,开始时所有牢房都关着,你从第一天开始会把牢房编号为当天天数倍数的牢房没有被打开的打开,已经被打开的关上。且100天之内所有罪犯都不会逃跑,而一百天之后你被调离,房门被打开的将会逃跑,请问都有哪几位犯人逃跑了?能说明为什么吗?答案:1 4 9 16 25 36 49 64 81 10012 .圆上有6个点,两两之间连线,最多可以把整个圆分成多少块?3113疯狂的世界杯:话说世界杯又要到了,木易要去巴西看世界杯,但是到了巴西利亚发现人生地不熟,现在他要去里约。好心的当地的居民LisLee
5、送他了一张地图,这张地图记载了巴西各大城市之间的直达距离,现在要求你写出巴西利亚到里约的最短路径,地图如下:6巴西利亚 圣保罗 帕拉 巴伊亚 马拉尼昂 里约巴西利亚 0 2 9 5 4 8圣保罗 2 0 4 3 5 6帕拉 9 4 0 3 2 4巴伊亚 5 3 3 0 3 3马拉尼昂 4 5 2 3 0 2里约 8 6 4 3 2 014给你一个长度为2n的无序数列,让你和你的同学每次从数列两端取一个数,可知到最后你们各自刚好有n个数,若规定由你先选,你能不能找出一种方式,使你的n个数的总和不小于你的同学的n个数的总和?答案:奇位置的数和偶位置的数的和15.现在来定义一种操作,对于一棵二叉树来
6、说,先访问它的左子树,再访问它的根节点,最后访问它的右子树,以此递归操作。现在给你一棵二叉树,求它的操作顺序:(注意:二叉树中子节点的左右位置就代表左右子节点)答案:3 2 4 6 7 5 116.求该图的拓扑排序:(任意一种即可)(IAG)(EB)(FD)(HC) 括号中的位置可以变17.很久很久以前,在森林里有一座城堡里面住着一位美丽的公主优酱,和她在一起的是王子小晴,由于公主很爱撒娇,所以城堡的卫生由王子负责,城堡内道路交错王子给你城堡地图问你是否可以从一个点开始打扫,打扫完整个城堡时刚好回到起点(不走回头路),因为王子很忙,打扫完后要去陪公主玩金坷垃游戏。如果可以,请写出打扫路线;如果
7、不可以,请说明理由,地图如下:答案不唯一18.神琦的密码:神琦发明了一种密码验证系统,系统中密码是由N个数s1,s2,sn,均为0或1,该系统每次随机生成N个数a1,a2,an,均为0或1,请用户回答(s1*a1+s2*a2+ sn*an)除以2的余数。如果多次回答总是正确的,即认为掌握密码。但是邪恶的黑客盗取用户一部分问答记录,现在他请教你是否可以套取到登录密码,如果可以,请写出密码;如果不可以,请说明理由,他问答记录如下图:问题编号 系统生成的N个数 用户回答a1 a2 a3 a41 0 1 0 1 12 1 1 0 0 13 1 1 0 1 14 0 0 0 1 05 1 0 1 1 0
8、答案:010019.帅帅的连通图:在一个无向图(什么?你居然不知道什么是无向图,好吧,就是往返无限制的图)中,如果任意两点之间都存在路径相连,则称其为连通图。下图是一个有5个顶点、8条边的连通图。现在你的任务就是通过删去其中的边,使它不在是一个连通图,请写出至少删边的个数及删边后的图。320. 奇怪的僵尸:IX同学喜欢玩植物大战僵尸,如下图所示最后一只僵尸他从中间而来,而面对他的是一个5*5的大蒜阵,僵尸会啃食大蒜,但大蒜的奇异味道会让它移到相邻的行(如果它在第1行只能到达第2行,如果它在第5行只能到达第4行),并且在某一列啃满4次后,第5次啃将进入下一列的相邻行,最终它会到达IX房子跟前,而
9、房子门口的小车会将他推死,求僵尸死于中间小车的概率。下图中代表小车,代表大蒜,代表僵尸。答案 021. K国有n个地堡,计划实施两期工程。第一期的任务是挖掘暗道让所有地堡互联互通。现已勘测设计了m条互不相交的暗道挖掘方案,如果这m条暗道都实施挖掘,肯定能达到互联互通的目的。事实上,适当选择其中n-1个方案挖掘,就能实现互联互通,即从每个地堡出发都能到达其他任何一个地堡(允许经过别的地堡)。连长精心谋算,在m个设计规划中选取了挖掘总距离最短且能保证互联互通的若干个暗道规划实施了挖掘,完成了第一期的施工任务后又接受了第二期的施工任务,要求选择一个地堡进行扩建改造,使其能向每个地堡提供弹药。为了让弹药供应更及时、更快捷,从改扩建的地堡到最远地堡的距离(称为最远输送距离)应当尽量小。现n=4(有1.4号4个地堡),m=5(5个暗道规划方案可供选取),接下来5组表示5个暗道规划方案,每组有a,b,c三个数,表示从a号地堡到b号地堡暗道长度为c:1 2 1 2 3 2 34 3 4 1 4 3 1 5求第一期工程需要选择暗道规划方案,使得所有地堡联通的情况下挖掘的总距离最小,最小总距离是( 6)。第二期工程选择的扩建地堡是(3)。