国家二级VB机试（公共基础知识）模拟试卷11
选择题
1.下列叙述中正确的是( )。 (B)
A. 算法的时间复杂度与计算机的运行速度有关
B. 算法的时间复杂度与运行算法时特定的输入有关
C. 算法的时间复杂度与算法程序中的语句条数成正比
D. 算法的时间复杂度与算法程序编制者的水平有关
解析：为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。为此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。算法所执行的基本运算次数还与问题的规模有关；对应一个固定的规模，算法所执行的基本运算次数还可能与特定的输入有关。
2.在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数( )。(C)
A. 不同，但元素的存储顺序与逻辑顺序一致
B. 不同，且其元素的存储顺序可以与逻辑顺序不一致
C. 相同，但元素的存储顺序与逻辑顺序一致
D. 相同，元素的存储顺序可以与逻辑顺序不一致
解析：在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数相同，在存储空间中是按逻辑顺序依次存放的。
3.设栈的存储空间为s(1：m)，初始状态为top=m+1。经过一系列入栈与退栈操作后，top=m。现又在栈中退出一个元素后，栈顶指针top值为( )。(C)
A. 0
B. m-1
C. m+1
D. 产生栈空错误
解析：栈的顺序存储空间为S(1：m)，初始状态top=m+1，所以这个栈是m在栈底(也可理解为开口向下的栈)。经过一系列入栈与退栈操作后top=m，则栈中有1个元素，若现在又退出一个元素，那么栈顶指针下移一位，回到m+1的位置。
4.设循环队列的存储空间为Q(1：m)，初始状态为空。现经过一系列正常的入队与退队操作后，front=m，rear=m-1，此后从该循环队列中删除一个元素，则队列中的元素个数为( )。(B)
A. m-1
B. m-2
C. 0
D. 1
解析：在循环队列中，如果rear-front＞0，则队列中的元素个数为rear-front个；如果rear-front＜0，则队列中的元素个数为rear-front+m。该题中m-1＜m，即rear-front＜0，则该循环队列中的元素个数为(m-1)-m+m=m-1。此后从该循环队列中删除一个元素，则队列中的元素个数为m-1-1=m-2。
5.下列叙述中正确的是( )。(A)
A. 带链栈的栈底指针是随栈的操作而动态变化的
B. 若带链队列的队头指针与队尾指针相同，则队列为空
C. 若带链队列的队头指针与队尾指针相同，则队列中至少有一个元素
D. 不管是顺序栈还是带链的栈，在操作过程中其栈底指针均是固定不变的
解析：由于带链栈利用的是计算机存储空间中的所有空闲存储结点，因此随栈的操作栈顶栈底指针动态变化。带链的队列中若只有一个元素，则头指针与尾指针相同。
6.下列叙述中错误的是( )。(B)
A. 循环链表中有一个表头结点
B. 循环链表是循环队列的存储结构
C. 循环链表的表头指针与循环链表中最后一个结点的指针均指向表头结点
D. 循环链表实现了空表与非空表运算的统一
解析：循环链表是指在单链表的第一个结点前增加一个表头绪点，队头指针指向表头结点，最后一个结点的指针域的值由NULL改为指向表头结点。循环链表是线性表的一种链式存储结构，循环队列是队列的一种顺序存储结构。
7.深度为5的完全二叉树的结点数不可能是( )。(A)
A. 15
B. 16
C. 17
D. 18
解析：设完全二叉树的结点数为n，根据深度为k的二叉树至多有2k-1个结点，再根据完全二叉树的定义可知，2k-1-1＜n≤2k-1。本题中完全二叉树的深度为5，则25-1-1＜n≤25-1，15＜n≤31。因此，结点数不能为15。
8.有二叉树如下图所示：
(A)
A. ABDEGCFH
B. DBGEAFHC
C. DGEBHFCA
D. ABCDEFGH
解析：前序遍历首先访问根结点，然后遍历左子树，最后遍历右子树；在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。故本题前序序列是ABDEGCFH。
中序遍历首先遍历左子树，然后访问跟结点，最后遍历右子树；在遍历左、右子树时，仍然先遍历左子树，然后访问跟结点，最后遍历右子树。故本题的中序序列是DBGEAFHC。
后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点；在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。故本题的后序序列是DGEBHFCA。
9.某完全二叉树按层次输出(同一层从左到右)的序列为ABCDEFGH。该完全二叉树的前序序列为( )。(B)
A. ABCDEFGH
B. ABDHECFG
C. HDBEAFCG
D. HDEBFGCA
解析：完全二叉树的特点是除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。根据这一特点，再根据题意输出序列为ABCDEFGH，可以得到该二叉树的结构如下：
10.在长度为n的顺序表中查找一个元素，假设需要查找的元素有一半的机会在表中，并且如果元素在表中，则出现在表中每个位置上的可能性是相同的。则在平均情况下需要比较的次数大约为( )。(B)
A. n
B. 3n／4
C. n／2
D. n／4
解析：在顺序表中查找，最好情况下第一个元素就是要查找的元素，则比较次数为1；在最坏情况下，最后一个元素才是要找的元素，则比较次数为n。这是找到元素的情况。如果没有找到元素，则要比较n次。因此，平均需要比较：找到元素的情况
，未找到元素的情况
11.在快速排序法中，每经过一次数据交换(或移动)后( )。(B)
A. 只能消除一个逆序
B. 能消除多个逆序
C. 不会产生新的逆序
D. 消除的逆序个数一定比新产生的逆序个数多
解析：在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。快速排序的思想是：从线性表中选取一个元素，设为T，将线性表中后面小于T的元素移到前面，而前面大于T的元素移到后面，结果就将线性表分成两部分(称两个子表)，T插入到其分割线
本文档预览：3600字符，共9072字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
