国家二级ACCESS机试选择题(数据结构与算法)模拟试卷15
- 格式:doc
- 大小:36.48 KB
- 文档页数:7
国家二级ACCESS机试选择题(数据结构与算法)模拟试卷15
(总分:64.00,做题时间:90分钟)
一、选择题(总题数:32,分数:64.00)
1.设循环队列为Q(1:m),其初始状态为front=rear=m。经过一系列入队与退队运算后,front=15,rear=20。现要在该循环队列中寻找最大值的元素,最坏情况下需要比较的次数为
(分数:2.00)
A.4 √
B.6
C.m-5
D.m-6
解析:解析:初始状态为:front=rear=m,rear-front=0,此时队列为空。经过一系列入队与退队运算后,front=15,rear=20。队尾大于队头,则队尾rear减队头front等于5个元素。此时队列中有5个元素,而查找最大项至少要比较n.1次,就是4次。因此选项A正确。
2.下列叙述中正确的是
(分数:2.00)
A.循环队列属于队列的链式存储结构
B.双向链表是二叉树的链式存储结构
C.非线性结构只能采用链式存储结构
D.有的非线性结构也可以采用顺序存储结构√
解析:解析:顺序存储方式不仅能用于存储线性结构,还可以用来存放非线性结构。例如,完全二叉树是属于非线性结构,但其最佳存储方式是顺序存储方式。
3.某二叉树中有n个叶子结点,则该二叉树中度为2l的结点数为
(分数:2.00)
A.n+1
B.n-1 √
C.2n
D.n/2
解析:解析:任意一棵二叉树,如果叶结点数为N 0,而度数为2的结点总数为N 2,则N 0 =N 2 +1;N 2 =N 0 -1。所以如果二叉树中有n个叶子结点,则该二叉树中度为2的结点数为n-1。因此选项B正确。4.下列叙述中错误的是
(分数:2.00)
A.算法的时间复杂度与算法所处理数据的存储结构有直接关系
B.算法的空间复杂度与算法所处理数据的存储结构有直接关系
C.算法的时间复杂度与空间复杂度有直接关系√
D.算法的时间复杂度与空间复杂度没有必然的联系
解析:解析:算法的时间复杂度,是指执行算法所需要的计算工作量。算法的空间复杂度,是指执行这个算法所需要的内存空间。两者与算法所处理数据的存储结构都有直接关系,但两者之间没有直接关系,因此选项C错误。
5.设栈的顺序存储空间为S(0:49),栈底指针bottom=49,栈顶指针top=30(指向栈顶元素)。则栈中的元素个数为
(分数:2.00)
A.30
B.29
C.20 √
D.19
bottom=49,栈顶指针top=30时,栈中的元素个数为:栈底-栈顶+1=49-30+1=20。因此选项C正确。
6.某二叉树的前序序列为:ABCDEFG,中序序列为:DCBAEFG,则该二叉树的深度(根结点在第1层)为(分数:2.00)
A.2
B.3
C.4 √
D.5
解析:解析:该二叉树的前序序列为ABCDEFG,中序序列为DCBAEFG,可知A为根结点,结点B、C、D位于根结点的左子树上,结点E、F、G位于根结点的右子树上;并且结点B、C、D在前序序列和中序序列中顺序颠倒,则说明这三个结点依次位于前一个结点的左子树上;结点E、F、G顺序未变,则说明这三个结点
依次位于前一个结点的右子树上。所以得到的二叉树为:所以这个二叉树的深度为4。选项C为正确答案。
7.下列叙述中正确的是
(分数:2.00)
A.存储空间连续的数据结构一定是线性结构
B.存储空间不连续的数据结构一定是非线性结构
C.没有根结点的非空数据结构一定是线性结构
D.具有两个根结点的数据结构一定是非线性结构√
解析:解析:数据结构从逻辑上来划分,分为线性结构和非线性结构,一对一是线性结构,其它的为非线性结构。判断一个非空的数据结构是否为线性结构必须满足以下两个条件:①有且只有一个根结点;②每一个结点最多有一个前件,也最多有一个后件。根据这两个条件,可知选项A)、B)和C)都不能判定是否是线性结构。
8.下列叙述中正确的是
(分数:2.00)
A.带链队列的存储空间可以不连续,但队头指针必须大于队尾指针
B.带链队列的存储空间可以不连续,但队头指针必须小于队尾指针
C.带链队列的存储空间可以不连续,且队头指针可以大于也可以小于队尾指针√
D.以上三项都错误
解析:解析:带链队列的存储空间可以不连续,且队头指针与队尾指针大小没有可比性,选项C正确。9.设循环队列为Q(1:m),其初始状态为front=rear=m。经过一系列入队与退队运算后,front=20,rear=15。现要在该循环队列中寻找最小值的元素,最坏情况下需要比较的次数为
(分数:2.00)
A.5
B.6
C.m-5
D.m-6 √
解析:解析:在循环队列中元素的个数为“(rear-front+M)%M”,式中rear为队尾指针,front为队首指针,M为存储容量,%为取余符号。对于找最小值的最坏情况下的比较次数,为循环队列中元素值个数减一。所以对于这个题目来说初始时元素个数为0;运算后,元素个数为m-5,找最小值的最坏情况下的比较次数为m-5-1=m-6。
10.某二叉树的前序序列为ABCDEFG,中序序列为DCBAEFG,则该二叉树的后序序列为
(分数:2.00)
A.EFGDCBA
B.DCBEFGA
C.BCDCGFEA
D.DCBGFEA √