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