1、国家二级 MS+Office高级应用机试（数据结构与算法）模拟试卷 20及答案解析(总分：56.00，做题时间：90 分钟)一、选择题(总题数：28，分数：56.00)1.下列结构属于线性结构链式存储的是( )。（分数：2.00）A.双向链表B.循环队列C.二叉链表D.二维数组2.某棵树的度是 3，其中度为 2、1、0 的节点个数分别是 3、4、15。则该树的总节点数为( )。（分数：2.00）A.25B.28C.30D.不可能有这样的树3.在长度为 100的顺序有序表中用二分法查找，最多需要比较( )次。（分数：2.00）A.6B.7C.8D.94.下列叙述错误的是( )。（分数：2.00）
2、A.循环链表中有一个表头节点B.循环链表的存储空间是连续的C.循环链表实现了空表与非空表运算的统一D.循环链表的表头指针与循环链表中最后一个节点的指针均指向表头节点5.下列结构中属于非线性结构的是( )。（分数：2.00）A.二维数组B.栈C.循环队列D.双向链表6.下列叙述正确的是( )。（分数：2.00）A.程序的执行效率和数据存储结构密切相关B.程序的执行效率只取决于程序的控制结构C.程序的执行效率只取决于处理的数据量D.以上说法都不对7.在希尔排序中，每经过一次数据交换后( )。（分数：2.00）A.能消除多个逆序B.只能消除一个逆序C.不会产生新逆序D.消除的逆序个数一定比新产生的逆
3、序个数多8.下列叙述中错误的是( )。（分数：2.00）A.向量是线性结构B.非空线性结构中只有一个节点没有前件C.非空线性结构中只有一个节点没有后件D.只有一个根节点和一个叶子节点的结构必定是线性结构9.下列叙述中正确的是( )。（分数：2.00）A.循环队列是队列的链式存储结构B.能采用顺序存储的必定是线性结构C.所有的线性结构都可以采用顺序存储结构D.具有两个指针的链表必定是非线性结构10.设循环队列的存储空间是 Q(1：20)，初始状态为 front=rear=-20，经过一系列正常的操作后，front-1=rear，为了在该队列中寻找值最大的元素，在最坏情况下需要的比较次数是( )。
4、（分数：2.00）A.0B.1C.18D.1911.设顺序表的长度是 40，对该表进行冒泡排序。在最坏情况下需要的比较次数是( )。（分数：2.00）A.780B.820C.40D.4112.设表的长度是 n，在下列算法中，最坏情况下时间复杂度最高的是( )。（分数：2.00）A.堆排序B.希尔排序C.有序链表查找D.循环链表中寻找最大项13.已知数据表 A中每个元素距其最终位置不远，为节省时间，应采用的算法是( )。（分数：2.00）A.堆排序B.直接插入排序C.快速排序D.直接选择排序14.在单链表中，增加头节点的目的是( )。（分数：2.00）A.方便运算的实现B.使单链表至少有一个节点
5、C.标识表节点中首节点的位置D.说明单链表是线性表的链式存储实现15.栈底至栈顶依次存放元素 A、B、C、D，在第五个元素 E入栈前，栈中元素可以出栈则出栈序列可能是( )。（分数：2.00）A.ABCEDB.DBCEAC.CDABED.DCBEA16.下列数据结构中，与所使用的计算机无关的数据是( )。（分数：2.00）A.存储结构B.物理结构C.逻辑结构D.物理和存储结构17.在下列排序方法中，要求内存量最大的是( )。（分数：2.00）A.插入排序B.选择排序C.快速排序D.归并排序18.在深度为 5的满二叉树中，叶子节点的个数为( )。（分数：2.00）A.32B.31C.16D.15
6、19.算法时间复杂度通常用什么符号表示?( )。（分数：2.00）A.TB.FC.QD.N20.下列关于线性表的叙述中，错误的是( )。（分数：2.00）A.线性表采用顺序存储，必须占用一片连续的存储单元B.线性表采用顺序存储，便于进行插入和删除操作C.线性表采用链接存储，不必占用一片连续的存储单元D.线性表采用链接存储，便于插入和删除操作21.某二叉树共有 12个节点，其中叶子节点只有 1个，则该二叉树的深度是( )。（分数：2.00）A.3B.6C.8D.1222.对下列二叉树进行前序遍历的结果是( )。 （分数：2.00）A.DYBEAFCZXB.YDEBFZXCAC.ABDYECFXZ
7、D.ABCDEFXYZ23.设一棵完全二叉树共有 699个节点，则在该二叉树中的叶子节点数为( )。（分数：2.00）A.349B.350C.255D.35124.从表中任何一个节点位置出发就可以不重复地访问到表中其他所有节点的链表是( )。（分数：2.00）A.循环链表B.双向链表C.单向链表D.二叉链表25.下列叙述中正确的是( )。（分数：2.00）A.算法复杂度是指算法控制结构的复杂程度B.算法复杂度是指设计算法的难度C.算法的时间复杂度是指设计算法的工作量D.算法的复杂度包括时间复杂度和空间复杂度26.下列叙述中错误的是( )。（分数：2.00）A.在双向链表中，可以从任何一个节点开
8、始直接遍历到所有节点B.在循环链表中，可以从任何一个节点开始直接遍历到所有节点C.在线性单链表中，可以从任何一个节点开始直接遍历到所有节点D.在二叉链表中，可以从根节点遍历到所有节点27.带链的栈与顺序存储的栈相比，其优点是( )。（分数：2.00）A.入栈与退栈操作方便B.可以省略栈底指针C.入栈操作时不会受栈存储空间的限制而发生溢出D.所占存储空间更小28.设循环队列的存储空间为 Q(1：100)，初始状态为空。现经过一系列正常操作后，front=49，则循环队列中的元素个数为( )。（分数：2.00）A.不确定B.49C.51D.50国家二级 MS+Office高级应用机试（数据结构与算
9、法）模拟试卷 20答案解析(总分：56.00，做题时间：90 分钟)一、选择题(总题数：28，分数：56.00)1.下列结构属于线性结构链式存储的是( )。（分数：2.00）A.双向链表 B.循环队列C.二叉链表D.二维数组解析：解析：双向链表是链式存储，一个节点有前后 2个指针域，分别指向它的前后节点。循环队列是顺序存储，只是逻辑上规定当队列满时队尾指针指向队头。二叉链表是二叉树的链式存储结构，不是线性结构。二维数组也是非线性结构。2.某棵树的度是 3，其中度为 2、1、0 的节点个数分别是 3、4、15。则该树的总节点数为( )。（分数：2.00）A.25B.28C.30D.不可能有这样的
10、树 解析：解析：树中节点的最大度数称为树的度数。树有一个性质：树的节点数比树的边数多 1，树的边数是指树的 2个节点之间连接的线段，也就是每个节点的度。设度为 3的节点个数为 x，则节点总数为3+4+15+x=22+x，边数为 23+14+015+3x=3x+10，则 22+x=3x+10+1，x=55，x 不是整数，因此不存在这样的树。3.在长度为 100的顺序有序表中用二分法查找，最多需要比较( )次。（分数：2.00）A.6B.7 C.8D.9解析：解析：用二分法查找说明该顺序表已经有序，那么比较次数是 log 2 100，也就是 7次。4.下列叙述错误的是( )。（分数：2.00）A.
11、循环链表中有一个表头节点B.循环链表的存储空间是连续的 C.循环链表实现了空表与非空表运算的统一D.循环链表的表头指针与循环链表中最后一个节点的指针均指向表头节点解析：解析：循环链表是链表的一种特殊形式，它的最后一个节点指向头节点，这样整个链表可以循环利用。循环链表的存储空间不一定是连续的。5.下列结构中属于非线性结构的是( )。（分数：2.00）A.二维数组 B.栈C.循环队列D.双向链表解析：解析：线性结构的特点：有且只有一个开始节点；每个节点最多有一个直接前驱和一个直接后继。常见的线性结构有：线性表、栈、队列、双队列、数组、串；常见的非线性结构有二维数组、多维数组，广义表、树(二叉树等)
12、、图。6.下列叙述正确的是( )。（分数：2.00）A.程序的执行效率和数据存储结构密切相关 B.程序的执行效率只取决于程序的控制结构C.程序的执行效率只取决于处理的数据量D.以上说法都不对解析：解析：程序执行的实际计算工作量不仅与程序的控制结构有一定的关系，与处理的数据量有关，而且还与数据的存储结构密切相关。7.在希尔排序中，每经过一次数据交换后( )。（分数：2.00）A.能消除多个逆序 B.只能消除一个逆序C.不会产生新逆序D.消除的逆序个数一定比新产生的逆序个数多解析：解析：希尔排序是根据增量分成多个组，每个组内使用插入排序。因此在各个组之间可能产生新的逆序，每次交换能消除组内的多个逆
13、序。8.下列叙述中错误的是( )。（分数：2.00）A.向量是线性结构B.非空线性结构中只有一个节点没有前件C.非空线性结构中只有一个节点没有后件D.只有一个根节点和一个叶子节点的结构必定是线性结构 解析：解析：只有一个根节点和一个叶子节点的可以是树，而树是非线性结构。9.下列叙述中正确的是( )。（分数：2.00）A.循环队列是队列的链式存储结构B.能采用顺序存储的必定是线性结构C.所有的线性结构都可以采用顺序存储结构 D.具有两个指针的链表必定是非线性结构解析：解析：循环队列是顺序存储结构；能采用顺序存储的也可以是非线性结构如完全二叉树；具有两个指针的链表可以是线性结构，如双向链表。10.
14、设循环队列的存储空间是 Q(1：20)，初始状态为 front=rear=-20，经过一系列正常的操作后，front-1=rear，为了在该队列中寻找值最大的元素，在最坏情况下需要的比较次数是( )。（分数：2.00）A.0B.1C.18 D.19解析：解析：front 表示队头指针，rear 表示队尾指针。front-1=rear，说明队列大小为 19，19 个元素需要比较的次数是 19-1=18。11.设顺序表的长度是 40，对该表进行冒泡排序。在最坏情况下需要的比较次数是( )。（分数：2.00）A.780 B.820C.40D.41解析：解析：冒泡排序在最坏情况下比较次数是 n(n-1
15、)2，即 40392=780。12.设表的长度是 n，在下列算法中，最坏情况下时间复杂度最高的是( )。（分数：2.00）A.堆排序B.希尔排序 C.有序链表查找D.循环链表中寻找最大项解析：解析：希尔排序是插入排序的一个变种，也称为缩小增量排序。在最坏情况下，直接插入是 O(n 2 )，堆排序是 O(nlog 2 n)，循环查找是 O(n)。13.已知数据表 A中每个元素距其最终位置不远，为节省时间，应采用的算法是( )。（分数：2.00）A.堆排序B.直接插入排序 C.快速排序D.直接选择排序解析：解析：当每个元素离最终位置不远，采用直接插入排序效率最高，因为移动元素次数比较少。14.在单
16、链表中，增加头节点的目的是( )。（分数：2.00）A.方便运算的实现 B.使单链表至少有一个节点C.标识表节点中首节点的位置D.说明单链表是线性表的链式存储实现解析：解析：加入头节点：使得链表首节点的插入删除操作和其他节点一样(因都有前驱节点)；使得非空链表和空链表的操作相同(因都有元素，空链表中包含头节点)。15.栈底至栈顶依次存放元素 A、B、C、D，在第五个元素 E入栈前，栈中元素可以出栈则出栈序列可能是( )。（分数：2.00）A.ABCEDB.DBCEAC.CDABED.DCBEA 解析：解析：由于 ABCD已经在栈里，不管怎么出栈，D 一定在 c前，C 一定在 B前，B 一定在
17、A前。采用排除法答案是 D项。16.下列数据结构中，与所使用的计算机无关的数据是( )。（分数：2.00）A.存储结构B.物理结构C.逻辑结构 D.物理和存储结构解析：解析：与计算机系统无关的是逻辑结构；与计算机系统有关的是物理结构，也称存储结构。17.在下列排序方法中，要求内存量最大的是( )。（分数：2.00）A.插入排序B.选择排序C.快速排序D.归并排序 解析：解析：快速排序的基本思想是，通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，再分别对这两部分记录继续进行排序，以达到整个序列有序；插入排序的基本操作是指将无序序列中的各元素依次插入已
18、经有序的线性表中，从而得到一个新的序列；选择排序的基本思想是：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面(这是它应有的位置)，然后对剩下的子表采用同样的方法，直到表空为止；归并排序是将两个或两个以上的有序表组合成一个新的有序表。归并排序需要额外使用一个等大的空间用于存放有序表，而其他的都不需要额外空间。18.在深度为 5的满二叉树中，叶子节点的个数为( )。（分数：2.00）A.32B.31C.16 D.15解析：解析：满二叉树的叶子节点数是 2 k-1 ，即 2 4 =16。19.算法时间复杂度通常用什么符号表示?( )。（分数：2.00）A.TB.FC.Q D.N解析：解析：
19、算法的时间复杂度用大写的英文字母 O表示。20.下列关于线性表的叙述中，错误的是( )。（分数：2.00）A.线性表采用顺序存储，必须占用一片连续的存储单元B.线性表采用顺序存储，便于进行插入和删除操作 C.线性表采用链接存储，不必占用一片连续的存储单元D.线性表采用链接存储，便于插入和删除操作解析：解析：线性表可以采用顺序存储，也可以采用链式存储。顺序存储的内存必须连续，不方便插入或删除元素，因为需要移动后面的元素。链式存储的内存不连续，方便插入和删除。21.某二叉树共有 12个节点，其中叶子节点只有 1个，则该二叉树的深度是( )。（分数：2.00）A.3B.6C.8D.12 解析：解析：
20、二叉树有一个性质：叶子节点比度为 2的节点多 1，叶子节点有 1个，那么度为 2的节点是0个，这样就有 11个度为 1的节点，整棵树的深度就是 12。22.对下列二叉树进行前序遍历的结果是( )。 （分数：2.00）A.DYBEAFCZXB.YDEBFZXCAC.ABDYECFXZ D.ABCDEFXYZ解析：解析：前序遍历先访问根节点 A，然后前序遍历左子树，左子树的遍历顺序是 BDYE，排除 ABD三项，答案是 C项。23.设一棵完全二叉树共有 699个节点，则在该二叉树中的叶子节点数为( )。（分数：2.00）A.349B.350 C.255D.351解析：解析：若设二叉树的高度为 h，
21、除第 h层外，其他各层(1-h-1)的节点数都达到最大个数，第 h层所有的节点都连续集中在最左边，这就是完全二叉树。完全二叉树是由满二叉树而引出来的。对于深度为K、有 N个节点的二叉树，当且仅当其每一个节点都与深度为 K的满二叉树中编号从 1至 n的节点一一对应时，称之为完全二叉树。本题目中，共 699个节点，因为是完全二叉树，2 10 16992 9 -1，所以高度为 10，可以确定 1到 9层全满，节点总数为 2 9 -1=511，剩下的 188个肯定为叶子节点。第 10层上的188个节点挂在第 9层的 1882=94 个节点上，则第 9层剩下的 2 9 -1-94=162个，也为叶子节点
22、，最后总共 188+162=350个叶子节点。本题也可以采用排除法。完全二叉树除了最后一层外就是一个满二叉树，满二叉树的总节点数是 2 k -1，是个奇数，而题目中的总节点数 699也是奇数，那么可知叶子节点数是个偶数，答案中是偶数的只有一个 B项。24.从表中任何一个节点位置出发就可以不重复地访问到表中其他所有节点的链表是( )。（分数：2.00）A.循环链表 B.双向链表C.单向链表D.二叉链表解析：解析：循环链表是一种特殊的链式存储结构，它的特点是表中最后一个节点的指针域指向头节点。整个链表形成一个环，循环一圈就能访问到了表中其他所有节点且不重复。双向链表只能从头尾节点开始访问才能做到不
23、重复，单向链表只能从头节点访问才能做到，二叉链表永远都会重复访问。25.下列叙述中正确的是( )。（分数：2.00）A.算法复杂度是指算法控制结构的复杂程度B.算法复杂度是指设计算法的难度C.算法的时间复杂度是指设计算法的工作量D.算法的复杂度包括时间复杂度和空间复杂度 解析：解析：算法复杂度包括时间复杂度和空间复杂度。时间复杂度是指执行算法所需要的计算工作量；空间复杂度是执行算法所需要的内存空间。26.下列叙述中错误的是( )。（分数：2.00）A.在双向链表中，可以从任何一个节点开始直接遍历到所有节点B.在循环链表中，可以从任何一个节点开始直接遍历到所有节点C.在线性单链表中，可以从任何一
24、个节点开始直接遍历到所有节点 D.在二叉链表中，可以从根节点遍历到所有节点解析：解析：双向链表中，任何一个节点可以向前遍历到头节点，也可以向后遍历到尾节点；循环链表中，由于尾节点和头节点是连起来的，因此从任何一个节点可以遍历到所有节点；二叉链表是二叉树的链式存储结构，根据二叉树的前序遍历可以从根节点遍历到所有节点；线性单链表中，一个节点只能知道它的后继节点不知道它的前驱节点，因此不能遍历到所有节点。27.带链的栈与顺序存储的栈相比，其优点是( )。（分数：2.00）A.入栈与退栈操作方便B.可以省略栈底指针C.入栈操作时不会受栈存储空间的限制而发生溢出 D.所占存储空间更小解析：解析：顺序存储的栈，其大小在开始的时候就已经固定，因此会发生溢出，而带链的栈可以动态增加容量大小，不存在溢出。28.设循环队列的存储空间为 Q(1：100)，初始状态为空。现经过一系列正常操作后，front=49，则循环队列中的元素个数为( )。（分数：2.00）A.不确定 B.49C.51D.50解析：解析：队列有队头指针 front和队尾指针 rear，只知道：front 指针的位置是不能确定队列的元素个数的。
