[计算机类试卷]国家二级MS Office高级应用机试(数据结构与算法)模拟试卷9及答案与解析.doc
《[计算机类试卷]国家二级MS Office高级应用机试(数据结构与算法)模拟试卷9及答案与解析.doc》由会员分享,可在线阅读,更多相关《[计算机类试卷]国家二级MS Office高级应用机试(数据结构与算法)模拟试卷9及答案与解析.doc(15页珍藏版)》请在麦多课文档分享上搜索。
1、国家二级 MS Office高级应用机试(数据结构与算法)模拟试卷 9及答案与解析 一、选择题 1 对长度为 n的线性表排序,存最坏情况下,比较次数不是 n(n一 1) 2的排序方法是 ( A)快速排序 ( B)冒泡排序 ( C)直接插入排序 ( D)堆排序 2 对于循环队列,下列叙述中正确的是 ( A)队头指针是固定不变的 ( B)队头指针一定大于队尾指针 ( C)队头指针一定小于队尾指针 ( D)队头指针可以大于队尾指针,也可以小于队尾指针 3 下列叙述中正确的是 ( A)栈是 “先进先出 ”的线性表 ( B)队列是 “先进后出 ”的线性表 ( C)循环队列是非线性结构 ( D)有序线性表
2、既可以采用顺序存储结构,也可以采用链式存储结构 4 下列叙述中正确的是 ( A)在栈中,栈中元素随栈底指针与栈顶指针的变化而动态变化 ( B)在栈中,栈顶指针不变,栈中元素随栈底指针的变化而动态变化 ( C)在栈中,栈底指针不变,栈中元素随栈顶指针的变化而动态变化 ( D)上述三种说法都不对 5 下列叙述中正确的是 ( A)循环队列是队列的一种链式存储结构 ( B)循环队列是队列的一种顺序存储结构 ( C)循环队列是 非线性结构 ( D)循环队列是一种逻辑结构 6 设二叉树共有 150个结点,其中度为 1的结点有 10个,则该二叉树中的叶子结点数为 ( A) 71 ( B) 70 ( C) 6
3、9 ( D)不可能有这样的二叉树 7 一棵二叉树中共有 80个叶子结点与 70个度为 1的结点,则该二叉树中的总结点数为 ( A) 219 ( B) 229 ( C) 230 ( D) 231 8 下列叙述中错误的是 ( A)在双向链表中,可以从任何一个结点开始直接遍历到所有结点 ( B)在循环链表中,可以从任何一个结点开始直接遍历到所有结点 ( C)在线性单链表中,可以从任何一个结点开始直接遍历到所有结点 ( D)在二叉链表中,可以从根结点开始遍历到所有结点 9 设某二叉树的后序序列为 CBA,中序序列为 ABC,则该二叉树的前序序列为 ( A) BCA ( B) CBA ( C) ABC
4、( D) CAB 10 算法空间复杂度的度量方法是 ( A)算法程序的长度 ( B)算法所处理的数据量 ( C)执行算法所需要的工作单元 ( D)执行算法所需要的存储空间 11 下列叙述中正确的是 ( A)存储空间连续的数据结构一定是线性结构 ( B)存储空间 不连续的数据结构一定是非线性结构 ( C)没有根结点的非空数据结构一定是线性结构 ( D)具有两个根结点的数据结构一定是非线性结构 12 下列叙述中正确的是 ( A)链表结点中具有两个指针域的数据结构可以是线性结构,也可以是非线性结构 ( B)线性表的链式存储结构中,每个结点必须有指向前件和指向后件的两个指针 ( C)线性表的链式存储结
5、构中,每个结点只能有一个指向后件的指针 ( D)线性表的链式存储结构中,叶子结点的指针只能是空 13 下列叙述中正确的是 ( A)循环队列是顺序存储结构 ( B)循环 队列是链式存储结构 ( C)循环队列是非线性结构 ( D)循环队列的插入运算不会发生溢出现象 14 设有二叉树如下图所示,则后序序列为 ( A) ABDEGCFH ( B) DBGEAFHC ( C) DGEBHFCA ( D) ABCDEFGH 15 设栈的存储空间为 S(1: 50),初始状态为 top=51。现经过一系列正常的入栈与退栈操作后, top=50,则栈中的元素个数为 ( A) 1 ( B) 0 ( C) 50
6、( D) 49 16 在具有 2n个结点的完全二叉树中,叶子结点个数为 ( A) n ( B) n+1 ( C) n-1 ( D) n 2 17 在长度为 n的顺序表中查找一个元素,假设需要查找的元素有一半的机会在表中,并且如果元素在表中,则出现在表中每个位置上的可能性是相同的。则在平均情况下需要比较的次数大约为 ( A) (3 n), 4 ( B) n ( C) n 2 ( D) n 4 18 循环队列的存储空间为 Q(1: 100),初始状态为 front=rear=100。经过一系列正常的入队与退队操作后, front=rear=99,则循环队列中的元素个数为 ( A) 0或 100 (
7、 B) 1 ( C) 2 ( D) 99 19 某二叉树的前序遍历序列与中序遍历序列相同,均为 ABCDEF,则按层次输出(同一层从左到右 )的序列为 ( A) ABCDEF ( B) BCDEFA ( C) FEDCBA ( D) DEFABC 20 下列各排序法中,最坏情况下时间复杂度最小的是 ( A)堆排序 ( B)快速排序 ( C)希尔排序 ( D)冒泡排序 21 下列叙述中正确的是 ( A)解决一个问题可以有不同的算法,且它们的时间复杂度可以是不同的 ( B)解决一个问题可以有不同的算法,但它们的时间复杂度必定是相同的 ( C)解 决一个问题的算法是唯一的 ( D)算法的时间复杂度与
8、计算机系统有关 22 设一棵树的度为 3,共有 27个结点,其中度为 3, 2, 0的结点数分别为 4, 1,10。该树中度为 1的结点数为 ( A) 11 ( B) 12 ( C) 13 ( D)不可能有这样的树 23 在带链队列中,经过一系列正常的操作后,如果 front=rear,则队列中的元素个数为 ( A) 0或 1 ( B) 0 ( C) 1 ( D)队列满 24 设某棵树的度为 3,其中度为 3、 2、 1的结点个数分别为 3、 0、 4。则该树中的叶子结点数为 ( A) 7 ( B) 8 ( C) 6 ( D)不可能有这样的树 25 下列结构中属于非线性结构的是 ( A)二叉链
9、表 ( B)二维数组 ( C)循环队列 ( D)双向链表 26 设某棵树的度为 3,其中度为 2、 1、 0的结点个数分别为 3、 4、 15。则该树中总结点数为 ( A) 22 ( B) 30 ( C) 35 ( D)不可能有这样的树 27 设循环队列的存储空间为 Q(1: 50),初始状态为 front=rear=50。经过一系列正常的操作后, front-1=rear。为了在该队列中寻找值最大的元素,在最坏情况下需要的 比较次数为 ( A) 0 ( B) 1 ( C) 48 ( D) 49 国家二级 MS Office高级应用机试(数据结构与算法)模拟试卷 9答案与解析 一、选择题 1
10、【正确答案】 D 【试题解析】 各种排序方法中最坏情况下需要比较的次数分别为:冒泡排序 n(n-1) 2、快速排序 n(n-1) 2、简单插入排序 n(n-1) 2、希尔排序 O(n1 5)、简单选择排序 n(n-1) 2、堆排序 O(nlog2n)。 【知识模块】 数据结构与算法 2 【正确答案】 D 【试题解析】 所谓循环队列,就是将 队列存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状空间,供队列循环使用。在循环队列中,用队尾指针 rear指向队列中的队尾元素,用队头指针 front指向队头元素的前一个位置。循环队列的主要操作是:入队运算和退队运算。每进行一次入队运算,队尾指针就进
11、一。每进行一次退队运算,队头指针就进一。当 rear或 front等于队列的长度加 1时,就把 rear或 front值置为 1。所以在循环队列中,队头指针可以大于队尾指针,也可以小于队尾指针。 【知识模块】 数据结构与算法 3 【正确答案】 D 【试题 解析】 本题主要考查了栈、队列、循环队列的概念,栈是先进后出的线性表,队列是先进先出的线性表。根据数据结构中各数据元素之间的前后件关系的复杂程度,一般将数据结构分为两大类型:线性结构与非线性结构。有序线性表既可以采用顺序存储结构,又可以采用链式存储结构。 【知识模块】 数据结构与算法 4 【正确答案】 C 【试题解析】 在栈中,允许插入与删除
12、的一端称为栈顶,而不允许插入与删除的另一端称为栈底。栈跟队列不同,元素只能在栈顶压入或弹出,栈底指针不变,栈中元素随栈顶指针的变化而动态变化,遵循后进先 出的规则。 【知识模块】 数据结构与算法 5 【正确答案】 B 【试题解析】 本题主要考查循环队列的概念,循环队列作为队列的一种也应该是线性结构。队列是一种逻辑结构,而循环队列是一种顺序存储结构的队列。 【知识模块】 数据结构与算法 6 【正确答案】 D 【试题解析】 根据二叉树的性质 3,在任意一颗二叉树中,度为 0的结点 (即叶子结点 )总是比度为 2的结点多一个。即有 n0=n2+1。对于这个题来说,总结点数150=n0+n1+n2=n
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
下载文档到电脑,查找使用更方便
2000 积分 0人已下载
下载 | 加入VIP,交流精品资源 |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 试卷 国家 二级 MSOFFICE 高级 应用 数据结构 算法 模拟 答案 解析 DOC
