奥赛基础知识部分补充试题.doc

《奥赛基础知识部分补充试题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、奥赛基础知识部分补充试题1、已知10个数据元素为（54，28，16，34，73，62，95，60，26，43），按依次插入结点的方法生成一棵二叉排序树后，查找值为62的结点所需用比较的次数为（　B），查找61的比较次数为（　）。A、2　B、3　C、4　D、52、设森林T中有三棵树，第一、二、三棵树的结点个数分别是n1，n2，n3，那么当把森林转换成二叉树后，其根结点的左子树上有（　）个结点，右子树上有（　）个结点。A、n1-1　B、n1　C、n1+n2　D、n2+n33、设有一个无向图G=(V,E)和G'=(V',E')，如果G'为G的生成树，则

2、下面不正确的说法是(D)　　A.G'为G的子图　　　　　　　　　　B.G'为G的一个无环子图　　C.G'为G的极小连通子图且V'=V　　　D.G'为G的连通分量4、在一棵有n个结点的完全二叉树中，对这些结点按层序编号，若一个结点编号为59，则其双亲编号为 （），若一个结点编号为23，则其有右孩子的条件是__5、具有N个结点的连通图的生成树有（        ）。A．N个结点，N条边                 B．N-1个结点，N-1条边  C．N-1个结点，N条边               D．N个结点，N-1条边6、欧拉图G是指可以构成

3、一个闭回路的图，且图G的每一条边恰好在这个闭回路上出现一次（即一笔画成）。在以下各个描述中,不一定是欧拉图的是：（）。A.图G中没有度为奇数的顶点B.包括欧拉环游的图(欧拉环游是指通过图中每边恰好一次的闭路径)C.包括欧拉闭迹的图(欧拉迹是指通过途中每边恰好一次的路径)D.存在一条回路,通过每个顶点恰好一次E.本身为闭迹的图7、堆是一个键值序列{K1,K2,...,Ki,...,Kn},对i=1,2,...,└n/2┘，满足(　A　)　　A.Ki<=K2i且Ki<=K2i+1(2i+1<=n)　　B.Ki

4、或Ki<=K2i+1(2i+1<=n)　D.Ki<=K2i<=K2i+18、假定查找有序表A[1..10]中每个元素的概率相等，则进行顺序查找时的平均查找长度为　　　，进行二分查找时的平均查找长度为　　　　。9、下面概念中，不属于面向对象方法的是（D）A）对象B）继承C）类D）过程调用10、以下数据结构中不属于线性数据结构的是（C）A）队列B）线性表C）二叉树D）栈11、下列关于列队的叙述中正确的是（C）A）在列队中只能插入数据B）在列队中只能删除数据C）列队是先进先出的线性表C）列队是先进后出的线性表12、在数据结构中，从逻辑上可以把数据结构分

5、成（B）A）动态结构和静态结构B）线性结构和非线性结构C）集合结构和非集合结构D）树状结构和图状结构13、设有两个串t和p，求p在t中首次出现的位置的运算叫做（    B    ）。 A   求子串  B  模式匹配     C   串替换     D 串连接14．下列哪一个不属于算法的设计目标（        ）。A．可读性     B．可执行性      C．健壮性    D．高空间效率15、在循环队列中（少用一个存储空间），队满的条件是（      ）A．（rear+1）%maxsize==front          B．raer==fr

6、ontC．（front+1）%maxsize==rear          D．rear==016、能采用二分查找的数据结构是（       ）A .线性表     B. 二叉树      C. 有序表    D . 哈希表17、NOIP竞赛推荐使用的语言环境: Dev-C++ 、 Lazarus  、 gcc/g++ 3.2.2版；、 free pascal、gdb 6.318、高度为n的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为n-1的满二叉树。在这里，树高等于叶结点的最大深度，根结点的深度为0，如果某个均衡的二叉树共有23

7、81个结点，则该树的树高为（）。A.10B.11C.12D.13E.210–119、与十进制数28.5625相等的四进制数是（）A．123.21B．131.22C．130.22D．130.21E．130.2020．在Pascal语言中，表达式(23or2xor5)的值是（）A.18B.1C.23D.32E.24二、不定项选择题1、若A=True，B=False，C=True，D=False，以下逻辑运算表达式真的有（）。A．（A∧B）V（C∧DV¬A）B．（（¬A∧B）VC）∧¬BC．（BVCVD）VD∧AD．A∧（DV¬C）∧B2、已知7个节点

8、的二叉树的先根遍历是1245637(数字为结点的编号，以下同)，后根遍历是4652731，则该二叉树的可能的中根遍历是（）A.42651