NOIP提高组初赛试题汇编(2002-2009)(2)

NOIP提高组初赛试题汇编(2002-2009)noip考试者必备我也是马上要考了!!!

16．设有一个含有13个元素的Hash表（0~12），Hash函数是：H（key）=key%13，，其

中%是求余数运算。用线性探查法解决冲突，则对于序列（2、8、31、20、19、18、53、27），18应放在第（）号格中。A）5B）9C）4D）0

17．按照二叉数的定义，具有3个结点的二叉树有（）种。

A）3B）4C）5D）6

18．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。

A）1/2B）1C）2D）419．要使1．．．8号格字的访问顺序为：8、2、6、5、7、3、1、4，则下图中的空格中应填

入（）。

12345678

4

6

1

-1

7

3

2

A）6B）0C）5D）3

20．设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5，e6依次通过栈S，

一个元素出栈后即进入队列Q，若出队的顺序为e2，e4，e3，e6，e5，e1，则栈S的容量至少应该为（）。A）2B）3C）4D）5问题求解：二．问题求解：（6+8=14分）1．在书架上放有编号为1，2，．．．，n的n本书。现将n本书全部取下然后再放回去，当

放回去时要求每本书都不能放在原来的位置上。例如：n=3时：

原来位置为：123

放回去时只能为：312或231这两种

问题：求当n=5时满足以上条件的放法共有多少种？（不用列出每种放法）

2．设有一棵k叉树，其中只有度为0和k两种结点，设n0，nk，分别表示度为0和度

试求出n0和nk之间的关系（n0=数学表达式，数学表达式仅含nk、为k的结点个数，

k和数字）。阅读程序，写出正确的程序运行结果：三．阅读程序，写出正确的程序运行结果：（8+9+9=26分）1．programGxp1;

vari,n,jr,jw,jb:integer;

ch1:char;ch:array[1..20]ofchar;begin

readln(n);

fori:=1tondoread(ch[i]);jr:=1;jw:=n;jb:=n;while(jr<=jw)dobegin

if(ch[jw]=’R’)thenbegin

ch1:=ch[jr];ch[jr]:=ch[jw];ch[jw]:=ch1;jr:=jr+1;end

elseifch[jw]=’W’

thenjw:=jw-1;elsebegin