全国信息学奥林匹克模拟试题.doc

全国信息学奥林匹克模拟试题(二)一、 选择题：（选出每题正确的答案代码，填在括号里，110题为单选题，每小题只有一个正确答案，1120题为不定项选择题，每小题有一个或一个以上的正确答案，共20题，每题1.5，共30分）1、二进制数转换成十六进制数是（ ）。A32 B64 C128 D100 E2562、操作系统是一类重要的系统软件，下面几个软件中，不属于系统软件的是（ ）。AJava BMS-DOS CLinux DWindows2000 EUnix3、计算机病毒的传染是以计算机运行和（ ）为基础的，没有这两个条件，病毒是不会传染的。A编辑文稿 B读写磁盘 C编程序 D扫描图画 E打印4、因特网不属于任何个人，也不属于任何组织。其中在网络知识这一块中有一个英文简写ISP，它的中文意思是（ ）。A因特网连接 B因特网使用 C因特网设计 D因特网服务提供者 E信息传输5、Internet给我们提供了资源共享、浏览、检索信息和远程登录等多种服务，下面几个选项中用于远程登录的是（ ）。AWWW BTCP/IP CTelnet DE-mail EFTP6、IE是目前流行的浏览器软件，它的工作基础是解释执行用（ ）语言书写的文件。AVC BHTML CBASIC DHTTP EVB7、给出3种排序：插入排序、冒泡排序、选择排序。这3种排序的时间代价分别是（ ）。AO(n)、O(n2)、O(logn) BO(logn) 、O(n)、O(n2) CO(n2)、O(n)、O(logn)DO(n2)、O(n)、O(n) EO(n2)、O(n2)、O(n2)8、一棵完全二叉树的结点总数为18，其叶结点数为（ ）。A7个 B8个 C9个 D10个 E11个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，下列序列中可能是栈的输出序列的是（ ）。A54312 B24135 C21543 D12534 E1234515、评价一个算法的好坏有多种指标，下列是算法评价指标的是（ ）。A 正确性 B运行时间 C占用空间 D迭代次数 E简单性16、下面描述用多维数组表示的数据结构的语句中，正确的是（ ）。A 多维数组存放的都是同一种类型的数据B 多维数组各维的下标范围必须一样C 多维数组在内存中的地址是连续的D 多维数组中的下标不能是表达式E 多维数组是随机存取的数据结构17、若已知一个栈的入栈顺序1，2，3，n，其输出序列为P1，P2，P3，Pn（它是输入序列的一个排列），则在输出序列中可能出现的情况是（ ）。APjPkPi，其中ijkBPk PjPi，其中ijkCPjPiPk，其中ijkDPiPk Pj，其中ijkE以上都不可能出现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的值。三、 选择题：（选出每题正确的答案代码，填在括号里，110题为单选题，每小题只有一个正确答案，1120题为不定项选择题，每小题有一个或一个以上的正确答案，共20题，每题1.5，共30分）1、二进制数转换成十六进制数是（ ）。A32 B64 C128 D100 E2562、操作系统是一类重要的系统软件，下面几个软件中，不属于系统软件的是（ ）。AJava BMS-DOS CLinux DWindows2000 EUnix3、计算机病毒的传染是以计算机运行和（ ）为基础的，没有这两个条件，病毒是不会传染的。A编辑文稿 B读写磁盘 C编程序 D扫描图画 E打印4、因特网不属于任何个人，也不属于任何组织。其中在网络知识这一块中有一个英文简写ISP，它的中文意思是（ ）。A因特网连接 B因特网使用 C因特网设计 D因特网服务提供者 E信息传输5、Internet给我们提供了资源共享、浏览、检索信息和远程登录等多种服务，下面几个选项中用于远程登录的是（ ）。AWWW BTCP/IP CTelnet DE-mail EFTP6、IE是目前流行的浏览器软件，它的工作基础是解释执行用（ ）语言书写的文件。AVC BHTML CBASIC DHTTP EVB7、给出3种排序：插入排序、冒泡排序、选择排序。这3种排序的时间代价分别是（ ）。AO(n)、O(n2)、O(logn) BO(logn) 、O(n)、O(n2) CO(n2)、O(n)、O(logn)DO(n2)、O(n)、O(n) EO(n2)、O(n2)、O(n2)8、一棵完全二叉树的结点总数为18，其叶结点数为（ ）。A7个 B8个 C9个 D10个 E11个9、在流程图的符号中，菱形框一般作为（ ）。A起始框 B判断框 C输入输出框 D处理工作框 E结速框10、在解决计算机主机与打印机之间速度不匹配时通常设置一个打印数据缓冲区，主要将要输出打印的数据依次写入该缓冲区，而打印机从该缓冲区中取出数据打印。该缓冲区应该是一个（ ）结构。A堆栈 B数组 C线性表 D队列 E链表11、多媒体技术中的“多媒体”的含义主要是指如（ ）等多种表达信息的形式。A磁盘 B音箱 C显示器 D声音 E图像12、下面有关计算机知识说明，正确的是（ ）。C 在WINDOWS98操作系统下，删除磁盘中的文件时都先存放在回收站中D FOXMAIL是用于收发电子邮件的工具C 文件夹组织是一个有层次的树状结构，其中最顶层的是桌面D存储器具有记忆能力，其中的信息任何时候都不会丢失E 为了提高软件的测试效率，应该选择发现错误的可能性大的测试数据13、对按关键字排序好的线性表进行二分查找，该线性表适合的存储结构为（ ）。A链接存储 B索引存储 C散列存储 D顺序存储 E循环存取14、一个栈的输入顺序为1、2、3、4、5，下列序列中可能是栈的输出序列的是（ ）。A54312 B24135 C21543 D12534 E1234515、评价一个算法的好坏有多种指标，下列是算法评价指标的是（ ）。B 正确性 B运行时间 C占用空间 D迭代次数 E简单性16、下面描述用多维数组表示的数据结构的语句中，正确的是（ ）。G 多维数组存放的都是同一种类型的数据H 多维数组各维的下标范围必须一样I 多维数组在内存中的地址是连续的J 多维数组中的下标不能是表达式K 多维数组是随机存取的数据结构17、若已知一个栈的入栈顺序1，2，3，n，其输出序列为P1，P2，P3，Pn（它是输入序列的一个排列），则在输出序列中可能出现的情况是（ ）。APjPkPi，其中ijkBPk PjPi，其中ijkCPjPiPk，其中ijkDPiPk Pj，其中ij=n; writeln(a);end.输入：415377输出：program test4;var m,n,i,p,k：integer;r:array1200 of integer;b:Boolean;beginm:=