NOIP初赛谈.doc

NOIP 初赛谈知识是基础,能力最重要 NOIP 初赛考的知识点,大纲上有 3块:计算机基本常识、计算机基本操作、程序设计基本知识。具体来说: 选择题考查的是计算机基本常识、基本操作和程序设计中的一些基本数据结构与基本算法;而填空题更加重视能力(尤其是队列、栈、二叉树等数据结构、数学问题、归纳法、数列和逻辑推理等)的考查;读程序写运行结果考察的是对程序的理解和跟踪,重在分析推理能力。读程序的 4 条题目往往有一定的层次, 试卷中给出程序的并不复杂,语句的含义容易明白,但是悟性好的选手总是很快就能体会到程序的设计思路并得出正确的答案,机械模仿计算机手工逐步算出结果的同学往往做的很慢,造成时间不够,而且容易失误;完善程序更是考察程序设计能力,尤其是在明确算法和数据结构的条件下,如何编程。读程序和完善程序,需要在平时的学****中提高,经常阅读、讨论和研究别人的优秀程序,提高自己的理解力和速度。各种题型的解题经验(以 2002 、 2001 年试题为例) l选择题( 30分=20* ) 一般是比较容易得分的,不可错过! 程序设计方面的知识多是平时计算机课堂教学或课外活动中学到的,建议大家找全国计算机等级考试(一、二级)的题目做做,一般不超过二级的知识点,知识要复****的系统一些。新大纲和最近两年的考试不再考 DOS ,但有 DOS 经验的选手可能会占一点便宜, 因为有些题目可以根据经验判断。另外,往更高层次发展的过程中,必要的 DOS 知识和命令还是必须的。Ø 分布: 5-6 个数据结构或算法方面的基本知识(高中组更多一些!!!); 200 2年初中组( 16):一个向量第一个元素的存储地址是 100, 每个元素的长度是 2,则第 5个元素的地址是(B) A) 110 B) 108 C) 100 D) 109 2002 年初中组( 17):在所有排序方法中,关键字比较的次数与记录的初始排列次序无关的是(D) A)希尔排序 B)起泡排序 C)插入排序 D)选择排序 2002 年初中组( 19) :设有一个含有 13 个元素的 Hash 表(O~12),Hash 函数是:H(key)=key % 13, 其中% 是求余数运算。用线性探查法解决冲突,则对于序列(2、 8、 31、 20、 19、 18、 53、 27),18 应放在第几号格中(B)。 A)5 B)9 C)4 D)0 2002 年高中组( 17):按照二叉数的定义,具有 3个结点的二叉树有( C)种。 A) 3B) 4C) 5D) 6 2002 年高中组( 18):在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的( B)倍。 A) 1/2 B) 1C) 2D) 4 2002 年高中组( 19) :要使 1... 8 号格字的访问顺序为: 8、 2、 6、 5、 7、 3、 1、 4 ,则下图中的空格中应填入( C)。 12345678 461 -1732 A) 6B) 0C) 5D) 3 2002 年高中组( 20):设栈 S和队列 Q 初始状态为空,元素 e1, e2, e3, e4, e5, e6依次通过栈 S ,一个元素出栈后即进入队列 Q ,若出队的顺序为 e2, e4, e3, e6, e5, e1 ,则栈 S 的容量至少应该为( B)。 A) 2B) 3C) 4D) 5 2001 年初中组( 19):在顺序表(2, 5, 7, 10, 14, 15, 18, 23, 35, 41, 52) 中, 用二分法查找 12,所需的关键码比较的次数为(C)。 A)2 B)3 C)4 D)5 2001 年初中组( 20):若已知一个栈的入栈顺序是 1, 2, 3, …, n,其输出序列为 P1 , P2 , P3 , …, Pn , 若 P1是 n,则 Pi是(C)。 A)i B)n-1 C)n-i+1 D) 不确定 2001 年高中组( 17):以下哪一个不是栈的基本运算(B)。 A) 删除栈顶元素 B)删除栈底的元素 C)判断栈是否为空 D) 将栈置为空栈 2001 年高中组( 19):一棵二叉树的高度为 h,所有结点的度为 0或 2,则此树最少有(B)个结点。 A)2h-1 B)2h-1 C)2h+1 D)h+1 2001 年高中组( 20):无向图 G=(V , E),其中 V={a,b,c,d,e,f} E={(a,b),(a,e),(a,c), (b,e),(c,f),(f,d),(e,d)} ,对该图进行深度优先遍历,得到的顶点序列正确的是(D)。 A)a,b,e,c,d,f B)a,c,f,e,b,d C)a,e,b,c,f,d D)a,b,e,d,f,c Ø 2-3 个计算机中数的表示(补码、反码等)和进制问题; 2002