程序和数据
【答案】B。长度为1的子串有7个，长度为2的子串有6个，……，长度为7的子串有1个，所有非空子串数目是：765432128。4．完全二叉树有2N1的结点，则它的叶子结点数目是（A．N1B．2NC．N）。D．2N1E．N2
【答案】C。设二叉树中度为0的结点叶子有N0个，度为1的结点有N1个，度为2的结点有N2个，所有结点个数：N0＋N1＋N2，所有的边数：N00N11N22N12N2。由于每个结点上都有一条边，除根结点外，所以有N0N1N2N12N21→N0N21…………①完全二叉树有2N1个结点（奇数个），而完全二叉树的上一层是一棵满二叉树，而满二叉树的结点个数是2k1（k是层数，是奇数个），所以此二叉树最下一层是偶数个结点，这样的二叉树没有度为1的结点，即N10，得到N0N22N1→N22NN01…………②
27
f马鞍山二中
NOIP20062008初赛（提高组）试题＆解析
将②式代入①式，得到N0N。5．将数组8，23，4，16，77，5，53，100中元素从大到小按顺序排序，每次可以交换任意两个元素，最少要交换（A．4【答案】B。第1次：8与100换；得到：10023416775538第2次：23与77换，得到：10077416235538第3次：4与53换，得到：10077531623548第4次：16与23换，得到：10077532316548第5次：5与8换，得到：100775323168456．设栈S的初始状态为空，元素a，b，c，d，e，f依次入栈，出栈顺序为b，d，c，f，e，a那么栈容量至少应该是（A．6B．5）。C．4D．3E．2B．5）次。C．6D．7E．8
【答案】D。栈基本操作。7．与十进制数285625相等的四进制数是（A．12321B．13122）D．13021E．13020
C．13022
【答案】D。进制转换的基础知识。8．递归过程和函数调用时，处理参数和返回地址，通常使用一种称为（A．队列【答案】E。9．TCPIP是一组构成互联网基础的网络协议，字面上包括两组协议：传输控制协议（TCP）和网际互联协议（IP）。TCPIP协议把I
ter
et网络系统描述成具有4个层次功能的网络模型，其中提供源节点和目的节点之间的信息传输服务，包括寻址和路由器选择等功能的是。（）A．链路层【答案】B。10．对有序数组5131921375664758892100进行二分查找，等概率情况下，查找成功的平均查找长度（平均比较次数）是（）。A．3511B．3411C．3311D．3211E．3410B．网络层C．传输层D．应用层E．会话层B．多维数组C．线性表D．链表）的数据结构。E．栈
【答案】C。根据二分查找的特点，可以构造以下二叉树：
28
f马鞍山二中
NOIP20062008初赛（提高组r