国家二级ACCESS机试（选择题）模拟试卷112
选择题
1.某二叉树共有7个节点，其中叶子节点只有1个，则该二叉树的深度为(假设根节点在第1层)( )。(D)
A. 3
B. 4
C. 6
D. 7
解析：根据二叉树的性质，度为0的节点(叶子节点)总是比度为2的节点多一个。题目中的二叉树的叶子节点为1．因此度为2的节点的数目为0。故该二叉树为7层，每层只有一个节点。
2.某二叉树共有l2个节点，其中叶子节点只有1个。则该二叉树的深度为(假设根节点在第1层)( )。(D)
A. 3
B. 6
C. 8
D. 12
解析：根据二叉树的性质，度为0的节点(叶子节点)总是比度为2的节点多一个。题目中的二叉树的叶子节点为1，因此度为2的节点的数目为0。故该二叉树为12层，每层只有一个节点。
3.设树T的深度为4，其中度为1，2，3，4的节点个数分别为4，2，l，lo则T中的叶子节点数为( )。(A)
A. 8
B. 7
C. 6
D. 5
解析：在一棵树中，节点总数=总分支数目+1，n0+4+2+1+1=( n0xO+lx4+2×2+3 x1+4xl )+1，则n0=8，其中n0表示叶子节点。
4.设一棵完全二叉树共有700个节点，则此二叉树中的叶子节点数为( )。(D)
A. 85
B. 120
C. 250
D. 350
解析：(1)具有n个节点的完全二叉树的深度为[log2n,] +1，计算出该完全二叉树的深度为10。
(2)设度为0的节点(叶子节点)为n0，度为1的节点为n1，度为2的节点为n2，总节点数为n，深度为k。n,=n1+n2+n0，由于n0=n2+1则n2=n0—1，故n=n1+n0—1+n0=n1+2n0一1。由于完全二叉树中度为1的节点数只有两种可能：0或1。
(3)假设度为1的节点数为0即满二叉树，根据满二叉树的定义，其2m一1个节点，根据以上计算所得的深度10来计算，应有210—1=1024—1=1023个节点，显然与题目中700个节点不符。因此，度为1的节点数必然为1。故n=n1+2n0—1=1+2n0—1=2n0，则n0=n/2=700/2=350．
5.在深度为7的满二叉树中，叶子节点的个数为( )。(C)
A. 32
B. 31
C. 64
D. 63
解析：所谓满二叉树是指这样的一种二叉树：除最后一层外，每一层上的所有节点都有两个子节点。也就是在满二叉树中，每一层上的节点数都是最大节点数，即在满二叉树的第k层上有2k—1个节点，深度为m的满二叉树有2m—1个节点。对于深度为7的满二叉树，叶子节点所在的是第7层，一共有27—1=64个叶子节点。全部节点共27—1=127个。
6.下列叙述中正确的是( )。(A)
A. 循环队列中的元素个数随队头指针与队尾指针的变化而动态变化
B. 循环队列中的元素个数随队头指针的变化而动态变化
C. 循环队列中的元素个数随队尾指针的变化而动态变化
D. 循环队列中的元素个数不会变化
解析：所谓循环结构就是将队列存储空间的最后一个位置绕到第一个位置上，形成逻辑上的环状空间，循环使用。在循环队列中，用队尾指针rear指向队列中的队尾元素，用队头指针front指向队头元素的前一个位置，因此，队列中的元素数等于从队头指针front指向的后一个位置与队尾指针rear指向位置之间的元素数量。
7.下列关于线性链表的叙述中，正确的是( )。(C)
A. 各数据节点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致
B. 各数据节点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续
C. 进行插入与删除时，不需要移动表中的元素
D. 以上都不正确
解析：线性表的链式存储结构称为线性链表。在链式存储结构中，存储数据结构的存储空间可以不连续，各数据节点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。
8.下列叙述中正确的是( )。(C)
A. 线性表链式存储结构的存储空间一般要少于顺序存储结构
B. 线性表链式存储结构与顺序存储结构的存储空间都是连续的
C. 线性表链式存储结构的存储空间可以是连续的，也可以是不连续的
D. 以上都不正确
解析：线性表的存储分为顺序存储和链式存储。在顺序存储中，所有元素所占的存储空间是连续的。而在链式存储的方式中，将存储空间的每一个存储节点分为两部分：一部分用于存储数据元素的值，称为数据域；另一部分用于存储下一个元素的存储序号，称为指针域。所以线性表的链式存储方式比顺序存储方式的存储空间要大一些。
9.下列叙述中正确的是( )。(B)
A. 线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的
B. 线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构
C. 线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构
D. 以上都不正确
解析：线性表的存储分为顺序存储和链式存储。在顺序存储中，所有元素所占的存储空间是连续的。而在链式存储的方式中，将存储空间的每一个存储节点分为两部分：一部分用于存储数据元素的值，称为数据域；另一部分用于存储下一个元素的存储序号，称为指针域。所以线性表的链式存储方式比顺序存储方式的存储空间要大一些。
10.下列对于线性链表的描述中正确的是( )。(A)
A. 存储空间不一定连续，且各元素的存储顺序是任意的
B. 存储空间不一定连续，且前件元素一定存储在后件元素的前面
C. 存储空间必须连续，且前件元素一定存储在后件元素的前面
D. 存储空间必须连续，且各元素的存储顺序是任意的
解析：一般来说，在线性表的链式存储结构中各数据节点的存储序号是不连续的，并且各节点在存储空间中的位置关系与逻辑关系也不一致。在线性链表中，各数据元素之间的前后件关系是由各节点的指针域来指示的。指向线性表中第一个节点的指针head称为头指针，当head=NULL(或0)时称为空表。
11.算法的有穷性是指( )。(A)
A. 算法程序的运行时间是有限的
B. 算法程序所处理的数据量是有限的
C. 算法程序的长度是有限的
D. 算法只能被有限的用户使用
解析：算法的有穷性是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。
12.下列叙述中正确的是( )。(D)
A. 算法就是程序
B. 设计算法时只需要考虑数据结构的设计
C. 设计算法时
本文档预览：3600字符，共8601字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
