衢州市青少年信息学竞赛-辅导教师比赛笔试试卷

衢州市青少年信息学竞赛辅导教师比赛笔试试卷请将答案填写在答题纸中。一、单项选择题（共20题，每题2分，共计40分。每题仅有一个正确答案。）1算法是指（）。A为解决问题而编制的计算机程序B为解决问题而采取的方法与步骤C为解决问题而需要采用的计算机语言D为解决问题而采用的计算方法2完全二叉树共有2N1个结点，则它的叶结点数是（）。AN1BNC2ND2N13递归过程或函数调用时，处理参数和返回地址，通常使用一种称为（）的数据结构。A队列B多维数组C线性表D栈4200785D16的结果是（）A100010001002B24148C46416D1214105在WORD环境下使用的“剪贴板”是。A一块内存区域B一块软盘空间C一块屏幕区域D一块硬盘空间6设ACTRUE，BDFALSE，以下逻辑运算表达式值为真的有（）。ABADCBADCBACD7设T是一棵有N个顶点的树，下列说法不正确的是（）。AT有N条边BT是连通的CT是无环的DT有N1条边8INTERNET网的通信协议是（）AX25BCSMA/CDCTCP/IPDCDMA9计算机在工作过程中，若突然停电，（）中的信息不会丢失。AROM和RAMBCPUCROMDRAM10在以下各项中，）不是操作系统软件。ASOLARISBLINUXCWINDOWSVISTADSYBASE11对有序数组5，13，19，21，37，56，64，75，88，92，100进行二分查找，成功查找元素19的查找长度（比较次数）是（）A1B2C3D412在WINDOWS9X中，菜单项后带有符号“”，表示该菜单项。A可以进行开关选择B执行时有对话框C有若干子命令D不能执行13二叉树T，已知其先根遍历是1243576（数字为节点的编号，下同），中根遍历2415736，则该二叉树的后根遍历是（）。A4257631B4275631C7425631D427653114面向对象程序设计（OBJECTORIENTEDPROGRAMMING）是一种程序设计的方法论，它将对象作为程序的基本单元，将数据和程序封装在对象中，以提高软件的重用性、灵活性和扩展性。下面关于面向对象设计的说法中，不正确的是（。A面向对象程序设计通常只采用自顶向下设计方法进行设计。B面向对象程序设计方法具有继承性（INHERITANCE）、封装性（ENCAPSULATION）、多态性POLYMORPHISM）等几大特点。C支持面向对象特性的语言称为面向对象的编程语言，目前较为流行的有C，JAVA，C等。D面向对象的程序设计的雏形来自于SIMULA语言，后来在SMALLTALK语言的完善和标准化的过程中得到更多的扩展和对以前思想的重新注解。至今，SMALLTALK语言仍然被视为面向对象语言的基础。15HTML的标准各称是（）。A主页制作语言B超文本标识语言CWWW编程语言DINTERNET编程语言16地面上有标号为A、B、C的3根细柱，在A柱上放有10个直径相同中间有孔的圆盘，从上到下一次编号为1，2，3，将A柱上的部分盘子经过B柱移入C柱，也可以再B柱上暂存。如果B柱上的操作记录为“进，进，出，进，进出，出，进，进，出，进，出，出”。那么C柱上，从下到上的盘子的编号为（）。A243657B241257C243176D24367517在以下各项中，（）不是CPU的组成部分。A控制器B运算器C寄存器D主板18设栈S的初始状态为空，元素A,B,C,D,E,F依次入栈S，出栈的序列为B,D,F,E,C,A，则栈S的容量至少应该是（）。A6B5C4D319欧拉图G是指可以构成一个闭合回路的图，且图G的每一条边恰好在这个闭合回路上出现一次（即一笔画成）。在以下各个描述中，不一定是欧拉图的是（）。A图G中没有度为奇数的顶点B包含欧拉环游图（欧拉环游是指通过图中每边恰好一次的闭路径）C包含欧拉闭迹的图（欧拉迹是指通过图中每边恰好一次的路径）D存在一条回路，通过每个顶点恰好一次20在WORD正文部分输入文字超过一行的宽度的时，WORD（）。A将把超出部分留在同一行B将等待按回车键把超出部分换行到下一行C将自动把超出部分换行到下一行D将把超出部分舍去二、不定项选择题。（共10题，每题2分，共计20分。每题正确选项可能为一项或多项。）1下列数中，（）与25625相等。A（11001111）2B（317）8C（11001101）2D（195）162在下列关于算法复杂性的说法中，正确的有（）。A算法的时间复杂度，是指它在某台计算机上具体实现时的运行时间。B算法的时间复杂度，是指对于该算法的一种或几种主要的运算，运算的次数与问题的规模之间的函数关系。C一个问题如果NPC类的，就意味着在解决该问题时，不存在一个具有多项式时间复杂度的算法。D一个问题如果是NP类的，与C有相同的结论。31对于一个大小为3的栈，若输入队列为123456，则下列输出队列有可能的是（）。A123456B654321C312456D316524E3216544正确的二维数组类型说明是ATYPEAR2ARRAY15,51OFINTEGERBTYPEAR2ARRAY15OFARRAY51OFINTEGERCTYPEAR2ARRAY15,15OFINTEGERDTYPEAR2ARRAY15OFARRAY15OFINTEGERETYPEAR2ARRAY15,15OF015下列关于数据结构的叙述中正确的是（）。A数据结构是带有结构的数据元素的集合B线性表的线性存储结构优于链式存储结构C队列是限定仅在一端进行插入，在另一端进行删除的线性表D二维数组是其数据元素为线性表的线性表E图是一种非线性数据结构6评价一个算法的好坏有多种指标，下列是算法评价指标的是（）。A正确性B运行时间C占用空间D迭代次数E简单性7对按关键字排序好的线性表进行二分查找，该线性表适合的存储结构为（）。A链接存储B索引存储C散列存储D顺序存储E循环存取8在下列防火墙（FIREWALL）的说法中，正确的有（）A防火墙式一项协助确保信息安全的设备，其会依照特定的规则，允许或是限制数据通过。B防火墙可能是一台专属的硬件或是安装在一般硬件上的一套软件。C网络层防火墙可以视为一种IP数据包过滤器，只允许符合特定规则的数据包通过，其余的一概禁止穿越防火墙。D应用层防火墙是在TCP/IP的应用层上工作，可以拦截进出某应用程序的所有数据包。9以下哪些是计算机的输出设备（）。A音箱B显示器C打印机D扫描仪E绘图仪10对给定的整数序列54,73,21,35,67,78,63,24,89进行从小到大的排序时,采用快速排序的第一趟扫描的结果是。A24,21,35,54,67,78,63,73,89B24,35,21,54,67,78,63,73,89C24,21,35,54,67,63,73,78,89D21,24,35,54,63,67,73,78,89三、问题求解（共4题，每题5分，共计20分）1（排列组合）在图中有5个编号为1、2、3、4、5的区域，要在每个区域中涂上红、黄、蓝、绿四种颜色中的一种，使有相邻边区域的颜色不同，共有_种不同的涂色方法。（2分）又有右图中有5个编号为1、2、3、4、5的区域，要在每个区域中涂上红、黄、蓝、绿四种颜色中的一种，使有相邻边区域的颜色不同，共有_种不同的涂色方法。（3分）2（图）请用邻接矩阵表示下图中各个顶点的相邻关系。3（二叉树）有二叉树中序序列为ABCEFGHD，后序序列为ABFHGEDC，请画出此二叉树，并求前序序列。4（递归问题）传说在印度佛教圣地贝拿勒斯圣庙里，安放着一个黄铜板，板上插着三根宝石针，其中一根宝石针从下到上插放着由大到小的49片有孔的金片，昼夜都有一个值班的僧侣按如下规则移动金片一次只能移动一片，而小片永远要在大片的上面，当时有人声称当49片金片全从一根宝石针上移动到另一根宝石针上时，就发生一声巨响。49片金片从一根宝石针上移动到另一根宝石针上总共需要移动_次。四、完善程序（共10空，每空2分，共20分）1、快速排序（过程）【参考程序】PROCEDUREQUICKSORTVARRARRAY1NOFDATATYPELOW,HIGHINTEGERVARI,JINT