第8节 树

第二章 程序设计基础知识
本题库配套信息学奥赛一本通(初赛真题解析)第95页-第102页真题在线评测。
本套题目共33题,满分165分,配合书本学习,事半功倍。
需要下载错题集微信联系陈老师,微信QQ同号:208234。
*
您的姓名:
一、单项选择题(共26题,每题5分,共计130分;每题有且仅有一个正确选项)
*
1.已知一棵二叉树有10个节点,则其中至多有()个节点有2个子节点。
A.4
B.5
C.6
D.7
*
2.已知一棵二叉树有2013个节点,则其中至多有()个节点有2个子节点。
A.1006
B.1007
C.1023
D.1024
*
3.如果根结点的深度记为1,则一棵恰有2011个叶结点的二叉树的深度最少是()。
A. 10
B. 11
C. 12
D. 13
*
4.如果树根算第1层,那么一棵n层的二叉树最多有()个结点。
A.2^(n) - 1
B.2^(n)
C.2^(n) + 1
D.2^(n+1)
*
5.一个包含n个分支结点(非叶结点)的非空二叉树,它的叶结点数目最多为():
A.2n + 1
B.2n-1
C.n-1
D.n+1
*
6.最优前缀编码,也称Huffman编码。这种编码组合的特点是对于较频繁使用的元素给与较短的唯一编码,以提高通讯的效率。下面编码组合哪一组不是合法的前缀编码()。
A.(00,01,10,11)
B.(0,1,00,11)
C.(0,10,110,111)
D.(1,01,000,001)
*
7.现有一段文言文,要通过二进制哈夫曼编码进行压缩。简单起见,假设这段文言文只由4个汉字“之”、“乎”、“者”、“也”组成,它们出现的次数分别为700、600、300、200。那么,“也”字的编码长度是()。
A. 1
B. 2
C. 3
D. 4
*
8.一棵二叉树如右图所示,若采用顺序存储结构,即用一维数组元素存储该二叉树中的结点(根结点的下标为1,若某结点的下标为i ,则其左孩子位于下标2i 处、右孩子位于下标(2i+1)处),则图中所有结点的最大下标为()。
A. 6
B. 10
C. 12
D. 15
*
9.一棵二叉树如右图所示,若采用二叉树链表存储该二叉树(各个结点包括结点的数据、左孩子指针、右孩子指针)。如果没有左孩子或者右孩子,则对应的为空指针。那么该链表中空指针的数目为()。
A. 6
B. 7
C. 12
D. 14
*
10.完全二叉树的顺序存储方案,是指将完全二叉树的结点从上至下、从左至右依次存放到一个顺序结构的数组中。假定根结点存放在数组的1号位置,则第k号结点的父结点如果存在的话,应当存放在数组的()号位置。
A.2k
B.2k+1
C.k/2下取整
D.(k+1)/2下取整
*
11.完全二叉树共有2*N-1个结点,则它的叶节点数是()。
A. N-1
B. N
C. 2*N
D. 2N-1
*
12.一个包含n个分支结点(非叶结点)的非空满k叉树,k>=1,它的叶结点数目为():
A) nk + 1
B) nk-1
C) (k+1)n-1
D. (k-1)n+1
*
13.如果根的高度为1,具有61个结点的完全二叉树的高度为()。
A.5
B.6
C.7
D.8
*
14.一棵具有5层的满二叉树中结点数为()。
A.31
B.32
C.33
D.16
*
15.根节点深度为 0,一棵深度为 h 的满 k(k>1)叉树,即除最后一层无任何子节点外,每一层上的所有结点都有 k 个子结点的树,共有()个结点。
A.(k^(h+1)-1)/(k-1)
B.k^(h-1)
C.k^h
D.k^(h-1)/(k-1)
*
16.二叉树的()第一个访问的节点是根节点。
A.先序遍历
B.中序遍历
C.后序遍历
D.以上都是
*
17.二叉查找树具有如下性质:每个节点的值都大于其左子树上所有节点的值、小于其右子树上所有节点的值。那么,二叉查找树的()是一个有序序列。
A.先序遍历
B.中序遍历
C.后序遍历
D.宽度优先遍历
*
18.前序遍历序列与中序遍历序列相同的二叉树为()
A.根结点无左子树的二叉树
B.根结点无右子树的二叉树
C.只有根结点的二叉树或非叶子结点只有左子树的二叉树
D.只有根结点的二叉树或非叶子结点只有右子树的二叉树
*
19.前序遍历序列与后序遍历序列相同的二叉树为()。
A.非叶子结点只有左子树的二叉树
B.只有根结点的二叉树
C.根结点无右子树的二叉树
D.非叶子结点只有右子树的二叉树
*
20.右图是一棵二叉树,它的先序遍历是()。
A. ABDEFC
B. DBEFAC
C. DFEBCA
D. ABCDEF
*
21.如果一棵二叉树的中序遍历是 BAC ,那么它的先序遍历 不可能 是()。
A.ABC
B.CBA
C.ACB
D.BAC
*
22.表达式a*(b+c)-d 的后缀表达形式为()。
A. abcd*+-
B. abc+*d-
C. abc*+d-
D. -+*abcd
*
23.表达式a * d - b * c 的前缀形式是()。
A. a d * b c * -
B. - * a d * b c
C. a * d - b * c
D. - * * a d b c
*
24.前缀表达式 + 3 * 2 + 5 12 的值是()。
A. 23
B. 25
C. 37
D. 65
*
25.二叉树T,已知其先根遍历是1 2 4 3 5 7 6(数字为结点的编号,以下同),中根遍历是2 4 1 5 7 3 6,则该二叉树的后根遍历是()。
A. 4 2 5 7 6 3 1
B. 4 2 7 5 6 3 1
C. 7 4 2 5 6 3 1
D. 4 2 7 6 5 3 1
*
26.一棵二叉树的前序遍历序列是 ABCDEFG,后序遍历序列是 CBFEGDA,则根结点的左子树的结点个数可能是()。
A. 2
B. 3
C. 4
D. 5
二、不定项选择题(共7题,每题5分,共计35分;每题有一个或多个正确选项,多选或少选均不得分)
*
1.设T是一棵有n个顶点的树,下列说法正确的是()。【多选题】
A. T是连通的、无环的
B. T是连通的,有n-1条边
C. T是无环的,有n-1条边
D. 以上都不对
*
2.下列说法中,是树的性质的有()。【多选题】
A. 无环
B. 任意两个结点之间有且只有一条简单路径
C. 有且只有一个简单环
D. 边的数目恰是顶点数目减1
*
3.下列有关树的叙述中,叙述正确的有()。【多选题】
A.在含有n个结点的树中,边数只能是(n-1)条
B.在哈夫曼树中,叶结点的个数比非叶结点个数多1
C.完全二叉树一定是满二叉树
D.在二叉树的前序序列中,若结点u在结点v之前,则u一定是v的祖先
*
4.二叉树T,已知其先根遍历是1 2 4 3 5 7 6(数字为结点的编号,以下同),后根遍历是4 2 7 5 6 3 1,则该二叉树的可能的中根遍历是()。【多选题】
A. 4 2 1 7 5 3 6
B. 2 4 1 7 5 3 6
C. 4 2 1 7 5 6 3
D. 2 4 1 5 7 3 6
*
5..如果根结点的深度记为1,则一棵恰有2011个叶子结点的二叉树的深度可能是()。【多选题】
A. 10
B. 11
C. 12
D. 2011
*
6.一棵二叉树一共有19个节点,其叶子节点可能有()个。【多选题】
A.1
B.9
C.10
D.11
*
7.2-3 树是一种特殊的树,它满足两个条件:(1)每个内部结点有两个或三个子结点;(2)所有的叶结点到根的路径长度相同。如果一棵2-3 树有10 个叶结点,那么它可能有()个非叶结点。【多选题】
A. 5
B. 6
C. 7
D. 8
问卷星提供技术支持
举报