国家二级ACCESS机试选择题（数据结构与算法）模拟试卷15
选择题
1.设循环队列为Q(1：m)，其初始状态为front=rear=m。经过一系列入队与退队运算后，front=15，rear=20。现要在该循环队列中寻找最大值的元素，最坏情况下需要比较的次数为(A)
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.下列叙述中正确的是(D)
A. 循环队列属于队列的链式存储结构
B. 双向链表是二叉树的链式存储结构
C. 非线性结构只能采用链式存储结构
D. 有的非线性结构也可以采用顺序存储结构
解析：顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构。例如，完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。
3.某二叉树中有n个叶子结点，则该二叉树中度为2l的结点数为(B)
A. n+1
B. n-1
C. 2n
D. n／2
解析：任意一棵二叉树，如果叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；N2=N0-1。所以如果二叉树中有n个叶子结点，则该二叉树中度为2的结点数为n-1。因此选项B正确。
4.下列叙述中错误的是(C)
A. 算法的时间复杂度与算法所处理数据的存储结构有直接关系
B. 算法的空间复杂度与算法所处理数据的存储结构有直接关系
C. 算法的时间复杂度与空间复杂度有直接关系
D. 算法的时间复杂度与空间复杂度没有必然的联系
解析：算法的时间复杂度，是指执行算法所需要的计算工作量。算法的空间复杂度，是指执行这个算法所需要的内存空间。两者与算法所处理数据的存储结构都有直接关系，但两者之间没有直接关系，因此选项C错误。
5.设栈的顺序存储空间为S(0：49)，栈底指针bottom=49，栈顶指针top=30(指向栈顶元素)。则栈中的元素个数为(C)
A. 30
B. 29
C. 20
D. 19
解析：在操作系统中，栈是向下生长的，如下图如示：
6.某二叉树的前序序列为：ABCDEFG，中序序列为：DCBAEFG，则该二叉树的深度(根结点在第1层)为(C)
A. 2
B. 3
C. 4
D. 5
解析：该二叉树的前序序列为ABCDEFG，中序序列为DCBAEFG，可知A为根结点，结点B、C、D位于根结点的左子树上，结点E、F、G位于根结点的右子树上；并且结点B、C、D在前序序列和中序序列中顺序颠倒，则说明这三个结点依次位于前一个结点的左子树上；结点E、F、G顺序未变，则说明这三个结点依次位于前一个结点的右子树上。所以得到的二叉树为：
7.下列叙述中正确的是(D)
A. 存储空间连续的数据结构一定是线性结构
B. 存储空间不连续的数据结构一定是非线性结构
C. 没有根结点的非空数据结构一定是线性结构
D. 具有两个根结点的数据结构一定是非线性结构
解析：数据结构从逻辑上来划分，分为线性结构和非线性结构，一对一是线性结构，其它的为非线性结构。判断一个非空的数据结构是否为线性结构必须满足以下两个条件：①有且只有一个根结点；②每一个结点最多有一个前件，也最多有一个后件。根据这两个条件，可知选项A)、B)和C)都不能判定是否是线性结构。
8.下列叙述中正确的是(C)
A. 带链队列的存储空间可以不连续，但队头指针必须大于队尾指针
B. 带链队列的存储空间可以不连续，但队头指针必须小于队尾指针
C. 带链队列的存储空间可以不连续，且队头指针可以大于也可以小于队尾指针
D. 以上三项都错误
解析：带链队列的存储空间可以不连续，且队头指针与队尾指针大小没有可比性，选项C正确。
9.设循环队列为Q(1：m)，其初始状态为front=rear=m。经过一系列入队与退队运算后，front=20，rear=15。现要在该循环队列中寻找最小值的元素，最坏情况下需要比较的次数为(D)
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，则该二叉树的后序序列为(D)
A. EFGDCBA
B. DCBEFGA
C. BCDCGFEA
D. DCBGFEA
解析：该二叉树的前序序列为ABCDEFG，中序序列为DCBAEFG，可知A为根结点，结点B、C、D位于根结点的左子树上，结点E、F、G位于根结点的右子树上；并且结点B、C、D在前序序列和中序序列中顺序颠倒，则说明这三个结点依次位于前一个结点的左子树上；结点E、F、G顺序未变，则说明这三个结点依次位于前一个结点的右子树上。根据以上分析，可以画出这个二叉树的形状如下：
11.下列叙述中正确的是(B)
A. 在链表中，如果每个结点有两个指针域，则该链表一定是非线性结构
B. 在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是非线性结构
C. 在链表中，如果每个结点有两个指针域，则该链表一定是线性结构
D. 在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是线性结构
解析：选项A叙述是错误的，如在双向链表中，每个结点有两个指针域，但该链表是线性结构；选项C叙述也是错误的，如每个二叉树的结点都有两个指针域，但是其结构是非线性结构；选项D叙述也是错误的，线性结构只有唯一的一个前驱和唯一的一个后继(头、尾除外)；排除法可判断选项B正确。
12.下列叙述中错误的是(B)
A. 在带链队列中，队头指针和队尾指针都是在动态变化的
B. 在带链栈中，栈顶指针和栈底指针都是在动态变化的
C. 在带链栈中，栈顶指针是在动态变化的曼．但栈底指针是不变的
D. 以上三项都错误
解析：栈是只在一端进行增加和删除的线性表，进行操作的那端称为栈顶，另一端称为栈底。所以在带链栈中，栈顶指针是在动态变化的，但栈底指针是不变的，选项C的说法正确，选项B的说法是错误的。队列是允许在队列的头和尾都可以进行操作的线性表，所以在带链队列中，
本文档预览：3600字符，共8971字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
