[急]NOIP的几个初赛问题

Question

[急]NOIP的几个初赛问题

本人选取了近6年来Noip普及组初赛中我不得方法的选择题。望高人赐教，不胜感激。

答案我已经附上，但皆网上搜集而来，准确性难以保证，仅供参考。

解题时，请附解此类题思路、方法，（及相关资料）越详细越好。感激不尽！

这些题无需都答出，但多多益善。我会根据数量及质量选出最佳答案。

谢谢！

第六届

8．设循环队列中数组的下标范围是1–n，其头尾指针分别为f和r，则其元素个数为（ D ）．
A．r- f B．r- f +1
C．（r- f ） MOD n+1 D．（r- f + n） MOD n

17．线性表若采用链表存贮结构，要求内存中可用存贮单元地址（ D ）．
[回答此问请附关于线性表的相关知识]
A．必须连续 B．部分地址必须连续
C．一定不连续 D．连续不连续均可

第八届
13)IP v4地址是由( ) 位二进制数码表示的。
A) 16 B) 32 c) 24 D) 8

第九届
20．IP地址是一个( C )位二进制码。
[回答此问请附关于IP地址（及TCP/IP）的相关常识]
A)8 B)16 C)32 D)64 E)12

第十届
13、由3个a，1个b和2个c构成的所有字符串中，包含子串“abc”的共有（ D ）个
A、20 B、8 C、16 D、12 E、24

16、满二叉树的叶节点为N，则它的节点总数为（ C ）
[回答此问题请附所有关于图、树的计算公式。]
A、N
B、2N
C、2N-1
D、2N+1
E、2^N-1

19、在下图，从端点（ E ）出发存在一条路径可以遍历图中的每条边一次，而且仅遍历一次
图见：http://img226.imageshack.us/img226/5248/q1hi9.jpg

第十一届

5. 平面上有五个点A(5, 3), B(3, 5), C(2, 1), D(3, 3), E(5, 1)。以这五点作为完全图G 的顶点，
每两点之间的直线距离是图G 中对应边的权值。以下哪条边不是图G 的最小生成树中
的边（ D ）。
A. AD B. BD C. CD D. DE E. EA

7. 处理器A 每秒处理的指令数是处理器B 的2 倍。某一特定程序P 分别编译为处理器A
和处理器B 的指令，编译结果处理器A 的指令数是处理器B 的4 倍。已知程序P 在处
理器A 上执行需要1 个小时，那么在输入相同的情况下，程序P 在处理器B 上执行需
要（ D ）小时。
A. 4 B. 2 C. 1 D. 1 / 2 E. 1 / 4

19. 二叉树T的宽度优先遍历序列为A B C D E F G H I，已知A是C的父结点，D 是G 的
父结点，F 是I 的父结点，树中所有结点的最大深度为3（根结点深度设为0），可知F
的父结点是（ C ）。
A. 无法确定B. B C. C D. D E. E

Answer 1

8．设循环队列中数组的下标范围是1–n，其头尾指针分别为f和r，则其元素个数为（ D ）．
A．r- f B．r- f +1
C．（r- f ） MOD n+1 D．（r- f + n） MOD n

是循环数组啊！如果r>f那么 是r-f+1 但是如果r小于F呢？就是r到N 加上1到f的个数。通用公式就是D。

17．线性表若采用链表存贮结构，要求内存中可用存贮单元地址（ D ）．
[回答此问请附关于线性表的相关知识]
A．必须连续 B．部分地址必须连续
C．一定不连续 D．连续不连续均可

一般数组A[1..n]在内存中是连续的一堆数，如32，25..8，46等等
但是占用固定内存空间，而链表就不是了，他的每个数带2个小口袋如32前口袋是空的，表示前面没有数，后口袋带了25数字所在的内存位置，这样所有的数字都连续起来了。所以内存中那不是连续的。
第八届
13)IP v4地址是由( ) 位二进制数码表示的。
A) 16 B) 32 c) 24 D) 8

第九届
20．IP地址是一个( C )位二进制码。
[回答此问请附关于IP地址（及TCP/IP）的相关常识]
A)8 B)16 C)32 D)64 E)12

8、9两题差不多，因为ip地址样式是255.255.255.255，一共四个最大是255的数段组成，总共能表达2^32种不同地址，所以32位了。
现在中国提出了ip v6计划，多少位？呵呵。
第十届
13、由3个a，1个b和2个c构成的所有字符串中，包含子串“abc”的共有（ D ）个
A、20 B、8 C、16 D、12 E、24

也就是由 2个a，一个abc，一个c左右有多少种组合，4*3＝12种。
16、满二叉树的叶节点为N，则它的节点总数为（ C ）
[回答此问题请附所有关于图、树的计算公式。]
A、N
B、2N
C、2N-1
D、2N+1
E、2^N-1

满二叉树就是所有的节点全部满啊（1分2，2分4...），第一层是1个，第二层4个，第三层8个……规律就是这样，公示自己也能推导了吧。
19、在下图，从端点（ E ）出发存在一条路径可以遍历图中的每条边一次，而且仅遍历一次

一笔画，遍历就是走一遍。

第十一届

5. 平面上有五个点A(5, 3), B(3, 5), C(2, 1), D(3, 3), E(5, 1)。以这五点作为完全图G 的顶点，
每两点之间的直线距离是图G 中对应边的权值。以下哪条边不是图G 的最小生成树中
的边（ D ）。
A. AD B. BD C. CD D. DE E. EA
做法：现在xy坐标轴中画出这些点，然后将所有点连接，然后依次删除较长的点，最后只留下最短的4条边并保证5个点都相连就ok了，

7. 处理器A 每秒处理的指令数是处理器B 的2 倍。某一特定程序P 分别编译为处理器A
和处理器B 的指令，编译结果处理器A 的指令数是处理器B 的4 倍。已知程序P 在处
理器A 上执行需要1 个小时，那么在输入相同的情况下，程序P 在处理器B 上执行需
要（ D ）小时。
A. 4 B. 2 C. 1 D. 1 / 2 E. 1 / 4

这个算一下啊，虽然速度慢一半，但是只用执行1/4的指令啊，当然1/2时间啊。
19. 二叉树T的宽度优先遍历序列为A B C D E F G H I，已知A是C的父结点，D 是G 的
父结点，F 是I 的父结点，树中所有结点的最大深度为3（根结点深度设为0），可知F
的父结点是（ C ）。
A. 无法确定B. B C. C D. D E. E
19去知道上查吧有很详细的答案的
如：就是按层次遍历，这棵树的机构可能是：

a
/ \
b c
/ \ /
d e f
/ \ /
g h i

a
/ \
b c
/ / \
d e f
/ \ /
g h i

a
/ \
b c
/ \ \
d e f
/ \ /
g h i

不管哪一种大案都是C

大后天考试了，祝你好运

Answer 2

d
d
b
c
d
c
d
d
b

Answer 3

第16题
有关二叉树 须记住那几条性质
不过我的窍门是:先画一个二叉树,再检验答案