18届全国青少年信息学奥林匹克联赛初赛(详解)(普及组)

《18届全国青少年信息学奥林匹克联赛初赛(详解)(普及组)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第十八届全国青少年信息学奥林匹克联赛初赛（普及组Pascal语言试题）竞赛时间：2012年10月13日14:30~16:30选手注意·试题纸共有10页，答题纸共有2页，满分100分。请在答题纸上作答，写在试题纸上一律无效。·不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料一、单项选择题（共20题，每题1.5分，共计30分；每题且仅有一个正确选项）1.计算机如果缺少（A），将无法正常启动。A.内存B.鼠标C.U盘D.摄像头2.（B）是一种先进先出的线性表。A.栈B.队列C.哈希表（散列表

2、）D.二叉树解析：1.栈的定义(可参考：http://student.zjzk.cn/course_ware/data_structure/web/zhanhuoduilie/zhanhuoduilie3.1.1.htm)　栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。　　(1)通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。　　(2)当表中没有元素时称为空栈。　　(3)栈为后进先出（LastInFirstOut）的线性表，简称为LIFO表。　栈的修改是按后进先出

3、的原则进行。每次删除（退栈）的总是当前栈中"最新"的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。2.队列：定义：队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。　　（1）允许删除的一端称为队头（Front）。　　（2）允许插入的一端称为队尾（Rear）。　　（3）当队列中没有元素时称为空队列。　　（4）队列亦称作先进先出（FirstInFirstOut）的线性表，简称为FIFO表。　队列的修改是依先进先出的原则进行的。新来的成员总是加入队

4、尾（即不允许"加塞"），每次离开的成员总是队列头上的（不允许中途离队），即当前"最老的"成员离队。　【例】在队列中依次加入元素a1，a2，…，an之后，a1是队头元素，an是队尾元素。退出队列的次序只能是a1，a2，…，an。3.哈希表(散列表)　散列方法是使用函数h将U映射到表T[0..m-1]的下标上（m=O(

5、U

6、)）。这样以U中关键字为自变量，以h为函数的运算结果就是相应结点的存储地址。从而达到在O(1)时间内就可完成查找。哈希表存在散列表的冲突现象：　两个不同的关键字，由于散列函数值相同，因而被

7、映射到同一表位置上。该现象称为冲突(Collision)或碰撞。发生冲突的两个关键字称为该散列函数的同义词(Synonym)。　【例】上图中的k2≠k5，但h(k2)=h(k5)，故k2和K5所在的结点的存储地址相同。   　----------------------------------------4.在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常根的子树被称作“左子树”（leftsubtree）和“右子树”（rightsubtree）,次序不能颠倒。·二叉树的5种形态：·二叉树的遍历

8、：3.目前计算机芯片（集成电路）制造的主要原料是（A），它是一种可以在沙子中提炼出的物质。A.硅B.铜C.锗D.铝4.十六进制数9A在（B）进制下是232.A.四B.八C.十D.十二解析：9A十六,先转化成十进制＝9*162-1+10*161-1十进制＝154十进制,再转化成二进制=10011010二进制＝10011010(从最右边起三个一组,分别转换成十进制数字,就得到八进制表示的数)=232八进制注：十进制,八进制和十六进制互化应以二进制作为桥梁，将二进制转化成16或8进制：以小数点为界分别向左右每4

9、（或3）个数字为一组进行分组，每组分别转化成二进制数，最后合并在一起，并把首0去掉（尾0不可以去）。如：(001101001)2=(151)8(00010110.01011011)2=(16.5B)165.（C）不属于操作系统。A.WindowsB.DOSC.PhotoshopD.NOILinux6.如果一棵二叉树的中序遍历是BAC，那么它的先序遍历不可能是（C）。解析：从题目“中序遍历是BAC”得知:还原此二叉树可能是以下几种情况:A.ABC+中序遍历是BAC，还原得到：B.CBA+中序遍历是BAC，还

10、原得到：C.ACB还原得到：这两个树的中序遍历都不是BAC。D.BAC中序遍历是BAC，还原得到：前序：先根节点，然后遍历左子树,最后遍历右子树，根-左-右。中序：先遍历左子树，再是根节点，最后遍历右子树，左-根-右后序：先遍历左子树，再遍历右子树，最后是根节点，左-右-根在每个左右子树也遵守以上各自规则！7.目前个人电脑的（B）市场占有率最靠前的厂商包括Intel、AMD等公司。A.显示器：三星，LG，戴尔，宏碁，HP……B