NOIP初赛选择题.ppt

《NOIP初赛选择题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、初赛选择题1、进制转换1）十进制转换成二进制。2）十进制转换成八进制、十六进制。（以二进制为跳板）3）二进制、八进制、十六进制转换成十进制。（以二进制为跳板）4）不同进制比较大小。5）不同进制运算。6）B二进制O八进制D十进制H十六进制二进制数11.01在十进制下是（）。A.3.25B.4.125C.6.25D.11.125在十六进制表示法中，字母A相当于十进制中的（）。A.9B.10C.15D.16十六进制数9A在（）进制下是232.A.四B.八C.十D.十二在二进制下，1101001+（）=1110110。A、1011B、1101C、1010D、1111一个正整数在二进制

2、下有100位，则它在十六进制下有（）位。A、7B、13C、25D、不能确定十进制小数125.125对应的八进制数是A)100.1B)175.175C)175.1D)100.175ABBBCC2、逻辑运算逻辑运算符：逻辑运算描述：1-true-真，0-false-假，非1-0，非0-1。解题：排除法，找反例。与或非∧∨ABA与B（A∧B）A或B（A∨B）0000010110011111逻辑表达式（）的值与变量A的真假无关。A.(A∨B)∧¬AB.(A∨B)∧¬BC.(A∧B)∨(¬A∧B)D.(A∨B)∧¬A∧BC3、栈和队列栈：栈是一种特殊的线性表。其特殊性在于限定插入和删除数

3、据元素的操作只能在线性表的一端进行。有后进先出的特点。队列(Queue)也是一种运算受限的线性表，它的运算限制与栈不同，是两头都有限制，插入只能在表的一端进行(只进不出)，而删除只能在表的另一端进行(只出不进)，允许删除的一端称为队尾(rear)，允许插入的一端称为队头(Front)。有先进先出的特点。（）是一种先进先出的线性表。A.栈B.队列C.哈希表（散列表）D.二叉树如果一个栈初始时为空，且当前栈中的元素从栈顶到栈底依次为a，b，c，另有元素d已经出栈，则可能的入栈顺序是（）。A.a,d,c,bB.b,a,c,dC.a,c,b,dD.d,a,b,c广度优先搜索时，需要用

4、到的数据结构是（）。A、链表B、队列C、栈D、散列表有六个元素FEDCBA从左到右依次顺序进栈，在进栈过程中会有元素被弹出栈。问下列哪一个不可能是合法的出栈序列？A)EDCFABB)DECABFC)CDFEBAD)BCDAEF在程序运行过程中，如果递归调用的层数过多，会因为（）引发错误。A.系统分配的栈空间溢出B.系统分配的堆空间溢出C.系统分配的队列空间溢出D.系统分配的链表空间溢出BD深度-栈BCA4、算法描述1）算法----故事2）算法执行过程的形式穷举法、递归、递推、分治、回溯。下面的故事与（）算法有着异曲同工之妙。从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事

5、：‚从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：‘从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事....’‛A.枚举B.递归C.贪心D.分治体育课的铃声响了，同学们都陆续地奔向操场，按老师的要求从高到矮站成一排。每个同学按顺序来到操场时，都从排尾走向排头，找到第一个比自己高的同学，并站在他的后面。这种站队的方法类似于（）算法。A、快速排序B、插入排序C、冒泡排序D、归并排序（）是一种选优搜索法，按选优条件向前搜索，以达到目标。当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。A、回溯法B、枚举法C、动态规划D、贪心法BBA5、树、二叉树树的

6、相关概念：度：任一结点拥有子树的数目，称为结点的度；所有结点的度的最大值，称为树的度。层：根为第一层，最大层数为树的深（高）度。根节点：叶子节点：度为0的结点。树的遍历：先（根左右）中（左根右）后（左右根）表达式中的前（中、后）缀表达式：已知一棵二叉树有10个节点，则其中至多有（）个节点有2个子节点。A.4B.5C.6D.7二叉树的（）第一个访问的节点是根节点。A.先序遍历B.中序遍历C.后序遍历D.以上都是如果一棵二叉树的中序遍历是BAC，那么它的先序遍历不可能是（）。A.ABCB.CBAC.ACBD.BAC如果根结点的深度记为1，则一棵恰有2011个叶结点的二叉树的深度最少

7、是（）。A、10B、11C、12D、13表达式a*(b+c)-d的后缀表达式是A)abcd*+-B)abc+*d-C)abc*+d-D)-+*abcd一个包含n个分支节点（非叶节点）的非空二叉树，它的叶节点数目最多为：A)2n+1B)2n-1C)n-1D)n+1AABDC6、图有向图：若图中的每条边都是有方向的，则称为有向图。有向图中的边是由两个顶点组成的有序对，有序对通常用尖括号表示，如表示一条有向边，其中vi是边的始点，vj是边的终点。和代表两条