1、国家二级 VB机试（公共基础知识）模拟试卷 1及答案与解析 一、选择题 1 下列叙述中正确的是 ( )。 （ A）所谓算法就是计算方法 （ B）程序可以作为算法的一种描述方法 （ C）算法设计只需考虑得到计算结果 （ D）算法设计可以忽略算法的运算时间 2 下列叙述中正确的是 ( )。 （ A）算法的复杂度包括时间复杂度与空间复杂度 （ B）算法的复杂度是指算法控制结构的复杂程度 （ C）算法的复杂度是指算法程序中指令的数量 （ D）算法的复杂度是指算法所处理的数据量 3 下列叙述中正确的 是 ( )。 （ A）算法的时间复杂度与计算机的运行速度有关 （ B）算法的时间复杂度与运行算法时特定的
2、输入有关 （ C）算法的时间复杂度与算法程序中的语句条数成正比 （ D）算法的时间复杂度与算法程序编制者的水平有关 4 下列叙述中正确的是 ( )。 （ A）非线性结构可以为空 （ B）只有一个根结点和一个叶子结点的必定是线性结构 （ C）只有一个根结点的必定是线性结构或二叉树 （ D）没有根结点的一定是非线性结构 5 设数据结构 B=(D， R)，其中 D=a， b， c， d， e， f R=(f， a)， (d， b)， (e， d)， (c， e)， (a， c) 该数据结构为 ( )。 （ A）线性结构 （ B）循环队列 （ C）循环链表 （ D）非线性结构 6 下列叙述中正确的是
3、( )。 （ A）矩阵是非线性结构 （ B）数组是长度固定的线性表 （ C）对线性表只能作插入与删除运算 （ D）线性表中各元素的数据类型可以不同 7 在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数 ( )。 （ A）不同，但元素的存储顺序与逻辑顺序一致 （ B）不同，且其元 素的存储顺序可以与逻辑顺序不一致 （ C）相同，元素的存储顺序与逻辑顺序一致 （ D）相同，但其元素的存储顺序可以与逻辑顺序不一致 8 下列叙述中正确的是 ( )。 （ A）能采用顺序存储的必定是线性结构 （ B）所有的线性结构都可以采用顺序存储结构 （ C）具有两个以上指针的链表必定是非线性结构 （ D
4、）循环队列是队列的链式存储结构 9 下列叙述中正确的是 ( )。 （ A）在栈中，栈顶指针的动态变化决定栈中元素的个数 （ B）在循环队列中，队尾指针的动态变化决定队列的长度 （ C）在循环 链表中，头指针和链尾指针的动态变化决定链表的长度 （ D）在线性链表中，头指针和链尾指针的动态变化决定链表的长度 10 设栈的顺序存储空间为 S(1： m)，初始状态为 top=0。现经过一系列正常的入栈与退栈操作后， top=m+1，则栈中的元素个数为 ( )。 （ A） 0 （ B） m （ C）不可能 （ D） m+1 11 设栈的存储空间为 S(1： m)，初始状态为 top=m+1。经过一系列入
5、栈与退栈操作后， top=m。现又在栈中退出一个元素后，栈顶指针 top值为 ( )。 （ A） 0 （ B） m一 1 （ C） m+1 （ D）产生栈空错误 12 下列处理中与队列有关的是 ( )。 （ A）二叉树的遍历 （ B）操作系统中的作业调度 （ C）执行程序中的过程调用 （ D）执行程序中的循环控制 13 设有栈 S和队列 Q，初始状态均为空。首先依次将 A， B， C， D， E， F入栈，然后从栈中退出三个元素依次入队，再将 X， Y， Z入栈后，将栈中所有元素退出并依次入队，最后将队列中所有元素退出，则退队元素的顺序为 ( )。 （ A） DEFXYZABC （ B） FE
6、DZYXCBA （ C） FEDXYZCBA （ D） DEFZYXABC 14 设循环队列的存储空间为 Q(1： 50)，初始状态为 front=rear=50。现经过一系列入队与退队操作后， front=rear=1，此后又正常地插入了两个元素。最后该队列中的元素个数为 ( )。 （ A） 3 （ B） 1 （ C） 2 （ D） 52 15 设循环队列的存储空间为 Q(1： m)，初始状态为空。现经过一系列正常的人队与退队操作后， front=m， rear=m-1，此后从该循环队列中删除一个元素，则队列中的元素个数为 ( )。 （ A） m一 1 （ B） m一 2 （ C） 0 （
7、D） 1 16 线性表的链式存储结构与顺序存储结构相比，链式存储结构的优点有 ( )。 （ A）节省存储空间 （ B）插入与删除运算效率高 （ C）便于查找 （ D）排序时减少元素的比较次数 17 在线性表的链式存储结构中，其存储空间一般是不连续的，并且 ( )。 （ A）前件结点的存储序号小于后件结点的存储序号 （ B）前件结点的存储序号大于后件结点的存储序号 （ C）前件结点的存储序号可以小于也可以大于后件结点的存储序号 （ D）以上三种说法均不正确 18 下列 叙述中正确的是 ( )。 （ A）结点中具有两个指针域的链表一定是二叉链表 （ B）结点中具有两个指针域的链表可以是线性结构，也
8、可以是非线性结构 （ C）循环链表是循环队列的链式存储结构 （ D）循环链表是非线性结构 19 下列叙述中正确的是 ( )。 （ A）带链栈的栈底指针是随栈的操作而动态变化的 （ B）若带链队列的队头指针与队尾指针相同，则队列为空 （ C）若带链队列的队头指针与队尾指针相同，则队列中至少有一个元素 （ D）不管是顺序栈还是带链的栈，在操作过程中其栈底指针均是固定不变的 20 某带链栈的初始状态为 top=bottom=NULL，经过一系列正常的入栈与退栈操作后， top=bottom=20。该栈中的元素个数为 ( )。 （ A） 0 （ B） 1 （ C） 20 （ D）不确定 21 某带链的
9、队列初始状态为 front=rear=NULL。经过一系列正常的入队与退队操作后， front=rear=10。该队列中的元素个数为 ( )。 （ A） 0 （ B） 1 （ C） 1或 0 （ D）不确定 22 某带链的队列初始状态为 front=rear=NULL。经过一系列正常的入 队与退队操作后， front=10， rear=5。该队列中的元素个数为 ( )。 （ A） 4 （ B） 5 （ C） 6 （ D）不确定 23 下列叙述中错误的是 ( )。 （ A）循环链表中有一个表头结点 （ B）循环链表是循环队列的存储结构 （ C）循环链表的表头指针与循环链表中最后一个结点的指针均指
10、向表头结点 （ D）循环链表实现了空表与非空表运算的统一 24 某棵树中共有 25个结点，且只有度为 3的结点和叶子结点，其中叶子结点有 7个，则该树中度为 3的结点数为 ( )。 （ A） 6 （ B） 7 （ C） 8 （ D）不存在这样的树 25 度为 3的一棵树共有 30个结点，其中度为 3， 1的结点个数分别为 3， 4。则该树中的叶子结点数为 ( )。 （ A） 14 （ B） 15 （ C） 16 （ D）不可能有这样的树 26 深度为 7的二叉树共有 127个结点，则下列说法中错误的是 ( )。 （ A）该二叉树是满二叉树 （ B）该二叉树有一个度为 1的结点 （ C）该二叉树
11、是完全二叉树 （ D）该二叉树有 64个叶子结点 27 深度为 5的完全二叉树的结点数不可能是 ( )。 （ A） 15 （ B） 16 （ C） 17 （ D） 18 28 某完全二叉树共有 256个结点，则该完全二叉树的深度为 ( )。 （ A） 7 （ B） 8 （ C） 9 （ D） 10 29 在具有 2n个结点的完全二叉树中，叶子结点个数为 ( )。 （ A） n （ B） n+1 （ C） n一 1 （ D） n 2 30 下列叙述中正确的是 ( )。 （ A）非完全二叉树可以采用顺序存储结构 （ B）有两个指针域的链表就是二叉链表 （ C）有的二叉树也能用顺序存储结构表示 （
12、D）顺序存储结构一定是线性结构 国家 二级 VB机试（公共基础知识）模拟试卷 1答案与解析 一、选择题 1 【正确答案】 B 【试题解析】 算法是指对解题方案的准确而完整的描述，算法不等于数学上的计算方法，也不等于程序。算法设计需要考虑可行性、确定性、有穷性与足够的情报，不能只考虑计算结果。算法设计有穷性是指操作步骤有限且能在有限时间内完成，如果一个算法执行耗费的时间太长，即使最终得出了正确结果，也是没有意义的，。算法在实现时需要用具体的程序设计语言描述，所以程序可以作为算法的一种描述方法。 【知识模块】 公共基础知识 2 【正 确答案】 A 【试题解析】 算法复杂度是指算法在编写成可执行程序
13、后，运行时所需要的资源，资源包括时间资源和内存资源。算法的复杂度包括时间复杂度与空间复杂度。算法的时间复杂度是指执行算法所需要的计算工作量；算法的空间复杂度是指算法在执行过程中所需要的内存空间。 【知识模块】 公共基础知识 3 【正确答案】 B 【试题解析】 为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。 为此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。算法所执行的基本运算次数还与问题的规模有关；对应一个固定的规模，算法所执行的基本运算次数还可能与特定的
14、输入有关。 【知识模块】 公共基础知识 4 【正确答案】 A 【试题解析】 如果一个非空的数据结构满足下列两个条件： 有且只有一个根结点； 每一个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构。如果一个数据结构不是线性结构，则称之为非线性结构。线性结构和非线性结构都可以是空的数据结构。树只有一个根结点，但不论有几个叶子结点，树都是非线性结构。 【知识模块】 公共基础知识 5 【正确答案】 A 【试题解析】 数据的逻辑结构有两个要素：一是数据元素的集合，通常记为 D；二是 D上的关系，它反映了 D中各数据元素之间的前后件关系，通常记为 R。即一个数据结构可以表示成 B=(D， R
15、)。其中 B表示数据结构。为了反映 D中各数据元素之间的前后件关系，一般用二元组来表示。例如，假设 a与 h是 D中的两个数据，则二元组 (a， b)表示 a是 b的前件， b是 a的后件。本题中 R中的根结点为 f，元素顺序为 facedb ，满足线性结构的条件。 【知识模块】 公共基础知识 6 【正确答案】 B 【试题解析】 矩阵也是线性表，只不过是比较复杂的线性表。线性表中各元素的数据类型必须相同。在线性表中，不仅可以做插入与删除运算，还可以进行查找或对线性表进行排序等操 作。 【知识模块】 公共基础知识 7 【正确答案】 C 【试题解析】 在线性表的顺序存储结构中，其存储空间连续，各个
16、元素所占的字节数相同，在存储空间中是按逻辑顺序依次存放的。 【知识模块】 公共基础知识 8 【正确答案】 B 【试题解析】 所有的线性结构都可以用数组保存，即都可以采用顺序存储结构。而反过来不可以，完全二叉树也能用数组保存 (按层次依次存放到数据元素中 )，但完全二叉树不属于非线性结构。双向链表具有两个以上的指针，但属于线性结构。循环队列是队列的顺序存储结构。 【知识模块】 公共基础知识 9 【正确答案】 A 【试题解析】 在栈中，通常用指针 top来指示栈顶的位置，用指针 bottom指向栈底。栈顶指针 top动态反应了栈中元素的变化情况。在循环队列中，队头指针和队尾指针的动态变化决定队列的
17、长度。链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致，故头指针和尾指针或栈顶指针无法决定链表长度。 【知识模块】 公共基础知识 10 【正确答案】 C 【试题解析】 栈为空时，栈顶指针 top=0，经过人 栈和退栈运算，指针始终指向栈顶元素。初始状态为 top=0，当栈满。 top=m，无法继续入栈， top值不可能为m+1。 【知识模块】 公共基础知识 11 【正确答案】 C 【试题解析】 栈的顺序存储空间为 s(1： m)，初始状态 top=m+1，所以这个栈是m在栈底 (也可理解为开口向下的栈 )。经过一系列入栈与退栈操作后 top=m
18、，则栈中有 1个元素，若现在又退出一个元素，那么栈顶指针下移一位，回到 m+1的位置。 【知识模块】 公共基础知识 12 【正确答案】 B 【试题解析】 队列是 指允许在一端进行插入，而在另一端进行删除的线性表。由于最先进入队列的元素将最先出队，所以队列具有 “先进先出 ”的特性，体现了 “先来先服务 ”的原则。操作系统中的作业调度是指根据一定信息，按照一定的算法，从外存的后备队列中选取某些作业调入内存分配资源并将新创建的进程插入就绪队列的过程。 【知识模块】 公共基础知识 13 【正确答案】 B 【试题解析】 栈是一种特殊的线性表，它所有的插入与删除都限定在表的同一端进行。队列是指允许在一端
19、进行插入，而在另一端进行删除的线性表。将 A， B，C， D， E， F入栈 后，栈中元素为 ABCDEF，退出三个元素入队，队列元素为FED，将 X， Y， Z入栈后栈中元素为 ABCXYZ，退栈全部入队后，队列元素为FEDZYXCBA。 【知识模块】 公共基础知识 14 【正确答案】 C 【试题解析】 由初始状态为 front=rear=50可知此时循环队列为空。经过一系列正常的入队和退队操作，由 front=rear=l可知队列空或者队列满，此后又可以正常地插入了两个元素，说明插入前队列为空，则插入后队列元素个数为 2。 【知识模块】 公共基础知识 15 【正确答案】 B 【试题解析】
20、在循环队列中，如果 rearfront0，则队列中的元素个数为rearfront个；如果 rearfront 0，则队列中的元素个数为 rearfront+m。该题中 m一 1m，即 rearfront 0，则该循环队列中的元素个数为 (m一 1)一m+m=m一 1。此后从该循环队列中删除一个元素，则队列中的元素个数为 m11=m一 2。 【知识模块】 公共基础知识 16 【正确答案】 B 【试题解析】 线性表的顺序存储结构称为顺序表，线性表的链式存储结构称为链表，两者的优 缺点如下表所示。【知识模块】 公共基础知识 17 【正确答案】 C 【试题解析】 在线性表的链式存储结构中，各数据结点的
21、存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致，因此前件结点的存储序号与后件结点的存储序号之间不存在大小关系。 【知识模块】 公共基础知识 18 【正确答案】 B 【试题解析】 结点中具有两个指针域的链表既可以是双向链表也可以是二叉链表，双向链表是线性结构，二叉链表属于非线性结构。循环链表是线性链表的一种形式，属于线性结构，采用链 式存储结构，而循环队列是队列的一种顺序存储结构。 【知识模块】 公共基础知识 19 【正确答案】 A 【试题解析】 由于带链栈利用前是计算机存储空间中的所有空闲存储结点，因此随栈的操作栈顶栈底指针动态变化。带链的队列中若只有一个元素，则头指针
22、与尾指针相同。 【知识模块】 公共基础知识 20 【正确答案】 B 【试题解析】 带链的栈就是用一个单链表来表示的栈，栈中的每一个元素对应链表中的一个结点。栈为空时，头指针和尾指针都为 NULL；栈中只有一个元素时，头指针和尾指针都指向这个 元素。 【知识模块】 公共基础知识 21 【正确答案】 B 【试题解析】 带链队列空时，头指针和尾指针都为 NULL；队列中只有一个元素时，头指针和尾指针都指向这个元素。 【知识模块】 公共基础知识 22 【正确答案】 D 【试题解析】 带链的队列使用了链表来表示队列，而链表中的元素存储在不连续的地址中，因此当 front=10， rear=5时，不能确定
23、队列中元素的个数。 【知识模块】 公共基础知识 23 【正确答案】 B 【试题解析】 循环链表是指在单链表的第一 个结点前增加一个表头结点，队头指针指向表头结点，最后一个结点的指针域的值由 NuLL改为指向表头结点。循环链表是线性表的一种链式存储结构，循环队列是队列的一种顺序存储结构。 【知识模块】 公共基础知识 24 【正确答案】 D 【试题解析】 根据题意，树中只有度为 3的结点和叶子结点 (7个 )，则度为 3的结点有 257=18个；又根据树中的结点数 =树中所有结点的度之和 +1，设度为 3的结点数为 n，则 3n+1=25，得 n=8。两种方式得到的度为 3的结点数不同，故不存在这
24、样的树。 【知识模块】 公共 基础知识 25 【正确答案】 B 【试题解析】 设叶子结点数为 n，则度为 2的结点数为 3034一 n=23一 n，根据树中的结点数 =树中所有结点的度之和 +1，得 33+2(23一n)+l4+0n+l=30，则 n=15。 【知识模块】 公共基础知识 26 【正确答案】 B 【试题解析】 满二叉树满足深度为 m的二叉树最多有 2m一 1个结点，本题中二叉树深度为 7且有 127个结点，满足 27一 1=127，达到最大值，故此二叉树为满二叉树，也是完全二叉树。满二叉树第 k层上有 2k-1结点，则该二叉 树的叶子结点数为 27-1=64个。满二叉树不存在度为
25、 1的结点。 【知识模块】 公共基础知识 27 【正确答案】 A 【试题解析】 设完全二叉树的结点数为 n，根据深度为 k的二叉树至多有 2k一 1个结点，再根据完全二叉树的定义可知， 2k-1一 1k一 1。本题中完全二叉树的深度为 5，则 25-1一 15一 1， 15 n31。因此，结点数不能为 15。 【知识模块】 公共基础知识 28 【正确答案】 C 【试题解析】 根据完全二叉树的性质：具有 n个结点的完全二叉树的深度为log2n+1。本题中完全 二叉树共有 256个结点，则深度为 log2256+1=8+1=9。 【知识模块】 公共基础知识 29 【正确答案】 A 【试题解析】 由
26、二叉树的定义可知，树中必定存在度为 0的结点和度为 2的结点，设度为 0结点有 a个，根据度为 0的结点 (即叶子结点 )总比度为 2的结点多一个，得度为 2的结点有 a一 1个。再根据完全二叉树的定义，度为 1的结点有 0个或 1个，假设度 1结点为 0个， a+0+a一 1=2n，得 2a=2n一 1，由于结点个数必须为整数，假设不成立；当度为 1的结点为 1个时， a+1+a一 1=2n，得 a=n，即叶子结点个数为 n。 【知识模块】 公共基础知识 30 【正确答案】 C 【试题解析】 在计算机中，二叉树为非线性结构，通常采用链式存储结构，但对于满二叉树和完全二叉树来说，可以按层进行顺序存储。因此 A项错误， C项正确。虽然满二叉树和完全二叉树可以采用顺序存储结构，但仍是一种非线性结构，因此 D项错误。双向链表也有两个指针域，因此 B项错误。 【知识模块】 公共基础知识
