资源描述：
《noip初赛复习知识点》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、六、数据结构与算法例题一个高度为h的二叉树最小元素数目是（ B ）。 A）2h+1 B）h C）2h-1 D）2h E）2h-1一个向量第一个元素的存储地址是100,每个元素的长度是2,则第5个元素的地址是(B)。A)110B)108C)100D)109设有一个含有13个元素的Hash表(0~12),Hash函数是:H(key)=key%13,其中%是求余数运算。用线性探查法解决冲突,则对于序列(2、８、31、20、19、18、53、27),18应放在第几号格中(B)。
2、A)5B)9C)4D)0按照二叉树的定义,具有3个结点的二叉树有(C)种。A)3B)4C)5D)6在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的(B)倍。A)1/2B)1C)2D)4要使1...8号格子的访问顺序为:8、2、6、5、7、3、1、4,则下图中的空格中应填入(C)。12345678461-1732A)6B)OC)5D)3设栈S和队列Q的初始状态为空,元素e1,e2,e3,e4,e5,e6依次通过栈S,一个元素出栈后即进入队列Q,若出队的顺序为e2,e4,e3,e6,e5,e1,则栈S的容量至少应该为(B
3、)。 A)2B)3C)4D)5设有一棵k叉树,其中只有度为0和k两种结点,设n0,nk分别表示度为0和度为k的结点个数,试求出n0,nk之间的关系(n0=数学表达式,数学表达式仅含nk,k和数字)N0=(K－1)Nk+1若已知一个栈的入栈顺序是1，2，3，…，n，其输出序列为P1，P2，P3，…，Pn，若P1是n，则Pi是(C) A)i B)n-1 C)n-i+1 D)不确定以下哪一个不是栈的基本运算(B) A)删除栈顶元素 B)删除栈底的元素 C)判断栈是否为空D)将栈置为空栈下面关于算法的错误说法是(B) A)算法必须有
4、输出 B)算法必须在计算机上用某种语言实现 C)算法不一定有输入D)算法必须在有限步执行后能结束在顺序表(2，5，7，10，14，15，18，23，35，41，52)中，用二分法查找12，所需的关键码比较的次数为(C) A)2 B)3 C)4 D)5一棵二叉树的高度为h，所有结点的度为0，或为2，则此树最少有(B)个结点 A)2h-1 B)2h-1 C)2h+1 D)h+1无向图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)}对该图进行
5、深度优先遍历,得到的顶点序列正确的是(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已知一棵二叉树的结点名为大写英文字母，其中序与后序遍历的顺序分别为：CBGEAFHDIJ与CGEBHFJIDA则该 二叉树的先序遍历的顺序为：ABCEGDFHIJ在有N个叶子节点的哈夫曼树中，其节点总数为（ B ）A.不确定 B.2N-1 C.2N+1 D.2N某数列有1000个各不相同的单元，由低至高按序排列；现要对该数列进行二分法检索（binary-search），在
6、最坏的情况下，需检视（ B ）个单元。A.1000 B.10 C.100 D.500线性表若采用链表存贮结构，要求内存中可用存贮单元地址（ D ）A.必须连续 B.部分地址必须连续 C.一定不连续 D.连续不连续均可下列叙述中，正确的是（ D ）A.线性表的线性存贮结构优于链表存贮结构 B.队列的操作方式是先进后出C.栈的操作方式是先进先出 D.二维数组是指它的每个数据元素为一个线性表的线性表已知，按中序遍历二叉树的结果为：abc问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。
7、5种 设有一个共有n级的楼梯，某人每步可走1级，也可走2级，也可走3级，用递推公式给出某人从底层开始走完全部楼梯的走法。例如：当n=3时，共有4种走法，即1+1+1，1+2，2+1，3。F(n)=f(n-1)+f(n-2)+f(n-3),n>=4;F(1)=1;f(2)=2;f(3)=4;在磁盘的目录结构中，我们将与某个子目录有关联的目录数称为度．例如下图：该图表达了A盘的目录结构：DI，Dll，……D2均表示子目录的名字.在这里，根目录的度为2，D1子目录的度为3，D11子目录的度为4，D12，D2，D111，D112，D1
8、13的度均为1。又不考虑子目录的名字，则可简单的图示为如下的树结构： 若知道一个磁盘的目录结构中，度为2的子目录有2个，度为3的子目录有1个，度为4的子目录有3个。试问：度为1的子目录有几个？2*2+3*1+4*3+1*x=(2+1+3+x-1)*2根据Nocomachns定
