全国青少年信息学奥林匹克联赛初赛练习卷(十)new答案 .pdfVIP

全国青少年信息学奥林匹克联赛初赛练习卷（十）new 答案 全国青少年信息学奥林匹克联赛初赛练习卷（十）答案 (普及组 PASCAL 语言二小时完成) ●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●● 一、单项选择题（20 题，每题 1.5 分，共计 30 分。每题有且仅有 一个正确答案） 1.计算机系统由硬件系统和软件系统组成，平常我们所说的计算 机软件是由程序和（） 组成。 A. 软盘 B. 文档 C. 操作平台 D. 相关软件工具 2.下面有关数制的式子中，正确的是（）。 A. (A2 B.C5)16 = (1010001010112 B. 在八进制中，2*6=14 C. (110010)2+(16)10=(1000100)2 D. (01000)2=(8)8 3.汉字输入方法实质上是对汉字进行编码。下面（）不是汉字输 入方法的编码方式。 A. 音码 B. 形码 C. 音形码 D. ASCII 码 4.Windows 是一种多任务的操作系统，各个 Windows 应用程序 之间可以非常方便地通过 （）来交换数据。 A. 复制 B. 读/写文件 C. 剪贴板 D. 剪切 5.因特网（Internet ）给我们提供了资源共享、浏览、检索信息和 远程登录等多种服务。 下面几个选项中，用于远程登录的是（）。 A. Telnet B. E-mail C. TCP/IP D. WWW 6.在数据结构中，链表是（）。 A. 顺序存储的线性表结构 B. 非顺序存储的线性表结构 C. 非顺序存储的非线性表结构 D. 顺序存储的非线性表结构 7.如果一棵 M 度树中有 N1 个度为 1 的顶点，N2 个度为 2 的顶 点，……，Nm 个度为 M 的顶点，则该树中的叶子顶点个数为（）。 A. N1 B. M-N1-N2 C. N1+2N2+…+(m-1)N m-1+1 D. N2+2N3+…+(m-1)N m+1 8.设有 1024 个数据，利用二分法进行查找时，最坏情况下的比较 次数为（）。 A. 11 B. 10 C. 9 D. 8 9.设数组 X[10..40, 20..50]以行优先的方式存储，每个元素占 4 个 字节，且已知 x[10,20] 的地址为 1000 ，则x[30,30]的地址为（）。 A. 2280 B. 2980 C. 2240 D. 2284 10.在各种排序算法中，其平均算法复杂度为 O(nlog2n)的是（）。 A. 快速排序 B. 冒泡排序 C. 归并排序 D. 直接插入排序 冒泡排序和直接插入排序的时间复杂度均为 O(n2) ，归并排序的 时间复杂度为 O(n+m) ，其中 n、m 分别为两个归并排序的长度。快 速排序是冒泡排序的一种改进，在最坏情况下其执行时间为 O(n2) ， 平均执行时间为 O(nlog2n)。 11.已知一棵二叉树的前序遍历序列为 ABDEGCFH ，中序遍历序 列为 DBGEACHF ，则该 二叉树的层次序列为（）。 A. GEDHFBCA B. DGEBHFCA C. ABCDEFGH D. ACBFEDHG 12.对于一个无向带权图 G= （V ，E ），其中V={a,b,c,d,e} ， E={(a,b),(a,c),(b,d),(c,d),(e,d),(c,e),(a,d),(b,e)} ，E 中边的权值分 别为{1,4,2,5,3,1,2,3} ，现寻找E 的一个子集 E1 ，使得V 中任意两个顶 点之间均存在至少一条路径，且子集 E1 中边的权值之和最小，则最小 权值是（）。 A. 5 B. 7 C. 6 D. 8 根据图