国家二级ACCESS机试选择题（数据结构与算法）模拟试卷23
选择题
1.某二叉树的中序遍历序列为CBADE，后序遍历序列为CBADE，则前序遍历序列为(A)
A. EDABC
B. CBEDA
C. CBADE
D. EDCBA
解析：后序遍历次序是“左右根”，中序遍历次序是“左根右”。
由定义可知：①后序遍历中最后一个就是树根结点，即E结点；②在中序遍历中，根结点左边的是左子树集，右边的是右子树集，即CBAD是根结点E的左子树集合。问题就会转化为：求后序遍历是CBAD，中序遍历是CBAD的子树，方法同上。因为中序遍历中，D结点右边没有结点了，所以D结点不包含右子树，否则就会被分为2个子问题
以下是这道题的详细推理过程：步骤1：由CBADE得出根结点为E，由中序遍历可知{CBAD}E，右子树为空；步骤2：由CBAD得出左子树集合的根节点为D，由中序可知{CBA}D，右子树为空；步骤3：同理，二叉树更新后如下图所示。
2.下列叙述中正确的是(A)
A. 在循环队列中，队头指针和队尾指针的动态变化决定队列的长度
B. 在循环队列中，队尾指针的动态变化决定队列的长度
C. 在带链的队列中，队头指针与队尾指针的动态变化决定队列的长度
D. 在带链的栈中，栈顶指针的动态变化决定栈中元素的个数
解析：循环队列是将顺序队列首尾相连形成的，随着插入元素或删除元素的进行，其队头指针及队尾指针是在不断变化的，有时可能会出现队头指针大于队尾指针的情况，也可能是队尾指针大于队头指针。循环队列中计算元素的个数公式为：(rear-front+queuc_size)％queue_size。所以选项A正确。
3.设栈的存储空间为S(1：60)，初始状态为top=61。现经过一系列正常的入栈与退栈操作后，top=1，则栈中的元素个数为(A)
A. 60
B. 59
C. 0
D. 1
解析：栈是向上增长的，每次压入一个元素，栈的TOP指针向上移动一位，即top-1。当压入第一个元素时，TOP指针指向60+1-1=60；当压入第二个元素时，TOP指针指向60+1-2=59；……；以此类推，当压入第N个元素时，TOP指针指向60+1-N=1，则N=60。所以选项A正确。
4.设顺序表的长度为n。下列排序方法中，最坏情况下比较次数小于n(n-1)／2的是(A)
A. 堆排序
B. 快速排序
C. 简单插入排序
D. 冒泡排序
解析：假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n／2遍的从前往后扫描和n／2遍的从后往前扫描，需要比较次数为n(n-1)／2。快速排序法的最坏情况比较次数也是n(n-1)／2。简单插入排序，无论是否最坏都需要n(n-1)／2比较。堆排序，无论是否最坏都需要比较O(nlog2n)次。
5.在长度为n的顺序表中查找一个元素，假设需要查找的元素有一半的机会在表中，并且如果元素在表中，则出现在表中每个位置上的可能性是相同的。则在平均情况下需要比较的次数大约为(A)
A. (3+n)／4
B. n
C. n／2
D. n／4
解析：在长度为n的顺序表中查找一个元素，最好的情况是目标在第一个，一次找到；最坏的情况是目标在最后一个，n次找到。那么平均长度为：(1+2+…+n)／n=(n(n+1)／2)／n=(n+1)／2。本题需要查找的元素有一半的机会在表中，则在平均情况下需要比较的次数大约为((1+n)／2+1)／2=(3+n)／4。
6.设一棵树的度为3，其中度为3，2，1的结点个数分别为4，1，3。则该棵树中的叶子结点数为(A)
A. 10
B. 11
C. 12
D. 不可能有这样的树
解析：因为任一棵树中，结点总数=总分支数目+1，所以：n0+4+1+3=(n0*0+3*4+2*1+1*3)+1，计算结果n0=10。其中，n0表示叶子结点。所以选项A正确。
7.设栈的存储空间为S(1：50)，初始状态为top=0。现经过一系列正常的入栈与退栈操作后，top=51，则栈中的元素个数为(A)
A. 不可能
B. 50
C. 0
D. 1
解析：栈是向上增长的，每次压入一个元素，栈的。TOP指针向上移动一位，即top-1。对于这个题目，由于top初始值等于0，此时入栈一个元素，top值减1，即0-1=-1，发生下溢错误。
8.设顺序表的长度为n。下列算法中，最坏情况下比较次数等于n(n-1)／2的是(A)
A. 快速排序
B. 堆排序
C. 顺序查找
D. 寻找最大项
解析：假设线性表的长度为n，则在最坏情况下，快速排序法的最坏情况比较次数也是n(n-1)／2；堆排序，无论是否最坏都是比较O(nlog2n)次，所以选项A正确。
9.设表的长度为n。下列算法中，最坏情况下比较次数小于n的是(A)
A. 二分查找法
B. 堆排序
C. 快速排序
D. 顺序查找法
解析：二分法查找只适用于顺序存储的有序表。二分查找的基本方法是：将被查元素x与线性表的中间项进行比较，若中间项的值等于x，则说明查到；若小于中间项的值则在线性表的前半部分；以相同的方法进行查找；若大于中间项的值，则在线性表的后半部分以相同的方法进行查找。在最坏情况下，二分查找需要比较log2n次。所以选项A正确。
10.下列叙述中错误的是(A)
A. 循环链表是循环队列的存储结构
B. 二叉链表是二叉树的存储结构
C. 栈是线性结构
D. 循环队列是队列的存储结构
解析：循环队列属于逻辑结构，其实质还是顺序存储，只是使用指针进行首尾的联结，其实现的存储方式可分为：分散的链表和连续的线性表，与其逻辑结构实现功能无关。所以选项A正确。
11.设一棵树的度为4，其中度为4，3，2，1的结点个数分别为2，3，3，0。则该棵树中的叶子结点数为(A)
A. 16
B. 15
C. 17
D. 不可能有这样的树
解析：因为任一棵树中，结点总数=总分支数目+1，所以：n0+2+3+3+0=(n0*0+4*2+3*3+2*3+1*0)+1。计算得出n0=16。其中，n0表示叶子结点，所以选项A正确。
12.循环队列的存储空间为Q(1：100)，初始状态为front=rear=100。经过一系列正常的入队与退队操作后，front=rear=99，则循环队列中的元素个数为(A)
A. 0或100
B. 1
C. 2
D. 99
解析：循环队列中，由于入队时尾指针rear。向前追赶头指针front；出队时头指针front向前追赶尾指针rear，造成队空和队满时头尾指针均相等。因此，无法通过条件front=rear来判别队列是“空”还是“满”。对于这个题目来说，经过一系列正常的入队与退队操作后，front=rear=99，此时，要么队列为空(元素个数为0)，要么队列为满(元素个数为100)，因此选项A正确。
13.设顺序表的长度为n。
本文档预览：3600字符，共7955字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
