算机的基本知识题（如CPU、内存、总线、字长、体系结构 …

算机的基本知识题（如CPU、内存、总线、字长、体系结构 … 2012信息学奥林匹克初赛练习---队、栈 1. 2010tgdx1.元素R1、R2、R3、R4、R5入栈的顺序为R1、R2、R3、R4、R5。如果第1个出栈的是R3， 那么第5个出栈的可能是( )。 A.R1 B.R2 C.R4 D.R5 2. 2008tg6(设栈S的初始状态为空，元素a，b，c，d，e，f依次入栈，出栈顺序为b，d，c，f，e，a 那么栈容量至少应该是( )。 A(6 B(5 C(4 D(3 E(2 3. 2007tg 7. 地面上有标号为A、B、C的3根细柱, 在A柱上放有10个直径相同中间有孔的圆盘, 从 上到下次依次编号为1, 2, 3, „„，将A柱上的部分盘子经过B柱移入C柱, 也可以在B柱上暂存。 如果B柱上的操作为:“进，进，出，进，进，出，出，进，进，出，进，出，出”。那么, 在C 柱上, 从下到上的盘子的编号为( )。 A. 2 4 3 6 5 7 B. 2 4 1 2 5 7 C. 2 4 3 1 7 6 D. 2 4 3 6 7 5 E. 2 1 4 3 7 5 4. 2006tg 7 (某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状 态为空，从这一时刻开始的出入记录为:“进，出，进，进，进，出，出，进，进，进，出,出”。 假设车辆入站的顺序为1 ， 2 ， 3 ，„„，则车辆出站的顺序为( )。 A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 C. 1, 4, 3, 7, 6 D. 1, 4, 3, 7, 2 E. 1, 4, 3, 7, 5 5. 2006tg dx13. 设栈S 的初始状态为空，元素a, b, c, d, e 依次入栈，以下出栈序列不可能出现的 有( )。 A. a, b, c, e, d B. b, c, a, e, d C. a, e, c, b, d D. d, c, e, b, a 6. 2005tg dx 14. 设栈S的初始状态为空，元素a, b, c, d, e, f, g依次入栈，以下出栈序列不可能 出现的有( )。 A. a, b, c, e, d, f, g B. b, c, a, f, e, g, d C. a, e, c, b, d, f, g D. d, c, f, e, b, a, g E. g, e, f, d, c, b, a 7. 2004tg3某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为 空，从这一时刻开始的出入记录为:“进，出，进，进，出，进，进，进，出，出，进，出”。假设车 辆入站的顺序为1，2，3，„„，则车辆出站的顺序为( )。 A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 C. 1, 3, 5, 4, 6 D. 1, 3, 5, 6, 7 E. 1, 3, 6, 5, 7 8. 2003tg 6.已知队列(13，2，11，34，4l，77，5，7，18，26，15)，第一个进入队列的元素是13，则 第五个出队列的元素是( )。 A. 5 B. 41 C. 77 D. 13 E. 18 9. 2003tg 9(表达式(1+34)*5-56,7的后缀表达式为( ) A.1+34*5-56,7 B. -*+1 345,567 C.1 34+5*56 7,- D.1 345*+56 7,- E.1 34+5 567-*, 10. 2003tg 19(已知元素(8，25，14，87，5l，90，6，19，20)，问这些元素以怎样的顺序进入栈，才 能使出栈的顺序满足:8在5l前面;90在87后面;20在14后面;25在6前面;19在90后面。 ( ) A. 20，6，8，51，90，25，14，19，87 B. 51，6，19，20，14，8，87，90，25 C. 19，20，90，7，6，25，5l，14，87 D. 6，25，51，8，20，19，90，87，14 E. 25，6，8，51，87，90，19，14，20 11. 2002tg设栈S和队列Q的初始状态为空，元素e ，e ，e ，e ，e ，e 依次通过栈S，一个元1 2 3 4 5 6 素出栈后即进入队列Q，若出队的顺序为e ，e ，e ，e ，e ，e ，则栈S的容量至少应该为2 4 3 6 5 1 (B)。 A.2 B.3 C. 4 D.5 12. 2001tg13若已知一个栈的入栈顺序是1，2，3，„，n，其输出序列为P1，P2，P3，„，Pn，若P1是 n，则Pi是(C ) A. i B. n-1 C.n-i+1 D.不确定 2012信息学奥林匹克初赛练习—树 1. 2011tgdx如果根结点的深度记为1，则一棵恰有2011个叶子结点的二叉树的深度可能是(CD )。 A(10 B(11 C(12 D(2011 2. 2011tgdx1现有一段文言文，要通过二进制哈夫曼编码进行压缩。简单起见，假设这段文言文只由4 个汉字“之”、“乎”、“者”、“也”组成，它们出现的次数分别为700、600、300、400。那么， “也”字的编码长度可能是(BC )。 A(1 B(2 C(3 D(4 1 3. 2010tg完全二叉树的顺序存储，是指将完全二叉树的结点从上到下、从左到右依次存放到一个顺 序结构的数组中。假定根结点存放在数组的1号位置上，则第k号结点的父结点如果存在的话，应当 存放在数组中的(C )号位置。 A. 2k B. 2k+1 C. k/2下取整 D. (k+1)/2 4. 2010tg7.前缀表达式“+ 3 * 2 + 5 12 ” 的值是(C )。 A. 23 B. 25 C. 37 D. 65 5. 2009tg 一个包含n个分支结点(非叶结点)的非空满k叉树，k>=1，它的叶结点数为(D) A. nk+1 B. nk-1 C. (k+1)n-1 D. (k-1)n+1 选择D考多叉树的性质，N0=(K-1)N+1，考试的时带入K=2时候，验证二叉树能得到结果。 6. 2009tg 表达式a*(b+c)-d的后缀表达式是( ) A. abcd*+- B. abc+*d- C. abc*+d- D. -+*abcd 7. 2009tg 最优前缀编码，也称Huffman编码。这种编码组合的特点是对于较频繁使用的元素给与较短的 唯一编码，以提高通讯的效率。下面编码组合哪一组不是合法的前缀编码(B) A.(00，01，10，11) B.(0，1，00，11) C.(0，10，110，111) D.(1，01，000，001) 8. 2008tg 4(完全二叉树有2*N-1的结点，则它的叶子结点数目是( C )。 A(N-1 B(2*N C(N D(2N-1 E(N/2 9. 2008tg 16(二叉树T，已知其先序遍历是1 2 4 3 5 7 6(数字为节点编号，以下同)，后序遍历是4 2 7 5 6 3 1，则该二叉树的中根遍历是( ABD ) A(4 2 1 7 5 3 6 B(2 4 1 7 5 3 6 C(4 2 1 7 5 6 4 D(2 4 1 5 7 3 6 10. (2007 13tg)14.已知7个节点的二叉树的先根遍历是1 2 4 5 6 3 7(数字为节点的编号，以下同)， 中根遍历是4 2 6 5 1 7 3，则该二叉树的后根遍历是(ABD)。 A(4 6 5 2 7 3 1 B(4 6 5 2 1 3 7 C(4 2 3 1 5 4 7 D(4 6 5 3 1 7 2 11. (2006tg)8 (高度为n 的均衡的二叉树是指:如果去掉叶结点及相应的树枝，它应该是高度为n-1 的 满二叉树。在这里，树高等于叶结点的最大深度，根结点的深度为0 ，如果某个均衡的二叉树共有2381 个结点，则该树的树高为( )。 A. 10 B. 11 C . 12 D. 13 E. 2 10 – 1 12. (2006tg 12tg_多项)14.已知 6 个结点的二叉树的先根遍历是 1 2 3 4 5 6(数字为结点的编号，以 下同)，后根遍历是3 2 5 6 4 1，则该二叉树的可能的中根遍历是( ) A. 3 2 1 4 6 5 B. 3 2 1 5 4 6 C. 2 3 1 5 4 6 D. 2 3 1 4 6 5 13. 4. (2005tg 11tg)4.完全二叉树的结点个数为4 * N + 3，则它的叶结点个数为( )。 A. 2 * N B. 2 * N - 1 C. 2 * N + 1 D. 2 * N - 2 E. 2 * N + 2 14. (2005tg 11tg _多项)13.二叉树T的宽度优先遍历序列为A B C D E F G H I，已知A是C的父结点， D 是G 的父结点，F 是I 的父结点，树中所有结点的最大深度为3(根结点深度设为0)，可知E的父 结点可能是( )。 A. A B. B C. C D. D E. F 15. (2004 10tg)4. 满二叉树的叶结点个数为N，则它的结点总数为( )。 A. N B. 2 * N C. 2 * N – 1 D. 2 * N + 1 E. 2N – 1 16. (2004 10tg)5. 叉树T，已知其前序遍历序列为1 2 4 3 5 7 6，中序遍历序列为4 2 1 5 7 3 6，则 其后序遍历序列为( )。 A. 4 2 5 7 6 3 1 B. 4 2 7 5 6 3 1 C. 4 2 7 5 3 6 1 D. 4 7 2 3 5 6 1 E. 4 5 2 6 3 7 1 17. (2003 tg)9.表达式(1+34)*5-56,7的后缀表达式为( ) A. 1+34*5-56,7 B. -*+1 345,567 C. 1 34+5*56 7,- D. 1 345*+56 7,- E. 1 34+5 567-*, 18. (2002 tg)17.按照二叉数的定义，具有3个结点的二叉树有( )种。 A. 3 B. 4 C. 5 D. 6 19. (2001 tg)13.若已知一个栈的入栈顺序是1，2，3，„，n，其输出序列为P1，P2，P3，„，Pn，若 P1是n，则Pi是( ) A. i B. n-1 C. n-i+1 D. 不确定 20. (2001 tg )19. 一棵二叉树的高度为h，所有结点的度为0，或为2，则此树最少有( )个结点 A. 2^h-1 B. 2h-1 C. 2h+1 D. h+1 21. (2000 tg )12.在有N个叶子节点的哈夫曼树中，其节点总数为( ) A.不确定 B. 2N-1 C. 2N+1 D. 2N 2