Noip初赛复习指南、题目分类解析(3)

/ 7

就不是，2和7的深度差2.

因为2^11 = 2048；所以一颗满二叉树从深度为0（根节点）到深度10的总节点数是2047，剩下2381-2047 = 334个节点，这剩下的节点的深度都是11。

所以答案为B

10．将 5 个数的序列排序，不论原先的顺序如何，最少都可以通过（ B ）次比较，完成从小到大的排序。

A. 6 B. 7 C. 8 D. 9 E. 10

13. 设栈S的初始状态为空，元素a, b, c, d, e 依次入栈，以下出栈序列不可能出现的有（ C ）。

A. a, b, c, e, d B. b, c, a, e, d C. a, e, c, b, d D. d, c, e, b, a

14. 已知 6 个结点的二叉树的先根遍历是 1 2 3 4 5 6（数字为结点的编号，以下同），后根遍历是 3 2 5 6 4 1，则该二叉树的可能的中根遍历是（ BC ）

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

NOIP2007：

2. 在关系数据库中, 存放在数据库中的数据的逻辑结构以( E )为主。

A. 二叉树 B. 多叉树 C. 哈希表 D. B+树 E. 二维表

9. 欧拉图G是指可以构成一个闭回路的图，且图G的每一条边恰好在这个闭回路上出现一次（即一笔画成）。在以下各个描述中, 不一定是欧拉图的是：（ D ）。 A. 图G中没有度为奇数的顶点

B. 包括欧拉环游的图(欧拉环游是指通过图中每边恰好一次的闭路径) C. 包括欧拉闭迹的图(欧拉迹是指通过途中每边恰好一次的路径) D. 存在一条回路, 通过每个顶点恰好一次 E. 本身为闭迹的图

14. 已知7个节点的二叉树的先根遍历是1 2 4 5 6 3 7(数字为结点的编号，以下同)， 后根遍历是4 6 5 2 7 3 1， 则该二叉树的可能的中根遍历是（ ABD ）

A. 4 2 6 5 1 7 3 B. 4 2 5 6 1 3 7 C. 4 2 3 1 5 4 7 D. 4 2 5 6 1 7 3 19. 在下列关于算法复杂性的说法中， 正确的有（ BC ）。

A. 算法的时间复杂度，是指它在某台计算机上具体实现时的运行时间

B. 算法的时间复杂度，是指对于该算法的一种或几种主要的运算， 运算的次数与问题的规模之间的函数关系 C. 一个问题如果是NPC类的， 就意味着在解决该问题时， 不存在一个具有多项式时间复杂度的算法. 但这一点还没有得到理论上证实，也没有被否定

D. 一个问题如果是NP类的，与C有相同的结论 由X2Studio.Net收集

5．将数组{8, 23, 4, 16, 77, -5, 53, 100}中的元素按从大到小的顺序排列，每次可以交换任意两个元素，最少需要交换（ B ）次。

A. 4 B. 5 C. 6 D. 7 E. 8

6．设栈S的初始状态为空，元素a，b，c，d，e，f依次入栈S，出栈的序列为b，d，c，f，e，a，则栈S的容量至少应该是（ D ）。

A. 6 B. 5 C. 4 D. 3 E. 2 18. 设T是一棵有n个顶点的树，下列说法正确的是（ ABC ）。

A. T是连通的、无环的 B. T是连通的，有n-1条边 C. T是无环的，有n-1条边 D. 以上都不对

NOIP2009：

5、一个包含n个分支结点（非叶结点）的非空满k叉树，k>=1，它的叶结点数目为：D A) nk + 1 B) nk-1 C) (k+1)n-1 D. (k-1)n+1

7、最优前缀编码，也称Huffman编码。这种编码组合的特点是对于较频繁使用的元素给与较短的唯一编码，

11

以提高通讯的效率。下面编码组合哪一组不是合法的前缀编码。B

A)（00，01，10，11） B)（0，1，00，11） C)（0，10，110，111） D)（1，01，000，001）

8、快速排序平均情况和最坏情况下的算法时间复杂度分别为：A

A) 平均情况 O(nlog2n)，最坏情况O(n2) B) 平均情况 O(n)， 最坏情况O(n2)

C) 平均情况 O(n)， 最坏情况O(nlog2n) D) 平均情况 O(log2n)， 最坏情况O(n2)

9、左图给出了一个加权无向图，从顶点V0开始用prim算法求最小生成树。则依次加入最小生成树的顶点集合的顶点序列为：A

A) V0, V1, V2, V3, V5, V4 B) V0, V1, V5, V4, V3, V3 C) V1, V2, V3, V0, V5, V4 D) V1, V2, V3, V0, V4, V5

6、若3个顶点的无权图G的邻接矩阵用数组存储为{{0，1，1}，{1，0，1}，{0，1，0}}，假定在具体存储中顶点依次为: v1，v2，v3。关于该图，下面的说法哪些是正确的：ABD

A) 该图是有向图。 B) 该图是强连通的。

C) 该图所有顶点的入度之和减所有顶点的出度之和等于1。

D) 从v1开始的深度优先遍历所经过的顶点序列与广度优先的顶点序列是相同的。

8、散列表的地址区间为0-10,散列函数为H(K)=K mod 11。采用开地址法的线性探查法处理冲突，并将关键字序列26，25，72，38，8，18，59存储到散列表中，这些元素存入散列表的顺序并不确定。假定之前散列表为空，则元素59存放在散列表中的可能地址有：ABC

A) 5 B) 7 C) 9 D) 10

类型5：数学与逻辑运算： NOIP1999：

17、十进制算术表达式 ：3*512 + 7*64 + 4*8 + 5的运算结果，用二进制表示为（ B ） A. 10111100101 B. 11111100101 C. 11110100101 D. 11111101101

NOIP2000：

1.下列无符号数中，最小的数是（ C ）

A.（11011001）2 B.(75)10 C.(37)8 D.(2A)16

10.某种计算机的内存容量是640K，这里的640K容量是指（ C ）个字节

A.640 B. 640*1000 C. 640*1024 D. 640*1024*1024

NOIP2001：

3、64KB的存储器用十六进制表示，它的最大的地址码是( B ) A)10000 B)FFFF C)1FFFF D)EFFFF 9、2KB的内存能存储( )个汉字的机内码 A A)1024 B)516 C)2048 D)218

11、运算式(2047)10—(3FF)16+(2000)8的结果是( A ) A)(2048)10 B)(2049)10 C)(3746)8 D)(1AF7)16 16.[x]补码=10011000，其原码为( B )

A)011001111 B)11101000 C)11100110 D)01100101

12

NOIP2002：

3． 十进制书11/128可用二进制数码序列表示为：（ D ）。

A）1011/1000000 B）1011/100000000 C）0.001011 D）0.0001011 4． 算式（2047）10 －（3FF）16 ＋（2000）8的结果是（ A ）。 A）（2048）10 B）（2049）10 C）（3746）8 D）（1AF7）16 5． 已知x =（0.1011010）2 ，则[ x / 2 ]补 =（ C ）2 。

A）0.1011101 B）11110110 C）0.0101101 D）0.100110

C）连接在网络上的高级 D）具有处理文字、图形、声音、影像等信息的 15．已知A = 35H，A /\\ 05H \\/ A /\\ 30H 的结果是：（ C ）。

A）30H B）05H C）35H D）53H

NOIP2003：

3. 十进制数2003等值于二进制数（ D ）。

A） 0100000111 B） 10000011 C） 110000111 D） 11111010011 E） 1111010011 4. 假设A=true,B=false,C=ture,D=ture,逻辑运算表达式A∧B∨C∧D的值是（ A ）。 A） ture B） false C） 0 D） 1 E） NULL

8. 设全集E={1，2，3，4，5}，集合A={1，4}，B={1，2，5}，C={2，4}，则集合（A ∩B）∪～C 为（ A） 空集 B） {1} C） {3，5} D）{1，5} E） {1，3，5} 18. 运算试(2008)10-(3723)8 的结果是（ BCD ）。

A）(-1715)10 B) (5)10 C) (5)16 D) (101)2 E) (3263)8

NOIP2004：

1. 设全集I = {a, b, c, d, e, f, g}，集合A = {a, b, c}，B = {b, d, e}，C = {e, f, g}，那么集合 为（ A ）。A. {a, b, c, d} B. {a, b, d, e} C. {b, d, e} D. {b, c, d, e} E. {d, f, g}

2. 由3个a，5个b和2个c构成的所有字符串中，包含子串“abc”的共有（ D ）个。

A. 40320 B. 39600 C. 840 D. 780 E. 60 13. (2004)10 + (32)16的结果是（ BCD ）。

A. (2036)16 B. (2054)10 C. (4006)8 D. (100000000110)2 E. (2036)10

NOIP2005：

1. 字符串“ababacbab”和字符串“abcba”的最长公共子串是（ B ）。

A. abcba B. cba C. abc D. ab E. bcba

2. 设全集I = {a, b, c, d, e, f, g, h}，集合B A??= {a, b, c, d, e, f}， C A??= {c, d, e}， B A ~ ??= {a, d}，那么集合C B A ????为（ A ）。

A. {c, e} B. {d, e} C. {e} D. {c, d, e} E. {d, f}

3. 以下二进制数的值与十进制数23.456 的值最接近的是（ D ）。

A. 10111.0101 B. 11011.1111 C. 11011.0111 D. 10111.0111 E. 10111.1111

11. 设A = true，B = false，C = false，D = true，以下逻辑运算表达式值为真的有（ BC ）。

A. (A B ∧ )∨(C D ∧ ) B. ((A B ∧ ) C ∨ ) D ∧ C. A∧((B C ∨ ) D ∨ ) D. (A∧(B C ∨ )) D ∨ E. (A B ∨ )∧(C D ∨ )

NOIP2006：

5．在 Pascal 语言中，表达式 (21 xor 2)的值是（ C ）

A. 441 B. 42 C.23 D.24 E.25

11. 设A=B=D=true，C=E=false，以下逻辑运算表达式值为真的有（ ABC ）。

A. (? A∧B)∨(C∧D)∨E B. (((A∧B)∨C)∧D∧E) C. A∧(B∨C∨D∨E) D. (A∧(B∨C)) ∧D∧E 12. (2010)16 + (32)8的结果是（ AB ）。

A. (8234)10 B. (202A)16

C. (100000000110)2 D. (2042)16

NOIP2007：

6．在 Pascal 语言中，判断整数a 等于 0 或b等于 0或c等于0 的正确的条件表达式是（ B ）

13

E ）。

A. not ((a<>0) or (b<>0) or (c<>0)) B. not ((a<>0) and (b<>0) and (c<>0)) C. not ((a=0) and (b=0)) or (c=0) D.(a=0) and (b=0) and (c=0) E. not ((a=0) or (b=0) or (c=0))

8. 与十进制数17.5625相对应的8进制数是（ B ）。

A. 21.5625 B. 21.44 C. 21.73 D. 21.731 E. 前4个答案都不对

11. 设A=B=true，C=D=false，以下逻辑运算表达式值为真的有（ ABC ）。

A. (「A∧B)∨(C∧D∨A) B. 「 ( ( (A∧B)∨C)∧D) C. A∧(B∨C∨D)∨D D. (A∧(D∨C)) ∧B

12. 命题“P→Q”可读做P蕴含Q， 其中P、Q是两个独立的命题. 只有当命题P成立而命题Q不成立时， 命题\→Q\的值为false， 其它情况均为true. 与命题\→Q\等价的逻辑关系式是（ AD ）。

A. 「 P∨Q B. P∧Q C. 「 (P∨Q) D. 「(「Q∧P ) 13. (2070)16+(34)8的结果是（ ABD ）。

A. (8332)10 B. (208C)16 C. (100000000110)2 D. (20214)8

NOIP2008：

3. 设字符串S=”Olympic”，S的非空子串的数目是（ B ）。

A. 29 B. 28 C. 16 D. 17 E. 7

13. 设A=true，B=false，C=true，D=false，以下逻辑运算表达式值为真的有（ BC ）。

A. (A∧B)∨(C∧D∨ A) B. (( A∧B)∨C)∧ D C. (B∨C∨D)∨D∧A D. A∧(D∨ C)∧B 15. (2008)10 + (5B)16的结果是（ ABC ）。

A. (833)16 B. (2099)10 C. (4063)8 D. (100001100011)2

NOIP2009：

4、在字长为16位的系统环境下，一个16位带符号整数的二进制补码为1111111111101101。其对应的十进制整数应该是：B

A) 19 B) -19 C) 18 D) -18

第二部分：问题求解（2*5=10分）

这部分题目对数学要求要高一点，往往考查的是数学问题（如代数变形、组合、概论统计等），数列（一般是考递推、递归、归纳法等），逻辑推理；也考查一些算法和数据结构知识（如队列、栈、二叉树）。建议大家多花一点时间做，尽量做对。

1.数组A[30..100,20..100]以行优先的方式存储,每个元素占8个字节,且已知A[40,30]的地址为20000,则A[60,90]的地址为:_________________。如果以列优先存储,则为:_________________。 解答：设数组首地址为X，则：X+（（40-30）*（100-20+1）+（30-20））* 8 = 20000 前面的行数 每行的列数 本行中序号 每个元素的基 则：X=13340，用上述的式子，不难算出：

A[60，90]的地址：33340

列优先存储，只要稍微改动上述公式，结果略；

? 考查了数据结构中数组存储方式。还可以考数组基类型为记录的情况，可以问你同样的问题；或者问你共

占用多少空间！

2.（1998年初中组）设栈S的初始状态为空,现有5个元素组成的序列{1,2,3,4,5},对该序列在S 栈上依次进行如下操作(从序列中的1开始,出栈后不在进栈):进栈,进栈,进栈,出栈,进栈,出栈,进栈,问出栈的元素序列是:_________,栈顶指针的值为______，栈顶元素为:___________________。

14

解答：出栈序列为{3，4}，栈顶指针值为3，栈顶元素为5。

? 考查了数据结构中的栈。还可以把栈和队列结合起来考！如下题：

3．如2002年高中组：设栈S和队列Q初始状态为空，元素e 1 ，e 2 ，e 3 ，e 4 ，e 5 ，e 6依次通过栈S，一个元素出栈后即进入队列Q，若出队顺序为e 2 ，e 4 ，e 3 ，e 6 ，e 5 ，e 1 ，则栈S的容量至少应该为______________。 解答：为3。 4．（2000年初中组）设循环队列中数组的下标范围是1..n，其头尾指针分别为f和r，则其元素个数为：_____________________。 解答：（r-f+n）mod n

? 考查了数据结构中的队列。

5.中缀表达式、前缀表达式、后缀表达式（1997年初中组） （1) 已知中缀表达式：A+B*C/D

求它的前缀表达式和后缀表达式？

（2）已知前缀表达式：+△A*B△C {注△表示一元运算符负号，即△A表示-A} 求它的中缀表达式和后缀表达式？ 解答：画（二叉）表达式树。

（1）的结果：+A*B/CD；ABCD/*+ （2）的结果：（-A）+B*（-C）；A△BC△*+

? 考查了数据结构中的表达式树。

6.（1998年初中组） 已知一个数列U1,U2,U3...Un...,往往可以找到一个最小的K值和K个数a1,a2,..,ak,使得数列从某项开始都满足:U(n+k)=a1*U(n+k-1)＋a2*U(n+k-2)+......＋akUn (式A)

例如数列 1,1,2,3,5......可以发现:当K=2,a1=1,a2=1时,从第3项起(N>=1)满足: U(n+2)＝U(n+1) ＋ Un

试对数列1^3 ,2^3 ,3^3 ,......,N^3,??,求K和a1,a2,...ak,使得式A成立。 解答：解方程，先设K=2，列出方程组：

222

a1*1+a2*2=3

222

a1*2+a2*3=4

以上方程组无整数解。再设K=3，列出方程组：

2222

a1*0+a2*1+a3*2=3

2222

a1*1+a2*2+a3*3=4

2222

a1*2+a2*3+a3*4=5

以上方程的整数解为：a1=1，a2=-3，a3=3，此时K=3。 ? 实质是考数学。

7.（1998年高中组）给出一棵二叉树的中序遍历:DBGEACHFI与后序遍历:DGEBHIFCA,画出此二叉树。

8.（1996年高中组）下面是一个利用完全二叉树特性,用顺序表来存储的一个二叉树,结点数据为字符型(结点

15

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库Noip初赛复习指南、题目分类解析(3)在线全文阅读。